Зимова школа з програмування, день 2

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

Сама ж Школа почалася з лекції автора цього дня Віталія Неспірного з Донецького національного університету.

Саме змагання почалося з розв'язання тренувальних завдань, під час яких з'ясувалося, що решта учасників з команди не можуть зчитувати зі стандартного пристрою введення ряд чисел. У мене то є виправдання у вигляді незнання С++, але все ж... Ще одне підтвердження моєї думки, що в команді всі мають «говорити» однією мовою. У підсумку зі зчитуванням і виведенням якось розібралися.

Потім були видані завдання основного туру, які складалися з 11 задач досить високого рівня, зрозуміло, що розв'язати їх за 3.5 години було нереально.

Найбільше часу пішло на першу задачу, де необхідно знайти співвідношення чисел у послідовності, що діляться й не діляться на задане число. Основна проблема була в роботі з великими числами, але в підсумку з'ясувалося, що ми натрапили на добряче приховане підводне каміння.

Усі задачі перелічувати немає сенсу, зупинюся на важливих і цікавих моментах.

Слід на майбутнє добре розібратися з Ханойськими вежами, оскільки за ними було дві задачі. Так само цікавою була задача про астронавта, яка, як виявилося, розв'язується за допомогою алгоритму Дейкстри. Була цікавою задача про більярд, де треба було пускати пряму траєкторію, а відбивати й перемальовувати стіл, яка розв'язувалася через дільник і розв'язання системи цілих чисел. Ця ж задача принесла команді ХПІ зливок золота вагою один грам за найкраще розв'язання задачі. Так само цікаво, що зі вступної лекції була схожа задача, тільки про перетин трикутників. Плюс була класична задача про знаходження відстані між двома прямими у тривимірному просторі. На майбутнє слід пригадати геометричні формули в такому просторі.

Підсумки зараз уже завершуються. На цей момент ми ділимо десь 27 місце разом з рештою і результат у команди такий самий, як і в тренера. Переможцем дня з розв'язаними 7 задачами стала команда Київського національного університету ім. Т. Шевченка. 2-4 місця з розв'язаними 6 задачами посіли команди ХПІ, КНУ Шевченка та Львівського національного університету. Усі ці команди посідають лідерські позиції в країні, тож немає сенсу уточнювати. З рекордів, найшвидше розв'язання першої задачі було здійснено за 7 хвилин.

Усе підбиття підсумків завершилося, ідемо. Розв'язувати задачі можна всі решта днів і надсилати розв'язання на дорозв'язуванні. Спробуємо зайнятися цим у готелі.

Редагувалося 22.02.2008