Задачи открытого командного чемпионата 2004

1. Пересечение

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

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

Во входном файле в первой строке содержатся три числа, разделенных пробелами – координаты центра круга (`X_0` и `Y_0`) и радиус круга `R`. Во второй строке содержатся три числа, разделенных пробелами – координаты левого нижнего угла (`X` и `Y`) и размер стороны квадрата `S`. Все числа находятся в диапазоне от 1 до 20.

В выходной файл вывести одно число – площадь пересечения круга и квадрата с двумя десятичными знаками.

Пример ввода

5.0 2.0 1.0
3.5 2.0 3.0

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

1.57

2. Предки

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

Исследовав гены нескольких тысяч людей, ученые предположили, что все человечество произошло от небольшого племени из 20 человек, жившего где-то в западной Африке.

Организация Association of Cloned Martians решила провести аналогичные исследования для жителей Марса. Напишите программу для ACM, которая, используя результаты большого генетического исследования марсиан, определит для каждого марсианина его прародителя.

В первой строке ввода содержится одно целое число `N\ (1\ <\ N\ ≤\ 100000)` – количество обследованных марсиан. Далее следует `N` строк, содержащих по одному целому числу от 0 до `N`. В `(i+1)`-ой строке ввода находится номер родителя `i`-го марсианина или 0, если у него нет родителя (т.е. он является прародителем, как Адам или Ева в Библии). Входные данные не содержат циклов.

Вывести для каждого марсианина номер его прародителя или 0, если он является прародителем.

Пример ввода

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

3. Палиндром

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

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

В первой строке входного файла содержится исходное слово.

В выходной файл вывести полученное слово-палиндром (любой из вариантов) или сообщение IMPOSSIBLE.

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

ABBAT

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

ABTBA

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

BAT

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

IMPOSSIBLE

4. XML-преобразователь

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

XML-формат используется для хранения различной структурной информации и обмена информацией между программами. В некоторой программе этот формат использовался для хранения конфигурационных файлов. В новой версии программы для увеличения ее быстродействия было решено использовать упрощенный XML-формат.

Обычный XML-формат	Упрощенный XML-формат
<ЭЛЕМЕНТ />	<ЭЛЕМЕНТ></ЭЛЕМЕНТ>
<ЭЛЕМЕНТ АТРИБУТ1 АТРИБУТ2='ЗНАЧЕНИЕ2' АТРИБУТ3="ЗНАЧЕНИЕ3" />	<ЭЛЕМЕНТ><АТРИБУТ1></АТРИБУТ1> <АТРИБУТ2>ЗНАЧЕНИЕ2</АТРИБУТ2> <АТРИБУТ3>ЗНАЧЕНИЕ3</АТРИБУТ3></ЭЛЕМЕНТ>
<ЭЛЕМЕНТ АТРИБУТ1 АТРИБУТ2='ЗНАЧЕНИЕ2' АТРИБУТ3="ЗНАЧЕНИЕ3"> ТЕКСТ</ЭЛЕМЕНТ>	<ЭЛЕМЕНТ><АТРИБУТ1></АТРИБУТ1> <АТРИБУТ2>ЗНАЧЕНИЕ2</АТРИБУТ2> <АТРИБУТ3>ЗНАЧЕНИЕ3</АТРИБУТ3> ПРЕОБРАЗОВАННЫЙ ТЕКСТ</ЭЛЕМЕНТ>

Имена элементов и атрибутов состоят только из латинских букв, цифр и символов подчеркивание, точка и минус. Длина имен не более 100 символов. ЗНАЧЕНИЕ2 в ' не содержит символа '. ЗНАЧЕНИЕ3 в " не содержит символа ". За этим исключением ЗНАЧЕНИЕ2 и ЗНАЧЕНИЕ3 могут содержать любые символы, включая переход на новую строку. ТЕКСТ может содержать вложенные элементы, которые подвергаются аналогичному преобразованию. После имени элемента и после атрибутов и может быть несколько пробелов, символов табуляции и перехода на новую строку. Эти символы в выходной файл не выводятся.

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

Во входном файле содержится одна или несколько строк текста, содержащего XML- элементы.

В выходной файл вывести преобразованный текст, в котором XML-элементы записаны в новом упрощенном XML-формате.

Пример ввода

<book genre="Science Fiction">
<autor>Asimov</autor><title>Foundation</title>
<info
  publisher="Booble's doc"
  year='1975' />
</book>

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

<book><genre>Science Fiction</genre>
<autor>Asimov</autor><title>Foundation</title>
<info><publisher>Booble's doc</publisher><year>1975</year></info>
</book>

5. Скобки

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

Дано выражение, состоящее только из букв а и знаков операций + и *. Напишите программу, вычисляющую количество способов расстановки полного набора скобок в этом выражении таким образом, чтобы каждая пара скобок содержала один знак операции и два операнда, каждый из которых является либо буквой а, либо выражением в скобках. Значение выражения при этом должно остаться прежним, т.е. сначала должны выполняться операции умножения, а затем сложения. Например, для выражения а+а+а*а*а существует 4 способа расстановки скобок:

(а+(а+(а*(а*а))))

(а+(а+((а*а)*а)))

((а+а)+((а*а)*а))

((а+а)+(а*(а*а)))

В первой строке входного файла содержится корректное выражение, содержащее не более 25 знаков операций.

В выходной файл вывести одно число – количество способов расстановки скобок.

Пример ввода

а+а+а*а*а

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

6. Монеты

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

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

В первой строке входного файла содержится целое число `N` от 4 до 10 – количество монет. Во второй строке содержится `N` чисел, разделенных пробелами, в диапазоне от 5 до 50 с тремя десятичными знаками – диаметры монет.

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

Пример ввода

8
10.000 10.000 10.000 10.000 10.000 10.000 12.000 10.000

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

1 2 3 4 5 6 8

7. Подделка чека

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

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

Во входном файле в первой строке содержится одно целое положительное число не более чем из 100 цифр.

В выходной файл вывести одно число – максимальное число, которое можно получить в результате указанной манипуляции, или исходное число, если увеличить число невозможно.

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

8. The most round number

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

The number is more round than other on condition that it has more concluding zeroes than other. If two numbers have equal amount of concluding zeroes, the smaller number is more round.

First line of an input file contains one integer `N` (`1\ ≤\ N\ ≤\ 100`), it is amount of numbers. Each line from next `N` lines contains one integer from 1 up to `10^9`.

Print into an output file the most round number among given `N` numbers.

Input Sample

Output Sample

10/03/2004	Открытый командный чемпионат по программированию (1)
06/05/2013	Занятие 27 (D)

10/03/2004	Открытый командный чемпионат по программированию (2)
26/05/2007	Практическое занятие 20 (B)

10/03/2004	Открытый командный чемпионат по программированию (3)
25/06/2012	1 курс, дорешивание (8D1)
04/07/2012	1 курс, день 8, группа 1 (D1)
02/07/2014	Лето 2014 1 курс (35)

10/03/2004	Открытый командный чемпионат по программированию (4)
12/05/2012	Занятие 18 (D)

10/03/2004	Открытый командный чемпионат по программированию (7)
06/09/2008	Занятие 1 (D)
25/06/2012	1 курс, дорешивание (6B2)
02/07/2012	1 курс, день 6, группа 2 (B2)

Назад

Подразделы

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

Дата и время

Авторизация

Задачи открытого командного чемпионата 2004

1. Пересечение

2. Предки

3. Палиндром

4. XML-преобразователь

5. Скобки

6. Монеты

7. Подделка чека

8. The most round number