Задания  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

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