Задачи Южно-Уральского командного чемпионата 2013

A. Скидки

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

Магазин предлагает покупателям воспользоваться накопительной системой скидок. За каждую тысячу рублей, потраченных в этом магазине, покупатель получает 1% скидки на последующие покупки. При этом после достижения 20% скидки (сделано покупок на 20000 или более рублей) процент скидки больше не меняется. Изменение процента скидки происходит после покупки товара (см. пример).

Напишите программу, определяющую по истории покупок текущий процент скидки покупателя и общую сумму покупок.

Формат ввода

Первая строка ввода содержит два целых числа: количество различных видов товаров `N` (`2\ ≤\ N\ ≤\ 100`) и количество купленных товаров `K` (`1\ ≤\ K\ ≤\ 1000`). Вторая строка содержит `N` целых чисел в диапазоне от 10 до 1000 – цены товаров в рублях. Третья строка содержит `K` целых чисел в диапазоне от 1 до `N` – последовательность номеров товаров, перечисленных в порядке их покупки.

Формат вывода

Вывести два числа — процент скидки на следующий купленный товар и общую сумму покупок в рублях с точностью до копейки.

Пример ввода

2 5
333 1000
1 1 1 2 2

Вывод для примера

2 2989.00

Примечание к примеру: После трех покупок (товары 1-го вида) сумма покупок равна 999 руб., скидка — 0%. После четвертой покупки (товар 2-го вида) сумма покупок равна 1999 руб., а скидка — 1%. Пятый товар покупатель получает за 990 руб., сумма покупок станет равной 2989 руб., а скидка — 2%.

B. Союз стран

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

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

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

Формат ввода

Первая строка ввода содержит два целых числа: количество городов `N` (`3\ ≤\ N\ ≤\ 2000`) и количество дорог `M` (`N-1\ ≤\ M\ ≤\ N*(N-1)/2`). Далее следует `M` строк, содержащих по три целых числа: номера городов `a_i` и `b_i` (`1\ ≤\ a_i,\ b_i\ ≤\ N`, `a_i\ ≠\ b_i`), связанных гравийной дорогой, и длина дороги `d_i` (`1\ ≤\ d_i\ ≤\ 10\ 000`). Движение по дорогам возможно в обе стороны. Гарантируется, что существует путь между двумя любыми городами и в графе нет кратных ребер и петель. Столицами стран являются города с номерами 1, 2 и 3.

Формат вывода

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

Пример ввода

Вывод для примера

3
3 4 6

C. Двоично-десятичные числа

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

Разряды двоичного числа содержат только цифры 0 и 1. Назовем двоичное число двоично-десятичным, если его значение в десятичной системе счисления совпадает с последними цифрами этого двоичного числа. Например, число `1011_2` является двоично-десятичным, так как `1011_2=11_10`, а это число совпадает с двумя последними разрядами двоичного числа.

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

Формат ввода

Ввод содержит одно целое число `N` в двоичной системе счисления (`0\ ≤\ N\ <\ 2^1000`).

Формат вывода

В первой строке вывести сначала наибольшее двоично-десятичное число, не превосходящее `N`, в двоичной системе счисления без ведущих нулей, затем через пробел количество (в десятичной системе счисления) неотрицательных двоично-десятичных чисел, не превосходящих `N`.

Пример ввода

Вывод для примера

1011 4

Двоично-десятичными числами, не превосходящими `1111_2`, являются числа `0_2`, `1_2`, `1010_2`, `1011_2`.

D. Исправление HTML

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

При создании веб-страницы в формате HTML необходимо соблюдать следующие правила:

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

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

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

 <  <  < a < b < … < z <  <  < 

где открывающие и закрывающие теги рассматриваются как символы.

Формат ввода

Ввод содержит одну строку длиной от 1 до 1000 символов, состоящую из строчных латинских букв и тегов , , , , , .

Формат вывода

Вывести скорректированную строку, соответствующую правилам.

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

<b>aaa<i>bbb</b>ccc</i>ddd

Вывод для примера 1

<b>aaa<i>bbb</i></b><i>ccc</i>ddd

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

<i><b>ooo<b>ppp</b>qqq</b></u>

Вывод для примера 2

<i><b>ooo</b><b>ppp</b><b>qqq</b><u></u></i>

E. Подсчет треугольников

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

В прямоугольнике, состоящем из `N\ times\ M` клеток, в каждой клетке-квадрате были проведены диагонали. Необходимо подсчитать количество треугольников, образованных границами клеток и проведенными диагоналями. Например, в прямоугольнике `2\ times\ 3` можно найти 72 различных треугольника: 24 треугольника с катетами `sqrt{2}/2`, 24 треугольника с катетами 1, 14 треугольников с катетами `sqrt{2}`, 8 треугольников с катетами 2 и 2 треугольника с катетами `(3\ sqrt{2})/2`.

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

Формат ввода

Первая строка ввода содержит два целых числа: `N` и `M` (`1\ ≤\ N,\ M\ ≤1\ 000\ 000`) — размеры прямоугольника.

Формат вывода

Вывести количество треугольников. Гарантируется, что количество треугольников для указанных ограничений не превысит `2^63-1`.

Пример ввода

2 3

Вывод для примера

F. Кошелёк

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

`N` друзей шли по улице и нашли кошелек с `K` рублями.

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

Формат ввода

Первая строка ввода содержит два целых числа: количество друзей `N` (`2\ ≤\ N\ ≤\ 100`) и количество рублей `K` (`1\ ≤\ K\ ≤\ 1000`).

Формат вывода

Вывести сообщение Yes, если возможно поделить деньги поровну, иначе — сообщение No.

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

5 2

Вывод для примера 1

Yes

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

3 10

Вывод для примера 2

No

G. Семантическая сеть

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

Семантическая сеть — информационная модель предметной области, имеющая вид графа, вершины которого соответствуют объектам предметной области, а рёбра (дуги) задают отношения между ними. Объектами могут быть люди, понятия, события, свойства. В этой задаче вам необходимо построить семантическую сеть на основании информации из СМИ, а затем определить силу семантических связей между некоторыми объектами. Если два объекта упоминаются вместе в `M` статьях, то будем считать силу прямой семантической связи между этими объектами равной `M`. Объекты могут быть связаны между собой не только прямо, но косвенно, через другие объекты. В этом случае силу семантической связи будем рассчитывать как `max_P\ {M(P)}/{L(P)}`, где `P` – кратчайший путь между объектами, `L(P)` – длина этого пути, `M(P)` – минимальная сила прямых семантических связей на пути `P`. Если пути между объектами не существует, то сила семантической связи равна 0. Например, между понятиями elkin и mafia есть два кратчайших пути elkin-sosnovskiy-mafia (с минимальной силой связи `M(P)=2`) и elkin-bank-mafia (`M(P)=1`). Длина кратчайшего пути `L(P)=2`. Максимум значения выражения достигается на первом пути: `2//2=1`.

Формат ввода

Первая строка ввода содержит два целых числа: количество статей `N` (`1\ ≤\ N\ ≤\ 1000`) и количество запросов `Q` (`1\ ≤\ Q\ ≤\ 1000`). В следующих `N` строках содержится от двух до четырех слов, разделенных пробелами. Каждая строка соответствует одной статье в СМИ и указывает, какие объекты в ней связываются между собой. Количество объектов не более 2000. Далее следует `Q` строк, содержащих ровно два слова, разделенных пробелом – запросы на расчет силы семантической связи между объектами. Все слова состоят из строчных латинских букв, и их длина не превышает 15 букв. Имена объектов в статье или запросе не повторяются.

Формат вывода

Для каждого запроса вывести строку, содержащее одно число – силу семантической связи между объектами с точностью `10^{-6}`.

Пример ввода

6 4
elkin bank sosnovskiy
bank sosnovskiy mafia
bank elkin sosnovskiy
bank elkin
mafia sosnovskiy
sosnovskiy mafia
bank sosnovskiy
bank mafia
elkin mafia
elkin palkin

Вывод для примера

H. Выборы

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

После поступления в университет каждая группа должна выбрать старосту и профорга. По традициям университета У. старостой становится самый старший студент в группе, а профоргом — самый молодой.

Напишите программу, определяющую по списку студентов группы, кто станет старостой, а кто — профоргом.

Формат ввода

Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 100`). Следующие `N` строк содержат информацию о студентах в формате имя dd mm yyyy, где имя — слово, состоящее из латинских букв, длиной не более 20 символов, dd mm yyyy — день, месяц и год рождения. Гарантируется, что в списке нет людей с одинаковым именем или датой рождения.

Формат вывода

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

Пример ввода

5
Mike 1 10 1991
Alice 30 12 1990
Tom 15 8 1993
Jerry 18 9 1990
Mary 20 9 1990

Вывод для примера

Jerry
Tom

I. Сейф

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

Шпиону необходимо открыть сейф в секретном центре. У сейфа электронный замок с дисплеем и 12 кнопками: цифры от 0 до 9, кнопка "open" (открыть сейф, используя комбинацию на дисплее) и кнопка "correct" (убрать последнюю цифру на дисплее). Шпион нашел листок бумаги, на котором были в беспорядке записаны несколько чисел. Шпион догадался, что хозяин кабинета записывал на нём коды для открытия сейфа, чтобы не забыть их. Но какой код используется сейчас? Шпиону придется проверить все эти коды.

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

Формат ввода

Ввод содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 100\ 000`) — количество чисел на листке. Далее следует `N` строк, каждая строка содержит одно число от 1 до `10^15-1` без ведущих нулей. Числа не повторяются.

Формат вывода

Вывести последовательность нажатий кнопок минимальной длины, проверяющую все коды. Кнопка "open" в последовательности обозначается строчной латинской буквой 'o', а кнопка "correct" — строчной латинской буквой 'c'. Если существует несколько последовательностей минимальной длины, можно вывести любую из них.

Пример ввода

Вывод для примера

25oсс123occ37o

J. Клумба

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

Цветовод Маша посадила на клумбе несколько видов цветов. Для каждого вида цветов Маша знает номер дня `X_i`, когда растения этого вида полностью расцветают, и интервал цветения `D_i`. В день `X_i\ -\ D_i` ни одно растение еще не цветет, затем математическое ожидание количества цветущих растение линейно возрастает, и в день `X_i` достигает максимума (все посаженные растения цветут), затем математическое ожидание линейно уменьшается и в день `X_i\ +\ D_i` становится равным 0 (все растения отцветают).

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

Формат ввода

Первая строка ввода содержит одно целое число `N` (`2\ ≤\ N\ ≤\ 100\ 000`) — количество видов цветов, высаженных на клумбе. Далее следует `N` строк, каждая строка содержит три целых числа: количество цветов `i`-го вида `K_i` (`1\ ≤\ K_i\ ≤\ 1000`), номер дня `X_i` (`1\ ≤\ X_i\ ≤\ 10^9`), когда они все расцветают, и интервал цветения `D_i` (`1\ ≤\ D_i\ ≤\ X_i`).

Формат вывода

Вывести два числа: номер дня, когда количество цветущих растений на клумбе будет максимальным, и математическое ожидание количества цветущих растений в этот день с точностью `10^{-6}`. Если существует несколько вариантов для дня с максимальным количеством цветущих растений, то можно вывести любой из них.

Пример ввода

Вывод для примера

62 3.400000

Примечание: изменились ограничения для `X_i`, добавлены новые тесты 11 и 12.

K. Scarecrow

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

Taso owns a very long field. He plans to grow different types of crops in the upcoming growing season. The area, however, is full of crows and Taso fears that they might feed on most of the crops. For this reason, he has decided to place some scarecrows at different locations of the field.

The field can be modeled as a 1 x N grid. Some parts of the field are infertile and that means you cannot grow any crops on them. A scarecrow, when placed on a spot, covers the cell to its immediate left and right along with the cell it is on.

Given the description of the field, what is the minimum number of scarecrows that needs to be placed so that all the useful section of the field is covered? Useful section refers to cells where crops can be grown.

Input Format

Input starts with a line containing an integer `N` (`1\ ≤\ N\ ≤\ 100`). The next line contains `N` characters that describe the field. A dot ('.') indicates a crop-growing spot and a hash ('#') indicates an infertile region.

Output Format

Output the number of scarecrows that need to be placed.

Sample Input #1

3
.#.

Sample Output #1

Sample Input #2

11
...##....##

Sample Output #2

Sample Input #3

2
##

Sample Output #3

L. High Score

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

You've just been playing a video game in which you had to move a worm through a maze using a joystick. You got the high score, and now you have to enter your name using this joystick. This works as follows.

The initial name displayed on the screen is a string consisting only of 'A' characters. Initially the first letter of the string is selected. When you move the joystick forward, the selected letter is changed to the letter that immediately follows it in the alphabet. When you move the joystick backward, the selected letter is changed to the letter that immediately precedes it in the alphabet. The alphabet wraps around, so the letter following 'Z' is 'A' and the letter preceding 'A' is 'Z'.

Moving the joystick left or right changes the selection one step to the left or right, respectively. The selection does not wrap around, so moving left when the first letter is selected or right when the last letter is selected does not change the selection.

Because you would like to spend as little time as possible on entering your name, you want to know the smallest possible number of joystick moves needed to do this. Given the name you want to enter, write a program that calculates the minimum number of moves needed. You may assume that the length of the initial string is the same as the length of the name that you want to enter. Furthermore, it does not matter which letter is selected at the end of the process.

Input Format

The first line of input contains a single word less than 15 uppercase letters: the name that you want to enter.

Output Format

Output one line with an integer: the minimum number of joystick moves needed.

Sample Input

JAN

Sample Output

30/03/2013	Южно-Уральский открытый командный чемпионат по программированию (A)
03/07/2019	Лето 2019 - 2 (упрощенное) (D)

30/03/2013	Южно-Уральский открытый командный чемпионат по программированию (B)
01/04/2013	Занятие 22 (дорешивание задач командного чемпионата) (A)
16/07/2018	Лето 2018 - 10 (B)
24/09/2021	Дискретная оптимизация - 2 (проводит BOGAT) (A)
14/09/2022	Пути в графах (повторение) (проводит BOGAT) (H)
17/02/2023	«Базовая олимпиадная подготовка» (second level) - алгоритм Дейкстры (проводит novink) (D)

30/03/2013	Южно-Уральский открытый командный чемпионат по программированию (C)
01/04/2013	Занятие 22 (дорешивание задач командного чемпионата) (B)

30/03/2013	Южно-Уральский открытый командный чемпионат по программированию (D)
01/04/2013	Занятие 22 (дорешивание задач командного чемпионата) (C)

30/03/2013	Южно-Уральский открытый командный чемпионат по программированию (E)
01/04/2013	Занятие 22 (дорешивание задач командного чемпионата) (D)

Назад

Подразделы

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

Дата и время

Авторизация

Задачи Южно-Уральского командного чемпионата 2013

A. Скидки

B. Союз стран

C. Двоично-десятичные числа

D. Исправление HTML

E. Подсчет треугольников

F. Кошелёк

G. Семантическая сеть

H. Выборы

I. Сейф

J. Клумба

K. Scarecrow

L. High Score