5.1. Таксомотор (рекурентні співвідношення на графах + динамічний розподіл пам'яті).
Алґоритм пошуку найдешевшого з найшвидших шляхів має такий вигляд:
Упорядкувати елементарні маршрути за зростанням часу подачі таксомотору на початкову зупинку. Наприклад, швидким методом Хоара з рекурсивним викликом процедури для послідовностей, розділених послідовністю максимальної довжини, всі елементи якої (послідовності) сталі.
Надати значення + &inf; ціні й часe першого прибуття на всі зупинки, за виключенням зупинки a, для якої цей час дорівнює t0.
або кінцеву зупинку розглядуваного маршруту неможливо досягнути за допомогою попередньо розглянутих маршрутів;
або кінцеву зупинку розглядуваного маршруту з використанням розглядуваного маршруту на останньому кроці можна досягнути за час, який менший за вже обчислений;
або кінцеву зупинку розглядуваного маршруту з використанням розглядуваного маршруту на останньому кроці можна досягнути за той же час, що вже знайдено, але за меншу ціну,
то вважаємо: кінцева зупинка розглядуваного маршруту досягається з використанням розглядуваного маршруту на останньому кроці. Розгляд елементарних маршрутів достатньо здійснювати до того моменту, починаючи з якого всі нерозглянуті маршрути починатимуться пізніше обчисленого часу досягнення зупинки b.
Цей алґоритм дає неправильну відповідь 8 6 8 5 замість 8 5 8 5 для вхідного файлу, який має такий вигляд.
3 3 1 1 3 1 1 0 2 4 5 1 1 0 2 5 4 2 7 0 3 8 1
Можна уникнути неправильної відповіді, використовуючи інформацію про прибуття таксомоторів на зупинки. Однак неможливо зберігати її в оперативній пам'яті при використанні середовища програмування Turbo Pascal. Є доволі простий вихід. Після 2-ого кроку (впорядкування даних про елементарні маршрути) для елементарних маршрутів, які не закінчуються у станції b, потрібно змінити час прибуття на кінцеву станцію на час відправлення таксомотору, який першим вирушає з кінцевої станції після прибуття на неї маршрутом таксомотору, дані про який змінюються. Якщо такого наступного маршруту немає, то потрібно змінити час прибуття на 1440 (хвилин), тобто на час закінчення доби. Дотримання останньої поради, зробленої Дмитром Петрашком (учасником відбірково-тренувальних зборів 2008 року, учнем 11-В класу Києво-Печерського ліцею «Лідер»), дозволяє отримати правильну відповідь 1444 22 1444 22 замість 1444 30 1444 22 для таких вхідних даних.
5 5 1 1 5 1 1 0 2 4 10 1 2 0 3 4 2 2 6 0 4 1398 10 3 6 0 4 1399 10 4 1 0 5 4 10
Алґоритм пошуку найшвидшого з найдешевших маршрутів відрізняється лише останнім кроком:
Розглянути всі елементарні маршрути, які починаються не раніше моменту t0, у порядку зростання часу відправлення. Якщо з використанням вже розглянутих маршрутів початкову зупинку розглядуваного маршруту можна досягнути за час, який не перевищує час подання таксомотору на початкову зупинку розглядуваного маршруту, то робимо таке. Якщо:
або кінцеву зупинку розглядуваного маршруту неможливо досягнути за допомогою попередньо розглянутих маршрутів;
або кінцеву зупинку розглядуваного маршруту з використанням розглядуваного маршруту на останньому кроці можна досягнути за ціну, яка менша за вже знайдену;
або кінцеву зупинку розглядуваного маршруту з використанням розглядуваного маршруту на останньому кроці можна досягнути за ту ж ціну, що вже знайдена, але за менший час,
то вважати: кінцева зупинка розглядуваного маршруту досягається з використанням розглядуваного маршруту на останньому кроці. Розгляд елементарних маршрутів достатньо здійснювати до тих пір, поки всі вони не будуть розглянуті як можливі ланки маршрутів.
В обох випадках, якщо обчислений час досягнення зупинки b не буде додатним навіть після розгляду всіх елементарних маршрутів, то час прибуття на початкову й кінцеву зупинки всіх таксомоторів збільшуємо на 1440 (кількість хвилин у добі) і продовжуємо розгляд маршрутів з першого.
Ще під час проведення ІІІ етапу олімпіади у 2004 році Юрій Знов'як, тоді учень 10 класу Києво-Печерського ліцею № 171 «Лідер» зауважив: повне розв'язання вимагає зберігання для кожної зупинки послідовності пар (час прибуття; вартість прибуття). Для будь-яких двох таких пар однієї послідовності (для однієї станції) нерівності між першими та другими елементами цих пар мають бути протилежні за змістом. Лише побудова й аналіз таких послідовностей пар цілих чисел надає можливість отримати правильну відповідь 8 4 10 3 для таких вхідних даних.
3 3 1 1 3 1 1 0 2 5 2 3 8 2 1 1 0 2 3 3 3 9 3 2 8 0 3 10 1
До 2006 року упорядник завдань свідомо уникав тестів, для коректного опрацювання яких потрібно динамічно розподіляти оперативну пам'ять. Починаючи з 2012 року результати опрацювання таких тестів враховуються при проведенні відбірково-тренувальних зборів.
5.2. Ряд фішок (теорія ігор + запис проміжних результатів).
Запровадимо поняття графа гри, який складається з вершин-позицій (множин натуральних чисел, які є номерами всіх наявних фішок і на рисунку їх зображено точками) і дуг-ходів (впорядкованих пар вершин, які вказують, яку позицію з якої можна отримати за один хід).
Для гри «Ряд фішок» хід з позиції A в позицію B дозволено, якщо B є підмножиною A і різниця множин A\B має вигляд {j} або {j, j + 1}.
Вершину, на яку не вказує жодна дуга, назвемо початковою позицією (початком гри).
Вершину, з якої не виходить жодна дуга (порожню множину) назвемо кінцевою позицією (кінцем гри).
Означимо поняття виграшної і програшної позицій.
Для кінцевої позиції виграшність позиції визначається згідно з правилами гри: кінцева позиція є виграшною (у даній грі).
Для решти (не кінцевих) позицій:
Інакше кажучи, у виграшній позиції гравець, чия черга ходу, може вибрати хід у програшну позицію, що забезпечує йому перемогу за умови відповідного вибору й надалі. У програшній позиції гравець завжди робить хід у виграшну позицію, тобто він не може позбавити суперника можливості виграти. Для нього виграш можливий лише, якщо суперник припуститься помилки і зробить хід у виграшну позицію.
Схема аналізу графа гри така.
Визначити виграшні позиції, з яких визначені раніше програшні позиції досягаються за 1 хід.
Визначити програшні позиції, з яких визначені раніше виграшні позиції досягаються за 1 хід.
Повторювати виконання пунктів 2-3 до встановлення, якими є всі позиції.
Таким чином за скінчену кількість кроків проводять аналіз усіх позицій гри. Аналіз завершується, якщо кроки 2-3 не дають ніякої нової інформації щодо виграшності чи програшності позицій.
Позицію A — підмножину множини {1, 2, 3, ... , n} — занумеруємо невід'ємним цілим числом k таким чином: якщо число k записати у двійковій системі числення, то j-та цифра, рахуючи від розряду одиниць, дорівнює 1, якщо j належить до A, і дорівнює 0, якщо не належить. Тоді розгляд позицій можна розглядати у порядку зростання номерів.
Після аналізу графа гри потрібно створити код програми, в якому інформацію про аналіз графа гри подано сталими масивами множин змінних типу byte для обох варіантів гри. Таке розв'язання буде оптимальним щодо часу роботи програми, поки не висуваються обмеження на час компіляції і об'єм тексту програми.