#1243

Распаковка строчки

Темы: [Алгоритмы на строках]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2003, Задача G ]

Будем рассматривать только строчки, состоящие из заглавных латинских букв. Например, рассмотрим строку AAAABCCCCCDDDD. Длина этой строки равна 14. Поскольку строка состоит только из латинских букв, повторяющиеся символы могут быть удалены и заменены числами, определяющими количество повторений. Таким образом, данная строка может быть представлена как 4AB5C4D. Длина такой строки 7. Описанный метод мы назовем упаковкой строки.

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

Входные данные

Входной файл содержит одну упакованную строку. В строке могут встречаться только конструкции вида nA, где n — количество повторений символа (целое число от 2 до 99), а A — заглавная латинская буква, либо конструкции вида A, то есть символ без числа, определяющего количество повторений. Максимальная длина строки не превышает 80.

Выходные данные

В выходной файл выведите восстановленную строку. При этом строка должна быть разбита на строчки длиной ровно по 40 символов (за исключением последней, которая может содержать меньше 40 символов).

Примеры

Входные данные

ABC

Выходные данные

ABC

Входные данные

O2A3O2AO

Выходные данные

OAAOOOAAO

Входные данные

A2B3C4D5E6F7G

Выходные данные

ABBCCCDDDDEEEEEFFFFFFGGGGGGG

#1244

Дремучий лес

Темы: [Элементарная геометрия]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2003, Задача H ]

Просека — эта такая прямая линия, которая проходит через лес (то есть деревья есть как с одной стороны от этой линии, так и с другой), и при этом она не проходит ни через одно из деревьев леса, а также не касается деревьев. Будем говорить, что лес является дремучим, если в нем нет ни одной просеки.

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

Входные данные

Во входном файле содержится сначала целое число N — количество деревьев (1N200). Затем идет N троек чисел, задающих деревья. Первые два числа задают координаты центра, а третье — радиус. Все данные задаются точно, и выражаются вещественными числами, не более чем с 2 знаками после десятичной точки, по модулю не превосходящими 1000.

Выходные данные

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

Примеры

Входные данные

3
      0.00      30.00      25.00
      0.00     -30.00      25.00
     40.00       0.00      16.00

Выходные данные

NO
     -833.3333340000      -552.7707973875
      833.3333340000       552.7707973875

Входные данные

3
      0.00      30.00      29.00
      0.00     -30.00      29.00
     40.00       0.00      19.00

Выходные данные

YES

#1616

Средняя зарплата

Темы: [Эвристические методы]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2009, Лига А, Задача A ]

В фирме MacroHard работают \(N\) сотрудников, каждый из которых получает зарплату, выражающуюся целым числом рублей. Известно, что ни один сотрудник не получает меньше 5000 рублей, и никто не получает больше 100000 рублей. Также известно, что средняя зарплата сотрудника в этой фирме выражается целым числом копеек и составляет \(A\) рублей \(B\) копеек.

Журналист, готовя публикацию об этой фирме, решил привести зарплаты всех сотрудников. Однако оказалось, что это коммерческая тайна. Журналиста это не смутило, и он решил придумать всем сотрудникам зарплаты. Однако у него возникла сложность – для правдоподобности должны выполняться все общеизвестные ограничения (зарплаты должны выражаться целым числом рублей из диапазона от 5000 до 100000, и вычисление средней зарплаты должно в точности приводить к результату \(A\) рублей \(B\) копеек).

Помогите ему! Напишите программу, которая по введенным числам \(N\), \(A\), \(B\) «придумает» и выведет \(N\) зарплат.

Входные данные

Вводятся натуральное число \(N\) (1 ≤ \(N\) ≤ 100), натуральное число \(A\) (10000 ≤ \(A\) ≤ 30000) и целое число \(B\) (0 ≤ \(B\) ≤ 99).

Выходные данные

Выведите \(N\) целых чисел, выражающих зарплаты сотрудников в рублях. Если возможных вариантов распределения зарплат несколько, выведите любой из них. Если распределить зарплаты с учетом наложенных условий невозможно, выведите одно число 0.

#1617

Стройка

Темы: [Элементарная геометрия]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2009, Лига А, Задача B ]

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

Деревья на плане изображаются кругами, которые попарно не вложены друг в друга и не пересекаются (но могут касаться).

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

Входные данные

Вводится информация о трех деревьях: для каждого дерева координаты центра и радиус круга, изображающего это дерево на плане. Все числа целые, не превосходящие по модулю 3000. Радиус – натуральное число.

Выходные данные

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

#1618

Кодовый замок

Темы: [Разные комбинаторные структуры]

Источники: [ Командные олимпиады, Московская командная олимпиада, 9-11 классы, 2009, Лига А, Задача C ]

Кодовый замок состоит из \(N\) рычажков, каждый из которых может быть установлен в любое из \(K\) положений, обозначенных натуральными числами от 1 до \(K\). Известно, что для того чтобы открыть замок, нужно, чтобы сумма положений любых трех последовательных рычажков была равна \(K\).

Два рычажка уже установлены в некоторые положения, и их переключать нельзя. Рычажок с номером \(p_1\) установлен в положение \(v_1\), а рычажок \(p_2\) – в положение \(v_2\).

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

Входные данные

Вводятся натуральные числа \(N\), \(K\), \(p_1\), \(v_1\), \(p_2\), \(v_2\). 3 ≤ \(N\) ≤ 100 000, 3 ≤ \(K\) ≤ 100 000, \(p_1\) ≠ \(p_2\), 1 ≤ \(p_1\) ≤ \(N\), 1 ≤ \(p_2\) ≤ \(N\), 1 ≤ \(v_1\) ≤ \(K\), 1 ≤ \(v_2\) ≤ \(K\).

Выходные данные

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

Примеры

Входные данные

3 3 1 1 2 1

Выходные данные

Входные данные

3 3 1 1 3 2

Выходные данные