Начало
СоревнованияПодразделы
Другие разделы
Дата и время
26/04/2024 05:54:03
Все задачи
Задачи очного тура личного первенства Южного Урала 2007
A. Браки по расчету
Модулярная арифметикаГенерация всех подмножеств, сочетаний, перестановок
Динамическое программирование и запоминающие функции
Олимпиадные задачи на русском языке
| 12/10/2007 | Личное первенство Южного Урала (A) |
| 17/10/2007 | Занятие 6 (дорешивание) (A) |
| 10/07/2023 | Лето 2023-7 сложные (D) |
| 07/03/2024 | ДП (повторение) (проводит BOGAT) (A) |
| 03/04/2024 | ДП по подмножествам (проводит BOGAT) (A) |
Ограничения: время – 2s/4s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод 
Послать решение Blockly Посылки Темы Где Обсудить (0)
Королевство Флатландия оказалось на грани войны, так как южные князья поссорились с северными. С каждой стороны в ссоре участвовало по `N` княжеств. Чтобы укрепить отношения между княжествами, король повелел заключить `N` браков между принцами и принцессами противников, чтобы из каждого княжества, участвовавшего в ссоре, кто-то вышел замуж или женился.
Герольдмейстер вычислил для каждой пары княжеств количество возможных способов заключить брак между их принцами и принцессами (c учетом пола, возраста и пожеланий сторон), и теперь хочет знать общее количество вариантов заключения `N` браков, удовлетворяющих требованиям короля. Так как число вариантов может быть очень велико, достаточно вычислить остаток от деления результата на число `P`.
Первая строка ввода содержит два целых числа `N` (`1\ ≤\ N\ ≤\ 20`) и `P` (`2\ ≤\ P\ ≤\ 10000`). Далее следует `N` строк, в каждой строке `N` целых чисел в диапазоне от 0 до 100. Число в `i`-й строке `j`-м столбце означает количество возможных способов заключить брак между `i`-м южным княжеством и `j`-м северным княжеством.
Вывести одно целое число – остаток от деления на `P` общего количества вариантов заключения `N` браков.
Пример ввода
2 100 2 3 1 4
Пример вывода
11
B. Broken Sword: потерянный файл
Динамическое программирование и запоминающие функцииОлимпиадные задачи на русском языке
| 12/10/2007 | Личное первенство Южного Урала (B) |
| 17/10/2007 | Занятие 6 (дорешивание) (B) |
| 18/10/2008 | Занятие 5 (G) |
| 19/11/2010 | Занятие 10 (C) |
| 09/12/2010 | Сборы: Общий итог (6B) |
| 13/01/2011 | Сборы 6: Практика (B) |
| 19/11/2013 | Занятие 9 для начинающих (C) |
| 19/07/2016 | Лето 2016 - 11 (C) |
| 05/05/2022 | «Базовая олимпиадная подготовка» (second level) - Двумерная динамика начало (проводит novink) (A) |
| 12/07/2023 | Лето 2023-8 простые (C) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (34)
— Ха-ха-ха! – с расстановкой произнес сеньор Сузарро и скрылся за дверью в противоположном конце склада. В качестве сувенира он оставил бомбу с часовым механизмом, который немедленно начал отсчитывать последние минуты перед взрывом.
Между Джорджем Стоббартом и выходом стоит несколько штабелей ящиков одинакового размера. Кроме этого в помещении склада есть мостовой кран и конвейер, по которому в неизвестном направлении двигаются аналогичные ящики. Джордж может перебраться с одного штабеля на соседний, если разница в количестве ящиков в этих штабелях не превышает 2. С помощью мостового крана Джордж может поставить ящик из любого штабеля на конвейер или, наоборот, взять ящик с конвейера и поставить его в любой штабель.
Требуется определить минимальное число ящиков, которые нужно переместить, чтобы Джордж смог пробраться к выходу. Начало и конец пути находятся на уровне земли, нельзя добавлять новые штабели ящиков.
В первой строке ввода содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 1000`) – количество штабелей ящиков. Во второй строке содержатся `N` целых чисел в диапазоне от 0 до 100 – количество ящиков в `i`-м штабеле (`1\ ≤\ i\ ≤\ N`).
Вывести одно целое число – минимальное количество перемещенных ящиков.
Пример ввода
4 1 5 4 3
Пример вывода
3
C. Кредитный калькулятор
Бинарный поискОлимпиадные задачи на русском языке
| 12/10/2007 | Личное первенство Южного Урала (C) |
| 17/10/2007 | Занятие 6 (дорешивание) (C) |
| 01/11/2008 | Занятие 7 (F) |
| 12/02/2014 | Занятие 13 (F) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Почти все банки в России используют схему погашения кредита аннуитетными платежами. Каждый месяц выплачивается одинаковая сумма, независимо от периода погашения (начало или конец срока). Размер такого платежа является некой усредненной суммой выплат по кредиту. Аннуитетный платеж в начале периода погашения состоит в основном из процентов по кредиту и только малая часть – тело кредита. Потом эта пропорция выравнивается, и к концу периода погашения выплачивается практически только тело кредита.
Напишите программу, которая по сумме кредита, сроку и процентной ставке, выводит схему погашения кредита. Месячная процентная ставка рассчитывается из годовой по следующей формуле:
`P_m=((1+P_g/100)^{1/12}-1)*100`
Начисление процентов за `i`-й месяц производится по следующей формуле:
`D_i=[S_i*P_m+0.9]/100`
где `S_i` – остаток долга на начало `i`-го месяца, [ ] – целая часть числа.
Остаток долга вычисляется по следующей формуле:
`S_{i+1}=S_i+D_i-R_i`
где `R_i` – платеж по кредиту.
Все платежи `R_i` должны быть равными, кроме последнего `R_k`. Последний платеж должен погасить остаток долга и месячный процент по нему, и должен быть как можно ближе к ежемесячному платежу `R_i`, но не превышать его.
Ввод содержит три целых числа – сумма кредита `S_1` (`10^3\ ≤\ S_1\ ≤\ 10^6`), срок кредита в месяцах `k` (`3\ ≤\ k\ ≤\ 60`) и годовая процентная ставка `P_g` (`1\ ≤\ P_g\ ≤\ 100`).
Вывести схему погашения кредита. Вывод должен содержать `k` строк, в каждой строке 5 чисел: номер месяца, остаток долга на начало месяца, процентные начисления за месяц, размер платежа по кредиту в этот месяц и общая сумма платежей.
Пример ввода
10000 3 24
Пример вывода
1 10000.00 180.88 3454.65 3454.65 2 6726.23 121.67 3454.65 6909.30 3 3393.25 61.38 3454.63 10363.93
D. Draw Grid
Реализация заданного алгоритмаОлимпиадные задачи на английском языке
| 12/10/2007 | Личное первенство Южного Урала (D) |
| 04/12/2021 | Тренировка: пришел, увидел, AC (проводит BOGAT) (A) |
| 19/06/2023 | Тестирование (проводит BOGAT) (A) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
It is very easy to draw grids with ASCII characters. For example look at the picture below. It shows a (2x3) grid, where each smallest square is of size 2.
+--+--+--+ |..|..|..| |..|..|..| +--+--+--+ |..|..|..| |..|..|..| +--+--+--+
In this problem your job is very simple: Given sizes of the grid and size of smallest square, you will just have to draw the grid.
Input
First line of the input contains three integers `S`, `N` and `M` (`0\ <\ S,\ N,\ M\ ≤\ 10`). Here `S` is the size of smallest squares, `N` and `M` are the sizes of the grid.
Output
You'd have to print an (`N`x`M`) sized grid where each smallest square is of size (`S`x`S`). Note that blank places are denoted with '.'.
Sample Input
2 2 3
Sample Output
+--+--+--+ |..|..|..| |..|..|..| +--+--+--+ |..|..|..| |..|..|..| +--+--+--+
E. Морской бой
Метод ветвей и границ, поиск с возвратомОлимпиадные задачи на русском языке
| 12/10/2007 | Личное первенство Южного Урала (E) |
| 28/10/2015 | Занятие по темам "Нумерация комбинаторных объектов, сокращение перебора" (B) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Расположите на игровом поле размером 10x10 клеток набор из 10 кораблей (1 флагман длиной 4 клетки, 2 корабля длиной 3, 3 корабля длиной 2 и 4 катера длиной 1). Некоторые клетки поля уже открыты. Цифры сбоку и снизу игрового поля показывает количество фрагментов кораблей, которое попало в эту строку или столбец. Корабли не могут касаться друг друга даже углами.
Ввод содержит 11 строк, в первых 10 строках содержится 10 символов и цифра от '0' до '8', в последней – 10 цифр от '0'до '8'. Первые 10 символов первых 10 строк содержат информацию об открытых клетках. Символ '.' означает клетку, о которой нет информации, символ '~' – клетку с водой, символ 'O' – клетку с катером, символ '#' – средний фрагмент большого корабля, символы '<', '>', 'v' и '^' – крайние фрагменты больших кораблей. Гарантируется, что для головоломки существует решение.
Выведите 10 строк по 10 символов, содержащие решение головоломки, используя аналогичные обозначения.
Пример ввода
..........0 ..........1 ....v.....1 .......~..4 ..........3 ..........3 ..........4 O.........1 ..........1 ..........2 4030421204
Пример вывода
~~~~~~~~~~ ~~~~^~~~~~ ~~~~v~~~~~ ^~^~~~O~~^ #~#~~~~~~# v~v~~~~~~# ~~~~<>~O~v O~~~~~~~~~ ~~~~~~~O~~ ~~~~<>~~~~
F. Фантастическая 4
Сложение и вычитание длинных целых, умножение и деление на короткоеПолный перебор
Олимпиадные задачи на русском языке
| 12/10/2007 | Личное первенство Южного Урала (F) |
| 17/10/2007 | Занятие 6 (дорешивание) (F) |
| 11/10/2008 | Занятие 4 (D) |
| 01/10/2010 | Занятие 4 (E) |
| 11/03/2013 | Занятие 19 (F) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
В данном числе нужно заменить одну из цифр 4 на любую из цифр от 0 до 9 так, чтобы получилось число, которое без остатка делится на 7.
В первой строке ввода содержится одно целое число `N` (`1\ ≤\ N\ <\ 10^100`), содержащее как минимум одну цифру 4.
Вывести число после замены цифры 4. Число не должно начинаться с 0. Если существует несколько вариантов, вывести наименьшее из возможных число.
Пример ввода 1
41
Пример вывода 1
21
Пример ввода 2
4
Пример вывода 2
7
G. Go Scoring
Поиск в глубину (DFS)Олимпиадные задачи на английском языке
| 12/10/2007 | Личное первенство Южного Урала (G) |
| 17/10/2007 | Занятие 6 (дорешивание) (G) |
| 17/07/2015 | Практика 1 и 2 курса (4) (E) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Go is played on a board with a 19x19 grid, by two players called Black and White. Starting with an empty board, the players alternate turns placing stones of own color on an unoccupied intersection.
At the end of game players count their scoring. It is taked plenty of time because the number of stones on board can be more than 300. Several variants of go exist and ones use different tricks to simplify counting of scores.
You should write program that count scores in a moment by following rule:
A player's score is the number of stones of her color, plus the number of empty intersections that reach only her color. A empty intersection `P` is said to reach color `C`, if there is a path of adjacent (vertically or horizontally) unoccupied intersections from `P` to a intersection with stone of color `C`.
Input contains 19 lines. Each line contains 19 characters. Character 'B' represents black stone, 'W' – white stone, '.' – unoccupied intersection.
First line of output must contain two integers separated by space – scores of Black and White players.
Sample Input
..B................ ..B................ BB................. ................... ................... ................... ................... ................... ................... ................... ................... ................... ................... ................... ................... ......W............ .....W.W........... ......W............ ...................
Sample Output
8 5
H. Среднее арифметическое
Аналитическое решение уравнений, неравенств, систем уравненийИндукция и другие математические методы
Олимпиадные задачи на русском языке
| 12/10/2007 | Личное первенство Южного Урала (H) |
| 17/10/2007 | Занятие 6 (дорешивание) (H) |
| 25/06/2012 | 1 курс, дорешивание (5B2) |
| 29/06/2012 | 1 курс, день 5, группа 2 (B2) |
| 02/07/2014 | Лето 2014 1 курс (14) |
| 12/02/2019 | Личное первенство ЕТ-112 и ЕТ-114 (I) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Для заданного целого числа `N` найти его представление в виде среднего арифметического квадратов натуральных чисел. Например, `2007=(2^2+12^2+22^2+86^2)/4`.
В первой строке ввода содержится одно целое число `N` (`1\ ≤\ N\ ≤\ 100000`).
Вывести в первой строке число `K` (`1\ ≤\ K\ ≤\ 1000`). Во второй строке `K` натуральных чисел от 1 до 1000, среднее арифметическое квадратов которых равно заданному числу `N`. Числа могут повторяться. Если существует несколько вариантов, то можно вывести любой из них.
Пример ввода
2007
Пример вывода
4 2 12 22 86
I. Лабиринт
Вычислительная геометрияКратчайшие пути из одной вершины
Олимпиадные задачи на русском языке
| 12/10/2007 | Личное первенство Южного Урала (I) |
| 16/07/2018 | Лето 2018 - 10 (E) |
| 07/10/2023 | Тренировка 1 (проводит gribanov) (H) |
Ограничения: время – 1s/2s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод
Послать решение Blockly Посылки Темы Где Обсудить (0)
Археолог закончил исследование пирамиды и переехал на Кипр, где стал руководить раскопками сооружения, от которого осталось несколько стен.
Чтобы быстро перемещаться по месту раскопок и не заблудиться в этом лабиринте из стен, ему необходима программа для КПК, определяющая кратчайший путь между двумя заданными точками.
В первой строке ввода содержатся 5 целых чисел `N`, `x_a`, `y_a`, `x_b`, `y_b` (`1\ ≤\ N\ ≤\ 50`, `0\ ≤\ x_a,\ y_a,\ x_b,\ y_b\ ≤1000`) – количество стен и координаты начальной и конечной точки пути. Далее следует `N` строк, в каждой строке 4 целых числа в диапазоне от 0 до 1000 – координаты концов `i`-й стены. Стены имеют ненулевую длину, не пересекаются, но могут соприкасаться краями. Начальная и конечная точка пути не попадают ни на одну из стен.
Разрешается идти вплотную к стене, но нельзя перелезать через стену или проходить сквозь нее или место стыковки стен.
Вывести длину кратчайшего пути с точностью `10^{-3}`. Если пройти невозможно, то вывести сообщение "IMPOSSIBLE".
Пример ввода
2 10 20 40 5 20 0 100 0 20 0 20 50
Пример вывода
80.867
