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

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

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

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

У меня для первых 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) и при добавлении следующего простого числа время удваивается.

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

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

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

З іншого боку, моя програма для
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).
Так що істина виявилася посередині -- простір для оптимізацій є, але навряд чи такий, щоб можна було забезпечити швидке виконання програми для всіх можливих заявлених в умові обмежень.

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

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

Ви можете не повірити, але в тесті
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

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

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) и при добавлении следующего простого числа время удваивается.

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

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

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

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

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

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

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.

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

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. Достатньо швидко для олімпіадної задачі -- я не знаю як.
Миритися з чистим "удваиванием времени при добавлении числа" тут необов'язково, його (подвоєння) неважко різати.

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

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

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. Достатньо швидко для олімпіадної задачі -- я не знаю як.
Миритися з чистим "удваиванием времени при добавлении числа" тут необов'язково, його (подвоєння) неважко різати.

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

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