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


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

Ви не зайшли.

#1 2011-01-06 14:18:46

trumen
Новий користувач
Зареєстрований: 2011-01-06
Повідомлень: 1

Задача Division

а в цій задачі k точно <= 100, а не 10?

Поза форумом

 

#2 2011-01-06 15:30:02

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

Re: Задача Division

Точно. -- НЕ ЗОВСІМ. ОСТАТОЧНЕ РІШЕННЯ ЖУРІ ДИВ У ПОВІДОМЛЕННІ #20 ДАНОЇ ТЕМИ

Відредаговано Ilya Porublyov (2011-01-17 22:10:39)

Поза форумом

 

#3 2011-01-14 18:10:59

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

Re: Задача Division

Дуже цікава і дуже складна задача,
тому прошу автора дати відповідь
на самий складний тест:
1 1000000000000000000 100
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541
від Вас не убуде(оскільки цього тесту думаю в перевірці не буде), а іншим буде шлях до пошуку.

Відредаговано LeonID (2011-01-14 18:12:03)

Поза форумом

 

#4 2011-01-14 19:47:23

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

Re: Задача Division

Если вместо 100 первых простых чисел взять 100 последних, то тест станет еще сложнее.


По закону Мёрфи, "Объяснение примера" есть только в задачах, условие которых было бы однозначно даже без примеров, а в задачах, где условие неоднозначно, его нет.

Поза форумом

 

#5 2011-01-14 19:53:32

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

Re: Задача Division

DiEvAl написав:

Если вместо 100 первых простых чисел взять 100 последних, то тест станет еще сложнее.

ні, не стане (моє теперішнє рішення (поки що не напишу, яке) тест з останніми числами проходить, а з першими - ні)

Відредаговано Dim_ov (2011-01-15 11:42:19)

Поза форумом

 

#6 2011-01-15 12:38:32

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Задача Division

У меня для первых 25-ти простых чисел

1 1000000000000000000 25
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

вывод: 120317290474566603

затрачивает поти 25 секунд (нетбук процессор 1,6 GHz) и при добавлении следующего простого числа время удваивается.

У кого лучше, отзовитесь.
Есть ли к чему стремиться? smile smile smile

Відредаговано LVV (2011-01-15 13:51:29)


Вік живи - вік навчайся.

Поза форумом

 

#7 2011-01-15 13:00:08

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

Re: Задача Division

LVV написав:

У меня для первых 25-ти простых чисел

1 1000000000000000000 20
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

вывод: 120317290474566603

затрачивает поти 25 секунд (нетбук процессор 1,6 GHz) и при добавлении следующего простого числа время удваивается.

У кого лучше, отзовитесь.
Есть ли к чему стремиться? smile smile smile

Для цього тесту(там використовується тільки 20 чисел, а не 25) у мене відповідь - 127797680375919858
І потрібно ~0,5 секунд

для 25 чисел - 17 секунд і час теж подвоюється при додаванні ще одного числа

Відредаговано Dim_ov (2011-01-15 13:09:16)

Поза форумом

 

#8 2011-01-15 13:28:53

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

Re: Задача Division

Обмеження, сформульовані в задачі, справді з'явилися внаслідок того, що при перевірці на час роботи програми сталася тупа технічна помилка, і я думав, що міряю макстест, а насправді міряв невідомо що.

З іншого боку, моя програма для
1 1000000000000000000 20
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71
працює менше 0,1 сек,
а для
1 1000000000000000000 25
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
менше 1 сек (на ASUS K40, 1.9GHz).
Так що істина виявилася посередині -- простір для оптимізацій є, але навряд чи такий, щоб можна було забезпечити швидке виконання програми для всіх можливих заявлених в умові обмежень.

Остаточне рішення, узгоджене журі, буде оприлюднено сьогодні пізніше.

Прошу пробачення за таку сумну ситуацію. А для уникнення аналогічних помилок у майбутньому, прошу успішних учасників, які вже не є школярами або перестануть бути школярами у наступному навчальному році, долучатися до проведення даної олімпіади. На жаль, нинішньому складу журі не вистачає часу писати вчасно по кілька незалежних розв'язків.

Поза форумом

 

#9 2011-01-15 13:47:30

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Задача Division

Уважаемый Dim_ov, а как с результатом для 25 простых чисел???
Наши ответы совпадают или нет???

Відредаговано LVV (2011-01-15 13:55:00)


Вік живи - вік навчайся.

Поза форумом

 

#10 2011-01-15 13:58:41

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

Re: Задача Division

Ви можете не повірити, але в тесті
1 1000000000000000000 20
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
значення
73 79 83 89 97
переважною більшістю програм просто не будуть читатися, тому по суті це тест
1 1000000000000000000 20
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71

Так що в даній задачі і даній темі помилялося не тільки журі wink

Поза форумом

 

#11 2011-01-15 16:56:30

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

Re: Задача Division

LVV написав:

Уважаемый Dim_ov, а как с результатом для 25 простых чисел???
Наши ответы совпадают или нет???

Ні, теж не співпадають(Але я теж можу помилятися, як і Ви)

Поза форумом

 

#12 2011-01-15 18:15:47

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

Re: Задача Division

LeonID написав:

Dim_ov написав:

LVV написав:

У меня для первых 25-ти простых чисел

1 1000000000000000000 20
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

вывод: 120317290474566603

затрачивает поти 25 секунд (нетбук процессор 1,6 GHz) и при добавлении следующего простого числа время удваивается.

У кого лучше, отзовитесь.
Есть ли к чему стремиться? smile smile smile

Для цього тесту(там використовується тільки 20 чисел, а не 25) у мене відповідь - 127797680375919858
І потрібно ~0,5 секунд

для 25 чисел - 17 секунд і час теж подвоюється при додаванні ще одного числа

Шановні Dim_ov та LVV ваша відповідь на 20-ти числовий тест неправильна в обох, (хоч я так зрозумів у LVV все таки написана відповідь на 25-ти числовий тест, але також неправильна).

Тоді будьте ласкаві, повідомте ще свою правильну відповідь smile

Відредаговано Dim_ov (2011-01-15 18:18:28)

Поза форумом

 

#13 2011-01-15 18:32:10

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Задача Division

Знаете, уважаемые, Dim_ov и LeonID? а давайте сверим ответы для первых 20-ти простых чисел в тесте 1 100000 20.
У кого нибудь будут возражения, что это 12707 ???


Вік живи - вік навчайся.

Поза форумом

 

#14 2011-01-15 18:39:03

LVV
Олімпієць
Звідки: Олешки
Зареєстрований: 2010-11-19
Повідомлень: 360
Вебсайт

Re: Задача Division

Ilya Porublyov написав:

Остаточне рішення, узгоджене журі, буде оприлюднено сьогодні пізніше.

Это была шутка?
Задача действительно хорошая, может и не стоит менять значение k<=100.
А вдруг кто нибудь додумается как быстрее чем за миллион лет (с учетом удваивания времени при добавлении числа) просчитать тест
1 1000000000000000000 100
для простых 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541. smile

Відредаговано LVV (2011-01-15 18:48:23)


Вік живи - вік навчайся.

Поза форумом

 

#15 2011-01-15 18:59:36

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

Re: Задача Division

Топік, мабуть, все-одно скоро почистять від обговорення рішень, тому пропоную почекати, що скаже жюрі на рахунок обмежень

Відредаговано Dim_ov (2011-01-15 19:12:19)

Поза форумом

 

#16 2011-01-16 10:22:25

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

Re: Задача Division

LVV написав:

А вдруг кто нибудь додумается как быстрее чем за миллион лет (с учетом удваивания времени при добавлении числа) просчитать тест
1 1000000000000000000 100
для простых 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541

Швидше ніж за мільйон років -- цілком можливо. Моя програма працювала на цьому тесті 13 год 38 хв (тактова 1.9GHz), відповідь 88749884546358561. Достатньо швидко для олімпіадної задачі -- я не знаю як.
Миритися з чистим "удваиванием времени при добавлении числа" тут необов'язково, його (подвоєння) неважко різати.

Більш того: програма на основі найпримітивнішого алгоритму розв'язуватиме цей тест не мільйон років, а менше трьох тисяч wink wink wink

Відредаговано Ilya Porublyov (2011-01-16 14:12:26)

Поза форумом

 

#17 2011-01-16 18:12:32

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

Re: Задача Division

Ilya Porublyov написав:

Точно. -- НЕ ЗОВСІМ. ОСТАТОЧНЕ РІШЕННЯ ЖУРІ (БУДЕ) ОПРИЛЮДНЕНО ДО ВЕЧОРА СУБОТИ 15.01.2011

Какое всё-таки решение приняло жюри? Вечер субботы уже прошёл.


laptop login: root
Password:
Last login: Thu Jan  1 00:00:00 UTC 1970
root@[laptop:~]# eix-sync && emerge -atuvDN world

Поза форумом

 

#18 2011-01-16 19:39:27

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

Re: Задача Division

Ilya Porublyov написав:

LVV написав:

А вдруг кто нибудь додумается как быстрее чем за миллион лет (с учетом удваивания времени при добавлении числа) просчитать тест
1 1000000000000000000 100
для простых 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449 457 461 463 467 479 487 491 499 503 509 521 523 541

Швидше ніж за мільйон років -- цілком можливо. Моя програма працювала на цьому тесті 13 год 38 хв (тактова 1.9GHz), відповідь 88749884546358561. Достатньо швидко для олімпіадної задачі -- я не знаю як.
Миритися з чистим "удваиванием времени при добавлении числа" тут необов'язково, його (подвоєння) неважко різати.

Більш того: програма на основі найпримітивнішого алгоритму розв'язуватиме цей тест не мільйон років, а менше трьох тисяч wink wink wink

Дякую Вам Ilya Porublyov за те, що Ви взяли на себе відповідальність і  повідомили аудиторії результат максимального тесту (менше навіть чим за добу). Очевидно всім іншим учасникам є до чого прагнути, але які тепер будуть обмеження до задачі? Адже навряд тест на задачу може перевірятися навіть декілька хвилин?

Поза форумом

 

#19 2011-01-17 08:32:58

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

Re: Задача Division

Всем участникам разослано письмо следующего содержания:
==========================================

На жаль, при підготовці задачі division сталася технічна помилка, і технічні обмеження на розмір вхідних даних виявилися неадекватними.
Перевірка задачі division відбудеться так:
80% балів припаде на тести, в яких кількість простих чисел не перевищує 30, а значення простих чисел та меж діапазона не перевищують
100000000000000 (інакше кажучи, 1e+14). Ще 20% балів припаде на тести, які авторський розв'язок проходить дуже швидко і в яких значення вхідних даних перевищують вказані зараз обмеження, але задовольняють вказаним в умові задачі (до 100 чисел,
значення до 1e+18). Ще 40% балів припаде на тести, які задовольняють обмеженням вказаним в умові задачі, на яких авторський розв'язок працює занадто довго.  Тобто, якщо комусь з учасників вдалося або удасться написати програму,
кращу за програму автора задачі, кількість балів виявиться більшою 100%.
Просимо пробачення за допущену помилку.

======
==RU==
======

К сожалению, при подготовке задачи division произошла техническая ошибка, и технические ограничения на размер входных данных оказались неадекватными. Проверка задачи division будет произведена так: 80% баллов будут соответствовать тестам, в которых количество простых чисел не превышает 30, а значения простых чисел и границ диапазона не превышают 100000000000000 (иначе говоря, 1e+14).
Ещё 20% баллов будут соответствовать тестам, которые авторское решение проходит очень быстро и в которых значения входных данных превышают указанные сейчас ограничения, но удовлетворяют указанным в условии задачи (до 100 чисел, значения до 1e+18).
Ещё 40% баллов будут соответствовать тестам, удовлетворяющим ограничения, указанные в условии задачи, на которых авторское решение  работает слишком долго. То есть, если кому-либо из участников удалось или удастся написать
программу, лучшую, чем программа автора задачи, количество баллов окажется большим 100%.

Просим прощения за допущенную ошибку.

Жюри олимпиады

Відредаговано Жюри_Пасихов (2011-01-17 08:33:55)

Поза форумом

 

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

Powered by Likt
© Copyright 2002–2009 Likt