Трипростые числа

Сложность алгоритма предложенного выше N * 10 * 10 * 10 при максимальном N = 10000 получим 10,000,000 такое число операций в 1секунду ну ни как не влезет...

Сложность алгоритма предложенного выше N * 10 * 10 * 10 при максимальном N = 10000 получим 10,000,000 такое число операций в 1секунду ну ни как не влезет...

прекрасно влезет

[mansur]

http://pastebin.com/h0bTQSMu
вот мой код на с++ он немного быстрее чем 10 * 10 * 10 * N, в нем я перебираю не все тройки цифр трехзначного числа, а все трехзначные простые числа всего их 143 поэтому сложность 143 * N даже так я получаю ТЛ, или может я ошибаюсь?

внутренний цикл пооптимизируй

(j % 100) / 10, j % 10, j / 100 - деление дорогая операция, меняем на таблицы.
(x + y) % mod - меняем на if проверяющий переполнение
long long нхаер, хватит просто unsigned или int
и vector<int> я бы на всякий случай все таки заменил статическимм массивами

[mansur]

http://pastebin.com/Ab6aV4GE
вот код со всеми предложенными оптимизациями дает ТЛ на том же самом тесте, откуда такая информация, что 10,000,000 операций влезет в 1 секунду???

[mansur]

Вообщем ошибку нашел, никаких оптимизации то и не надо было, это был не ТЛ и Рантайм увеличил размер массива с 10000 до 10001 и АС, долго ж я ее искал... Спасибо всем кто помогал разбираться))

ты свю программу хоть раз сам запускал?

$ g++ -o p p.cc
p.cc:8: error: ‘stdin’ was not declared in this scope
p.cc:8: error: ‘freopen’ was not declared in this scope
p.cc:9: error: ‘stdout’ was not declared in this scope
$ vim
<стираем нахер эту гадость>
$ time echo 10000 | ./p
104715764
real	0m0.034s
user	0m0.020s
sys	0m0.010s

и это на слабеньком нетбуке с Atom 1.6Ghz

[mansur]

У тебя компилятор немного другой, на acmp.ru и на моем домашнем эта программа прекрасно работает и так (P.S. просто нужно добавить библиотеку stdio.h)

Код это хорошо.
А в чем суть алгоритма. И как к примеру решить такую задачу:

Назовем число трипростым, ясли из любых трех его цифр, идущих подряд, можно сложить простое число.
Трипростое число может начинаться с одного или двух нулей. Например, 302 и 700 трипростые, а 212 – нет.
Числа 0 и 1 не простые. Найдите количество трипростых чисел заданной длины n.

#include <fstream>
#define FOR(i,a,b) for (int i = a; i <= b; i++)
#include <math.h>
using namespace std;
ifstream fin ("input.txt");
ofstream fout ("output.txt");
const int N = 1004;
const int INF = 1000000009;
int n, total = 0;
int num[N], num1[N], prime[N], indexPrime[N];
bool isPrime[N];
void MakePrimes()
{
FOR(i,100,999)
{
int q = 1;
FOR(j,2,i-1)
if (i % j == 0)
q = 0;
if (q)
{
total++;
prime[total] = i;
num[total] = 1;
isPrime[i] = true;
indexPrime[i] = total;
}
}
}
void DP()
{
FOR(i,4,n)
{
FOR(j,1,total)
{
if (num[j] != 0)
{
int ch = (prime[j] % 100) * 10;
FOR(k,1,9)
{
if (isPrime[ch + k])
{
num1[indexPrime[ch + k]] = (num1[indexPrime[ch + k]] + num[j]) % INF;
}
}
}
}
FOR(i,1,total)
{
num[i] = num1[i];
num1[i] = 0;
}
}
int ans = 0;
FOR(i,1,total)
ans = (ans + num[i]) % INF;
fout<<ans<<endl;
}
int main()
{
MakePrimes();
fin >> n;
DP();
return (0);
}