Задача тижня 02.04.12 – 08.04.12

Крадіжка у музеї

З Харківського художнього музею викрали картину Іллі Рєпіна «Казак у степу». Слідчі вирішили, що крадіжка відбулася підчас найбільшого заповнення музею відвідувачами. Камери відеоспостереження, встановлені в музеї, реєструють перебування кожного відвідувача від моменту його входу до моменту виходу з музею. Слідчім необхідно з’ясувати, в який проміжок часу в музеї знаходилась максимальна кількість відвідувачів.

1. Створіть програму, що визначає проміжок часу, впродовж якого в музеї одночасно знаходилась максимальна кількість відвідувачів.

Вхідні дані (вводяться з файлу або з клавіатури)

Значення N – кількість зафіксованих відвідувачів музею протягом доби.
Значення H[i] (i = 1, 2, …, N) – N рядків, які містять у довільному порядку терміни перебування відвідувачів у музеї в форматі «ГГ:ХХ-ГГ:ХХ» (00:00 ≤ ГГ:ХХ ≤ 23:59).

Вихідні дані (виводяться на екран)

Значення K – максимальна кількість відвідувачів, що одночасно знаходились у музеї.

Значення «ГГ:ХХ-ГГ:ХХ» – термін, упродовж якого спостерігалась максимальна кількість відвідувачів. Якщо таких термінів декілька, вивести всі у хронологічному порядку.

2. Заповніть тестову таблицю за результатами роботи програми:

Аналіз розв’язку задачі «Крадіжка в музеї»

Для кращого розуміння розв’язку задачі представимо її рішення у графічній формі. Зобразимо вхідні дані в елементах теорії множин. Зокрема графічне тлумачення пошуку рішення для прикладу з тестової таблиці

матиме вигляд

На малюнку зображена сукупність N множин на часовій осі, межі i – множини відповідають значенням H[i]. Максимальна кількість відвідувачів і відповідні часові межі відповідають заштрихованій області на малюнку.

Аналіз надісланих учасниками рішень показав, що більшість не звернули увагу на той факт, що проміжок часу, коли у музеї налічувалася максимальна кількість відвідувачів, може бути меншим за хвилину. Саме тому, якщо представити в графічному вигляді рішення до тестів №4, 5, 6, то замість заштрихованої області отримаємо лише «крапку», що й буде вказувати на те, що проміжок часу не вийшов за межі певної хвилини.

Алгоритм розв’язку задачі складається послідовності наступних кроків:

1. Насамперед змінимо формат значень часу перебування у музеї «ГГ:ХХ» перевівши час в хвилини і отримавши значення часу у вигляді цілого числа.

2. Сформуємо масив з елементами значень часу входу і масив зі значеннями часу виходу відвідувачів.

3. Допишемо значення масиву часу виходу відвідувачів з музею в кінець масиву часу входу, взявши їх зі знаком мінус.

4. Виконаємо сортування сформованого на попередньому кроці масиву за зростанням абсолютної величини його значень. В результаті моменти часу входу і виходу розташуються в хронологічному порядку, водночас, значення для часу входу буде додатнім, а для часу виходу – від’ємним.

5. Введемо зміну цілого типу i – лічильник підрахунку відвідувачів.

Рухаючись по масиву отриманому на другому кроці введемо умову:

якщо елемент від’ємний, то i = i -1

6. Максимальне значення лічильника буде дорівнювати максимальній кількості відвідувачів.

7. Для знаходження інтервалу часу з найбільшою кількістю відвідувачів, необхідно при заміні поточного найбільшого значення лічильника на ще більше запам’ятовувати час входу останнього врахованого відвідувача, тобто значення i-го елемента масива – воно визначає початок шуканого проміжку часу. Як тільки у процесі подальшого перегляду масиву поточне найбільше значення i зменшиться, фіксуємо відповідне значення i-го елемента – кінець проміжку часу.

Таблиця за результатами роботи програми:

Журі оцінило надіслані розв’язки наступним чином: