Задачи очного тура отборочных командных соревнований школьников

A. Лишний гном

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

Робопёс услышал подозрительный шум и оглянулся – всё выглядело как обычно, но количество садовых гномов, кажется, изменилось. Садовые гномы обычно стояли по росту, при этом рост каждого гнома был ровно на 1 больше роста гнома, стоящего перед ним в ряду. Но сейчас порядок был нарушен. Лишний гном постарался спрятаться среди гномов, но его выдавал рост.

Напишите программу, которая поможет робопсу найти лишнего гнома.

Первая строка ввода содержит одно целое число – количество гномов `N` (`3\ ≤\ N\ ≤\ 100`). Во второй строке содержится `N` целых чисел в диапазоне от 1 до 1000 – рост гномов слева направо. Эта последовательность образуется как подпоследовательность ряда натуральных чисел, в которую вставляется одно число. Гарантируется, что лишний гном определяется однозначно (например, в последовательности нет одинаковых чисел подряд).

Вывести одно целое число – номер лишнего гнома.

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

5 
4 5 6 3 7

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

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

3
9 5 6

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

B. Стелс-миссия

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

Робот-шпион пытается проникнуть на охраняемый секретный объект. Два прожектора освещают путь к объекту. Время от времени свет прожекторов перемещается на другие участки и тогда робот может приблизиться к объекту. Но пока хотя бы один прожектор освещает путь к объекту, робот прячется в тени ящиков или маскируется под предметы в саду. Первый прожектор освещает путь `A` секунд, затем `B` секунд освещает другие участки, затем снова `A` секунд – путь, затем `B` секунд – другие участки и так далее. Второй прожектор работает аналогично, но освещает путь `C` секунд, а другие участки – `D` секунд.

Робот только что переместился и притворился садовым гномом. В этот момент свет обоих прожекторов переместился на путь к объекту. Роботу нужно дождаться следующего интервала темноты и вычислить продолжительность этого интервала, чтобы выбрать следующее укрытие.

Напишите программу, которая определяет, через сколько секунд и на какое время путь к объекту не будет освещен ни одним прожектором.

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

Вывести два целых числа – через сколько секунд и на какое время путь к объекту не будет освещен ни одним прожектором.

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

6 5 3 3

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

9 2

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

100 1 99 1

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

10099 1

C. Битва роботов

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

Робот-детектив расследует битву роботов, произошедшую между роботами двух разных моделей. Роботы отличаются формой корпуса, а также, возможно, количеством рук и ног. У первой модели `A_1` рук и `B_1` ног, у второй – `A_2` рук и `B_2` ног. Роботы сражались, пока не потеряли все конечности. На месте битвы остались `A_s` рук и `B_s` ног. Известно, что с каждой стороны сражалось ненулевое количество участников.

Напишите программу, которая определяет, сколько роботов каждой модели участвовали в битве.

Первая строка ввода содержит одно целое число – количество тестов `N` (`1\ ≤\ N\ ≤\ 100`). Далее следует `N` строк, каждая строка содержит шесть целых чисел в диапазоне от 1 до 10000 – количество рук и ног для каждой модели роботов `A_1`, `B_1`, `A_2`, `B_2` и обнаруженное количество рук и ног `A_s` и `B_s`.

Для каждого теста вывести на отдельной либо два целых числа – количество роботов первой модели и количество роботов второй модели, либо символ ? (вопрос), если однозначно определить количество участников драки с каждой стороны не удается или данные не соответствуют какому-либо варианту.

Пример ввода

3
5 1 3 2 9 4
1 4 1 2 5 16
1 2 3 6 8 16

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

?
3 2
?

D. Сбой в программе

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

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

F – двигаться вперед на одну единицу;
L – поворот налево на 90 градусов;
R – поворот направо на 90 градусов.

Перед выполнением программы робот находится в начале координат (0,0) и смотрит в направлении оси Y (вверх). Компьютерный вирус заменил одну из команд на другую, и теперь робот не может добраться до места назначения.

Напишите программу, которая поможет исправить ошибку в программе.

Первая строка ввода содержит два целых числа в диапазоне от –100000 до 100000 – координаты места назначения. Вторая строка содержит последовательность букв F, L и R длиной от 1 до 100000 – программу с одной ошибочной командой.

Вывести одно целое число и букву F, L и R – номер ошибочной команды в программе и команду, на которую её нужно заменить, чтобы робот смог добраться до места назначения. Если существует несколько вариантов замены, то выведите вариант, в котором заменяемая команда находится в программе раньше.

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

3 2
FRFFLFFLFRF

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

8 R

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

-1 1
RLF

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

1 F

E. Количество цифр

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

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

Напишите программу, которая вычисляет количество цифр в числе `2^a*5^b`.

Первая строка ввода содержит два целых числа – `a` и `b` (`0\ ≤\ a,\ b\ ≤\ 10^6`).

Вывести одно целое число – количество цифр.

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

7 3

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

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

3 3

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

Пояснение к примеру 1: `2^7*5^3=128*125=16000`, количество цифр в числе равно 5.

F. Доставка почты

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

Робот-почтальон разносит почту по улице из `N` домов, пронумерованных последовательно числами от 1 до `N`. Здание почтового отделения находится слева от дома 1. Каждый день все дома получают по одному письму, но робот не сортирует почту перед доставкой, а разносит письма в том порядке, в котором они лежат в стопке. Обычно после прочтения адреса на верхнем письме в стопке робот записывает в протокол выбранное направление движения и расстояние от своего текущего местоположения до дома, указанного в адресе. Но на этот раз из-за поломки пройденное расстояние не было записано в протоколе, только информация о направлении движения.

Напишите программу, которая определяет по протоколу порядок, в котором робот разносил почту.

Первая строка ввода содержит одно целое число – количество домов `N` (`2\ ≤\ N\ ≤\ 10^5`). Вторая строка содержит последовательность из `N` символов R и L, которая начинается с символа R – протокол движения робота.

Вывести перестановку чисел от 1 до `N`, соответствующую протоколу движения робота. Из всех возможных перестановок нужно вывести лексикографически наименьшую.

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

3
RLR

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

2 1 3

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

6
RRLLRL

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

1 4 3 2 6 5

G. Восстановление строки

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

Робот должен построить строку `s` из 0 и 1, для которой `f(0,0)=A`, `f(0,1)=B`, `f(1,0)=C`,`f(1,1)=D`, где функция `f(x,y)` определяется как количество пар `(i,j)` таких, что `i<j` и `s_i=x` и `s_j=y`. Например, для строки из `N` нулей `f(0,0)=(N*(N-1))/2`.

Первая строка ввода содержит четыре целых числа `A,\ B,\ C,\ D` в диапазоне от 0 до `10^9`.

Вывести строку, для которой выполняются указанные свойства. Если существует несколько вариантов таких строк, то можно вывести любой из них. Если такой строки не существует, то вывести сообщение "NO SOLUTION".

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

3 2 4 1

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

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

4 0 0 4

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

NO SOLUTION

H. 2018

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

На листе бумаги нанесены несколько точек с целочисленными координатами. Робот-художник соединяет отрезком все пары точек, расстояние между которыми равно точно 2018.

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

Первая строка ввода содержит одно целое число – количество точек `N` (`1\ ≤\ N\ ≤\ 10^5`). Далее следует `N` строк, содержащих по два целых числа в диапазоне от 0 до `2^31` – координаты точек. Все точки различны.

Вывести одно целое число – количество отрезков.

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

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

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

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

I. Головоломка

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

Для проверки интеллекта роботов используется головоломка, показанная на рисунке, в которой цифры от 1 до 7 располагаются в ячейках, а одна из ячеек свободна. Необходимо переставить цифры, используя свободную ячейку, чтобы цифры расположились так, как показано на рисунке. Перемещение буквы в свободную ячейку возможно, только если ячейки соединены линией.

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

Первая строка ввода содержит одно целое число – количество тестов `N` (`1\ ≤\ N\ ≤\ 40000`). Далее следует `N` строк, содержащих перестановку чисел 0, 1, 2, 3, 4, 5, 6, 7 – начальную позицию. Числа перечисляются в порядке чтения слева направо, сверху вниз. Число 0 обозначает пустую ячейку.

Для каждой начальной позиции вывести на отдельной строке сначала минимальное количество ходов, затем саму последовательность ходов – последовательность цифр от 1 до 7, которые нужно перемещать на очередном ходе в свободную ячейку. Если существует несколько минимальных вариантов для последовательности ходов, то можно вывести любой из них. Гарантируется, что все начальные позиции для головоломки имеют решение.

Пример ввода

3
1 2 3 4 0 5 6 7
2 1 3 4 0 5 6 7
0 1 2 3 4 5 6 7

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

0
7 5321235
18 213451323154213124

J. Ленивый кот

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

Робокот должен поймать мышей прежде, чем они спрячутся в норках. Для каждой мыши известны её координаты и время до исчезнования. В начальный момент времени кот находится в начале координат (0,0) и может начать двигаться с любой скоростью `V_0` по направлению к любой из мышей. Поймав её, он выбирает любую из оставшихся мышей и мгновенно меняет направление движения, но при этом уже не может изменять скорость, более того – после поимки очередной мыши из-за роста массы скорость кота падает на коэффициент `D`. Например, если до поимки мыши скорость была `V`, то после этого он будет двигаться со скоростью `D*V`, и скорость кота перед поимкой последней мыши будет равна `D^(N-1)*V_0`.

Робокот хочет рассчитать минимальную начальную скорость, которая позволит ему поймать всех мышей.

Первая строка ввода содержит одно целое число – количество мышей `N` (`1\ ≤\ N\ ≤\ 12`). Следующие `N` строк содержат три целых числа – координаты мыши `x_i,\ y_i` (`-1000\ ≤\ x_i,\ y_i\ ≤\ 1000`) и время до исчезновения мыши `t_i` (`1\ ≤\ t_i\ ≤\ 10000`). Последняя строка содержит одно вещественное число с двумя десятичными знаками – коэффициент уменьшения скорости кота после поедания мыши `D` (`0.75\ ≤\ D\ ≤\ 0.99`).

Вывести одно число – минимальную начальную скорость робокота с относительной точностью 0.001 (т.е. если `A` – точный ответ, а `X` – ваш ответ, то `|X-A|<0.001*A`).

Пример ввода

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

1.000

K. Очень сложная задача

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

Задача, которую не может решить ни один робот, формулируется следующим образом: "Найти все разложения заданного натурального числа `Z` на пару слагаемых `X` и `Y` таких, что числа `Z`, `X` и `Y` не имеют общих цифр и `X\ <\ Y`".

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

Первая строка ввода содержит одно целое число `Z` (`1\ ≤\ Z\ ≤\ 10^{18}`).

В первой строке вывести одно число – количество разложений числа `Z`. Далее вывести первые 5000 разложений числа `Z`, если они существуют. Разложения на пару слагаемых нужно выводить в порядке возрастания значения `X`.

Пример ввода

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

28/10/2018	Очный тур региональных отборочных командных соревнований для школьников (H)
02/12/2023	Марафон 80 задач, 7 этап (G)

Назад

Подразделы

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

Дата и время

Авторизация

Задачи очного тура отборочных командных соревнований школьников

A. Лишний гном

B. Стелс-миссия

C. Битва роботов

D. Сбой в программе

E. Количество цифр

F. Доставка почты

G. Восстановление строки

H. 2018

I. Головоломка

J. Ленивый кот

K. Очень сложная задача