Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #11  
Старый 30.01.2011, 16:12
Мансур

 
Сообщений: n/a

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

 
Сообщений: n/a

Сообщение от Мансур Посмотреть сообщение
Сложность алгоритма предложенного выше N * 10 * 10 * 10 при максимальном N = 10000 получим 10,000,000 такое число операций в 1секунду ну ни как не влезет...
прекрасно влезет
  #13  
Старый 31.01.2011, 14:07
Новичок

Отправить личное сообщение для mansur Посмотреть профиль Найти все сообщения от mansur
 
Регистрация: 25.12.2010
Сообщений: 4

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

 
Сообщений: n/a

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

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

Отправить личное сообщение для mansur Посмотреть профиль Найти все сообщения от mansur
 
Регистрация: 25.12.2010
Сообщений: 4

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

Отправить личное сообщение для mansur Посмотреть профиль Найти все сообщения от mansur
 
Регистрация: 25.12.2010
Сообщений: 4

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

 
Сообщений: n/a

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

Код:
$ 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
  #18  
Старый 01.02.2011, 16:27
Новичок

Отправить личное сообщение для mansur Посмотреть профиль Найти все сообщения от mansur
 
Регистрация: 25.12.2010
Сообщений: 4

У тебя компилятор немного другой, на acmp.ru и на моем домашнем эта программа прекрасно работает и так (P.S. просто нужно добавить библиотеку stdio.h)
  #19  
Старый 20.02.2011, 20:03
мимо проходил

 
Сообщений: n/a

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

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

 
Сообщений: n/a

rewenie
#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);
}
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра