Задачи муниципального этапа олимпиады школьников по информатике 2016

Петру необходимо попасть с этажа `A` на этаж `B`. Для вызова лифта на всех этажах офисного здания, кроме первого и последнего, есть две кнопки – для перемещения вниз и перемещения вверх. В тот момент, когда Петр нажал нужную кнопку вызова, лифт находился на этаже `C` и вез одного пассажира на этаж `D`. Если лифт проезжает мимо этажа, на котором нажата кнопка вызова, и лифт движется в подходящем направлении, то лифт останавливается, чтобы посадить дополнительного пассажира. Лифт перемещается между соседними этажами за одну единицу времени, также одну единицу времени занимает остановка лифта на этаже для высадки или посадки пассажиров.

Напишите программу, вычисляющую, через сколько времени Петр доберется до этажа `B`, при условии, что никто больше не будет вызвать лифт.

Первая строка ввода содержит четыре целых числа `A`, `B`, `C` и `D`, разделенных одним пробелом (`1\ ≤\ A,\ B,\ C,\ D\ ≤\ 20`, `A≠B`, `C≠D`, `A≠C`).

Вывести одно целое число – количество единиц времени от момента вызова лифта до момента, когда Петр выйдет из лифта на этаже `B`.

3 9 2 5

10

3 9 5 2

13

Лифт за 1 единицу времени доедет до 3-го этажа, остановится на 1 единицу времени, чтобы Петр сел в лифт, затем через 2 единицы времени доедет до 5-го этажа и остановится на 1 единицу времени для высадки предыдущего пассажира, через 4 единицы времени лифт довезет Петра до 9-го этажа, и через 1 единицу времени Петр выйдет из лифта.

В этой задаче 20 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.

По запросу сообщается результат окончательной проверки на каждом тесте.

Реализуйте на одном из языков программирования алгоритм, представленный на схеме.

В первой строке ввода содержится два целых числа, разделенных пробелом - `S` (`0 ≤ S ≤ 2000`) и `P` (`0 ≤ P ≤ 1000000`).

Вывести два целых числа `I` и `J` через пробел.

22 120

10 12

В этой задаче 10 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.

По запросу сообщается результат окончательной проверки на каждом тесте.

Стелла изучает снежинки, измеряя длину их шести лучей, и собрала уже много данных. Теперь Стелла собирается определить, сколько различных видов снежинок ей удалось обнаружить. Она считает снежинки одинаковыми, если снежинки можно совместить после поворота и/или переворачивания.

Напишите программу, которая поможет Стелле провести классификацию снежинок.

Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 100000`). Далее следует `N` строк, содержащих по 6 целых чисел `a_1\ a_2\ a_3\ a_4\ a_5\ a_6` от 1 до `10^9`, разделенных пробелами – длины лучей снежинок в порядке обхода по часовой стрелке.

Вывести одно целое число – количество различных снежинок, обнаруженных Стеллой.

5
1 2 3 4 5 6
3 4 5 6 1 2
3 2 1 4 5 6
6 5 4 3 2 1
2 3 6 5 4 1

2

Совпадают снежинки 1 и 2 и 4 после поворота или после переворачивания и снежинки 3 и 5 после переворачивания и поворота.

`2\ ≤\ N\ ≤\ 1000`, у всех снежинок `a_1=a_2=a_3=a_4=a_5=a_6`

В этой подзадаче 5 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.

`1000\ <\ N\ ≤\ 100000`, у всех снежинок `a_1=a_2=a_3=a_4=a_5=a_6`

В этой подзадаче 5 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.

В этой подзадаче 5 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.

В этой подзадаче 5 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.

По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач. Внимание! Тест из примера не подходит под ограничения для подзадач 1 и 2, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест, даже если оно рассчитано на решение только подзадач 1 и 2.

Напишите программу, которая в некоторой последовательности целых чисел находит подпоследовательность наименьшей длины, сумма элементов в которой является числом, оканчивающимся на 6 или более нулей (делится без остатка на 1000000).

Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 100000`). Вторая строка ввода содержит `N` целых чисел в диапазоне от 1 до `10^9`, разделенных пробелами.

Вывести два целых числа – количество элементов в подпоследовательности и номер её первого элемента. Если существует несколько вариантов такой подпоследовательности с наименьшей длиной, выведите подпоследовательность с наименьшим номером первого элемента. Если такой подпоследовательности не существует – выведите одно число –1.

6
1 2 701000 299000 1000 999000

2 3

3
1 2 3

-1

`2\ ≤\ N\ ≤\ 100`, числа от 1 до `10^6`

В этой подзадаче 6 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.

В этой подзадаче 6 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.

В этой подзадаче 5 тестов, каждый тест оценивается в 8 баллов. Баллы за каждый тест начисляются независимо.

По запросу сообщается результат окончательной проверки на каждом тесте.

Для сборки компьютера необходимо `T` компонентов различного типа (видеокарта, жесткий диск, монитор и т.д.). В магазине продаются `N` компонентов. Каждый компонент относится к определенному типу и имеет некоторую стоимость и рейтинг по обзорам в журналах.

Напишите программу, определяющую из каких компонентов нужно собрать компьютер, чтобы его стоимость не превышала `B`, в составе были по одному компоненту каждого типа, а суммарный рейтинг использованных компонентов был максимальным.

Первая строка ввода содержит одно целое число – количество типов компонентов `T` (`1\ ≤\ T\ ≤\ 5`). Вторая строка ввода содержит одно целое число – количество компонентов в магазине `N` (`1\ ≤\ N\ ≤\ 1000`). Далее следует `N` строк, содержащих по три целых числа, разделенных пробелами – стоимость `i`-го компонента `C_i` (`1\ ≤\ C_i\ ≤\ 3000`), его рейтинг `R_i` (`1\ ≤\ R_i\ ≤\ 3000`) и его тип `t_i` (`1\ ≤\ t_i\ ≤\ T`). Далее следует строка, содержащая одно целое число – бюджет на покупку компьютера `B` (`1\ ≤\ B\ ≤\ 3000`).

Вывести в первой строке одно целое число – максимальный суммарный рейтинг использованных компонент. Во второй строке вывести `T` целых чисел – `i`-е число означает номер компонента типа `i`, выбранного для сборки. Если существует несколько вариантов с максимальным суммарным рейтингом, то из них вывести вариант с минимальной стоимостью, а среди таких вариантов можно вывести любой. Если не существует варианта сборки компьютера в рамках указанного бюджета, то вывести в первой строке одно число –1

2
5
10 6 1
5 7 1
6 10 2
1 5 1
11 11 2
16

18
2 5

В этой подзадаче 2 теста, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.

В этой подзадаче 4 теста, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.

В этой подзадаче 10 тестов, каждый тест оценивается в 7 баллов. Баллы за каждый тест начисляются независимо.

По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач. Внимание! Тест из примера не подходит под ограничения для подзадачи 1, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест, даже если оно рассчитано на решение только подзадачи 1.

Робот может двигаться по слову и переставлять местами соседние буквы. Для управления роботом составляется программа, содержащая следующие команды:

> – движение вправо;

< – движение влево;

% – поменять местами текущую и следующую букву;

(буква команды1 : команды2) – если робот стоит на указанной букве, то выполнить команды1, иначе выполнить команды2.

В начальный момент робот стоит на первой букве слова. Команда < не выполняется (игнорируется), если робот стоит на первой букве слова, команды > и % не выполняются, если робот стоит на последней букве слова.

Следующая программа для робота (W>>%:>(D:%<)%) превратит слово WORD в WODR, а слово RODW в DROW.

Напишите три программы для превращения некоторого заданного слова, являющегося перестановкой букв W, O, R и D, в слово WORD. Вы должны выслать текстовый файл, содержащий ровно 3 строки. В первой строке нужно написать программу для решения первой подзадачи, во второй строке – для решения второй подзадачи, в третьей строке – для решения третьей подзадачи. Если вы не можете написать программу для решения одной из подзадач, поставьте в соответствующей строке символ - (минус).

В этой подзадаче только 1 тест, слово DROW. Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

В этой подзадаче 4 теста, каждый тест оценивается в 10 баллов. Тесты содержат слова WORD, OWRD, WODR, OWDR в некотором порядке, т.е. могут быть переставлены 1-я и 2-я буквы и 3-я и 4-я буквы слова WORD. Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.

В этой подзадаче 10 тестов, каждый тест оценивается в 5 баллов. Тесты содержат анаграммы слова WORD. Баллы за каждый тест начисляются независимо.

По запросу сообщается результат окончательной проверки для всех подзадач (без разделения на отдельные тесты).