Подразделы

Другие разделы

Дата и время

13/10/2024 15:34:36

Авторизация

Имя:
Пароль:
Зарегистрироваться
Восстановить пароль
 

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

print1. Лифт (все классы)

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

35612.jpg
Петру необходимо попасть с этажа `A` на этаж `B`. Для вызова лифта на всех этажах офисного здания, кроме первого и последнего, есть две кнопки – для перемещения вниз и перемещения вверх. В тот момент, когда Петр нажал нужную кнопку вызова, лифт находился на этаже `C` и вез одного пассажира на этаж `D`. Если лифт проезжает мимо этажа, на котором нажата кнопка вызова, и лифт движется в подходящем направлении, то лифт останавливается, чтобы посадить дополнительного пассажира. Лифт перемещается между соседними этажами за одну единицу времени, также одну единицу времени занимает остановка лифта на этаже для высадки или посадки пассажиров.
Напишите программу, вычисляющую, через сколько времени Петр доберется до этажа `B`, при условии, что никто больше не будет вызвать лифт.
Первая строка ввода содержит четыре целых числа `A`, `B`, `C` и `D`, разделенных одним пробелом (`1\ ≤\ A,\ B,\ C,\ D\ ≤\ 20`, `A≠B`, `C≠D`, `A≠C`).
Вывести одно целое число – количество единиц времени от момента вызова лифта до момента, когда Петр выйдет из лифта на этаже `B`.

Пример ввода 1

3 9 2 5

Пример вывода 1

10

Пример ввода 2

3 9 5 2

Пример вывода 2

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

print2. Алгоритм (7-9 классы)

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

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

Пример ввода

22 120

Пример вывода

10 12
Система оценки
В этой задаче 10 тестов, каждый тест оценивается в 10 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.

print2. Классификация снежинок (10-11 классы)

Ограничения: время – 1000ms/2000ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (9)

Стелла изучает снежинки, измеряя длину их шести лучей, и собрала уже много данных. Теперь Стелла собирается определить, сколько различных видов снежинок ей удалось обнаружить. Она считает снежинки одинаковыми, если снежинки можно совместить после поворота и/или переворачивания.
Напишите программу, которая поможет Стелле провести классификацию снежинок.
Первая строка ввода содержит одно целое число `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 после переворачивания и поворота.
Система оценки и описание подзадач
Подзадача 1 (25 баллов)
`2\ ≤\ N\ ≤\ 1000`, у всех снежинок `a_1=a_2=a_3=a_4=a_5=a_6`
В этой подзадаче 5 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (25 баллов)
`1000\ <\ N\ ≤\ 100000`, у всех снежинок `a_1=a_2=a_3=a_4=a_5=a_6`
В этой подзадаче 5 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 3 (25 баллов)
`2\ ≤\ N\ ≤\ 1000`
В этой подзадаче 5 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 4 (25 баллов)
`1000\ <\ N\ ≤\ 100000`
В этой подзадаче 5 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач. Внимание! Тест из примера не подходит под ограничения для подзадач 1 и 2, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест, даже если оно рассчитано на решение только подзадач 1 и 2.

print3. Подпоследовательность (все классы)

Ограничения: время – 300ms/600ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Напишите программу, которая в некоторой последовательности целых чисел находит подпоследовательность наименьшей длины, сумма элементов в которой является числом, оканчивающимся на 6 или более нулей (делится без остатка на 1000000).
Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 100000`). Вторая строка ввода содержит `N` целых чисел в диапазоне от 1 до `10^9`, разделенных пробелами.
Вывести два целых числа – количество элементов в подпоследовательности и номер её первого элемента. Если существует несколько вариантов такой подпоследовательности с наименьшей длиной, выведите подпоследовательность с наименьшим номером первого элемента. Если такой подпоследовательности не существует – выведите одно число –1.

Пример ввода 1

6
1 2 701000 299000 1000 999000

Пример вывода 1

2 3

Пример ввода 2

3
1 2 3

Пример вывода 2

-1
Система оценки и описание подзадач
Подзадача 1 (30 баллов)
`2\ ≤\ N\ ≤\ 100`, числа от 1 до `10^6`
В этой подзадаче 6 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (30 баллов)
`100\ <\ N\ ≤\ 10000`
В этой подзадаче 6 тестов, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 3 (40 баллов)
`10000\ <\ N\ ≤\ 100000`
В этой подзадаче 5 тестов, каждый тест оценивается в 8 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте.

print4. Сборка компьютера (9-11 классы)

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Для сборки компьютера необходимо `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
Система оценки и описание подзадач
Подзадача 1 (10 баллов)
`T=1`
В этой подзадаче 2 теста, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 2 (20 баллов)
`T=2`
В этой подзадаче 4 теста, каждый тест оценивается в 5 баллов. Баллы за каждый тест начисляются независимо.
Подзадача 3 (70 баллов)
`3\ ≤\ T\ ≤\ 5`
В этой подзадаче 10 тестов, каждый тест оценивается в 7 баллов. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки на каждом тесте для всех подзадач. Внимание! Тест из примера не подходит под ограничения для подзадачи 1, но решение принимается на проверку только в том случае, если оно выводит правильный ответ на тесте из примера. Решение должно выводить правильный ответ на тест, даже если оно рассчитано на решение только подзадачи 1.

print4. Слово и робот (7-8 классы)

Ограничения: время – 200ms/500ms, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Робот может двигаться по слову и переставлять местами соседние буквы. Для управления роботом составляется программа, содержащая следующие команды:
> – движение вправо;
< – движение влево;
% – поменять местами текущую и следующую букву;
(буква команды1 : команды2) – если робот стоит на указанной букве, то выполнить команды1, иначе выполнить команды2.
В начальный момент робот стоит на первой букве слова. Команда < не выполняется (игнорируется), если робот стоит на первой букве слова, команды > и % не выполняются, если робот стоит на последней букве слова.
Следующая программа для робота (W>>%:>(D:%<)%) превратит слово WORD в WODR, а слово RODW в DROW.
Напишите три программы для превращения некоторого заданного слова, являющегося перестановкой букв W, O, R и D, в слово WORD. Вы должны выслать текстовый файл, содержащий ровно 3 строки. В первой строке нужно написать программу для решения первой подзадачи, во второй строке – для решения второй подзадачи, в третьей строке – для решения третьей подзадачи. Если вы не можете написать программу для решения одной из подзадач, поставьте в соответствующей строке символ - (минус).
Система оценки и описание подзадач
Подзадача 1 (10 баллов)
В этой подзадаче только 1 тест, слово DROW. Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 2 (40 балла)
В этой подзадаче 4 теста, каждый тест оценивается в 10 баллов. Тесты содержат слова WORD, OWRD, WODR, OWDR в некотором порядке, т.е. могут быть переставлены 1-я и 2-я буквы и 3-я и 4-я буквы слова WORD. Баллы за подзадачу начисляются только в случае, если все тесты успешно пройдены.
Подзадача 3 (50 баллов)
В этой подзадаче 10 тестов, каждый тест оценивается в 5 баллов. Тесты содержат анаграммы слова WORD. Баллы за каждый тест начисляются независимо.
По запросу сообщается результат окончательной проверки для всех подзадач (без разделения на отдельные тесты).
loading