Завдання  4-го (REAL-TIME) туру NetOI-2012

17 лютого 2013 р.

Задача Remake.  Розглянемо 7-значні цілі числа в десятковій системі числення, дозволяючи нулі в старших розрядах. Тобто, числа від 0000000 до 9999999. Над числом дозволено виконувати такі перетворення:

- додати 1  (не застосовне до 9999999);

- відняти 1 (не застосовне до 0000000);

- домножити на будь-яке натуральне число k від 2 до 9 (застосовне тільки коли отриманий добуток не перевищує 9999999);

- поділити на будь-яке натуральне число k від 2 до 9 (застосовне тільки коли число  до перетворення кратне k);

 - виконати циклічний зсув вліво, тобто стерти найстаршу цифру і дописати її справа (наприклад, 1234567 → 2345671; застосовне до будь-якого числа);

- виконати циклічний зсув вправо, тобто стерти наймолодшу цифру і дописати її зліва (наприклад, 1234567 → 7123456; застосовне до будь-якого числа).

Напишіть програму, яка за двома вказаними 7-значними числами A та B знаходитиме, як перетворити перше у друге за мінімальну кількість кроків.

Технічні умови. Програма Remake читає з клавіатури (пристрою стандартного введення)  початкове та кінцеве значення A та B. Кожне значення складається рівно з 7-ми десяткових цифр, між значеннями знаходиться рівно один пропуск.

Програма виводить на пристрій стандартного виведення (екран)  спочатку мінімальну кількість перетворень M, далі треба вивести M+1 штук 7-цифрових чисел, де перше дорівнює A, останнє дорівнює B, і кожне наступне отримане з попереднього згідно одного з перетворень. Числа, менші 10⁶, мають бути доповнені нулями до 7-значних. Якщо можливі різні правильні послідовності з однаковою мінімальною кількістю перетворень — виводьте будь-яку одну з них. Числа виводяться через пропуск.

Приклади

Введення

3330333 3333033

Виведення

1 3330333 3333033

Введення

0000000 0370370

Виведення

6 0000000 0000001 1000000 0999999 0111111 0037037 0370370

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Задача Spider2.  Конус з твірною L (м)  і радіусом основи R (м) здійснює N  обертів навколо своєї осі за час T (с). Біля вершини конуса нерухомо зависла  муха. Павук, помітивши муху, прямує бічною поверхнею конуса від його основи до вершини з сталою швидкістю V (м/с)  найкоротшим, як він вважає,  шляхом. Слід  відмітити особливості будови ока павука – він бачить лише конус, на якому знаходиться, та  муху.  Муха ж, в силу особливостей свого зору, бачить рух павука по поверхні конуса, але не бачить самого конуса.  Муха, виходячи з того, що вона бачить, хоче знати, який шлях (м) повинен подолати павук, аби до неї дістатися. Допоможіть їй.

Технічні умови. Програма Spider2 читає з клавіатури (стандартного введення) 5 додатних цілих чисел (кожне з яких не більше за 5*10⁵) L, R, N, T, V через пропуск. Програма виводить на екран (пристрій стандартного виведення) одне дійсне число — шлях у метрах, виміряний мухою з точністю у 4 гарантованих значущих цифр після коми.

Приклад

Введення

10 1 1 10 10

Виведення

1.0006575845386885E+0001

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Задача Disted. Є n користувачів системи електронного навчання disted.edu.vn.ua  в Інтернеті. Кожен користувач зареєстрований в 2-х навчальних курсах і має два    цілі додатні числа-ідентифікатори – L[i] і R[i]. Користувачі швидко розібралися в можливостях системи і почали обмінюватися між собою приватними повідомленнями  Вважатимемо, що  i-й користувач    надсилає листи j-му, якщо виконується одна з двох умов:

1)     i<j, а також j-i≤R[i]

2)     i>j, а також i-j≤L[i]

Ваша задача – для кожного користувача порахувати кількість тих користувачів,  від яких він отримує листи.

Технічні умови. Програма Disted читає з клавіатури натуральне число – кількість користувачів системи n(1≤n<=100000).

Наступний рядок містить n цілих чисел L[i], розділених пропусками (1≤L[i]≤100000).

Наступний рядок містить n цілих чисел R[i], розділених пропусками (1≤R[i]≤100000). 

Програма  виводить  на екран n чисел через пропуск - відповідь на задачу.

Приклад

Введення

4

1 2 1 2

1 2 3 4

Виведення

1 3 2 2

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Задача Nth.   Розглянемо сукупність послідовностей:

послідовність №1 має вигляд 1, 2, 3, …, n, …;

послідовність №2 має вигляд 1, 4, 9, …, n², …;

послідовність №3 має вигляд 1, 8, 27, …, n³, …;

і так далі;

послідовність №k має вигляд 1, 2^k, 3^k, …, n^k, …;

і так далі.

Очевидно, що кожна з цих послідовностей монотонно зростає. Об’єднанням двох послідовностей будемо вважати послідовність, куди входять елементи обох послідовностей, теж у порядку зростання (числа, що належать обом послідовностям, належать об’єднанню лише один раз). Наприклад, об’єднання послідовностей №2 та №3 має вигляд: 1, 4, 8, 9, 16, 25, 27, 36, 49, 64, 81, 100, 121, 125, …

Технічні умови.  Напишіть програму Nth, яка оброблятиме серію запитів вигляду: знайти N-й елемент об’єднання послідовностей №a та №b.

Програма читає з клавіатури (пристрою стандартного введення) спочатку кількість запитів q (1≤ q ≤100), потім самі запити. Кожен запит має вигляд трійки чисел a b N, де a та b — номери послідовностей, N — номер шуканого елемента в об’єднанні послідовностей. Всі вхідні дані записані в один рядок і розділені пропусками (не обов’язково одинарними). Усі числа a b N цілі, не менші 1; верхнє обмеження на a b N не задається явно, але гарантується, що значення кожної відповіді не перевищуватиме 10¹⁹. Програма повинна вивести на екран (пристрій стандартного виведення) відповідь для кожного з запитів (теж у один рядок, розділяючи пропусками).

Приклад

Введення

3   2 3 4   3 2 11   4 7 17

Виведення

9 81 38416

Примітка. Не менш ніж у 30% тестів гарантовано, що кількість запитів q=1, номери послідовностей a та b в межах 1≤a<b≤9, номер шуканого елемента у межах 1≤j≤100.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Задача  Container. Ви – капітан корабля.  У трюмі, що має форму квадрата розміром N*N, Ви перевозите контейнери розміром 1*1*2.  Ці контейнери не можна пересувати, але можна кантувати (тобто перекочувати відносно ребра, що на підлозі), як показано на малюнку (вид згори). На кантування контейнера витрачається одна хвилина. На початку всі контейнери дотикаються підлоги стороною 1*1. Відстань від ребра кожного контейнера до стіни – завжди ціле число. Крім першого, інші контейнери залишаються на місці. Не можна ставити контейнер на інший. Не можна, щоб контейнер виходив за межу трюму, але він може дотикатись до стіни. За скільки хвилин Ви зможете перекантувати перший контейнер у задану клітинку так, щоб він дотикався підлоги стороною 1*1?

Технічні умови. Програма Container читає з клавіатури два цілих числа – розмір трюму N (3<=N<=1000) та кількість контейнерів M (1<=M<=N*N-2). Далі програма читає M+1 пару чисел x,y – координати контейнерів та координати клітинки, куди необхідно поставити перший контейнер. Всі клітинки різні. Програма виводить на екран шуканий мінімальний час. Якщо перекантувати контейнер неможливо, виводьте -1.

Приклади

Введення

4 1 1 1 4 4

Виведення

4

Введення

6 3 3 2 4 4 4 5 1 1

Виведення

7

Введення

7 5 4 4 4 5 4 3 3 4 5 4 1 1

Виведення

-1

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