Завдання 2-го туру NetOI-2020
(28 листопада - 27 грудня 2020 р.)
Задача Plant. Для розміщення будівель нового заводу фірма вирішила придбати земельну ділянку. Кожна з 3-х будівель в плані має форму прямокутника, розміри і-го корпусу ai x bi. Ділянка також повинна мати форму прямокутника. При розміщенні будівель останні повинні розміщуватися таким чином, аби їх сторони були паралельні сторонам ділянки. Будівлі можуть торкатися одна одної своїми сторонами або кутами. Напишіть програму, яка дозволить розрахувати площу мінімальної земельної ділянки, яку повинна придбати фірма для будівництва заводу.
Технічні умови. Програма Plant читає з пристрою стандартного введення рядок з 6 цілих чисел a1, b1, a2, b2, a3 і b3 відповідно (1 ⩽ ai , bi ⩽ 104 ). Програма виводить на пристрій стандартного виведення одне число - мінімальну площу ділянки, яку треба придбати.
Приклади
|
Введення 4 10 5 11 12 3 |
Виведення 144 |
|
Введення 2 2 2 4 2 6 |
Виведення 24 |
Задача Pixels2020. Монохромне зображення складається з m пікселів по вертикалі та n пікселів по горизонталі. Колір пікселя задається цілим числом від 0 (чорний) до 255 (білий). Фрагментом зображення називатимемо прямокутник з a пікселів по вертикалі та b по горизонталі. Яскравістю фрагмента вважаємо суму чисел, що йому належать. Знайдіть найменшу та найбільшу яскравість фрагмента.
Технічні умови. Програма Pixels2020 читає з пристрою стандартного введення з першого рядка розділені пропуском числа m,n,a,b (1≤a≤m≤480,1≤b≤n≤640). Далі програма читає m рядків по n розділених пропуском чисел – яскравість пікселя (ціле невід’ємне число, не більше 255). Програма виводить на пристрій стандартного виведення два числа, розділені пропуском – мінімальна та максимальна яскравість фрагмента.
Приклад
Введення
5 4 3 2
2 5 7 4
1 9 7 3
3 8 6 9
2 4 5 7
6 7 8 3
Виведення
27 42
Коментар
Мінімальна яскравість
1 9
3 8
2 4
Максимальна яскравість
5 7
9 7
8 6
Задача Sum2020. Нехай f(k) – сума цифр числа k, n і s – натуральні числа. Знайдіть кількість n-цифрових натуральних чисел k таких, що f(k)=s.
Технічні умови. Програма читає з пристрою стандартного введення розділені пропуском числа n,s (1≤n≤1000,1≤s≤9000). Програма виводить на пристрій стандартного виведення шукану кількість за модулем 1000000007.
Приклад
Введення
2 11
Виведення
8
Задача Parket0. Ідея зобразити на паркеті Новий Візерунок виникла не зразу. Спочатку підлогу хотіли замостити більш звичним способом, узявши прямокутну частину нескінченного візерунка, початок якого зображено на малюнку. Ця прямокутна частина задається цілими невід’ємними координатами xmin, xmax, ymin та ymax. Наприклад, частині, виділеній на малюнку сірим, відповідають координати 4 12 , 4 10. Напишіть програму, яка за вказаними координатами прямокутної частини знаходитиме, скільки всередині неї є дощечок розміру 1×1,скільки розміру 2×1,скільки 3×1, скільки 4×1 та скільки 5×1.
Технічні умови. Програма Parket0 читає з клавіатури чотири цілі невід’ємні числа xmin, xmax, ymin та ymax (саме в такому порядку) в одному рядку, розділені пропусками. Програма виводить на екран п’ять чисел, розділених пропусками N1, N2, N3, N4 та N5, що позначають кількості дощечок розмірами 1×1, 2×1, 3×1, 4×1 та 5×1. Гарантовано, що 0 ≤ xmin < xmax, 0 ≤ ymin < ymax ( xmax, ymax ≤ 109)
 |
|
||||||
Задача Fixshow.Оскільки Дім Дімич у черговий раз забув привітати бабусю з днем народження, він вирішив влаштувати для неї грандіозне музичне шоу. Для цього він знайшов рівний майданчик, у певних координатах якого розставив N найсучасніших електронних синтезаторів звуку. За задумом Дім Дімича, у деякі (можливо різні) моменти часу, вони почнуть видавати звуки (гарантовано різні), і звучання буде тривалим. Оскільки Дім Дімич хоче, щоб бабуся почула усі звуки якомога швидше, він вирішив знайти таку точку на майданчику, в якій вперше будуть чутися всі N звуків одночасно. Вирішити таку складну задачу самостійно він не зміг, а тому вдався до вашої допомоги.
Напишіть програму, яка обчислює координати точки і час, за який у ній звуки від усіх синтезаторів будуть чутися вперше, за умови, що звук поширюється тільки по повітрю зі швидкістю С, однаковою для усіх синтезаторів і напрямків. Іншими затримками (наприклад, кінцевою швидкістю поширення електричних сигналів) можна знехтувати.
Технічні умови. Програма Fixshow зчитує з клавіатури (стандартного пристрою введення) спочатку число N (1<=N<=555) – кількість синтезаторів, потім N трійок чисел – координати синтезаторів на майданчику та час початку їх звучання і, нарешті, число С (0.1<=C<=1000) – швидкість розповсюдження звуку. Значення координат не перевищують по модулю 106 та не обов’язково цілі.Програма fixshow виводить на екран (стандартний пристрій виведення) три числа через пропуск: координати точки, в якій вперше будуть чутися всі звуки одночасно, і час, коли це відбудеться. Результат зараховується, якщо час відрізняється від правильного не більше ніж на 10-3 та у вказаний час у вказаній точці будуть чутися всі синтезатори.
Приклад
|
Введення
|
4 2 8 6 16 4 0 5 1 8 3 6 2 1
|
|
Виведення
|
5 4 11 |
Завдання підготували Г.Непомнящий, Ю.Пасіхов