http://www.e-olimp.com/ua/problems/972

Сортування часу

Технічні умови

Інформація про задачу

Ліміт часу: 1 секунда
Ліміт пам`яті: 64 MB
Бали за пройдений тест: 1.96078
Складність: 8% 214/232
Класифікація: Сортування та послідовності

Приклад

4
10 20 30
7 30 00
23 59 59
13 30 30

7 30 0
10 20 30
13 30 30
23 59 59

10-11 класи

1. Приготування яєць. Петя любить їсти варені яйця. Для того, щоб приготувати яйце некруто потрібно варити його Х хвилин. Щоб приготувати яйце круто, потрібно спочатку приготувати його некруто, а потім варити ще Y хвилин. Петя любить їсти яйце, коли воно наполовину приготовлено круто, тобто коли яйце спочатку приготовлено некруто, а потім ще пройшла половина часу, необхідного для того, щоб це яйце стало приготованим круто. Знайдіть скільки хвилин Петі потрібно варити яйце.

У єдиному рядку задаються два цілих числа Х і У (1 ≤ Х, У <10¹⁸).

Виведіть одне число - час у хвилинах, необхідне для приготування наполовину крутого яйця.

2. Годинник. Є свідчення N годин. Відомо, що До з них показують неправильний час, показання інших - вірні. Потрібно написати програму для визначення точного часу.

У першому рядку задається два цілих числа N і К (0 <К GNG 1000). У кожному з наступних N рядків задаються по два числа - кількість годин (від 0 до 23) і хвилин (від 0 до 59), які показують відповідні години.

Виведіть два числа, що визначають правильний час у годинах і хвилинах. Якщо неможливе можна однозначно визначити точний час, виведіть одне число -1.

З. Транспортна задача. У країні Інформландія є всього два види міського транспорту: метро і автобус. Грошова одиниця в Інформландіі - природно, біт. Одна поїздка на метро коштує 3 біта, а на автобусі - 2 біти. При цьому можна купити місячний проїзний на необмежену кількість поїздок: на метро - 40 бітів, на автобус - 30 бітів, на автобус і метро - 60 бітів. Яку найменшу суму потрібно витратити на проїзд у місяць жителю Інформландіі, якщо в тому місяці належить зробити х поїздок на метро і у на автобусі.

У єдиному рядку задаються два цілих числа х і у (0 <х, у <100).

Виведіть найменшу суму в бітах, яка буде потрібно жителю на проїзд.

4. Морозиво. Є N морозив. Дитина з'їдає будь морозиво за 1 хвилину. Для кожного морозива відомо, через скільки хвилин воно розтане. Потрібно визначити мінімальну кількість дітей, які можуть з'їсти ці всі ці морозива так, щоб ні одне з них не встигло розтанути. Кожну хвилину одна дитина може їсти лише одне морозиво, і кожне морозиво може їсти лише одна дитина.

У першому рядку задано ціле число N (1 ≤N ≤ 10⁵). Другий рядок містить N натуральних чисел, що не перевищують 10⁶, кожне з яких визначає час, через який розтане відповідне морозиво.

Виведіть одне число - мінімальну кількість дітей, які зможуть з'їсти все морожені, не допустивши їх танення.

5. Ліфт. У будівлі з N поверхами поставили новий ліфт, який необхідно перевірити ліфтерові. За посадової інструкції перевірка працездатності ліфта полягає в тому, щоб зробити принаймні по одному разу поїздки між кожною парою різних поверхів (при цьому поїздки від одного поверху до іншого і у зворотний бік вважаються різними). Спочатку ліфт знаходиться на першому поверсі. Далі ліфтер послідовно натискає кнопки на панелі ліфта, переміщаючи ліфт на відповідні кнопкам поверхи. Працівник хоче впоратися з перевіркою якомога швидше, тому просить вас написати програму для знаходження послідовності натискань на кнопки мінімальної довжини.

У єдиному рядку задано ціле число N (1≤N≤1000).

Виведіть послідовність натискань для повної перевірки працездатності ліфта мінімальної довжини. Якщо існує декілька послідовностей, що задовольняють умові, виведіть будь-яку з них.

Зауваження. При виконанні наведеної в прикладі послідовності натискань ліфт здійснить такі поїздки: {(1 - + 3), (3 - + 2), (2 - + 3), (3 - + 1), (1 - + 2), (2 - + 1)}, що є достатнім для перевірки, оскільки містить в собі всі можливі поїздки.