asyan.org
добавить свой файл
1

Олімпіада школярів з програмування

    Завдання A. Свята

Ім'я вхідного файлу:

а.in

Ім'я вихідного файлу:

а.out

Максимальний час роботи на одному тесті:

1 секунда

Максимальний об'єм використовуваної пам'яті:

64 мегабайти

Максимальна оцінка за завдання:

80 балів







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

Залежно від того, на який день тижня доводиться 1 січня, кількість неробочих днів, які йдуть підряд, може мінятися.

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

Формат вхідних даних

У вхідному файлі записана однина K (1K50).

Формат вихідних даних

У вихідний файл потрібно записати однину — найбільшу кількість неробочих днів, що йдуть підряд.

Приклади

а.in

а.out

2

4

10

16




    Завдання B. Розфарбовування плиток

Ім'я вхідного файлу:

b.in

Ім'я вихідного файлу:

b.out

Максимальний час роботи на одному тесті:

1 секунда

Максимальний об'єм використовуваної пам'яті:

64 мегабайти

Максимальна оцінка за завдання:

100 балів







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

Формат вхідних даних

У першому рядку вхідного файлу записано через пропуск два числа: N — кількість плиток в одному ряду (1N натуральних чисел, що позначають номери квітів фарб, в які колись фарбували відповідні плитки даного горизонтального ряду. Номери квітів — натуральні числа в діапазоні від 1 до K.

Формат вихідних даних

У вихідний файл виведіть два числа: L — яке мінімальне число разів доведеться занурювати кисть у відро з фарбою, і номер фарби З, в яку в результаті опиняться перефарбовані всі плитки двору. Якщо таких фарб може бути декілька, то виведіть номер будь-якій з них.

Якщо перефарбувати всі плитки, слідуючи придуманим Томом правилам, не можна, виведіть двічі число 0.

Приклади

b.in

b.out

3 2

1 2 1

2 1 1

1 2 2

4 1

2 1

1 1

1 1

2 1




    Завдання C. Маскарад

Ім'я вхідного файлу:

з.in

Ім'я вихідного файлу:

з.out

Максимальний час роботи на одному тесті:

1 секунда

Максимальний об'єм використовуваної пам'яті:

64 мегабайти

Максимальна оцінка за завдання:

120 балів







З нагоди введення великих новорічних канікул влаштовується великий святковий бал-маскарад. До свята залишилися лічені дні, тому терміново потрібні костюми для учасників. Для пошивки костюмів потрібний L метрів тканини. Тканина продається в N магазинах, в яких надаються знижки оптовим покупцям. У магазинах можна купити тільки ціле число метрів тканини. Реклама магазина номер i свідчить "Ми з радістю продамо Вам метр тканини за Pi бурлей, проте якщо Ви купите не менше Ri метрів, то отримаєте прекрасну знижку — кожен куплений метр обійдеться Вам всього в Qi бурлей". Щоб утілити в життя гасло "економіка країни повинна бути економною", уряд вирішив витратити на закупівлю тканини для костюмів мінімальна кількість бурлей з державної казни. При цьому тканині можна купити більше, ніж потрібно, якщо так виявиться дешевшим. Відповідальний за покупку тканини подзвонив в кожен магазин і дізнався, що:

1) реклама кожного магазина містить правдиву інформацію про ціни і знижки;

2) магазин номер i готовий продати йому не більш Fi метрів тканини.

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

Формат вхідних даних

У першому рядку вхідного файлу записано два цілі числа N і L (1N100, 0L100). У кожній з подальших N рядків знаходиться опис магазина номер i — 4 цілих числа Pi, Ri, Qi, Fi (1QiPi1000, 1Ri100, 0Fi100).

Формат вихідних даних

Перший рядок вихідного файлу повинен містити однину — мінімальну необхідну кількість бурлей.

У другому рядку виведіть N чисел, розділених пропусками, де i-ое число визначає кількість метрів тканини, яке потрібно купити в i-ом магазині. Якщо в i-ом магазині тканина купуватися не буде, то на i-ом місці повинне стояти число 0. Якщо варіантів покупки декілька, виведіть будь-який з них.

Якщо тканині в магазинах недостатньо для пошивки костюмів, вихідний файл повинен містити однину -1.

Приклади

з.in

з.out

2 14

7 9 6 10

7 8 6 10

88

10 4

1 20

1 1 1 1

-1






Сторінка из