Подразделы

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

Дата и время

16/11/2024 15:17:44

Авторизация

Задачи 1 тура областной олимпиады по информатике 2013

1. Кастинг

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

В театре работает `n` актеров. Известно, что среди них `a` – высоких, `b` – голубоглазых и `с` – блондинов. Для главной роли в новом спектакле режиссеру требуется только один высокий голубоглазый блондин. Чтобы спланировать свое время для беседы с каждым таким артистом из труппы театра, режиссеру необходимо узнать, какое максимальное или какое минимальное количество артистов из работающих в театре подходит для этой роли.

Требуется написать программу, которая по заданным числам `n`, `a`, `b` и `с` определяет минимальное или максимальное количество актеров, с которыми режиссер должен переговорить.

Формат входного файла

Первая строка входного файла содержит одно число, которое задает, минимальное или максимальное количество актеров необходимо найти в данном тесте. Это число может принимать следующие значения:

1, если в данном тесте требуется определить минимальное количество актеров;
2, если в данном тесте требуется определить максимальное количество актеров.

Вторая строка входного файла содержит разделенные пробелами четыре целых числа: `n`, `a`, `b`, `с` (`1\ ≤\ n\ ≤\ 10000`, `0\ ≤\ a\ ≤\ n`, `0\ ≤\ b\ ≤\ n`, `0\ ≤\ c\ ≤\ n`).

Формат выходного файла

Выходной файл должен содержать одно число – минимальное или максимальное (в зависимости от входных данных) количество актеров, которые могут претендовать на главную роль в новом спектакле.

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

2
5 3 4 5

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

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

1
5 3 4 5

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

Пояснения к примерам

В первом примере, поскольку высоких актеров всего трое, то на главную роль не может подойти больше трех человек.

Во втором примере все актеры – блондины и все, кроме одного, – голубоглазые. Тогда среди трех высоких актеров найдутся хотя бы два голубоглазых (и, естественно, они будут блондинами). Следовательно, минимум два актера точно подойдут на главную роль в новом спектакле.

Система оценивания

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

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

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

Источник: региональный этап Всероссийской олимпиады по информатике 2012/2013, http://neerc.ifmo.ru/school/

2. Города

Юный программист решил придумать собственную игру. Игра происходит на поле размером `N\ times\ N` клеток, в некоторых клетках которого расположены города (каждый город занимает одну клетку; в каждой клетке может располагаться не более одного города). Всего должно быть чётное количество городов.

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

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

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

Формат входного файла

Первая строка входного файла содержит одно целое положительное число `N`, задающее размер игрового поля (`2\ ≤\ N\ ≤\ 50`).

Последующие `N` строк содержат по `N` заглавных латинских букв (без пробелов), кодирующих соответствующие клетки игрового поля: ‘C’ обозначает клетку, занятую городом, ‘D’ – пустую клетку. Гарантируется, что на поле есть хотя бы два города и всего их четное число.

Формат выходного файла

Выходной файл должен содержать `N` строк по `N` цифр (без пробелов) в каждой, кодирующих соответствующие клетки. Цифра 1 обозначает, что данная клетка принадлежит первому государству, цифра 2 – данная клетка принадлежит второму государству.

Если решений несколько, необходимо вывести любое из них.

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

3
DDD
DDC
DDC

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

222
212
211

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

5
DDDDD
CDCDC
DCCDC
DDDDD
DDDDD

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

Система оценивания

Правильные решения для тестов, в которых всего два города, будут оцениваться из 40 баллов.

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

Источник: региональный этап Всероссийской олимпиады по информатике 2012/2013, http://neerc.ifmo.ru/school/

3. A + B = C

Часто для пробного тура на различных олимпиадах по информатике предлагается задача "A + B", в которой по заданным целым числам `A` и `B` требуется найти их сумму.

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

Пусть председатель жюри выбрал число `C`, запись которого состоит из `n` десятичных цифр и не начинается с нуля. Теперь он хочет подобрать такие целые положительные числа `A` и `B`, чтобы их сумма была равна `C`, и запись каждого из них также состояла из `n` десятичных цифр и не начиналась с нуля. В дополнение к этому председатель жюри старается подобрать такие числа `A` и `B`, чтобы каждое из них было красивым. Красивым в его понимании является число, запись которого не содержит двух одинаковых подряд идущих цифр. Например, число 1272 считается красивым, а число 1227 — нет.

Требуется написать программу, которая для заданного натурального числа `C` вычисляет количество пар красивых положительных чисел `A` и `B`, сумма которых равна `C`. Поскольку количество пар красивых чисел может быть большим, необходимо вывести остаток от деления этого количества на число `10^9+7`.

Формат входного файла

Первая строка входного файла содержит одно целое положительное число `C`. Число `C` не начинается с нуля. Количество цифр в записи числа `С` не превышает 10000.

Формат выходного файла

Выходной файл должен содержать одно целое число — остаток от деления количества искомых пар красивых чисел `A` и `B` на число `10^9+7`.

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

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

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

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

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

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

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

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

Пояснения к примерам

Число 22 можно представить в виде суммы двузначных чисел тремя способами: 10 + 12, 11 + 11, 12 + 10. Способ 11 + 11 не подходит, поскольку число 11 не является красивым. Следовательно, ответ для числа 22 равен 2.

Число 200 можно представить в виде суммы трехзначных чисел единственным способом: 100 + 100. Этот способ не подходит, поэтому ответ для числа 200 равен 0.

Число 1000 нельзя представить в виде суммы четырехзначных чисел, поэтому ответ для числа 1000 аналогично равен 0.

Система оценивания

Правильные решения для тестов, в которых `1\ ≤\ C\ ≤\ 999` (`1\ ≤\ n\ ≤\ 3`), будут оцениваться из 25 баллов.

Правильные решения для тестов, в которых `1\ ≤\ C\ ≤\ 999\ 999` (`1\ ≤\ n\ ≤\ 6`), будут оцениваться из 50 баллов.

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

Источник: региональный этап Всероссийской олимпиады по информатике 2012/2013, http://neerc.ifmo.ru/school/

4. Березовая аллея

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

На краю деревни растет старая березовая аллея. Аллея имеет форму прямой полосы шириной `W` метров. Вдоль левой стороны аллеи растет `N` берез, а вдоль правой — `M` берез, при этом `i`-я береза с левой стороны аллеи находится на расстоянии `a_i` метров от начала аллеи, а `j`-я береза с правой стороны — на расстоянии `b_j` метров от начала аллеи.

Отдыхая в деревне прошедшим летом, один юный информатик обнаружил, что кору берез стали грызть зайцы. Чтобы защитить деревья от зайцев, мальчик решил окружить березы красной лентой (зайцы не любят красный цвет и не станут заходить на огражденную лентой территорию). К сожалению, в его распоряжении оказалась только лента длиной `L` метров, которую, к тому же, нельзя было разрезать. Единственное, что можно было делать в этом случае — окружить этой лентой как можно больше берез. При этом, чтобы сохранить аллею, необходимо окружить на каждой стороне аллеи хотя бы одну березу.

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

Формат входного файла

Первая строка входного файла содержит два разделенных пробелом целых числа: длину ленты `L` и ширину аллеи `W` (`1\ ≤\ L\ ≤\ 2*10^5`, `1\ ≤\ W\ ≤\ 10^4`).

Вторая и третья строки описывают березы вдоль левой стороны аллеи. Вторая строка содержит число `N` — количество берез (`1\ ≤\ N\ ≤\ 2000`), а третья строка содержит `N` различных целых чисел `a_1,\ a_2,\ …,\ a_N`, заданных по возрастанию (`0\ ≤\ a_i\ ≤\ 10^5`).

Четвертая и пятая строки описывают березы вдоль правой стороны аллеи. Четвертая строка содержит число `M` — количество берез (`1\ ≤\ M\ ≤\ 2000`), а пятая строка содержит `M` различных целых чисел `b_1,\ b_2,\ …,\ b_M`, заданных по возрастанию (`0\ ≤\ b_i\ ≤\ 10^5`).

Формат выходного файла

Выходной файл должен содержать одно целое число: максимальное количество берез, которое можно оградить заданной лентой.

Гарантируется, что если максимальное число берез, которое можно оградить лентой длины `L`, равно `X`, то нет способа оградить `(X+1)` березу лентой длины `(L\ +\ 10^{-5})`.

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

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

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

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

Пояснения к примерам

В первом примере можно, например, оградить березы способом, указанным на рисунке ниже.

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

Система оценивания

Правильные решения для тестов, в которых `1\ ≤\ (N+M)\ ≤\ 50`, будут оцениваться из 30 баллов.

Правильные решения для тестов, в которых `1\ ≤\ (N+M)\ ≤\ 500`, будут оцениваться из 60 баллов.

Источник: региональный этап Всероссийской олимпиады по информатике 2012/2013, http://neerc.ifmo.ru/school/

19/01/2013	Областная олимпиада школьников по информатике. I тур. (1)
19/07/2019	Лето 2019 - 9 (командное) (B)
17/07/2020	Лето 2020 - 8 (командное) (B)

Назад

Подразделы

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

Дата и время

Авторизация

Задачи 1 тура областной олимпиады по информатике 2013

1. Кастинг

2. Города

3. A + B = C

4. Березовая аллея