Начало
Соревнования
Задачи 1 тура областной олимпиады по информатике 2013
1. Кастинг
Вывод формулыОлимпиадные задачи на русском языке
| 19/01/2013 | Областная олимпиада школьников по информатике. I тур. (1) |
| 19/07/2019 | Лето 2019 - 9 (командное) (B) |
| 17/07/2020 | Лето 2020 - 8 (командное) (B) |
Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение 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
3
Пример ввода 2
1 5 3 4 5
Пример вывода 2
2
Пояснения к примерам
В первом примере, поскольку высоких актеров всего трое, то на главную роль не может подойти больше трех человек.
Во втором примере все актеры – блондины и все, кроме одного, – голубоглазые. Тогда среди трех высоких актеров найдутся хотя бы два голубоглазых (и, естественно, они будут блондинами). Следовательно, минимум два актера точно подойдут на главную роль в новом спектакле.
Система оценивания
Правильные решения для тестов, в которых требуется найти минимальное количество актеров, будут оцениваться из 50 баллов.
Правильные решения для тестов, в которых требуется найти максимальное количество актеров, будут оцениваться из 50 баллов.
Несмотря на выделение отдельных групп тестов для минимального и максимального количества артистов, на окончательную проверку будут приниматься только решения, правильно работающие для всех тестов из условия задачи.
Источник: региональный этап Всероссийской олимпиады по информатике 2012/2013, http://neerc.ifmo.ru/school/ 2. Города
Сокращение перебора с помощью идеиОлимпиадные задачи на русском языке
| 19/01/2013 | Областная олимпиада школьников по информатике. I тур. (2) |
Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Юный программист решил придумать собственную игру. Игра происходит на поле
размером `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
11111 12221 12221 11111 11111
Система оценивания
Правильные решения для тестов, в которых всего два города, будут оцениваться из 40 баллов.
Несмотря на выделение отдельной группы тестов с двумя городами, на окончательную проверку будут приниматься только решения, правильно работающие также для всех тестов из условия задачи.
Источник: региональный этап Всероссийской олимпиады по информатике 2012/2013, http://neerc.ifmo.ru/school/ 3. A + B = C
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 19/01/2013 | Областная олимпиада школьников по информатике. I тур. (3) |