ЗАВДАННЯ 3-ГО ТУРУ NetOI-2020 (26 січня 2021 - 10 лютого 2021 р.)


Задача DIFF

“Вундеркінд” Сергійко на уроці математики придумав для сусіда гру. Записавши в ряд N цілих чисел x1,x2,…,xN, він запропонував замінити якусь пару чисел xk,xk+1, що стоять поруч, їхньою різницею xk-xk+1 (завжди віднімаємо з першого числа друге, але не навпаки). Потім він повторював цю дію доти, доки не залишиться одне число. Яке максимальне число M можна отримати таким чином?

Технічні умови. Програма DIFF читає з стандартного пристрою введення з першого рядка кількість чисел N(1<N≤10000), з наступних N рядків числа x1,x2,…,xN (-10000≤xk≤10000,k=1,2,…,N). Програма виводить на пристрій стандартного виведення шукане число M.

Приклад.

Введення

3

1

2

3

Виведення

2

 


Задача AGENTS.

Відділ доставки фірми «Роги і Копита» обслуговує торгові точки. Щодня товар завозиться в одну з них. Графік завезення по днях складено заздалегідь, причому в цьому графіку точки можуть повторюватися.

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

Технічні умови. Програма AGENTS читає з першого рядка кількість торгових точок N (1,1<N≤10), далі з наступних N рядків N пар дійсних чисел (x1,y1),(x2,y2),…,(xN,yN) — координати 1-ої, 2-ої, …, N-ої торгових точок (-1000.0≤xk,yk≤1000.0,k=1,2,…,N), з наступного рядка кількість днів у графіку M(1<M≤10000), з наступних M рядків числа K1,k2,…,kM(1≤Kj≤N,j=1,2,…,M)— номери точок, які треба відвідати в 1-й, 2-й, …, M-й день. Програма виводить на пристрій стандартного виведення сумарний пробіг машин S з точністю до 10-5.

Приклад.

Введення

3

3.0 4.0

1.0 4.0

4.0 1.0

5

2

3

1

3

2

Виведення

12.2462112512

 

Задача BARREL.

Є бочка з деякою кількістю води. У бочку опускають  задану кількість брусків у формі куба різних розмірів і густини. Потім згори опускають кришку так, що вона торкається країв бочки. Треба визначити отримуваний рівень води. Передбачається, що густина води дорівнює 1.0; присутність повітря можна не враховувати; усі бруски цілком влізають у бочку; бруски розташовуються у воді вертикально і не торкаються один одного.

Технічні умови. Програма BARREL читає з клавіатури з першого рядка три дійсні числа - площу дна бочки S (0<S≤1000.0), висоту бочки H (0<H≤1000.0), об'єм води V (0<V≤SH), з  наступного рядка кількість брусків N (0<N≤1000), і далі з наступних N рядків N пар дійсних чисел - довжини сторін кубів Lk (0<Lk≤1000.0) і їх густини Dk (0<Dk≤10.0), k=1,2,…,N. Програма повинна вивести на екран дійсне число   - рівень води у бочці після додавання брусків. Це число треба визначити з точністю до 10-4.

Приклад

Введення

100.0 10.0 500.0

1

1.0 0.5

 

Виведення

5.0050

 


 


Задача COOKIES.

Бабуся готувала печиво. Для цього вона розкотила тісто у великий пласт у формі круга і скляночками різних діаметрів видавила в ньому круглі шматочки, щоб потім запекти їх і отримати з них смачне печиво. Відомо, що жодні два круглі вирізи не перетинаються між собою, крім того, усі вирізи повністю містяться всередині пласта. Проте вирізи можуть торкатися один одного і краю пласта. Улюблений онук з корисливих міркувань вирішив допомогти бабусі: він вирішив видавити в частині пласта, що залишилася, круглу заготовку для печива якомога більшого розміру. Проте він не знає, який діаметр має бути у скляночки, якою треба видавлювати таку заготовку. Допоможіть йому.

Технічні умови. Програма COOKIES читає зі стандартного пристрою введення з першого рядка радіус пласта R (1<R≤1000.0). Відомо, що центр пласта знаходиться в точці (0,0). З другого рядка програма читає натуральне число N (1≤N≤100) – кількість вирізаних заготовок. З наступних N рядків програма читає положення і радіуси вирізаних заготовок - дійсні числа, розділені пропуском. Програма виводить до стандартного пристрою виведення радіус максимальної за розміром заготовки, яку ще можна вирізати з цього пласта. Відповідь не повинна відрізнятись від правильної більше, ніж на 10-3.

Приклад

Введення

1.01

3

0.0 0.83333 0.166667

0.72169 -0.416667 0.166667

-0.72169 -0.416667 0.166667

Виведення

0.666666


Задача TRIANG

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

Дано правильний N-кутник. Перенумеруємо всі його вершини у порядку обходу проти годинникової стрілки натуральними числами від 1 до N. Нехай дано невід’ємні цілі числа d1, d, …, dN. Потрібно визначити, чи існує хоча б одна така триангуляція, що для усіх i від 1 до N вершина i має відносно неї степінь di, і якщо існує, вказати будь-яку з них.

Технічні умови. Програма TRIANG у першому рядку читає з клавіатури ціле число N (3≤N≤200000), у другому – N цілих чисел d1, d, …, dN (0≤diN). Програма виводить на екран К – кількість діагоналей, які задають шукану триангуляцію, а далі – K рядків з діагоналями. Кожна діагональ задаєтся двома числами ­– номерами вершин, які нею з’єднуються. Кожна діагональ повинна виводитися у окремому рядку. Номери вершин розділяються одним пропуском. У випадку, якщо триангуляції із заданими степенями вершин не існує, виведіть одне число -1.

Приклад

Введення

Виведення

6

1 0 2 1 0 2

3

1 3

3 6

4 6

Введення

5

2 0 2 0 2

Виведення

-1

Завдання підготували Г.непомнящий , Ю.Пасіхов

© LIKT 1998-2018