Завдання ІІІ (обласного) етапу Всеукраїнської олімпіади з інформатики 2017-2018 н.р.

3 лютого 2018 р.

Задача Math2018. Легендарнi числа - то є такi числа, якi можна подати у виглядi a^b ·b^a, де a та b - різні цiлi числа. Напишіть програму, яка перевіряє число  на «легендарність».

Технічні умови. Програма Math2018 читає з пристрою стандартного введення  цiле число N, що не перевищує 10⁶ за абсолютною величиною - число для перевiрки. Програма виводить на пристрій стандартного виведення два рiзних цiлих числа a та b через пропуск, які за модулем не повиннi перевищувати 10⁶. Якщо число не може бути подане в заданому вигляді, вивести 0 0.

Приклади

Пояснення до прикладiв: У першому варіанті маємо 72 = 2³·3². Звернiть увагу, що можна було вивести пару «3 2» замiсть пари «2 3».

У другому варiантi 30375 = 3⁵ ·5³.

Задача Numberone.  Коли на уроці сумно, учасник обласної олімпіади з інформатики Василько грає в таку гру. Він просить сусіда за партою написати йому на чернетці  цiле невiд’ємне число, а  далі діє так:  розрiзає число на окремi цифри, після чого ставить між парами сусідніх цифр або «+», або ж «*» таким чином, аби в результаті виконання дій отримати  мiнiмальне число.  Але Васильку набридло це робити на папері і він написав програму, яка завжди розставляла знаки так, аби отримане у наслідок виконаних дій число було мінімальне. Зробіть так і ви.

Технічні умови. Програма Numberone читає з пристрою стандартного введення цiле невiд’ємне число N(N ≤ 20000). Програма виводить на пристрій стандартного виведення   єдине число - відповідь на задачу.

Пояснення до прикладів: Усього чотири варіанти для контрольного прикладу №1:

3 · 2 · 8 = 48,  3 · 2+8 = 14,  3+2 · 8 = 19,  3+2+8 = 13

Звісно, що у останньому варіанті результуюче число виявляється мiнiмальним. Для контрольного прикладу №2 оптимальним є варіант 2 · 2+8. У третьому прикладі оптимальним є 1 · 2.

Приклади

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

Системний адміністратор  має органайзер (спеціальний жолоб, в який вкладаються кабелі), у якому вони йдуть згори донизу, якимось чином, можливо, переплітаючись. Органайзер має комірки - N по ширині та M по довжині органайзера. Комірки зроблено так, що кабель може з неї йти до  сусідних, але через жодну комірку  їх не може пройти більше двох. Системному адміністратору необхідно віднайти для кожного «вихідного» кабеля його номер серед «вхідних» («вихідні» це ті, які розташовані внизу, «вхiдні» - кабелі вгорі). Кабелі нумеруємо злiва направо.

Технічні умови. Програма Manywires читає з пристрою стандартного введення  у першому рядку число N - кількість комірок в довжину, а в другому M – кількість комірок в ширину  (2 ≤ N,M ≤ 200). Далi N рядкiв, в кожному з яких по M символiв, що задають «мапу» кабелів.

Символ «.» означає, що в данiй комiрцi жоден кабель не проходить. Символ «/» означає, що дрiт йде вниз i лiворуч, вiдповiдно, «\» - вниз і праворуч, символи «(» та «)» задають «перегин» дроту, коли вiн змiнює напрямок. Крiм того, ще iснує символ «X», що означає перетин кабелів у поточнiй комiрцi. Гарантується, що в першому i останньому рядках схеми органайзера вiдсутнi символи «X», «(», «)». Програма виводить на пристрій стандартного виведення   номер «входу», що  відповідає вихідному кабелю в даній позиції.

Приклад

Задача Friends. Троє колишніх переможців олімпіад з інформатики  вирiшили створити стартап. Сучасних iнвесторiв складно зацiкавити нейронними мережами чи блокчейном, тож замiсть цього хлопцi вирiшили створити аеропорт для квадрокоптерiв. Для цього молодики знайшли дiлянку  розмiром N на N метрiв. Студенти живуть лише на стипендiю, тож змушенi купувати землю по одному квадратному метру щомiсяця. Щоб максимально ефективно використовувати бюджет, хлопцi скористались останнiми розробками в нейронних мережах та передбачили цiни на найближчий час. Пiсля цього вони склали графiк закупiвлi землi.  Усiм вiдомо, що найголовнiша частина аєропорту — це злiтна смуга. Мiжнароднi стандарти вимагають, щоб злiтна смуга мала форму прямокутника, що має розмiр A на B. Для полегшення роботи авiадиспетчера злiтна смуга буде розмiщена паралельно однiй з сторiн.  Як тiльки буде побудована злiтна смуга, можна починати наступний раунд iнвестицiй i запрошувати мiжнародних експертiв. Їх цiкавить наступне питання: через скiльки мiсяцiв буде куплена земельна дiлянка, достатня для побудови злiтньої смуги. Звiсно, що будувати студентам дозволено лише на куплених дiлянках. Писати нейроннi мережi хлопцi навчились, а як розв’язувати алгоритмiчнi задачi   вже підзабули (бізнес!), тому й просять вас допомогти.

Технічні умови. Програма Friends читає  з пристрою стандартного введення в першому рядку числа N,A,B(1 ≤ N ≤ 1000,1 ≤ A,B ≤ N - розмiри. В наступних N рядках рiвно по N рiзних натуральних чисел, кожне не перевищує N². Кожне число задає номер мiсяця, у якому буде придбана вiдповiдна дiлянка землi.

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

Приклад