Вітаю Вас, Гость

Задача А. "Залізниця" SIV

Бали за задачу: 25
Обмеження часу: 1 с
Обмеження пам'яті: 64 M

   В деякій країні K дуже незвичайна залізна дорога: вона є орієнтованим графом, що не містить циклів, причому з кожного міста існує лише один шлях в деяке інше, або не існує жодного(кінцева).  Турист Василь планує провести відпустку в країні K. Він хоче прилетіти літаком в деяке місто та відвідати якомога більше міст цієї країни, користуючись потягом. Допоможіть Василю підрахувати найбільшу кількість міст, які зможе відвідати Василь.

   Вхідні дані:
   Перший рядок вхідного потоку містить одне натуральне число N – кількість міст в країні (1 ≤ N ≤ 100). Наступні N рядків містять цілі числа A[z] (1 ≤ A[z] ≤ n): дорога від міста z до міста A[z], або 0, якщо це кінцева.

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

   Приклади

Вхідні дані   Результат роботи
3
0
1
2
3


 
3
0
1
1
2


 

 

Задача В. "Розкладка клавіатури" SOM

Бали за задачу: 25
Обмеження часу: 1 с
Обмеження пам'яті: 64 M
Ім'я файлу, який містить вхідні дані: qwerty.in
Ім'я вихідного файлу: qwerty.out

   Василько почав вивчати інформатику та на одному з уроків він познайомився з клавіатурою. При спробі ввести текст Василько дуже здивувався, що алфавітні клавіші розташовуються у якомусь дивному порядку. Юний інформатик поцікавився у Вікіпедії та знайшов таку:
   "В перших друкарських машинках Кристофера Шоулза, розроблених у 1867-1871 роках, було два рядки клавіш, що розташовувалися в алфавітному порядку. Таке положення літер приводило до частого зчеплення важелів між собою. Для вирішення цієї проблеми КристоферШоулз почав експерементувати з розкладками. Першою популярною друкарською машинкою стала Ремінгтон 1, на якій була встановлена саме QWERTY. Цілих п'ять років ця машинка була єдиною на ринку, тому до розкладки встигли звикнути покупці.
   У 1888 році для машинки Ремінгтон 2 Франком Макгуріном був винайдений сліпий метод друку, що допомогло популяризації даної розкладки.
   Нині QWERTY — найпопулярніша у світі розкладка."

   Після такого переконливого пояснення юний дослідник вирішив скласти свою розкладку та придумав такий принцип: у центрі клавіатури повинні розташовуватися клавіші, які найчастіше зустрічаються, а далі навколо них прямо пропорційно кількості повторів у тексті. Таким чином розкладка Василька має таку схему:

26    21    17    9    11    12    10    18    22    24
    25    19     5     1     3     4      2      6     20           
23    15    7    13    14     8     16    
   

   Зрозуміло, що в залежності від тексту, розкладка може змінюватися. Наша задача на основі заданого тексту, в якому присутні літери латиниці скласти розкладку за принципом Василька.
   Якщо деякі літери зустрілися у тексті однакову кількість разів, в розкладці Василька розташовуються тоді за порядком зростання латинської абетки. Наприклад, літери U та D зустрілися 5 разів. В розкладці Василька літера D буде попереду літери U.
   Назва розкладки клавіатури визначається початковими літерами першого рядка. Для прикладу будемо використовувати початкові 6 літер у першому рядку розкладки Василька.

   Вхідні дані:
   У вхідному файлі qwerty.in знаходиться текст довжина якого не перевищує 3000 символів.

   Вихідні дані:
   У вихідний файл qwerty.out вивести великими літерами назву отриманої розкладки за принципом Василька.

   Приклади

Вхідні дані   Результат роботи
A a    B b    C c    D d    E e     F f     G g    H h    I i     J j    
          K k    L l    M m    N n    O o    P p   Q q    R r   S s    
          T t    U u    V v    W w   X x    Y y    Z z
ZUQIKL

 

 

Задача С. "Передвиборча агітація" SOM

Бали за задачу: 25
Обмеження часу: 1 с
Обмеження пам'яті: 64 M
Ім'я файлу, який містить вхідні дані: piar.in
Ім'я вихідного файлу: piar.out

   На телеканал звертаються кандидати у депутати з приводу розміщення власної політичної реклами. Телеканал має строгий графік телепередач, та відведені проміжки часу на рекламу. У кожного кандидата є власний ролик, тривалість ролику не перевищує 1 хв. У рекламному проміжку крутять ролики по черзі, поки не завершиться проміжок на рекламу. Черговість роликів визначається порядком звернення депутатів до телеканалу. Якщо якийсь ролик в даному проміжку не встигає прокрутитися, тоді він першим прокручується у наступному проміжку. Якщо залишок часу після прокручування роликів замалий для наступного ролику, телеканал заповнює його власною рекламою. Складіть програму, яка за заданими часовими проміжками, чергою і тривалістю роликів, вартістю 1 секунди ефірного часу розраховує для кожного кандидата суму за політичну рекламу на телеканалі.

   Вхідні дані:
   У вхідному файлі piar.in в першому рядку вказано три цілих числа k-кількість кандидатів, r-кількість часових проміжків на рекламу, v - вартість одної секунди ефірного часу 0<k,r<=100, 0<v<=1000. У другому рядку відповідно до черги звернення кандидатів до телеканалу записано через пропуск k цілих чисел, тривалість роликів у секундах, у наступних r рядкахзаписано часові рекламні проміжки у форматі HH:MM-HH:MM

   Вихідні дані:
   У вихідний файл piar.out виведіть через пропуск вартість ефірного часу для кожногокандидата, враховуючи їх черговість звернення до телеканалу.

   Приклади

Вхідні дані   Результат роботи
3 3 100
17 20 23
07:15-07:17
07:59-08:02
08:30-08:35
17000 20000 23000



 

 

Задача D. "Велика чистка" POP

Бали за задачу: 25
Обмеження часу: 1 с
Обмеження пам'яті: 64 M
Ім'я файлу, який містить вхідні дані: clear.dat
Ім'я вихідного файлу: clear.dat

   Якось юний програміст Петько Паскаленко черговий раз прибирав робочий стіл свого комп’ютера,видаляючи з нього зайві об’єкти. Об’єкти були розміщені правильними рядками і стовпцями. Він виділяв мишею прямокутну групу об’єктів, після чого натискав Delete і об’єкти зникали. Деякі об’єкти слід було залишити, тому Петько задумався: чи не можна зменшити спрацювання клавіатури (зокрема, клавіші Delete), якось оптимізувавши цей процес?
   Допоможіть йому скласти програму, яка, отримавши інформацію про розміщення потрібних і зайвих об’єктів на екрані, підрахує найменшу можливу кількість операцій видалення.

   Вхідні дані:
   У першому рядку текстового файлу clear.dat записані два цілі числа D і S (2≤D≤50, 2≤S≤50), відокремлені пропуском: кількість місць для об’єктів, відповідно, по довжині і ширині екрану. У наступних S рядках розміщені по D цілих чисел (також відокремлених пропусками), які показують стан відповідного місця на екрані: 0 – зайвий об’єкт, 1 – потрібний об’єкт, 2 – порожнє місце.

   Вихідні дані:
   У єдиний рядок текстового файлу clear.sol вивести ціле число N – найменшу можливу кількість операцій видалення.

   Приклади

Вхідні дані   Результат роботи
4 4
2 0 1 2
0 1 2 2
1 0 0 1
0 0 0 2
4



 

 

Задача Е. "Розкладання числа" ZVV

Бали за задачу: 25
Обмеження часу: 3 с
Обмеження пам'яті: 64 M

   Будь-яке ціле додатне число N  можна записати у вигляді суми двох або більше цілих додатних чисел, кожне з яких не більше попереднього.
   Наприклад, число 5 можна записати в такому вигляді шістьма способами: 4 + 1, 3 + 2, 3 + 1 + 1, 2 + 2 + 1, 2 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1.
   Потрібно визначити, скільки існує різних способів розкладання заданого числа N на суму, що складається з k  доданків.

   Вхідні дані:
   Стандартний вхідний потік містить числа N, k(2 ≤ N ≤ 80, 2 ≤ k ≤ N). Числа розділяються пропуском.

   Вихідні дані:
   У стандартний вихідний потік вивести кількість

   Приклади

Вхідні дані   Результат роботи
5 2 2