Завдання особистої олімпіади з ІТ-2018

Числа Сміта (Smith)  (юніори)

Поняття числа Смита було введено Альбертом Віланскі з Університету Лехай у 1982 році. Переглядаючи свою телефонну книжку, математик звернув увагу на те, що телефонний номер його зятя Гарольда Сміта (493-7775) має таку цікаву властивість, що сума його цифр дорівнювала сумі цифр усіх його простих співмножників. Число 4937775 розкладається на прості співмножники таким чином: 4937775=3×5×5×65837. Сума цифр телефонного номера дорівнює 4+9+3+7+7+7+5=42 і сума цифр його розкладання на прості множники також дорівнює 3+5+5+6+5+8+3+7=42. Віланскі назвав такий тип чисел на ім’я свого зятя. Оскільки таку властивість мають всі прості числа, Віланскі не включив їх до означення. Допоможіть Альберту знайти ще числа Сміта. Для кожного числа із заданого набору знайдіть мінімальне число Сміта, що його перевищує.

Формат введення-виведення: 

Програма Smith зчитує з клавіатури (стандартного пристрою введення) натуральне число N (1≤N≤10) – кількість чисел у наборі, а також N натуральних чисел a_i (1≤ a_i <2³¹).  Програма Smith виводить на екран (стандартний пристрій виведення) N знайдених чисел через пробіл.

Приклад вхідних та вихідних даних

Введення                           Виведення

2 4937774 234                   4937775 265

Обнулення масиву (Zeroing)  (юніори+ старша ліга)

Є масив, що складається з N чисел. За один крок дозволяється зменшити на 1 кілька (можливо один) підряд рівних елементів. Мета – зробити всі елементи рівними нулю. За яку мінімальну кількість кроків це може бути зроблено? 

Формат введення-виведення:  Програма Zeroing зчитує з клавіатури (стандартного пристрою введення) натуральне число N (1≤N≤2∙10⁵) – кількість чисел у масиві, а з наступного рядка N невід’ємних цілих чисел, елементів масиву, кожне з яких не перевищує 2∙10⁹. Програма Zeroing виводить на екран (стандартний пристрій виведення) єдине число – шукану кількість кроків.

Приклад вхідних та вихідних даних

Введення 1            Виведення 1

3                                 4

3 4 1

Введення 2            Виведення 2

3                                 6

3 1 4

Кооперація (Coop)  (юніори+ старша ліга)

Гноми-велетні знамениті своїми гігантськими розмірами та любов'ю до золота. В одному з поселень гномів існує N пар гномів, причому в i-ій (1 ≤ i ≤ N) парі як чоловік-гном, так і жінка-гном мають зріст рівно i. Крім того, кремезні чоловіки-гноми зазвичай виступають у якості опори, у той час як тендітні жінки-гноми вправно орудують киркою. Геологічна розвідка виявила неподалік селища гномів вертикальну нескінченно високу скелю. Гноми вирішили, що там з великою вірогідністю буде золото, тож домовилися вранці вирушити на полювання на нього. Щоправда, дійшовши до скелі, гноми виявили проблему: K сімей не прийшли на зустріч. Гноми збираються довбати скелю в наступний спосіб: нехай якийсь чоловік-гном зросту A виступає опорою для якоїсь жінки-гнома зросту B. Разом цей тандем здатний довбати скелю лише на висоті A + B. Для кожної висоти обирається підходящий тандем, причому будь-який присутній гном може виступати (в різні моменти часу) у складі різних тандемів. Тепер гномів цікавить, скільки ж існує досяжних висот. Іншими словами, для скількох висот знайдеться підходящий тандем?

Формат введення-виведення: Програма Coop спочатку зчитує з клавіатури (стандартного пристрою введення) два цілих числа N(1 ≤ N ≤ 2·10⁹) та K (1 ≤ K ≤ min{N, 10000}) – кількість пар гномів у поселенні та кількість відсутніх на видобутку сімей гномів.Потім зчитується рівно K різних невід’ємних цілих чисел – номери сімей, у довільному порядку, що не прийшли на видобуток. Кожне число не перевищує N.Програма Coop виводить на клавіатуру (стандартний пристрій виведення) єдине ціле число – кількість досяжних висот.

Система оцінки.  30% балів припадає на тести, в яких N, K ≤ min{N, 1000}.  Ще 40% балів припадає на тести, в яких N ≤ 10⁹, K ≤ min{N, 500}.

Приклад вхідних та вихідних даних:

Введення 1                        Виведення 1

6 2                   9

3 6

Введення 2                        Виведення 2

5 3                   3

2 3 4

Введення 3                        Виведення 3

10 4                 15

2 3 4 5

Багатокутники (Numconv)  (юніори+ старша ліга)

Задана клітчаста сітка. Скільки різних опуклих багатокутників може бути на ній намальовано, якщо всі вершини повинні лежати у вузлах сітки, а сторони бути або горизонтальними, або вертикальними, або діагональними (під кутом 45 градусів)? Шириною сітки назвемо кількість вузлів у кожному її ряду, а висотою – кількість вузлів у кожному її стовпчику. Багатокутники, які потрібно знайти, повинні мати такі властивості:

- їх вершини повинні лежати у вузлах решітки;

- всі сторони горизонтальні, вертикальні або діагональні (45 градусів);

- багатокутник опуклий.

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

Формат введення-виведення: Програма Numconv зчитує з клавіатури (стандартного пристрою введення) два натуральні числа a та b (2≤a,b≤100) – ширину та висоту сітки. Програма Numconv виводить на екран (стандартний пристрій виведення) єдине число – кількість можливих багатокутників.

Приклад вхідних та вихідних даних

Введення 1            Виведення 1

3 2                              19

Введення 2            Виведення 2

2 2                              5

Вікторина (Quiz) (старша ліга)

Гноми-велетні вирішили взяти участь у чемпіонаті гри «Що? Де? Коли?». Чемпіонат складається з t турів. Кожен тур містить деяку кількість питань. Серія питань – це підпослідовність питань одного туру від l-ого до r-ого включно, причому l ≤ r і підпослідовність неперервна (беруться до уваги всі підряд питання від l-ого до r-ого). Гноми будуть вважати серію питань вдалою, якщо вони дадуть відповіді не менш, ніж на q відсотків питань з цієї серії. Для підняття настрою команди, знайдіть для кожного туру кількість вдалих серій.

Формат введення-виведення:

Програма Quiz зчитує з клавіатури (стандартного пристрою введення) число t – кількість турів у чемпіонаті, 1 ≤ t ≤ 10. У наступних t рядках знаходиться інформація про кожен з турів у такому вигляді: n q a₁...a_n, 0 ≤ q ≤ 100. a_i =  може бути 0, якщо команда не відповіла на i питання, або ж 1 в іншому випадку. Крім того, усього на чемпіонаті було задано не більш, ніж 500000 питань. Усі числа вхідних даних цілі.  Програма Quiz виводить на екран (стандартний пристрій виведення) рівно t чисел в один рядок через пробіл: i-те число дорівнює кількості вдалих серій питань у i-ому турі.

Система оцінки.70% балів припадатиме на тести, в яких q_i = 50.

Приклад вхідних та вихідних даних

Введення                                        Виведення

2

10 50 1 0 1 0 1 1 0 0 0 1                    32 4

5 50 1 0 0 0 1

Завдання командної олімпіади IT -2018

Завдання командної олімпіади

Штанга (Barbell) Гноми добре знають, наскільки важливі заняття спортом, а тому часто ходять до тренажерної зали. Утім, займатися прибиранням після виснажливого тренування зовсім не хочеться, тож більшість тренажерів залишаються у стані «хай буде». Адміністратору зали особливого клопоту завдають штанги (виявляться, зняти усі диски самотужки досить складно). Штанга – спортивний снаряд, що складається з грифу (металевого стержня) масою M, розміщеного на двох опорах, віддалених від центру мас грифу на L. Ліворуч від лівої опори щільно розміщено N дисків, кожен шириною 2W маси Ai. Ці N дисків нумеруються, починаючи від опори (тобто справа наліво). Праворуч від правої опори аналогічним чином розміщено K дисків, кожен шириною також2W та маси Bi. Ці K дисків нумеруються, починаючи від опори (тобто зліва направо). Гном-адміністратор вміє швидко знімати диски (звісно, починаючи від крайнього), але досить повільно змінює сторону. Крім того, гному зовсім не хочеться, щоб в якийсь момент часу штанга перехилилася (тобто, щоб її центр мас був не між опорами; якщо центр мас виявляється рівно на якійсь з опор, штанга не перехиляється). У початковий момент часу штанга не перехиляється, тобто центр мас усієї конструкції знаходиться між лівою та правою опорою (можливо, рівно на одній з опор). Адміністратор хоче обрати сторону, з якої починати, підійти до неї, зняти якусь кількість крайніх дисків, після чого змінити сторону, повторити ті самі дії, потім знову змінити сторону і продовжувати, поки можливо знімати хоча б один диск без перекидання всієї конструкції. Вам необхідно заздалегідь сказати гному таку інформацію: яку максимальну кількість дисків можна зняти та яку мінімальну кількість змін сторони необхідно на це витратити. Зверніть увагу, що в першу чергу вам необхідно максимізувати кількість знятих дисків, а в другу мінімізувати кількість змін сторони. З самого початку гном може обрати сторону «безкоштовно», тобто до кількості змін сторони цей вибір не додається. Формат введення-виведення: Програма Barbell читає з клавіатури (стандартного пристрою введення) три рядки. У першому рядку розміщено чотири числа: M, L, W, N, K (1 ≤ M, L, W, N, K ≤ 105) – відповідно, маса грифу, половина відстані між опорами, половина ширини кожного з дисків та кількості дисків на правій та на лівій половині. У другому рядку рівно N цілих невід'ємних чисел, кожне не перевищує 103– маса кожного з дисків, що розташовані праворуч. У третьому рядку рівно K натуральних чисел, кожне не перевищує 103 – маса кожного з дисків, що розташовані ліворуч. Програма Barbell виводить на екран (стандартний пристрій виведення) рівно 2 цілих числа через пробіл: максимальну кількість дисків, що можна зняти, та мінімальну необхідну кількість змін сторони. Приклад вхідних та вихідних даних Введення 1 Виведення 1 3 6 1 2 2 9 3 9 3 4 1 Введення 2 Виведення 2 2 9 1 2 3 10 3 9 3 1 5 2 Зображення до другого тесту - - - - - - - - - - - - - - - - - - - - - - - - - Опуклі оболонки (ConvexHulls) Опукла оболонка множини точок - опуклий багатокутник з найменшою площею, що містить усю множину точок. Вам дано n точок на площині. Довільним чином можна вибрати і видалити одну із заданих точок, після чого побудувати опуклу оболонку решти. Очевидно, що видаляючи різні точки, ви будете отримувати різні опуклі оболонки. Припустимо, Ви по черзі видаляєте точки заданої множини і будуєте опуклі оболонки (видаляючи чергову точку, попередньо видалену Ви повертаєте назад). Зробивши вказану дію для кожної точки, Ви отримаєте n опуклих оболонок (деякі з яких можуть співпадати). Запишемо набір чисел, що дорівнюють кількості вершин в кожній з отриманих опуклих оболонок. Знайдіть середнє арифметичне даного набору чисел. Вважати, що якщо опукла оболонка є відрізком, то в ній дві вершини. Якщо ж вона є невиродженим багатокутником, то всі кути при вершинах строго менше π. Формат введення-виведення: Спочатку програма ConvexHulls читає з клавіатури (стандартного пристрою введення) число n (3 ⩽ n ⩽ 2 · 105) - кількість точок множини. Далі у наступному рядку читаються пари цілих чисел, що не перевищують по модулю 109 - координати точок. Гарантується, що жодні дві точки не співпадають. Програма ConvexHulls виводить на екран (стандартний пристрій виведення) два числа через пробіл p q, де p, q – цілі невід'ємні числа. Приклад вхідних та вихідних даних Введення Виведення 5 0 0 0 4 4 0 3 3 4 4 17 5 - - - - - - - - - - - - - - - - - - - - - - - - - Іспити (Exams) Одного чудового ранку студент прокинувся і зрозумів: скоро сесія! Студент знає, скільки часу (від даного моменту) залишилося до початку кожного іспиту, та скільки часу потрібно на підготовку до кожного іспиту. Студент складає іспити моментально. Крім того, студент вміє готуватися до іспитів як безперервно, так і з розривами на підготовку до інших іспитів та/або на складання інших іспитів (все це не впливає на сумарну тривалість підготовки). Яку максимальну кількість іспитів може скласти студент? Формат введення-виведення: Спочатку програма Exams читає з клавіатури (стандартного пристрою введення) ціле число n (0<=n<=10000) і далі n пар цілих чисел Ti, Di (0<=Ti<1000000, 0<Di<1000000, всі Ti попарно різні) – момент початку та тривалість підготовки для i-го іспиту. Всі числа розділені пробілами. Програма Exams виводить на екран (стандартний пристрій виведення) єдине ціле число: максимальну кількість іспитів, які студент може. Приклад вхідних та вихідних даних Введення 1 Виведення 1 3 3 2 5 4 10 5 2 Введення 2 Виведення 2 3 3 2 5 3 10 5 3 - - - - - - - - - - - - - - - - - - - - - - - - - Нелюбимі цифри (Numbering) Новий керівник організації виявив, що його попередник, по одному йому відомим причинам, для нумерації офіційних документів принципово не використовував числа, десяткові записи яких містили деякі цифри. Причому в різні роки обструкції підлягали різні комплекти цифр. У якості початкового номеру в кожному році попередній керівник брав мінімальне невід’ємне число, що не містило знехтуваних у даному році цифр. При нумерації кожного наступного документу, у тих випадках, коли наступний номер містив знехтувану цифру, це число просто пропускалося. І так, доки чергове число не виявлялося вільним від небажаних для нього цифр. Наприклад, якщо нехтувалися цифри 8, 7, 9, 5, 1, то перші кілька документів цього року мали наступні номери: 0, 2, 3, 4, 6, 20, 22, 23, 24, 26, 30, 32, 33, ... Оскільки попередник керував організацією досить довго і накопичилась велика кількість перенумерованих ним документів, у нового керівника виникла потреба у програмі, яка для заданого комплекту знехтуваних цифр за вихідним номером документа (тобто за номером, який був йому наданий) швидко визначить порядковий номер цього документа, відрахований від нуля. Формат введення-виведення: Програма Numbering зчитує з клавіатури (стандартного пристрою введення) два непустих рядки. У першому рядку через пробіл перераховано нелюбимі цифри (їх загальна кількість від однієї до восьми включно). У другому рядку дано вихідний номер шуканого документу (не менше нуля та не більше 1,000,000,000). Програма Numbering виводить на екран (стандартний пристрій виведення) єдине число – номер шуканого документу, тобто порядковий номер документу, вихідний номер якого вказано у вхідному файлі. Приклад вхідних та вихідних даних Введення Виведення 8 7 9 5 1 24 8 - - - - - - - - - - - - - - - - - - - - - - - - - Гномоградуси (Gnomedegrees) Гноми чудово розуміють, що «Математика – цариця наук!» і тому приділяють цьому предмету особливу увагу. Найулюбленішими у них є геометричні задачі з колами. Однак, зверніть увагу, що одиницею вимірювання кута у гномів є не градуси чи радіани, а деяка величина – гномоградус. Причому, в залежності від настрою, ця величина може змінюватися! Визначається ця величина таким чином: задається число L – кількість рівних частин, на які ділиться коло. И ось гномам задали таку задачу. На колі є N перегородок з відомими кутами, заданими у гномоградусах, причому число L, що визначає гномоградус, обов’язково кратно кількості перегородок N. Необхідно визначити мінімальну кількість переміщень перегородок, в результате якого коло буде розділено на рівні частини. Перегородки можна рухати тільки в межах від попередньої до наступної, тобто заборонено міняти їх місцями відносно заданого розташування. Крім того, перегородки дозволяється рухати тільки по умовним поділкам, тобто нові кути повинні бути виражені цілою кількістю гномоградусів. Формат введення-виведення: Програма Gnomedegrees читає з клавіатури (стандартного пристрою введення) два непустих рядка. У першому рядку два цілих числа L та N (L≤109, N≤103, L кратно N), а у другому N цілих чисел через пробіл ai (0≤ ai≤L-1) – кути, на яких знаходяться перегородки у гномоградусах. Початок відліку кожного з кутів від вертикалі (див. рисунок). Програма Gnomedegrees виводить на екран (стандартний пристрій виведення) єдине ціле число: мінімальну кількість переміщень. Приклад вхідних та вихідних даних Введення Виведення 27 9 13 2 11 9 10 20 1 21 22

Сайти для підготовки до олімпіади інформатики

Стратегічна задача на  оптимізацію кількості

 інформаційних  зв’язків між користувачами.

У деякій освітній системі є n працівників. Між деякими із них здійснюються двосторонні мобільні зв'язки.

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

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

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

Відповідь: m(n)=n-[n/3]-1.

Вказівка. Переформулюємо умову задачі на мові теорії графів. Потрібно знайти таке мінімальне число s,  що у будь-якому зв’язному графі, у якого n вершин можна відмітити не більше ніж s його вершин таким чином, що у будь-якої вершини знайдеться відмічена сусідня вершина(вважаємо,  що сусідня вершина зветься сусідкою).

Доведемо, що s >= n-[n/3]-1. Розглянемо граф з чотирма вешинами v⁽⁰⁾, v⁽¹⁾_j, v⁽²⁾ _j, v⁽³⁾_j , j = 1, . . . , [n/3], та ребрами (v⁽⁰⁾, v⁽¹⁾_j), (v⁽¹⁾, v⁽²⁾_j),  (v⁽²⁾, v⁽³⁾_j), j = 1, . . . , [n/3].

Нехай k - довільне число від 1 до [n/3]. У вершин v⁽²⁾ _k, v⁽³⁾_k  повинна бути відмічена сусідка, а це значить обов’язково буде відмічена v⁽²⁾ _k, як єдина сусідка v⁽³⁾_k  і одна з вершин v⁽¹⁾_j, v⁽³⁾_j повинна бути відмічена, оскільки інших сусідів у   v⁽²⁾ _k  немає. Таким чином, всього повинно бути відмічено  не менше  2*[n/3]-1 вершини.

Доведемо, що s <= n-[n/3]-1. Можна вважати, що заданий граф являється деревом, так як в протилежному випадку можна виділити скріплююче дерево і довести твердження для нього.  Виберемо в якості кореня висячу вершину і назвемо її v⁽⁰⁾,а інші розташуємо по рівнях стандартним чином.  Розфарбуємо вершини в три кольори так, що  вершини на рівнях 3k+1 пофарбовані в один колір, на рівнях виду 3k+2 пофарбовані в другий колір, а інші в третій колір. За принципом Діріхле знайдеться такий колір, в який пофарбовано що найменше  [n/3]+1 вершини. Відмітимо вершини інших кольорів. Тоді ми відмітили не більше n-[n/3]-1 вершин, і у будь-якої невисячої вершини є відмічена сусідня вершина. Нехай v – висяча вершина(v не дорівнює v⁽⁰⁾),  нехай v₁ – батько– батько v₁. ВІдмітимо, що v₂ існує, так як рівнів не менше трьох. Якщо у v не існує відміченої v, v₂ сусідньої вершини, то v₁ – невідмічена, а значіть, відмічені  v та  v₂. Приберемо мітку з вершини v, та відмітимо вершину v₁. Тоді кількість відмічених вершин не зміниться, у всіх вершин, у яких   була відмічена сусідка, вона залишається, а також вона і у вершини v тепер буде відмічена сусідка. Аналогічно зробимо для кореневої вершини. Зробивши, при необхідності подібну операцію скінчену кількість разів, ми отримаємо те, що у всіх вершин була відмічена сусідка. Що і вимагало довести.

Зразки задач для складання алгоритмів мовою програмування Pascal (це задачі міської олімпіади з інформатики за 2017 рік у м. Вінниці)

Задача Tel. Василь з батьком купували два мобільні телефона – мамі і Василеві. Так як на другий товар у супермаркеті суттєва знижка, за перший заплатили R1  гривень, а за другий менше -  R2 . Число S називається середнім з двох чисел R1 і R2, якщо S дорівнює (R1 + R2) / 2.  Василь негайно підрахував  середнє значення ціни S, яке також виявилося цілим числом. Коли мамі вручили новий телефон, сказали його ціну R1  та розповіли про знижку. Мама поцікавилася, а скільки ж коштує телефон Василя, але він пам’ятав лише середнє значення ціни та ціну маминого телефона.  Допоможіть Василю сказати мамі правду.

Технічні умови. Програма Tel  читає з пристрою стандартного введення  два цілих числа R1 і S, (обидва між 1000 і +10000) в одному рядку через пропуск, програма виводить на пристрій стандартного виведення єдине ціле число – вартість телефона Василя.

Приклад.  Введення   4000 3000. Виведення 2000.  Функція для розв’язання Задача Tel: R2(R1;S)=2*S-R1 якщо (1000<=R1<=10000), &(1000<=S<=10000).

var  R2, S, R1: integer; begin read (R1, S); R2:= 2*S – R1; write (R1); end.

var r1,r2,s:int64; begin   read(r1,s);   r2:=2*s-r1;   write(r2); end.

Задача Ink. Як відомо, все частіше і частіше  різні папери не пишуть від руки, а друкують на принтері. Актуальною є проблема придбання запасних картриджів. Їх варто купувати разом з принтером. Якщо разом з принтером купити N  картриджів, це буде коштувати А+В*N гривень. Відомо, що  покупець на всю покупку може витратити не більше С гривень.

Визначте максимальне число запасних картриджів, що їх зможе купити покупець.

Технічні умови. Програма Ink  читає з пристрою стандартного введення  три цілих числа A, B, C (1 ≤ A, B, C ≤ 2*109, A ≤ C) - вартість принтера, вартість одного картриджа і максимальну вартість усієї покупки. Програма виводить єдине число - максимальне придбаних картриджів.

Приклад .  Введення	Виведення
20 10 55	3

Функція для розв’язання Задача Ink: N(a;b;c)=[(c-a)/b],  якщо а+b *n<=C

var A, B, C, N: real; begin read(A, B, C); N:=(C-A)/B; write(trunc(N)); end.

var a,b,c,n:int64; begin   read(a,b,c);   c:=c-a;   if c<0 then c:=0;   n:=(c div b);   write(n) end.

Задача Wiring.   Василь бажає підключити всі свої m електроприладів  до n розеток, що є в кімнаті. У магазині продаються  розгалужувачі з 1 розетки на 2 по ціні A гривні за штуку, а мультиплексори з однієї розетки на п’ять — по ціні B гривні за штуку. Запас обох товарів у магазині завжди достатній. Розгалужувачі та мультиплексори можна вільно підключати один до одного та розетки, що є. Яку мінімальну суму доведеться  витратити Василю, аби  підключити всі наявні в нього  електроприлади?  Василь не проти, якщо після підключення всіх m приладів залишаться незаняті розетки, его турбує  лише мінімізація затрат.

Технічні умови. Програма  Wiring  читає з пристрою стандартного введення рядок  чисел через пропуск: n (1 ≤ n ≤ 1015) — кількість розеток,  m (1 ≤ m ≤ 1015) — кількість електроприладів, два цілих числа a і b (1 ≤ a,b ≤ 1000), - вартість розгалужувача  і мультиплексора відповідно. Програма виводить на пристрій стандартного виведення  єдине число – мінімальну суму, яку повинен витратити Василь.

Приклади

Введення	Виведення
1 3 1 10	2
2 4 9 10	10
3 8 9 10	19

Функція для розв’язання Задача Wiring: 1)C(a;b;k;l)=min[(ak+bl],  цей мінімум шукають на множині (k+4l<=m-n)&(k+l<=m-n), якщо n-m<0.  2) C(a;b;k;l)=0, якщо (n-m)>=0. 

var n,m,a,b,min,k,d,mo:int64; begin    read(n,m,a,b);    k:=m-n;    if k<=0 then begin write(0) end            else begin     d:=(k div 4);    mo:=(k mod 4);                    min:=k*a;                    if mo>0 then m:=d*b+b                            else m:=d*b;                    if min>m then min:=m;                    m:=d*b+mo*a;                    if m<min then min:=m;                    write(min);                 end; end.

Задача Tiles. План будинку має форму прямокутника зі сторонами axb. Вздовж всіх стін  (всередині будинку) проходить коридор шириною h. Підлогу коридору вирішили покрити плиткою розміром 1х1. Скільки плиток для цього потрібно купити? Вважайте, що a>2h,  b>2h.

Технічні умови.  Програма Tiles читає з пристрою стандартного введення  три натуральних  числа  a,b,h (кожне з них не більше 106. Програма виводить на пристрій стандартного виведення  єдине число – кількість плиток, яку потрібно купити.

Приклад. Введення  5 10 2.  Виведеня  44.  Функція для розв’язання Задача Tiles: K(a;b;h)=2ah+2h(b-2h],  якщо a>2h,  b>2h.

var a, b, h, x: integer; begin read (a, b, h); x:=2*h*(a+b-(2*h)); write (x); end.

var a,b,h,r:int64; begin   read(a,b,h);   r:=a*b-(a-2*h)*(b-2*h);   write(r); end.

Завдання  для самостійного програмування

Завдання С 

 

Задання С1. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних розв’язків на числових проміжках [-k; k], де k- ціле число, рівняння

n²+(n-1)²+n²(n-1)²=(n(n-1)+1)²,

де n - ціле невідоме число.

 

 

Завдання С2. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних розв’язків на числових проміжках [-k; k], де k- ціле число, рівняння 

n²+(n-1)²+(n-2)²+ n²(n-1)² +(n-1)²(n-2)² =(n(n-1)(n-2)+1)²,

де n - ціле невідоме число.

 

Задання С3. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (a;b;c)  на проміжках [-k; k], де k- ціле число, рівняння

(a-b)³+(b-c)³+(c-a)³=3(a-b)(b-c)(c-a)

де a, b,c - цілi невідомі числa.

 

 

Задання С4. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (a;b;c) на числових проміжках [-k; k], де k- ціле число, рівняння

(a+b)³+(b+c)³+(c+a)³-3(a+b)(c+b)(a+c) =2(a³+b³+c³-3abc)

де a, b,c - цілi невідомі числa.

  

Задання С5. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (a;b;c) на числових проміжках [-k; k], де k- ціле число, рівняння

(a+b+c)(a²+b²+c²-ab-cb-ac)=a³+b³+c³-3abc

де a, b,c - цілi невідомі числa.

 

Задання С6. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (a;b;c) на числових проміжках [-k; k], де k- ціле число, рівняння

(a+b+c)³-3(a+b)(b+c)(c+a)=a³+b³+c³-3abc

де a, b,c - цілi невідомі числa.

 

Завдання D 

Задання D1. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних розв’язків на числових проміжках [-p; p], де p - ціле число, рівняння

1² + n² = 4(9+n),

де  n - ціле невідоме числa.

 

Задання D2. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних двійок-розв’язків (m;n)  на числових проміжках [-p; p], де p - ціле число, рівняння

m² + n² = m(m+n),

де m,n - цілi невідомі числa.

 

Задання D3. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (k;m;n)  на числових проміжках [-p; p], де p - ціле число, рівняння

m² + n² + k²=km+mn+kn,

де k,m,n, - цілi невідомі числa.

 

 

Задання D4. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (k;m;n)  на числових проміжках [-g; g], де g - ціле число, рівняння

m²n+k²n+n²m=n³+m³+k³

де k,m,n - цілi невідомі числa.

Задання D5. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (k;m;n) на числових проміжках [-q; q], де q - ціле число, рівняння

m³n²+k³m²+n³k² = n⁵ +m⁵+k⁵,

де k,m,n, - цілi невідомі числa.

 

Задання D6. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних четвірок-розв’язків (k;m;n;р) на числових проміжках [-g; g], де g - ціле число, рівняння

(mn+kp)²=(n²+m²)(k²+p²)

де k,m,n,p - цілi невідомі числa.

 

 

 

Завдання F 

Задання F1. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних розв’язків на числових проміжках [-d; d], де d - ціле число, рівняння

1 + 18n+ n² = (2+n)(59+n),

де  n - ціле невідоме числa.

Задання F2. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних двійок-розв’язків (m;n)  на числових проміжках [-t; t], де t - ціле число, рівняння

m² + n² = (m-6)(m+n+30),

де m,n - цілi невідомі числa.

 

Задання F3. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (k;m;n)  на числових проміжках [-r; r], де r - ціле число, рівняння

(m-1)² + n² + (k+1)²=k(m-1)+mn+(k+1)n,

де k,m,n, - цілi невідомі числa.

 

 

Задання F4. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (k;m;n)  на числових проміжках [-h; h], де h - ціле число, рівняння

m²(n-1)+k²n+(n+1)²m=(n-1)³+m³+(k+1)³

де k,m,n - цілi невідомі числa.

Задання F5. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (k;m;n) на числових проміжках [-s; s], де s - ціле число, рівняння

m⁴n+k⁴m+n⁴k = n⁵ +m⁵+k⁵,

де k,m,n, - цілi невідомі числa.

 

Задання F6. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних четвірок-розв’язків (k;m;n;р) на числових проміжках [-g; g], де g - ціле число, рівняння

(mn+kp)²=((n-1)²+(m-1)²)((k+1)²+(p+1)²)

де k,m,n,p - цілi невідомі числa.

 

Завдання W 

Задання W1. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних розв’язків на числових проміжках [-n; n], де n - ціле число, рівняння

1=0.25(m²+1)² – 0.25(m²-1)²

де  m - ціле невідоме числa.

Задання W2. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних двійок-розв’язків (m;n)  на числових проміжках [-t; t], де t - ціле число, рівняння

mⁿ=0.25(mⁿ+n)²-0.25(mⁿ-n)²   

де m,n - цілi невідомі числa.

 

Задання W3. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних трійок-розв’язків (k;m;n)  на числових проміжках [-y; y], де y - ціле число, рівняння

k⁴ + 4 =  (m² – 2m + 2)(n² + 2n + 2),

де k,m,n, - цілi невідомі числa.

 

 

Задання W4. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних двійок-розв’язків (a;b)  на числових проміжках [-h; h], де h - ціле число, рівняння

a⁴ + 4b⁴ = (a² – 2ab + 2b²)(a² + 2ab + 2b²);

де a,b - цілi невідомі числa.

Задання W5. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних двійок-розв’язків (k;n) на числових проміжках [-s; s], де s - ціле число, рівняння

k⁴+(n+k)(n+2k)(n+3k)(n+4k)=(n² + 5kn+5k²)²,

де k,n, - цілi невідомі числa.

 

Задання W6. Створити та реалізувати мовою програмування Python3 в середовищі програмування Thonny

алгоритм пошуку цілочисельних двійок-розв’язків (k;n) на числових проміжках [-g; g], де g - ціле число, рівняння

k⁴+(n-k)n(n+k)(n+2k)=(n² + kn- k²)²;

де k,n - цілi невідомі числa.

 

 

Список рекомендованих сайтів для підготовки до олімпіади

http://schoololymp.byethost32.com – школа олімпійського резерву при ВІППО
http://www.olymp.vinnica.ua – Всеукраїнські Інтернет-олімпіади з різних предметів (фізика, інформатика). На сайті розміщена цікава інформація про Всеукраїнські олімпіади по інформатиці, фізиці. Проводилася мережна олімпіада по інформатиці.
http://www.uoi.in.ua – Всеукраїнська олімпіада з інформатики
http://www.e-olimp.com.ua E-Olimp система підготовки та проведення олімпіад зіспортивного програмування
http://www.qbit.org.ua/ -Молодёжное научное общество QBit - Кубит - г. Харьков
http://algolib.chat.ru –алгоритми: методи розв’язання
http://algolist.manual.ru –алгоритми: методи розв’язання
http://olympiads.win.true.nl/ioi – Міжнародна олімпіада з інформатики
http://www.olympiads.ru - Події, задачі, тести, рішення, коментарі. На сайті також можна викачати бібліотеку для написання "перевірялок" до задач - Testlib.
http://neerc.ifmo.ru/School/ - На цьому сайті міститься інформація про олімпіади школярів по інформатиці, які проходять в Росії, в яких беруть участь Петербурзькі школярі
http://www.olympiada.km.ua/ - Задачі заочних і обласних олімпіад Хмельницької області. Архіви турнірів, конкурсів. Багато іншої корисної інформації.
http://comp-science.narod.ru/ - Матеріали олімпіад школярів по програмуванню в Пермській області; підготовка до олімпіад по програмуванню; дидактичні матеріали по алгебрі і геометрії; технологія генерації дидактичних матеріалів по математиці; дидактичні матеріали по інформатиці (задачі, тести); методична скарбничка; посилання на освітні ресурси Internet.
http://acm.timus.ru- Тут ви можете знайти деяку кількість задач з різних змагань. Перевіряюча система дозволяє вам перевірити ваш розв’язок для кожної задачі.
http://www.informatics.ru/ - Даний сайт присвячений російським олімпіадам школярів по інформатиці. Автори сайту - члени журі і наукового комітету Всеросійської олімпіади, а також тренери збірної команди Росії для міжнародної олімпіади. Тут викладаються матеріали Всеросійських олімпіад, учбово-тренувальних зборів по інформатиці, різні книги і статті, присвячені даній тематиці.
http://g6prog.narod.ru - Сайт присвячений докладному розбору олімпіадних задач по інформатиці. Рівень задач від міської до міжнародної олімпіад. Програмні тексти до задач не додаються (представлений словесний опис рішення). До деяких задач додаються тести. Є багато корисних книг по олімпіадних задачах і велика кількість посилань на аналогічні ресурси.
http://byoi.narod.ru - Архів республіканських, міських, районних олімпіад, зборів до IOI. Підбір рідкісних, ефективних алгоритмів.
http://homepages.compuserve.de/chasluebeck - Дуже великий архів задач по інформатиці на російській мові.
http://www.stream.newmail.ru/index.html - Тут можна отримати відповідь на питання про олімпіади, взнати останні новини, підготуватися до олімпіад. На сайті є бібліотека книг і докладний каталог ресурсів.