7866.png
ЧЕЛЯБИНСК,ЮУРГУ,ИЕТН

Назад

images/home.png Начало
images/balloon.gif Соревнования
2014

Подразделы

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

Задачи личных соревнований по спортивному программированию 2014

Дата и время

16/11/2024 15:17:56

Авторизация

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

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

print1. Серое королевство (все классы)

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

В Сером королевстве запрещены все цвета. Жители королевства могут использовать только варианты серого цвета от черного до белого. Если рассмотреть цвет с использованием модели RGB, где каждый из трех каналов принимает значение от 0 до 255, то в Сером королевстве разрешены только цвета, у которых разница между значениями в любой паре каналов не превышает 25.
Напишите программу, которая определяет для цвета, заданного в модели RGB, является ли он разрешенным в Сером королевстве.
Первая строка ввода содержит три целых числа в диапазоне от 0 до 255 — значения в каналах R, G и B.
Вывести сообщение ALLOWED, если цвет является разрешенным в Сером королевстве, иначе выведите сообщение FORBIDDEN.

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

120 145 135

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

ALLOWED

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

100 140 135

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

FORBIDDEN

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

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

29754.png
Реализуйте на одном из языков программирования алгоритм, представленный на схеме.
В первой строке ввода содержатся целое число `N` (`1\ ≤\ N\ ≤\ 100`). Далее следует `N` строк, содержащих по одному целому числу в диапазоне от `-1000` до `1000`.
Вывести одно целое число – значение `M` после завершения работы алгоритма.

Пример ввода

4
2
3
-7
4

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

5

print2. Раздел королевства (10-11 класс)

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

Король решил разделить королевство между двумя своими сыновьями. При этом он хочет минимизировать будущие расходы на административное управление новыми королевствами. В королевстве `N` городов. Нужно выбрать два города — столицы королевств, а остальные города разделить между этими королевствами. Так как расходы на управление прямо зависят от расстояния до столицы королевства, то город нужно включать в то королевство, расстояние до столицы которого меньше. При равенстве расстояний до столиц город можно включить в любое из королевств. Будущие столицы нужно выбрать так, чтобы сумма расстояний от столиц до городов, включенных в соответствующее королевство, было минимальным.
Напишите программу, которая определит по координатам городов, какие города нужно сделать столицами новых королевств.
Первая строка ввода содержит одно целое число `N` (`4\ ≤\ N\ ≤\ 100`) – количество городов. Далее следует `N` строк, содержащих по два целых чисел в диапазоне от 0 до 1000 – координаты городов. Все координаты попарно различны.
Вывести в первой строке два целых числа – номера городов, которые нужно сделать столицами. Номера должны быть выведены в порядке возрастания. Если существует несколько вариантов, минимизирующих расходы на управление, то можно вывести любой из них.

Пример ввода

6
0 0
10 0
20 0
0 20
10 20
20 20

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

2 5

print3. Делёж (9 класс)

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

Лиса Алиса и кот Базилио нашли в пещере огромный слиток золота. Хотя они смогли вдвоем приподнять этот слиток, но не смогли вытащить его из пещеры, так как каждый тянул слиток в свою сторону из-за жадности. Вдруг в пещере появилась фея. Она сказала, что слиток весит `2^n` грамм и что она знает заклинание, которое может поделить любой кусок золота на 2 равные части. Это известие обрадовало мошенников, так как лиса Алиса могла унести `a` грамм золота, а кот Базилио – `b` грамм, что в сумме давало ровно `2^n` грамм.
Напишите программу, которая определяет, сколько минимально раз фея должна произнести заклинание, чтобы поделить слиток на куски так, чтобы Алиса и Базилио могли взять из них ровно `a` и `b` грамм соответственно.
Первая строка ввода содержит три целых числа `n` (`2\ ≤\ n\ ≤\ 30`), `a` и `b` (`1\ ≤\ a`, `1\ ≤\ b`, `a+b\ =\ 2^n`).
Вывести одно целое число — сколько минимально раз фея должна произнести заклинание, чтобы поделить золото между мошенниками.

Пример ввода

4 6 10

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

3
Пояснение к примеру: фея должна поделить `2^4=16` грамм на две части по 8 грамм, затем одну из них на две части по 4 грамм, затем одну из этих частей на две части по 2 грамма. Алисе достанется две части весом 4 и 2 грамма, а Базилио — 8 и 2 грамма.

print3. Делёж-2 (10-11 класс)

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

Лиса Алиса и кот Базилио нашли в пещере огромный слиток золота, но они не смогли поднять слиток даже вдвоем. Вдруг в пещере появилась фея. Она сказала, что слиток весит `2^n` грамм и что она знает заклинание, которое может поделить любой кусок золота на 2 равные части. Лиса Алиса сказала, что она может унести `a` грамм золота, а кот Базилио – `b` грамм. Естественно, каждый из них хочет взять ровно столько золота, сколько может унести, а остаток золота – `2^n\ -\ a\ -\ b` грамм  – фея может забрать себе за работу по дележу.
Напишите программу, которая определяет, сколько минимально раз фея должна произнести заклинание, чтобы поделить слиток на куски так, чтобы Алиса и Базилио могли взять из них ровно `a` и `b` грамм соответственно.
Первая строка ввода содержит три целых числа `n` (`2\ ≤\ n\ ≤\ 30`), `a` и `b` (`1\ ≤\ a`, `1\ ≤\ b`, `a+b\ <\ 2^n`).
Вывести одно целое число — сколько минимально раз фея должна произнести заклинание, чтобы поделить золото между мошенниками.

Пример ввода

5 8 12

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

4
Пояснение к примеру: фея должна поделить 32 грамма на две части по 16 грамм, затем каждую из них на две части по 8 грамм, и одну из этих частей на две части по 4 грамма. Лиса Алиса берет один кусок 8 грамм, кот Базилио – два куска весом 8 и 4 грамма, фее остаются два куска весом 8 и 4 грамма.

print3. Робот-маляр (7-8 класс)

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

Вам нужно написать программу для робота-маляра, который должен покрасить забор по образцу, заданному цветами двух первых досок забора. Остальные доски забора не окрашены. Всего в заборе от 4 до 100 досок.
Программа состоит из набора инструкций следующего вида:
состояние_робота текущий_цвет новый_цвет направление новое_состояние
где состояние_робота и новое_состояние – числа от 0 до 9, текущий_цвет и новый_цвет – символ R (красный), G (зеленый), B (синий), ? (неокрашенная доска, только для текущий_цвет) или _ (любой текущий цвет или отсутствие окраски, сохранение текущего состояния доски), направление – символ < (переход к предыдущей доске забора) или > (переход к следующей доске забора). Параметры инструкции отделяются друг от друга ровно одним пробелом.
В начале работы робот находится на первой доске забора и имеет состояние 0. Далее на каждом шаге он ищет, начиная с первой строки, инструкцию в программе, соответствующую текущему состоянию робота и текущему цвету доски. Если такой инструкции нет, то робот прекращает работу. Если инструкция найдена, робот перекрашивает доску забора в новый_цвет (если новый цвет – символ _, то робот оставляет доску без изменений), изменяет свое состояние на новое_состояние и переходит к предыдущей или следующей доске забора, в зависимости от параметра направление. Если робот выходит при этом за пределы забора, то он прекращает работу.
Пример программы для робота, который распознает образцы RR и RB:
0 R _ > 0
0 B _ > 1
0 ? R > 0
1 ? R > 2
2 _ B > 1
25 баллов вы можете получить за модификацию этой программы, которая может обработать все образцы из красного и синего цветов: RR, RB, BB и BR.
100 баллов вы можете получить за универсальную программу, которая может обработать все 9 образцов из красного, зеленого и синего цветов.
В качестве решения вы должны выслать программу для робота.

print4. Пеппи Длинныйчулок (7-9 класс)

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

У Пеппи есть `N` чулок, среди которых нет двух одинаковых по расцветке, и, более того, чулки отличаются друг от друга по длине. Каждый день Пеппи выбирает новую пару чулок среди `N*(N-1)/2` вариантов. При этом она не хочет повторяться, и, после того как все варианты будут опробованы, она решила выбросить старые чулки и купить новый набор. Чтобы не допустить случайного повторения она решила упорядочить варианты в порядке неубывания разницы длин чулок в паре, а при совпадении разницы – в порядке возрастания длины чулка меньшей длины из пары. В `K`-й день она решила надевать `K`-й вариант пары чулок из этого упорядоченного списка.
Напишите программу, которая поможет Пеппи выбрать, какую пару чулок нужно надеть в `K`-й день, если следовать указанному выше правилу.
Первая строка ввода содержит два целых числа – количество чулок `N` (`3\ ≤\ N\ ≤\ 1000`) и номер дня `K` (`1\ ≤\ K\ ≤\ N*(N-1)/2`). Во второй строке содержится `N` целых чисел в диапазоне от 1 до `10^9` в порядке возрастания – длины чулок.
Вывести два целых числа через пробел – длины чулок, которые должна выбрать Пеппи в `K`-й день, сначала длина меньшего чулка в паре, затем большего.

Пример ввода

4 5
1 7 8 12

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

1 8
Пояснение к примеру: Пеппи будет надевать чулки в следующем порядке (7,8) (8,12) (7,12) (1,7) (1,8) (1,12).
Характеристика тестов к задаче: в 50% тестов `N\ ≤\ 50`.

print4. Пеппи Длинныйчулок-2 (10-11 класс)

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

У Пеппи есть `N` чулок, среди которых нет двух одинаковых по расцветке, и, более того, чулки отличаются друг от друга по длине. Каждый день Пеппи выбирает новую пару чулок среди `N*(N-1)/2` вариантов. При этом она не хочет повторяться, и, после того как все варианты будут опробованы, она решила выбросить старые чулки и купить новый набор. Чтобы не допустить случайного повторения она решила упорядочить варианты в порядке неубывания разницы длин чулок в паре, а при совпадении разницы – в порядке возрастания длины чулка меньшей длины из пары. В `K`-й день она решила надевать `K`-й вариант пары чулок из этого упорядоченного списка.
Напишите программу, которая поможет Пеппи выбрать, какую пару чулок нужно надеть в `K`-й день, если следовать указанному выше правилу.
Первая строка ввода содержит два целых числа – количество чулок `N` (`3\ ≤\ N\ ≤\ 100 000`) и номер дня `K` (`1\ ≤\ K\ ≤\ N*(N-1)/2`). Во второй строке содержится `N` целых чисел в диапазоне от 1 до `10^9` в порядке возрастания – длины чулок.
Вывести два целых числа через пробел – длины чулок, которые должна выбрать Пеппи в `K`-й день, сначала длина меньшего чулка в паре, затем большего.

Пример ввода

4 5
1 7 8 12

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

1 8
Пояснение к примеру: Пеппи будет надевать чулки в следующем порядке (7,8) (8,12) (7,12) (1,7) (1,8) (1,12).
Характеристика тестов к задаче: в 25% тестов `N\ ≤\ 50`, в 50% тестов `N\ ≤\ 1000`.
loading