Форум Всеукраїнської інтернет-олімпіади NetOI

maked0n · 2012-12-01 22:28:20

"...выводит на экран искомое количество способов по модулю 1000000007."
Имеется в виду, что искомое количество способов НЕ ПРЕВЫШАЕТ по модулю 1000000007?

iliiliilya123 · 2012-12-01 22:45:27

maked0n написав:
"...выводит на экран искомое количество способов по модулю 1000000007."
Имеется в виду, что искомое количество способов НЕ ПРЕВЫШАЕТ по модулю 1000000007?

Нет, вывести остаток от деления на 10^9+7.

vovova1997 · 2012-12-16 22:53:47

задача элементарная. там надо только одно условие проверить и умножить на что-то

stanislav1 · 2012-12-17 15:30:12

У умові задачі точно дані обмеження на n? Може бути n<=10000?

adamant · 2012-12-17 17:13:31

Что даёт вам повод предполагать это? Оо

stanislav1 · 2012-12-17 17:57:48

Мій алгоритм працює за n^2 і не можу знайти краще

Жюри_Непомнящий · 2012-12-19 00:13:57

Нагадую, що тут обговорюють не розв"язки, а умови задач.

LeonID · 2012-12-19 20:49:18

stanislav1 написав:
Мій алгоритм працює за n^2 і не можу знайти краще

Не знаю який найкращий алгоритм для цієї задачі, але взагалі потрібно орієнтуватись так - якщо автор дав обмеження n до 100 отже проходить алгоритм n^3, до 1000 то n^2, до 10000 то nlog(n), 100000 то n, більше то log(n)

adamant · 2012-12-20 12:57:04

До 10 - O(n!), до 25 - O(2^n)

shoa169 · 2012-12-20 15:18:10

LeonID написав:
Не знаю який найкращий алгоритм для цієї задачі, але взагалі потрібно орієнтуватись так - якщо автор дав обмеження n до 100 отже проходить алгоритм n^3, до 1000 то n^2, до 10000 то nlog(n), 100000 то n, більше то log(n)

Не очень-то практичный совет. Считаете, что его нужно выучить наизусть или писать шпаргалку?
Много проще ориентироваться так:

Число "операций" алгоритма на макс.тесте для полного балла не должно превышать ~10^7. ( 10^7 - 10^8 - может "прокатить". > 10^8 - ПОЧТИ БЕЗ ШАНСОВ! )

Точное значение предела зависит от TimeLimit задачи, от производительности проверяющего сервера и от сложности элементарной "операции" алгоритма.
Желательно не забывать об оптимизации кода внутри "операции". Иногда удаётся получить полный балл при не лучшей асимптотике алгоритма, но крайне оптимизированным кодом.

adamant · 2012-12-20 16:07:31

shoa169 написав:
Иногда удаётся получить полный балл при не лучшей асимптотике алгоритма, но крайне оптимизированным кодом.

Например, ассемблерными вставками Х)

Жюри_Пасихов · 2012-12-20 19:02:13

Дискуссия не имеет отношения к усовиям, ничего залуживающего внимания не заметил. Прошу прекратить обсуждать запрещенные на форуме вопросы, и варианты решений.

shoa169 · 2012-12-21 11:02:12

Жюри_Пасихов написав:
ничего залуживающего внимания не заметил.

При всём моём уважении к жюри не могу не заметить, что по-моему - уметь оценивать асимптотику своего алгоритма и знать "магическое" число 10^7 должен каждый спортивный программист уровня выше, чем "призёр района". Уже тут, во 2-ом туре ЭТО нужно во всех(!) задачах.
Как колокольчик на шее потерявшегося барашка: откуда звенит - туда идешь искать. Какой алгоритм даст значение асимптотики на ограничениях задачи 10^7 - тот кандидат на полный балл. Разумеется, алгоритм должен быть ещё и верным и безошибочно реализованным!
Впрочем, большая часть участников интернетки, наверняка ЭТО уже знали. Но уверен, что знали не все, но теперь - таких больше!
Прошу прощения за некоторый off-top.

shoa169 · 2012-12-22 00:37:58

stanislav1 написав:
Мій алгоритм працює за n^2 і не можу знайти краще

LeonIDА написав:
обговорення асимптотики розвязку - це і є обговорення умови задачі.

Вот тут я не согласен. Обсуждение асимптотики решения зачач тура допустимо только после его окончания в рамках разбора решений!
За такое обсуждение до окончания тура я бы банил - после предупреждения. Наше жюри напоминание уже сделало! Может начать банить
Всё что писал я об асимптотике относится ко всем задачам на любых контестах.

hotsnr · 2012-12-27 20:55:46

У меня такое странное поведение системы: я отсылаю Тримино и получаю неправильный ответ на втором тесте. Хотя у меня выводит 0 и на Линуксе тоже. Я использую iostream и вывожу перевод строки.
Подскажите что не так.

adamant · 2012-12-27 21:00:20

На каком языке вы пишите? Приведите пример программы, которая, считав входные данные, независимо от их сути выводит 0.

hotsnr · 2012-12-27 21:01:43

C++

#include <iostream>

using namespace std;

int main (){
cout<<0<<endl;
return 0;
}

hotsnr · 2012-12-27 21:03:57

Извините, не то

adamant · 2012-12-27 21:04:11

Такая программа выдаст вердикт Bad Data, вы должны считать входные данные целиком.

hotsnr · 2012-12-27 21:05:20

#include <iostream>

using namespace std;

int main (){
int N;
cin>>N;
cout<<0<<endl;
return 0;
}

и оно проходит второй тест. Буду смотреть у себя, хотя я четко вижу 0 и перевод строки

adamant · 2012-12-27 21:06:24

Какой именно вердикт? Bad Data или Wrong Answer? И первый тест у Вас проходит?

hotsnr · 2012-12-27 21:07:33

Первый - ОК, второй WA

hotsnr · 2012-12-27 21:09:01

Только вот отсылал

adamant · 2012-12-27 21:12:17

А какой вы используете компилятор?

hotsnr · 2012-12-27 21:13:35

Visual C++ 2012 и проверялось на Линуксе g++ 4.4.6

Форум Всеукраїнської інтернет-олімпіади NetOI

#1 2012-12-01 22:28:20

Trimino

#2 2012-12-01 22:45:27

Re: Trimino

maked0n написав:

#3 2012-12-16 22:53:47

Re: Trimino

#4 2012-12-17 15:30:12

Re: Trimino

#5 2012-12-17 17:13:31

Re: Trimino

#6 2012-12-17 17:57:48

Re: Trimino

#7 2012-12-19 00:13:57

Re: Trimino

#8 2012-12-19 20:49:18

Re: Trimino

stanislav1 написав:

#9 2012-12-20 12:57:04

Re: Trimino

#10 2012-12-20 15:18:10

Re: Trimino

LeonID написав:

#11 2012-12-20 16:07:31

Re: Trimino

shoa169 написав:

#12 2012-12-20 19:02:13

Re: Trimino

#13 2012-12-21 11:02:12

Re: Trimino

Жюри_Пасихов написав:

#14 2012-12-22 00:37:58

Re: Trimino

stanislav1 написав:

LeonIDА написав:

#15 2012-12-27 20:55:46

Re: Trimino

#16 2012-12-27 21:00:20

Re: Trimino

#17 2012-12-27 21:01:43

Re: Trimino

#18 2012-12-27 21:03:57

Re: Trimino

#19 2012-12-27 21:04:11

Re: Trimino

#20 2012-12-27 21:05:20

Re: Trimino

#21 2012-12-27 21:06:24

Re: Trimino

#22 2012-12-27 21:07:33

Re: Trimino

#23 2012-12-27 21:09:01

Re: Trimino

#24 2012-12-27 21:12:17

Re: Trimino

#25 2012-12-27 21:13:35

Re: Trimino

Нижній колонтитул