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


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

Ви не зайшли.

#1 2012-01-09 23:19:20

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

задача Dividers

Які обмеження за часом роботи має програма?

Поза форумом

 

#2 2012-01-10 00:58:00

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 281
Вебсайт

Re: задача Dividers

це вже неодноразово обговорювалось - програма може працювати трохи довше, ніж найшвидша правильна(найчастіше така надходить від журі) точні ТЛи тут не повідомляють.

Але, у будь-якому разі, думаю, не варто розраховувати, що програмі дадуть більше секунди або кількох секунд.

Поза форумом

 

#3 2012-01-12 08:29:44

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: задача Dividers

Учасник (не важливо, який) по пошті написав:

Скільки часу має працювати программа? Я зробив її на Паскалі, малі числа рахує швидко а великі(шестизначні наприклад довго і висне і я не розумію у чому причина)
допоможіть якщо можете маленьку підказочку як скоротити час

Не знаю, чи це товстий тролінг, чи просто хлопчик не розуміє, що таке олімпіада... На цей лист дам відповідь, надалі натискатиму кнопочку "Спам" мовчки.

Скільки часу має працювати програма -- який тайм-ліміт поставить журі, такий і буде. Гарантовано в межах від 0,1 сек до 10 сек, точніше на даній олімпіаді зарані не повідомляють. Див. також попереднє повідомлення даної теми (учасника Dim_ov).

Якщо програма довго рахує для 6-тизначних чисел -- значить, вона не має абсолютно ніяких шансів щось порахувати для 19-значних, отже не має абсолютно ніяких шансів набрати великі бали. Але, якщо для 1--5-значних рахує правильно і швидко -- є надія отримати десь так дуже приблизно від 1 до 15 балів (з 60 можливих).

Як скоротити час -- ну так у цьому й полягає завдання: придумати такий алгоритм, щоб він розв"язував задачу правильно і швидко, та реалізувати (закодити) його на одній з дозволених мов програмування.
Коли закінчиться тур -- сподіваюсь, буде розбір задач, в тому числі й даної. А питати під час туру -- так само нечесно, як красти.

Поза форумом

 

#4 2012-01-14 22:11:32

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

Re: задача Dividers

Ilya Porublyov написав:

Учасник (не важливо, який) по пошті написав:

Скільки часу має працювати программа? Я зробив її на Паскалі, малі числа рахує швидко а великі(шестизначні наприклад довго і висне і я не розумію у чому причина)
допоможіть якщо можете маленьку підказочку як скоротити час

Не знаю, чи це товстий тролінг, чи просто хлопчик не розуміє, що таке олімпіада... На цей лист дам відповідь, надалі натискатиму кнопочку "Спам" мовчки.

Скільки часу має працювати програма -- який тайм-ліміт поставить журі, такий і буде. Гарантовано в межах від 0,1 сек до 10 сек, точніше на даній олімпіаді зарані не повідомляють. Див. також попереднє повідомлення даної теми (учасника Dim_ov).

Якщо програма довго рахує для 6-тизначних чисел -- значить, вона не має абсолютно ніяких шансів щось порахувати для 19-значних, отже не має абсолютно ніяких шансів набрати великі бали. Але, якщо для 1--5-значних рахує правильно і швидко -- є надія отримати десь так дуже приблизно від 1 до 15 балів (з 60 можливих).

Як скоротити час -- ну так у цьому й полягає завдання: придумати такий алгоритм, щоб він розв"язував задачу правильно і швидко, та реалізувати (закодити) його на одній з дозволених мов програмування.
Коли закінчиться тур -- сподіваюсь, буде розбір задач, в тому числі й даної. А питати під час туру -- так само нечесно, як красти.

Т.е. программа работающая за 1000 операция должна пройти по времени?

Поза форумом

 

#5 2012-01-14 23:33:10

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 281
Вебсайт

Re: задача Dividers

kiberok написав:

Т.е. программа работающая за 1000 операция должна пройти по времени?

Так, програма, яка гарантовано вкладеться в 1000 елементарних операцій(операцій, що потребують лише кількох тактів процесора), чи навіть 100000000 операцій має дуже високі шанси пройти по часу, але мені, наприклад, важко уявити, як це можна порахувати. Тому більш прийнято для оцінки часу роботи програми використовувати асимптотичну оцінку.

Куріть вікіпедію, або якісь інші джерела, якщо знайдете. Ще гарно описано у Кормена з компанією (Тут англійською, але переклад, при бажанні, можна знайти)




А взагалі, надалі - на подібні питання буде нормальна реакція, якщо вони задаються після закінчення олімпіади. А обговорення часу роботи, чи асимптотики під час туру - це в деякій мірі обговорення рішень, що заборонено.

Поза форумом

 

#6 2012-01-14 23:52:03

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

Re: задача Dividers

спасибо за весьма исчерпывающий ответ.

Поза форумом

 

#7 2012-01-15 13:51:07

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

Re: задача Dividers

Ilya Porublyov написав:

Скільки часу має працювати програма -- який тайм-ліміт поставить журі, такий і буде. Гарантовано в межах від 0,1 сек до 10 сек, точніше на даній олімпіаді зарані не повідомляють.

Прокомментируйте тогда этот вердикт:
http://2.firepic.org/2/images/2012-01/1 … 1eli6l.png
(Для тех, кому интернет не позволяет посмотреть картинку, там результат отправки на онлайн проверку с таким вердиктом:
00    FAILED (Time Out)    0.04 сек.
)

Поза форумом

 

#8 2012-01-15 15:35:02

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 281
Вебсайт

Re: задача Dividers

Scorpy написав:

Прокомментируйте тогда этот вердикт:
http://2.firepic.org/2/images/2012-01/1 … 1eli6l.png
(Для тех, кому интернет не позволяет посмотреть картинку, там результат отправки на онлайн проверку с таким вердиктом:
00    FAILED (Time Out)    0.04 сек.
)

Мабуть Ілля Миколайович трохи помилився з порядком і мав на увазі від 0.01 до 10 сек., бо в задачі Sequence також ТЛи стоять близько 0.05 сек.

Поза форумом

 

#9 2012-01-18 14:23:48

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

Re: задача Dividers

Я написав программу до задача Dividers.Вона працює на комп'ютері просто чудово, але на сайті перевірки вона не проходе перевірку, там якась ошибка чи що??.Що робити???

Поза форумом

 

#10 2012-01-18 14:25:36

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

Re: задача Dividers

В мене та сама проблема як і в Scorpy - 00    FAILED (Time Out)    0.04 сек.

Поза форумом

 

#11 2012-01-18 19:26:01

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 281
Вебсайт

Re: задача Dividers

byme8 написав:

Я написав программу до задача Dividers.

Молодець!

byme8 написав:

Вона працює на комп'ютері просто чудово, але на сайті перевірки вона не проходе перевірку

Це дуже погано

byme8 написав:

там якась ошибка чи що??

Так

byme8 написав:

Що робити???

Оптимізувати програму так, щоб вона знаходила правильну відповідь швидше, ніж за 0.04 сек.

Завжди Ваш,
http://www.absolutelyfirst.com/wp-content/uploads/2011/04/CaptainObvious.jpg

Поза форумом

 

#12 2012-01-19 07:00:25

Ilya Porublyov
журі
Зареєстрований: 2005-10-27
Повідомлень: 130

Re: задача Dividers

Scorpy написав:

Ilya Porublyov написав:

Гарантовано в межах від 0,1 сек до 10 сек, точніше на даній олімпіаді зарані не повідомляють.

Прокомментируйте тогда этот вердикт:
00    FAILED (Time Out)    0.04 сек.

Прошу пробачення за не зовсім точне висловлення і за затримку з відповіддю.

"від 0,1 сек до 10 сек" малося на увазі для хоч скільки-небудь великих тестів, а 42 до хоч скільки-небудь великих не відноситься, тому там тайм-ліміт менший. Що на різні тести однієї задачі на даній олімпіаді можуть бути різні тайм-ліміти -- обговорювалося багатократно.

byme8 написав:

Вона працює на комп'ютері просто чудово, але на сайті перевірки вона не проходе перевірку
00    FAILED (Time Out)    0.04 сек.

Не знаю, як такого можна добитися на настільки малих вхідних даних, як 42... Вам вдавалося написати розв"язки любих інших задач цього сайту так, щоб вони проходили хоча б по кілька тестів? Якщо ні -- можливо, проблема в чомусь зовсім дурному, як-то зайві readln-и або щось подібне.
Ви пробували кілька разів і завжди було FAILED (Time Out) чи тільки один раз? Якщо один раз -- малоймовірно, але гіпотетично можливо, що час був поміряний неправильно (це неможливо при офіційному режимі перевірки, але саме в он-лайн режимі -- малоймовірно, але гіпотетично можливо).

ЯКЩО(!!!) впевнені, що всі очевидні причини перебрали й проблема не в них -- вишліть код програми мені особисто (через лінк "E-mail" даного форума).

Поза форумом

 

#13 2012-01-20 10:37:22

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

Re: задача Dividers

Я переписав код з Turbo Delphi у С++ і тільки тоді, програма пройшла перевірку без запинок.

Поза форумом

 

#14 2012-02-02 22:49:13

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

Re: задача Dividers

Не подскажите, почему fpc не компилирует тип UInt64? У меня под линуксом все идет.
И есть ли этому типу замена в fpc?

Поза форумом

 

#15 2012-02-03 00:20:08

Dim_ov
Новий користувач
Зареєстрований: 2009-11-29
Повідомлень: 281
Вебсайт

Re: задача Dividers

kiberok написав:

Не подскажите, почему fpc не компилирует тип UInt64? У меня под линуксом все идет.
И есть ли этому типу замена в fpc?

Мабуть уже не актуально, але відповім.

Сам на паскалі майже не пишу, але гугл говорить, що є тип QWord (або ж LongestWord, але це начебто gnu pascal-івське розширення, тому мабуть теж не працюватиме).

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt