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


На форумі обговорюються лише питання, пов'язані з олімпіадою

Ви не зайшли.

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

maked0n
Новий користувач
Зареєстрований: 2012-12-01
Повідомлень: 14

Trimino

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

Поза форумом

 

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

iliiliilya123
Новий користувач
Зареєстрований: 2012-10-27
Повідомлень: 16

Re: Trimino

maked0n написав:

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

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

Поза форумом

 

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

vovova1997
Новий користувач
Зареєстрований: 2012-12-16
Повідомлень: 5

Re: Trimino

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

Поза форумом

 

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

stanislav1
Новий користувач
Зареєстрований: 2012-12-17
Повідомлень: 2

Re: Trimino

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

Поза форумом

 

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

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Trimino

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

Поза форумом

 

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

stanislav1
Новий користувач
Зареєстрований: 2012-12-17
Повідомлень: 2

Re: Trimino

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

Поза форумом

 

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

Жюри_Непомнящий
Журі
Зареєстрований: 2005-11-03
Повідомлень: 151

Re: Trimino

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

Поза форумом

 

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

LeonID
Новий користувач
Зареєстрований: 2008-12-09
Повідомлень: 160

Re: Trimino

stanislav1 написав:

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

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

Поза форумом

 

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

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Trimino

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

Поза форумом

 

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

shoa169
Новий користувач
Зареєстрований: 2010-11-10
Повідомлень: 56

Re: Trimino

LeonID написав:

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

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

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

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

Поза форумом

 

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

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Trimino

shoa169 написав:

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

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

Поза форумом

 

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

Жюри_Пасихов
Адміністратор
Зареєстрований: 2009-11-08
Повідомлень: 439

Re: Trimino

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

Поза форумом

 

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

shoa169
Новий користувач
Зареєстрований: 2010-11-10
Повідомлень: 56

Re: Trimino

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

ничего залуживающего внимания не заметил.

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

Поза форумом

 

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

shoa169
Новий користувач
Зареєстрований: 2010-11-10
Повідомлень: 56

Re: Trimino

stanislav1 написав:

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

LeonIDА написав:

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

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

Поза форумом

 

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

hotsnr
Новий користувач
Зареєстрований: 2011-11-16
Повідомлень: 12

Re: Trimino

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

Поза форумом

 

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

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Trimino

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

Поза форумом

 

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

hotsnr
Новий користувач
Зареєстрований: 2011-11-16
Повідомлень: 12

Re: Trimino

C++

#include <iostream>

using namespace std;

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

Поза форумом

 

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

hotsnr
Новий користувач
Зареєстрований: 2011-11-16
Повідомлень: 12

Re: Trimino

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

Поза форумом

 

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

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Trimino

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

Поза форумом

 

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

hotsnr
Новий користувач
Зареєстрований: 2011-11-16
Повідомлень: 12

Re: Trimino

#include <iostream>

using namespace std;

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

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

Поза форумом

 

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

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Trimino

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

Поза форумом

 

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

hotsnr
Новий користувач
Зареєстрований: 2011-11-16
Повідомлень: 12

Re: Trimino

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

Поза форумом

 

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

hotsnr
Новий користувач
Зареєстрований: 2011-11-16
Повідомлень: 12

Re: Trimino

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

Поза форумом

 

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

adamant
Новий користувач
Звідки: Запорожье
Зареєстрований: 2012-10-17
Повідомлень: 141

Re: Trimino

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

Поза форумом

 

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

hotsnr
Новий користувач
Зареєстрований: 2011-11-16
Повідомлень: 12

Re: Trimino

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

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt