Завдання 4 (фінального Real-time) туру Всеукраїнської Інтернет-олімпіади NetOI-2010

12 лютого 2011 року   

Задача Painting

Васильку Пупкіну, герою NetOI, на день народження подарували набір кольорових олівців (всі олівці в наборі різних кольорів). Василько накреслив прямокутну таблицю, що містить m рядків клітинок по n клітинок в кожному рядку, і став зафарбовувати клітинки таблиці кольоровими олівцями – кожну клітинку якимось одним кольором. Коли всі клітинки були зафарбовані, він помітив, що :

-           для зафарбовування клітинок будь-якого з m рядків  використовувалися всі наявні в наборі олівці, кожен по одному разу;

-           серед m рядків не було двох, зафарбованих однаково (два рядки вважаються зафарбованими однаково, якщо всі клітинки з однаковими номерами цих рядків зафарбовані однаковими кольорами);

-           якби кількість рядків була на 1 більшою (тобто, m+1), то обов‘язково знайшлися б два рядки, зафарбованих однаково.

Знаючи, що кожен з олівців Василько використав рівно m разів, знайдіть кількість олівців в наборі.

Технічні умови. Програма Painting зобов’язана прочитати з клавіатури  натуральне число k – кількість цифр числа   m (1<= k <1000), а далі – k   цифр числа m, записаних через пропуск (цифри записані зліва направо, починаючи з найстаршого розряду).

Програма виводить на екран єдине число – кількість олівців у наборі.

Приклад

Введення:   2 2 4

Виведення: 4

Задача Crystal

 Юний хімік Ліза вирощує кристали. На прямокутну пластину з поживним середовищем вона капає зародковими кристалами, які згодом ростуть і заповнюють усю пластину. У зв'язку з постійним недосипанням та мікроскопічними розмірами пластини  вкраплення виходять розкиданими випадково по пластині і інколи кристали розростаються досить довго. Ліза вирішила визначити, за який час пластина повністю покриється кристалами, якщо відомі її розміри і місця вкраплення. З підручника з координаційної хімії відомо, що за 1 хвилину кристал розростається на сусідні клітинки, з якими він має спільне ребро.

Технічні умови.  Програма Crystal читає з клавіатури числа H та W - кількість рядків і стовпців пластини,  K - кількість вкраплень, які зробила Ліза, після чого K пар чисел  R та C - відповідно рядок і стовпець вкраплення. Усі числа цілі та задовольняють обмеженням:

1 <= H, W <= 500;  0 <= K <= 50; 1 <= R <= H; 1 <= C <= W.    Програма виводить на екран  єдине число - мінімальну кількість хвилин, через яку вся пластина буде покрита кристалами, а якщо це ніколи не відбудеться, то вивести  - 1

Задача ABACABA 

Абацабівська мова складається з усіх тих послідовностей літер  A, B, C,  (звичайно, латиницею), у яких одна й та сама літера повторюється не більше двох разів підряд. Усі ці слова занумеровані за правилами: спочатку всі однобуквенні, потім усі двобуквенні і т. д., а серед слів з однаковою кількістю букв — за словниковим порядком, тобто спочатку порівнюються перші букви; якщо вони однакові, то порівнюються другі, і т. д. Зокрема, словами абацабівської мови з 1‑го по 47‑е є A, B, C, AA, AB, AC, BA, BB, BC, CA, CB, CC, AAB, AAC, ABA, ABB, ABC, ACA, ACB, ACC, BAA, BAB, BAC, BBA, BBC, BCA, BCB, BCC, CAA, CAB, CAC, CBA, CBB, CBC, CCA, CCB, AABA, AABB, AABC, AACA, AACB, AACC, ABAA, ABAB, ABAC, ABBA, ABBC. Напишіть програму, яка виконуватиме перетворення між буквенним та порядковим поданням слів абацабівської мови.

Технічні умови Програма ABACABA читає з клавіатури або ціле строго додатне число, або послідовність літер, що утворює слово абацабівської мови. Програма повинна вивести у першому випадку слово абацабівської мови, що має такий номер, а у другому — порядковий номер введеного слова.  Достатньо, щоб програма вміла працювати зі словами, номери яких не перевищують 10¹⁸.

Програма повинна виводити на екран лише відповідь, без будь-яких зайвих символів, в т. ч. й пробілів. Числа повинні починатися з ненульової цифри.

 Задача Oddsum

Дана прямокутна таблиця розміром N рядків на M стовпчиків; у кожній клітинці записане ціле число. По ній потрібно пройти згори донизу, розпочавши шлях у якій-небудь клітинці верхнього рядка, далі щоразу переходячи у одну з «нижньо-сусідніх» клітинок (іншими словами, з клітинки з номером (i, j) можна перейти або до (i+1, j–1), або до (i+1, j), або до (i+1, j+1); у випадку j=M можливі лише 1-й та 2-й з трьох перелічених варіантів, у випадку j=1 — лише 2-й та 3-й) і закінчивши шлях у якій-небудь клітинці нижнього рядка. Напишіть програму, яка знаходитиме максимально можливу непарну суму значень пройдених клітинок (серед усіх допустимих шляхів).При цьому окремі числа можуть бути парними; непарною має вийти остаточна сума.

Технічні умови Програма Oddsum читає з клавіатури   N та M — кількість рядків та кількість стовпчиків (2≤M≤500, 2≤N≤500), а далі -  N рядків з M розділених пропусками цілих чисел (кожне не перевищує за модулем 1 000 000) — значення клітинок таблиці. Програма виводить на екран єдине ціле число — знайдену максимально можливу непарну суму. Якщо сформувати непарну суму взагалі неможливо, програма повинна замість відповіді вивести -2.

Приклад

Примітка до прикладу

Найкращий (з сумою 39) допустимий шлях проходить через клітинки зі значеннями 15, 9, 9, 6. Шлях, що проходить через клітинки зі значеннями 15, 9, 9, 9, має ще більшу суму  42, але для даної  задачі він не допустимий, бо сума 42 парна.

  Задача Efractions

Математики стародавнього Єгипту не знали дробів у сучасному розумінні, але вміли подавати нецілі числа як суму дробів вигляду 1/k, причому всі k в цій сумі мали бути різними. Наприклад, сучасне поняття 2/5 виражалося як «одна третя та одна п’ятнадцята» (справді, 1/3 + 1/15 = 5/15 + 1/15 = 6/15 = 2/5).

Математики Нового часу довели, що будь-який правильний звичайний дріб можна подати у єгипетському поданні (як суму дробів вигляду 1/k), причому це подання не єдине. Напишіть програму, яка перетворюватиме правильний звичайний дріб до єгипетського подання із мінімальною кількістю доданків. Якщо є різні єгипетські подання, що мають однакову мінімальну кількість доданків, програма має знаходити будь-який один з них.

Технічні умови. Програма Efractions читає з клавіатури два натуральні числа n та m (1≤n<m≤1000) — чисельник та знаменник правильного звичайного дробу. Програма виводить на екран послідовність різних натуральних чисел, розділених пропусками — сукупність знаменників у єгипетському поданні цього дробу.

Приклад 1

Введення

2 5

Виведення

3 15

Приклад 2

Введення

732 733

Виведення

2 5 8 9 16 65970 105552

Завдання підготували В.Бондар, Б.Дібров, Г.Непомнящий, Ю.Пасіхов, С.Петров, І.Порубльов