Написання програм CLOCK, POLICE і WATER (Задачі XI Всеукраїнської олімпіади з інформатики та рекомендації по їх розв’язанню)

Задачі XI Всеукраїнської олімпіади з інформатики та рекомендації по їх розв’язанню.

Годинник

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

Завдання. Написати програму CLOCK.*, яка буде обчислювати мінімальну кількість діб, необхідних для того, щоб початкове положення кульок в черзі повторилося.

Вхідні дані. Вхідний текстовий ASCII-файл CLOCK.DAT містить в єдиному рядку натуральні числа S, M, H, K (кількість секунд в хвилині, хвилин в годині, годин в добі і загальну кількість кульок відповідно; S, M, H £ 60, S+M+H-2 £ K £1000).

Вихідні дані. Вихідний текстовий ASCII-файл CLOCK.SOL повинен містити в єдиному рядку підраховану Вашою програмою кількість діб.

Зауваження. В тестах, що будуть застосовуватися при перевірці, використання довгої арифметики не передбачається. Для подання кількості діб радимо використовувати типи даних extended в Pascal та long double в C.

Приклад введення і виведення.

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

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

Наприклад, для випадку S=M=H=2, K=4 отримаємо після першої доби з послідовності (1,2,3,4) послідовність (2,3,1,4). Бачимо, що остання кулька залишилась на своєму місці, а решта циклічно зсунулась вліво. Після другої доби отримаємо послідовність (3,1,2,4). Вона виникає після такої ж перестановки з послідовності (2,3,1,4). Ще одне перетворення приведе до послідовності (1,2,3,4), яка співпадає з початковою. Отже, відповідь – 3 доби.

Відповідь отримується в 2 етапи. Перший – моделювання роботи годинника на протязі першої доби для отримання добової перестановки. Другий – застосування добової перестановки до черги до отримання початкової послідовності. Очевидно, застосування перестановки вимагає набагато менше часу ніж моделювання роботи годинника на протязі доби, але існує можливість ще більш скоротити час обчислень.

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

Кожна кулька переміщується за своїм циклом, довжина якого є періодом переміщення кульки. В розглянутому прикладі кулька 1 переміщується по позиціях 1, 3, 2, 1, 3, 2, 1, …, тобто її цикл – (1,3,2), період – 3. Кульки 2 та 3 ведуть себе так само, а от кулька 4 залишається на місці, отже її цикл – (4) і період – 1.

Періодом повторення початкового розташування кульок в черзі має бути кратним всім періодам переміщень кульок, отже він буде дорівнювати найменшому спільному кратному періодів всіх кульок. Для приклада загальний період НСК(3,3,3,1) = 3, що співпадає з раніше отриманим розв’язком.

Охорона.

Дано N (1 £ N £ 100) пронумерованих об’єктів, що охороняються і з’єднані K шляхами (1 £ K £ 4950). З будь-якого об’єкта на будь-який інший можна проїхати шляхами. Рух кожним шляхом можливий в обидва боки. Необхідно розташувати підрозділ охорони так, щоб найвіддаленіший об’єкт досягався якомога швидше.

Завдання. Напишіть програму POLICE.*, що знаходить найкраще місце для підрозділу охорони. Підрозділ може знаходитися як на одному з об’єктів так і на шляху між об’єктами).

Вхідні дані. Вхідний текстовий ASCII-файл POLICE.DAT в першому рядку містить натуральні числа N і K. В наступних K рядках містяться по три натуральних числа F, T, S (об’єкти з номерами F і T з’єднує шлях довжиною S кілометрів, 1 £ S £ 100; безпосередньо між F і T може бути не більше одного шляху).

Вихідні дані. Вихідний текстовий ASCII-файл POLICE.SOL повинен містити числа D, L, M, R (відстань до найдальшого пункту дорівнює D; підрозділ слід розташувати в R кілометрах від об’єкту L на шляху до об’єкту M).

Приклад введення і виведення.

Зафіксуємо  два об’єкта i та j, між якими є дорога.  Розглянемо залежність відстані до об’єкту k від розташування підрозділу на  дорозі між об’єктами i та j. Якщо підрозділ розташовано на відстані x від об’єкту i, то треба обрати коротший із шляхів, один з яких проходить через i, а інший через j, і відстань буде y_ijk(x) = min {d_ik+x, d_ij+d_kj-x}, де d_ab – відстань між об’єктами a і b.