Назад
 Начало |
 Соревнования |
| 2013 |
Подразделы
Другие разделы
| Задачи Южно-Уральского командного чемпионата 2013 |
| Задачи отборочных командных соревнований школьников 2013 |
| Задачи муниципального этапа олимпиады школьников по информатике 2013 |
Дата и время
25/04/2024 09:50:57
Задачи очного тура личного первенства 2013
A. Пираты!
Поиск в ширину (BFS)Олимпиадные задачи на русском языке
| 05/10/2013 | Личное первенство Южного Урала (A) |
| 02/07/2018 | Лето 2018 - 4 (D) |
| 06/07/2020 | Лето 2020 - 3 (D) |
| 09/12/2023 | Марафон 80 задач, 8 этап (E) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
В Карибском море появились пираты, которые на быстроходных катерах брали на абордаж торговые суда, а
после нападения скрывались среди многочисленных коралловых островков. Инспектор Клузо хочет
определить местонахождение логова пиратов, используя информацию о местах нападений и дальности хода катера.
Напишите программу, которая проанализирует карту с отметками о местах нападений пиратов и
найдет область, в которой нужно искать логово пиратов.
В первой строке ввода заданы три целых числа: размеры карты `N`, `M` и максимальное расстояние от логова до места
нападения `K` (`2\ ≤\ N,\ M,\ K\ ≤\ 100`). Каждая из следующих `N` строк содержит `M` символов. Символ '.'
обозначает клетку с водой на карте, символ '#' – клетку с сушей, а символ '*' – клетку с водой,
где произошло нападение. Гарантируется, что на карте отмечено не менее 1 и не более 100 мест нападения.
При решении задачи будем считать, что катер может двигаться из клетки в клетку только по горизонтали или
вертикали и не может заплывать в клетку с сушей или выходить за пределы карты.
Вывести карту, где символом '?' отмечены клетки, из которых до всех мест нападения катеру нужно
сделать не более `K` переходов из клетки в клетку. Символы '*' на карте заменяются
на '.' или '?', а символы '#' сохраняются.
Пример ввода
4 6 3 ..###. .*#.*. ....#. ..*...
Пример вывода
..###. ..#... ..??#. ......
B. Города
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 05/10/2013 | Личное первенство Южного Урала (B) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В игре "Вокруг света" необходимо угадывать название города. При этом известна длина названия и некоторые буквы.
Петя не знает географии и поэтому перебирает все возможные варианты для названия городов. Петя знает, что
не существует названий городов, в которых имеется более трех гласных или согласных букв подряд или
более двух одинаковых букв подряд, и не рассматривает такие варианты. Гласными буквами будем считать
буквы A, E, I, O, U и Y.
Напишите программу, определяющую количество вариантов для названия города с учетом указанных ограничений.
Первая строка ввода содержит последовательность из прописных латинских букв и символов '?'.
Символ '?' означает неизвестную букву в названии города. Длина строки от 1 до 1000 символов.
В первой строке вывести одно целое число — остаток от деления количества вариантов на `1\ 000\ 000\ 009`.
Пример ввода
?O??OW
Пример вывода
16620
C. Числовая цепочка
Задачи на построениеОлимпиадные задачи на русском языке
| 05/10/2013 | Личное первенство Южного Урала (C) |
| 10/10/2013 | Занятие 6 для начинающих (C) |
Ограничения: время – 2s/4s, память – 4MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Числа от 0 до `N`, представленные в виде 7-разрядных чисел с ведущими нулями, нужно расположить в цепочку
таким образом, чтобы соседние числа отличались не более чем на одну цифру и не более чем на 1 в этой цифре.
Каждое число от 0 до `N` должно присутствовать в цепочке ровно одни раз.
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ ≤\ 5\ 000\ 000`).
Вывести цепочку из `N+1` числа по указанным правилам. Каждое число цепочки должно быть напечатано
на отдельной строке в форме 7-разрядного числа с ведущими нулями. Если существует несколько
вариантов цепочки, то можно вывести любой из них.
Пример ввода
12
Пример вывода
0000009 0000008 0000007 0000006 0000005 0000004 0000003 0000002 0000001 0000000 0000010 0000011 0000012
D. Полный квадрат
Сокращение перебора с помощью идеиОлимпиадные задачи на русском языке
| 05/10/2013 | Личное первенство Южного Урала (D) |
| 10/10/2013 | Занятие 6 для начинающих (A) |
| 12/07/2017 | Лето 2017 (1 курс) - 7 (A) |
| 19/07/2019 | Лето 2019 - 9 (командное) (C) |
| 17/07/2020 | Лето 2020 - 8 (командное) (C) |
| 09/07/2021 | Лето 2021-6 (командное) (D) |
| 08/07/2022 | Лето 2022-6 (командное) (D) |
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (3)
Напишите программу, определяющую, какое наименьшее число цифр нужно приписать
к заданному числу справа, чтобы получился полный квадрат.
Первая строка ввода содержит одно целое число `N` (`1\ ≤\ N\ <\ 10^8`).
Вывести одно целое число — число с приписанными цифрами, являющееся полным квадратом. Если существует
несколько вариантов с минимальным количеством приписываемых цифр, то можно вывести любой из них.
Пример ввода
87
Пример вывода
87025
E. Рамка
Аналитическое решение уравнений, неравенств, систем уравненийРазбор случаев
Генерация всех подмножеств, сочетаний, перестановок
Олимпиадные задачи на русском языке
| 05/10/2013 | Личное первенство Южного Урала (E) |
| 10/10/2013 | Занятие 6 для начинающих (B) |
| 19/07/2019 | Лето 2019 - 9 (командное) (F) |
| 17/07/2020 | Лето 2020 - 8 (командное) (F) |
| 16/07/2021 | Лето 2021-9 (командное) (D) |
| 15/07/2022 | Лето 2022-9 (командное) (C) |
Ограничения: время – 250ms/500ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (2)
У Феди есть четыре рейки, из которых он хочет сделать прямоугольную рамку.
При этом не обязательно, чтобы все рейки были использованы полностью или частично.
Федя может разрезать любую рейку на 2 или более частей, но не умеет соединять рейки или их части для
использования полученной склейки в качестве какой-либо стороны рамки. Федя хочет, чтобы рамка
имела наибольший периметр.
Напишите программу, определяющую максимальный периметр прямоугольной рамки, которую можно сделать из
четырех реек заданных размеров.
Первая строка ввода содержит четыре целых числа `a`, `b`, `c`, `d` в неубывающем порядке (`1\ ≤\ a\ ≤\ b\ ≤\ c\ ≤\ d\ ≤\ 1000`) — размеры реек.
В первой строке необходимо вывести одно целое число — максимальный периметр рамки.
Пример ввода
5 7 12 15
Пример вывода
34
F. Строительство водопровода
Вычислительная геометрияГенерация всех подмножеств, сочетаний, перестановок
Минимальное остовное дерево
Олимпиадные задачи на русском языке
| 05/10/2013 | Личное первенство Южного Урала (F) |
| 12/07/2016 | Лето 2016 - 8 (C) |
| 05/03/2023 | «Базовая олимпиадная подготовка» (second level) - Остовные деревья (проводит novink) (E) |
Ограничения: время – 1s/2s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
От артезианской скважины до всех домов в поселке нужно проложить водопровод.
Можно сэкономить при строительстве, используя несколько больших труб, проложенных еще в доперестроечные времена.
Новые трубы имеют меньший диаметр, чем старые, и их можно прокладывать по прямой линии либо между двумя домами,
либо между домом и скважиной, либо между домом или скважиной и любой точкой старой трубы, либо между любыми
точками двух старых труб.
Напишите программу, которая определяет минимальную длину новых труб.
Первая строка ввода содержит два целых числа: количество домов `N` в поселке и количество старых труб `K`
(`1\ ≤\ N\ ≤\ 100`, `1\ ≤\ K\ ≤\ 10`). Далее следует строка с координатами скважины и `N` строк с координатами
домов. Далее следует `K` строк с координатами концов старых труб. Все координаты являются целыми числами
в диапазоне от 0 до 1000. Старые трубы не пересекаются между собой, но могут соприкасаться концами.
В первой строке вывести минимальную длину новых труб с точностью `10^{-6}`.
Пример ввода
2 2 3 6 1 4 2 2 0 5 4 5 5 1 7 3
Пример вывода
4.236068
G. Оптимизация производства
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 05/10/2013 | Личное первенство Южного Урала (G) |
Ограничения: время – 2s/4s, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В зависимости от настроек оборудования и установленного инструментов мастерская может выпускать несколько видов
продукции. Каждый вид продукции характеризуется временем изготовления и величиной прибыли. В каждый момент
времени может изготовляться только одно изделие. По окончании рабочего дня мастера прекращают работу
над изделием и на следующий день продолжают работу с того места, где остановились.
Изменение настроек и установка инструментов производится наладчиками только ночью.
При этом работа над изделием должна быть завершена, поэтому перед настройкой оборудования мастера не должны
приступать к работе над изделием, если его не удастся завершить к концу рабочего дня, и могут уйти с работы пораньше.
Напишите программу, вычисляющую максимальную прибыль, которую можно получить за `N` дней работы мастерской, выбирая
моменты настройки оборудования и виды производимых изделий.
Первая строка ввода содержит три целых числа: количество настроек оборудования `K` (`1\ ≤\ K\ ≤\ 10`), продолжительность
рабочего дня в минутах `T` (`100\ ≤\ T\ ≤\ 1000`) и количество дней `N` (`1\ ≤\ N\ ≤\ 1000`). Далее следует `K` строк,
описывающих виды продукции, которые можно изготовить при соответствующей настройке оборудования. Сначала в
строке указывается количество видов продукции `M_i` (`1\ ≤\ M_i\ ≤\ 10`), затем следует `M_i` пар целых чисел:
время изготовления в минутах `W_{ij}` (`1\ ≤\ W_{ij}\ ≤\ 10000`) и прибыль от продажи этого изделия `P_{ij}` (`1\ ≤\ P_{ij}\ ≤\ 1000000`).
В первой строке вывести одно число — максимальную прибыль, которую можно получить за `N` дней работы мастерской.
Пример ввода
2 300 5 2 1000 10000 900 5000 2 50 10 170 1000
Пример вывода
11020
H. Распознавание образов
Компоненты связности, мосты, точки сочлененияОлимпиадные задачи на русском языке
| 05/10/2013 | Личное первенство Южного Урала (H) |
| 17/07/2015 | Практика 1 и 2 курса (4) (C) |
| 01/07/2019 | Лето 2019 - 1 (B) |
| 30/09/2022 | Графы и бинарный поиск (проводит BOGAT) (C) |
| 28/11/2022 | «Базовая олимпиадная подготовка» (second level) - Поиск в глубину (DFS) (проводит novink) (C) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Дано прямоугольное черно-белое изображение размера `N` x `M`, которое содержит только два вида фигур:
окружности и отрезки. Фигуры нарисованы с помощью алгоритма растеризации, который окрашивает
в черный цвет все пиксели, через которые проходит окружность или отрезок.
Гарантируется, что не существует соседних черных пикселей, полученных при растеризации разных фигур.
Соседними пикселями считаются пиксели, соприкасающиеся сторонами или углами. Также гарантируется, что все
фигуры целиком лежат внутри данного изображения, внутри изображения каждой окружности есть хотя один белый пиксель,
и все пиксели на границе этого изображения являются белыми.
Напишите программу, определяющую число окружностей и отрезков на заданном изображении.
Первая строка ввода содержит два целых числа `N` и `M` (`1\ ≤\ N,\ M\ ≤\ 1000`) — размеры изображения.
Каждая из последующих `N` строк состоит ровно из `M` символов (нулей и единиц). Нули соответствуют белым пикселям, а
единицы — черным пикселям.
В первой строке вывести два целых числа, разделенных одним пробелом, — количество окружностей и
количество отрезков на изображении.
Пример ввода
7 8 00000000 00100010 01010010 00100110 00000100 01100000 00000000
Пример вывода
1 2
I. Newspaper
Реализация заданного алгоритмаОлимпиадные задачи на английском языке
| 05/10/2013 | Личное первенство Южного Урала (I) |
Ограничения: время – 500ms/1000ms, память – 256MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
News agency pays money for articles according to some rules. Each character has
its own value (some characters may have value equals to zero). Only printable characters have value.
Author gets his payment as a sum of all character's values in the article. You have to determine the amount
of money that news agency must pay to an author.
The first line contains an integer `K` (`1\ ≤\ K\ ≤\ 100`), the number of paid characters. On next `K` lines there
are table of paid characters and its values (character values are written in cents in the range from 1 to 1000). If
character can not be found in the table, then its value is equal to zero. Next lines contain an article itself.
Article can contain up to 10000 characters.
Print how much money publisher must pay for an article in format "x.yy$". Where "x" is
a number of dollars without leading zeros, and "yy" number of cents with one leading zero if necessary.
Examples: "3.32$", "13.07$", "71.30$", "0.09$".
Sample Input
4 a 3 A 100 . 5 I 13 ACM International Collegiate Programming Contest (abbreviated as ACM-ICPC or just ICPC) is an annual multi-tiered competition among the universities of the world.
Sample Output
2.77$
