Білоруські олімпіади з інформатики

Білоруські олімпіади з інформатики   http://byoi.narod.ru/

1993 рік. Умови олімпіадних завдань з інформатики

СКОБКИ

---

Входной файл: стандартный ввод
Выходной файл: стандартный вывод
Время на тест: 10 секунд

Если мы из корректно записанного арифметического выражения, содержащего числа, знаки операций и открывающие и закрывающие круглые скобки выбросим числа и знаки операций, а затем запишем оставшиеся в выражении скобки без пробелов между ними, то полученный результат назовем правильным скобочным выражением [скобочное выражение "(()(()))''- правильное, а "()('' и "())('' - нет].

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

ЗАБОР

---

Входной файл: стандартный ввод
Выходной файл: стандартный вывод
Время на тест: 10 секунд

На местности, представляющей собой идеально ровную поверхность, стоит высокий забор. План забора представляет собой замкнутую ломаную без самопересечений. Эта ломаная задается N парами координат своих вершин в порядке обхода ограничиваемой забором области против часовой стрелки. Вершины пронумерованы от 1 до N, N<100.

В точке (x,y) стоит человек ( (x,y) не может лежать на ломаной). Считая, что каждому звену ломаной становится в соответствие пара номеров концевых вершин, указать, какие звенья человек увидит полностью или частично в качестве невырожденного отрезка, а какие - вообще нет. Если при взгляде звено видно как точка или как пара, точек, то полагаем, что оно не видно. 

ОБЕЗЬЯНЫ

---

Входной файл: стандартный ввод
Выходной файл: стандартный вывод
Время на тест: 10 секунд

Есть две обезьяны и куча из L бананов. Обезьяны по очереди, начиная с первой, берут из кучи бананы, причем 1-ая обезьяна может при каждом очередном ходе взять из кучи либо a₁, либо a₂, либо ... a_S бананов (а₁ < a₂ < ... < a_S ), а 2-ая при каждом очередном ходе - либо b₁, либо b₂, либо ... b_K бананов (b₁ < b₂ < ... < b_K ). Нумерация индексов при a и b не имеет никакого отношения к номерам ходов обезьян

Выигрывает та обезьяна, которая на своем ходе не может взять банан(ы) (либо потому, что их не осталось, либо потому что бананов осталось меньше чем a₁ (при ходе первой обезьяны) либо b₁(при ходе второй обезьяны)).

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

ЧИНОВНИКИ

---

Входной файл: стандартный ввод
Выходной файл: стандартный вывод
Время на тест: 10 секунд

Есть министерство из N чиновников, где N натуральное число. У каждого из чиновников могут быть как подчиненные,так и начальники,причем справедливы правила: подчиненные моего подчиненного - мои подчиненные, начальники моего начальника - мои начальники, мой начальник не есть мой подчиненный, у каждого чиновника не более одного непосредственного начальника.

Для того чтобы получить лицензию на вывоз меди необходимо получить подпись 1-ого чиновника - начальника всех чиновников. Проблема осложняется тем, что каждый чиновник, вообще говоря, может потребовать "визы", т.е. подписи некоторых своих непосредственных подчиненных и взятку - известное количество долларов. Для каждого чиновника известен непустой список возможных наборов "виз" и соответствующая каждому набору взятка.Пустой набор означает,что данный чиновник не требует виз в данном случае. Чиновник ставит свою подпись лишь после того,как ему представлены все подписи одного из наборов "виз" и уплачена соответствующая взятка.

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

N < 100. Количество наборов для каждого чиновника не превосходит 15.

BASIC

---

Входной файл: стандартный ввод
Выходной файл: стандартный вывод
Время на тест: 10 секунд

Пусть программа на языке BASIC состоит из последовательностей операторов. Каждая последовательность состоит из ненулевого числа операторов. Операторы отделяются друг от друга символом двоеточие (:), который для других целей в программе не используется. Последовательность может располагаться на нескольких строках, при этом разбивка оператора на 2 строки не допускается; если последо- вательность продолжается на следующей строке, в конце текущей строки стоит двоеточие. Последовательности операторов в тексте программы имеют уникальные номера. Таким образом, структура последовательности операторов следующая:

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

Переходы в программе осуществляются посредством операторов goto или gosub (эти ключевые слова могут быть записаны как с использованием заглавных, так и прописных букв, например GoSUb).

Вид операторов

• goto номер последовательности
• gosub номер последовательности

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

Написать программу, которая читает из файла имя файла (имя файла вводится с клавиатуры), текст BASIC программы и перенумеро- вывает последовательности операторов так, чтобы

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

Текст программы состоит не более чем из 100 строк, длина строки не превышает 80 символов.

Преобразованную BASIC-программу выводить в файл
имя_файла.OUT.

Входные данные корректны.

                   1994 рік. Умови олімпіадних завдань з інформатики


КАРТОЧКИ

---

Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 15 секунд
Тесты к задаче: Скачать

Есть N карточек. На каждой из них черными чернилами написан ее уникальный номер - число от 1 до N. Также на каждой карточке красными чернилами написано еще одно целое число, лежащее в промежутке от 1 до N (некоторыми одинаковыми "красными" числами могут помечаться несколь- ко карточек).

Например, N=5, 5 карточек помечены следующим образом:

"черное" число	1	2	3	4	5
"красное" число	3	3	2	4	2

Необходимо выбрать из данных N карточек максимальное число карточек таким образом, чтобы множества "красных" и "черных" чисел на них совпадали.

Для примера выше это будут карточки с "черными" номерами 2, 3, 4 (множество красных номеров, как и требуется в задаче, то же - {2,3,4}).

Ввод:

<N>, N<=50
<"Черное" число 1> <"Красное" число 1>
......
<"Черное" число N> <"Красное" число N>

Вывод:

<В выбранном множестве элементов количество элементов S>
"Черные" номера выбранных карточек:
<a₁>
...
<a_S>

Пример ввода	Пример вывода
6	6
1 2	1
2 3	2
3 4	3
4 5	4
5 1	5
6 6	6

АРБУЗЫ

---

Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 15 секунд
Тесты к задаче: Скачать

В ряд лежат N арбузов, пронумерованных от 1 до N. Нам известно:

1. массы первого и N-го арбузов m₁ и m_N соответственно
2. масса i-го арбуза m_i есть среднее арифметическое масс двух соседних арбузов, увеличенное на d: m_i=d+(m_i-1+m_i+1)/2

По введенным m₁, m_N, d и j найти m_j.

Ограничение

N<200

Если найти m_j по введенным данным невозможно, вывести "error"

Формат ввода	Формат вывода
M1	Mj
MN
N
D
J

Пример 1 ввода	Пример 2 ввода
1.0	30.0
1.0	210.0
21	10
1.0	-5.0
15	8
Пример 1 вывода	Пример 2 вывода
85.0	error

УДАЛИТЕ ЦИФРЫ

---

Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 15 секунд
Тесты к задаче: Скачать

Вводятся N и s.

Задано натуральное число N из K>s цифр (K не вводится). Составить алгоритм, определяющий, какие s цифр удалить, чтобы оставшиеся цифры составили наименьшее число. Выдать в порядке возрастания номера уда ленных цифр. Цифры пронумерованы слева направо, нумерация начинается с единицы.

Пример. N=2435, s=1. Если удалить вторую цифру (4), получим число 235. Это и есть наименьшее число (остальные: 435,245,243).

Число N представляется следующим образом:

Задается количество строк ввода p, в каждой строке по два числа a_i и b_i, a_i<=60000, b_i состоит из не более чем 60 цифр. a_i указывает, сколько раз в числе встречается группа цифр b_i. p<30.

N=a₁ b₁ ... a_p b_p. Например, если p=3
a1=3 b1=123
a2=1 b2=0
a3=2 b3=09
то N=12312312300909

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

p
a1 b1
...
ai bi
...
ap bp
s

Пример ввода	Пример вывода
2	2
2 01	4
1 02	6
3

ЗНАМЕНИТОСТИ

---

Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 10 секунд

Пусть группа состоит из N человек (1<=N<=1000). Назовем одного из этих людей знаменитостью, если он не знает никого из оставшихся, а его знают все. Задача состоит в том, что бы в этой группе определить знаменитость (если она там есть). При этом разрешается задавать только вопросы вида "Извините, знаете ли Вы вон того человека?" Предполагается,что все ответы правдивы, и что даже знаменитость ответит на поставленный ей вопрос.

Найти минимальное необходимое число вопросов, которое надо задать. Если знаменитости в группе нет, то необходимо вывести минимальное число вопросов, чтобы доказать это.

Входные данные: матрица C[i,j], такая, что C[i,j]=1, если i знает j и C[i,j]=0 иначе.

Входной файл:

N
c[1,1] c[1,2] ... c[1,N]
c[2,1] c[2,2] ... c[2,N]
...
c[N,1] c[N,2] ... c[N,N]

Выходной файл:

K - минимальное количество вопросов

Пример ввода: 4 1 1 1 1 0 1 1 1 0 0 1 0 1 0 1 1

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

ПРЯМОУГОЛЬНИКИ

---

Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 5 секунд
Тесты к задаче: Скачать

Написать программу, отвечающую на вопрос, можно ли из N данных прямоугольников Пi размеров (ai, bi), i=1...N, сложить один большой прямоугольник П размера (a, b). Нижний левый угол большого прямоугольника имеет координату (0, 0), стороны параллельны осям координат. Маленькие прямоугольники можно перемещать и поворачивать, но так, чтобы после движения их стороны оставались параллельны осям координат. При составлении прямоугольника П прямоугольники Пi могут быть использованы не все. Использованные прямоугольники не должны перекрываться.

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

N A B
A1 B1
...
AN BN

Здесь Ai и Bi – ширина и высота i-того прямоугольника, соответственно.
N<8; A, B, Ai, Bi – целые числа, не превосходящие 27000.

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

Yes/No
[L
N1 PY1 PX1 AY1 AX1
...
NL PYL PXL AYL AXL]

То, что заключено в квадратные скобки, нужно выводить только, если ответ положительный.
Здесь L - количество использованных прямоугольников,
Ni, Xi, Yi, Ai, Bi – номер, координаты левого нижнего угла, ширина и высота i-того использованного прямоугольника, соответственно.

Пример ввода: 2 1 200 1 1 199 1

Пример вывода: Yes 2 2 0 1 1 199 1 0 0 1 1

РАБОТЫ

---

Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 5 секунд
Тесты к задаче: Скачать

В нулевой момент времени мастеру одновременно поступает N работ. Работы пронумерованы от 1 до N. Для каждой работы i заранее известно следующее:

1. время выполнения работы ti, кратное суткам
2. штраф сi за каждые сутки ожидания работы i до момента начала ее выполнения.

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

Таким образом, суммарный штраф, который надо будет уплатить,  равен сумме сi*(время начала выполнения работы i) по всем i.

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

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

N
t1 c1
...
tN cN

Здесь N – число работ для выполнения, ti и ci – время на выполнение и штрафной тариф i-той работы.
Ограничения: N <= 100; ti, ci < 1000.

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

C
i1 i2 ... iN

Здесь C – минимальный суммарный штраф за неустойки по всем работам.
Далее следует последовательность номеров выполненных работ в порядке их выполнения.

Пример ввода: 3 4 1 1 1 10 3

Пример вывода: 14 2 3 1

Білоруські олімпіади з інформатики   http://byoi.narod.ru/

1993 рік. Умови олімпіадних завдань з інформатики

СКОБКИ

---

Входной файл: стандартный ввод
Выходной файл: стандартный вывод
Время на тест: 10 секунд

Если мы из корректно записанного арифметического выражения, содержащего числа, знаки операций и открывающие и закрывающие круглые скобки выбросим числа и знаки операций, а затем запишем оставшиеся в выражении скобки без пробелов между ними, то полученный результат назовем правильным скобочным выражением [скобочное выражение "(()(()))''- правильное, а "()('' и "())('' - нет].

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

ЗАБОР

---

Входной файл: стандартный ввод
Выходной файл: стандартный вывод
Время на тест: 10 секунд

На местности, представляющей собой идеально ровную поверхность, стоит высокий забор. План забора представляет собой замкнутую ломаную без самопересечений. Эта ломаная задается N парами координат своих вершин в порядке обхода ограничиваемой забором области против часовой стрелки. Вершины пронумерованы от 1 до N, N<100.

В точке (x,y) стоит человек ( (x,y) не может лежать на ломаной). Считая, что каждому звену ломаной становится в соответствие пара номеров концевых вершин, указать, какие звенья человек увидит полностью или частично в качестве невырожденного отрезка, а какие - вообще нет. Если при взгляде звено видно как точка или как пара, точек, то полагаем, что оно не видно. 

ОБЕЗЬЯНЫ

---

Входной файл: стандартный ввод
Выходной файл: стандартный вывод
Время на тест: 10 секунд

Есть две обезьяны и куча из L бананов. Обезьяны по очереди, начиная с первой, берут из кучи бананы, причем 1-ая обезьяна может при каждом очередном ходе взять из кучи либо a₁, либо a₂, либо ... a_S бананов (а₁ < a₂ < ... < a_S ), а 2-ая при каждом очередном ходе - либо b₁, либо b₂, либо ... b_K бананов (b₁ < b₂ < ... < b_K ). Нумерация индексов при a и b не имеет никакого отношения к номерам ходов обезьян

Выигрывает та обезьяна, которая на своем ходе не может взять банан(ы) (либо потому, что их не осталось, либо потому что бананов осталось меньше чем a₁ (при ходе первой обезьяны) либо b₁(при ходе второй обезьяны)).

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

ЧИНОВНИКИ

---

Входной файл: стандартный ввод
Выходной файл: стандартный вывод
Время на тест: 10 секунд

Есть министерство из N чиновников, где N натуральное число. У каждого из чиновников могут быть как подчиненные,так и начальники,причем справедливы правила: подчиненные моего подчиненного - мои подчиненные, начальники моего начальника - мои начальники, мой начальник не есть мой подчиненный, у каждого чиновника не более одного непосредственного начальника.

Для того чтобы получить лицензию на вывоз меди необходимо получить подпись 1-ого чиновника - начальника всех чиновников. Проблема осложняется тем, что каждый чиновник, вообще говоря, может потребовать "визы", т.е. подписи некоторых своих непосредственных подчиненных и взятку - известное количество долларов. Для каждого чиновника известен непустой список возможных наборов "виз" и соответствующая каждому набору взятка.Пустой набор означает,что данный чиновник не требует виз в данном случае. Чиновник ставит свою подпись лишь после того,как ему представлены все подписи одного из наборов "виз" и уплачена соответствующая взятка.

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

N < 100. Количество наборов для каждого чиновника не превосходит 15.

BASIC

---

Входной файл: стандартный ввод
Выходной файл: стандартный вывод
Время на тест: 10 секунд

Пусть программа на языке BASIC состоит из последовательностей операторов. Каждая последовательность состоит из ненулевого числа операторов. Операторы отделяются друг от друга символом двоеточие (:), который для других целей в программе не используется. Последовательность может располагаться на нескольких строках, при этом разбивка оператора на 2 строки не допускается; если последо- вательность продолжается на следующей строке, в конце текущей строки стоит двоеточие. Последовательности операторов в тексте программы имеют уникальные номера. Таким образом, структура последовательности операторов следующая:

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

Переходы в программе осуществляются посредством операторов goto или gosub (эти ключевые слова могут быть записаны как с использованием заглавных, так и прописных букв, например GoSUb).

Вид операторов

• goto номер последовательности
• gosub номер последовательности

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

Написать программу, которая читает из файла имя файла (имя файла вводится с клавиатуры), текст BASIC программы и перенумеро- вывает последовательности операторов так, чтобы

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

Текст программы состоит не более чем из 100 строк, длина строки не превышает 80 символов.

Преобразованную BASIC-программу выводить в файл
имя_файла.OUT.

Входные данные корректны.

                   1994 рік. Умови олімпіадних завдань з інформатики


КАРТОЧКИ

---

Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 15 секунд
Тесты к задаче: Скачать

Есть N карточек. На каждой из них черными чернилами написан ее уникальный номер - число от 1 до N. Также на каждой карточке красными чернилами написано еще одно целое число, лежащее в промежутке от 1 до N (некоторыми одинаковыми "красными" числами могут помечаться несколь- ко карточек).

Например, N=5, 5 карточек помечены следующим образом:

"черное" число	1	2	3	4	5
"красное" число	3	3	2	4	2

Необходимо выбрать из данных N карточек максимальное число карточек таким образом, чтобы множества "красных" и "черных" чисел на них совпадали.

Для примера выше это будут карточки с "черными" номерами 2, 3, 4 (множество красных номеров, как и требуется в задаче, то же - {2,3,4}).

Ввод:

<N>, N<=50
<"Черное" число 1> <"Красное" число 1>
......
<"Черное" число N> <"Красное" число N>

Вывод:

<В выбранном множестве элементов количество элементов S>
"Черные" номера выбранных карточек:
<a₁>
...
<a_S>

Пример ввода	Пример вывода
6	6
1 2	1
2 3	2
3 4	3
4 5	4
5 1	5
6 6	6

АРБУЗЫ

---

Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 15 секунд
Тесты к задаче: Скачать

В ряд лежат N арбузов, пронумерованных от 1 до N. Нам известно:

1. массы первого и N-го арбузов m₁ и m_N соответственно
2. масса i-го арбуза m_i есть среднее арифметическое масс двух соседних арбузов, увеличенное на d: m_i=d+(m_i-1+m_i+1)/2

По введенным m₁, m_N, d и j найти m_j.

Ограничение

N<200

Если найти m_j по введенным данным невозможно, вывести "error"

Формат ввода	Формат вывода
M1	Mj
MN
N
D
J

Пример 1 ввода	Пример 2 ввода
1.0	30.0
1.0	210.0
21	10
1.0	-5.0
15	8
Пример 1 вывода	Пример 2 вывода
85.0	error

УДАЛИТЕ ЦИФРЫ

---

Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 15 секунд
Тесты к задаче: Скачать

Вводятся N и s.

Задано натуральное число N из K>s цифр (K не вводится). Составить алгоритм, определяющий, какие s цифр удалить, чтобы оставшиеся цифры составили наименьшее число. Выдать в порядке возрастания номера уда ленных цифр. Цифры пронумерованы слева направо, нумерация начинается с единицы.

Пример. N=2435, s=1. Если удалить вторую цифру (4), получим число 235. Это и есть наименьшее число (остальные: 435,245,243).

Число N представляется следующим образом:

Задается количество строк ввода p, в каждой строке по два числа a_i и b_i, a_i<=60000, b_i состоит из не более чем 60 цифр. a_i указывает, сколько раз в числе встречается группа цифр b_i. p<30.

N=a₁ b₁ ... a_p b_p. Например, если p=3
a1=3 b1=123
a2=1 b2=0
a3=2 b3=09
то N=12312312300909

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

p
a1 b1
...
ai bi
...
ap bp
s

Пример ввода	Пример вывода
2	2
2 01	4
1 02	6
3

ЗНАМЕНИТОСТИ

---

Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 10 секунд

Пусть группа состоит из N человек (1<=N<=1000). Назовем одного из этих людей знаменитостью, если он не знает никого из оставшихся, а его знают все. Задача состоит в том, что бы в этой группе определить знаменитость (если она там есть). При этом разрешается задавать только вопросы вида "Извините, знаете ли Вы вон того человека?" Предполагается,что все ответы правдивы, и что даже знаменитость ответит на поставленный ей вопрос.

Найти минимальное необходимое число вопросов, которое надо задать. Если знаменитости в группе нет, то необходимо вывести минимальное число вопросов, чтобы доказать это.

Входные данные: матрица C[i,j], такая, что C[i,j]=1, если i знает j и C[i,j]=0 иначе.

Входной файл:

N
c[1,1] c[1,2] ... c[1,N]
c[2,1] c[2,2] ... c[2,N]
...
c[N,1] c[N,2] ... c[N,N]

Выходной файл:

K - минимальное количество вопросов

Пример ввода: 4 1 1 1 1 0 1 1 1 0 0 1 0 1 0 1 1

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

ПРЯМОУГОЛЬНИКИ

---

Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 5 секунд
Тесты к задаче: Скачать

Написать программу, отвечающую на вопрос, можно ли из N данных прямоугольников Пi размеров (ai, bi), i=1...N, сложить один большой прямоугольник П размера (a, b). Нижний левый угол большого прямоугольника имеет координату (0, 0), стороны параллельны осям координат. Маленькие прямоугольники можно перемещать и поворачивать, но так, чтобы после движения их стороны оставались параллельны осям координат. При составлении прямоугольника П прямоугольники Пi могут быть использованы не все. Использованные прямоугольники не должны перекрываться.

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

N A B
A1 B1
...
AN BN

Здесь Ai и Bi – ширина и высота i-того прямоугольника, соответственно.
N<8; A, B, Ai, Bi – целые числа, не превосходящие 27000.

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

Yes/No
[L
N1 PY1 PX1 AY1 AX1
...
NL PYL PXL AYL AXL]

То, что заключено в квадратные скобки, нужно выводить только, если ответ положительный.
Здесь L - количество использованных прямоугольников,
Ni, Xi, Yi, Ai, Bi – номер, координаты левого нижнего угла, ширина и высота i-того использованного прямоугольника, соответственно.

Пример ввода: 2 1 200 1 1 199 1

Пример вывода: Yes 2 2 0 1 1 199 1 0 0 1 1

РАБОТЫ

---

Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 5 секунд
Тесты к задаче: Скачать

В нулевой момент времени мастеру одновременно поступает N работ. Работы пронумерованы от 1 до N. Для каждой работы i заранее известно следующее:

1. время выполнения работы ti, кратное суткам
2. штраф сi за каждые сутки ожидания работы i до момента начала ее выполнения.

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

Таким образом, суммарный штраф, который надо будет уплатить,  равен сумме сi*(время начала выполнения работы i) по всем i.

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

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

N
t1 c1
...
tN cN

Здесь N – число работ для выполнения, ti и ci – время на выполнение и штрафной тариф i-той работы.
Ограничения: N <= 100; ti, ci < 1000.

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

C
i1 i2 ... iN

Здесь C – минимальный суммарный штраф за неустойки по всем работам.
Далее следует последовательность номеров выполненных работ в порядке их выполнения.

Пример ввода: 3 4 1 1 1 10 3

Пример вывода: 14 2 3 1

1995 рік. Умови олімпіадних завдань з інформатики

ДИСКИ

---

Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 5 секунд
Тесты к задаче: Скачать

Имеется N (N<7) дисков одинаковой толщины с радиусами r₁, ..., r_N. Эти диски упаковываются в коробку таким образом, что каждый из них стоит ребром на дне коробки и все диски находятся в одной плоскости.

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

Вход:

1-я строка: N
2-я строка: r₁ r₂ ... r_N

Выход

Минимальная длина: число (с точностью до 2-х знаков после запятой)
Возможный порядок

Пример.

input.txt

3
2.0 2.0 1.0

output.txt

9.66
1 3 2

КВАДРАТЫ


Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 5 секунд
Тесты к задаче: Скачать



Для введенного числа S необходимо определить общее количество квадратов размера 4х4, у которых сумма чисел по строкам, столбцам и диагоналям равна S. Квадрат составляется из костяшек домино одного набора (прямоугольников размера 1х2 с числами от 0 до 6). Костяшки кладутся только горизонтально.

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


Выходные данные
<общее количество>


Пример

Input.txt
5


Output.txt
56










ВИННИ-ПУХ И ПЯТАЧЕК


Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 5 секунд
Тесты к задаче: Скачать



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

Тактика хаккеров.

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

Примечание.

В сети Винни-Пуха и Пяточка ни у каких 2-х ЭВМ количество терминалов не совпадает.

Техническое задание.

Вам необходимо написать программу, входными данными которой было бы описание сети, а выходными - список номеров ЭВМ, которые могут быть выбраны хаккерами для захвата сети согласно их тактике.

Формат ввода.
Количество ЭВМ в сети : N
ЭВМ #1 имеет терминалов : T[1]
ЭВМ #2 имеет терминалов : T[2]
  ...
ЭВМ #N имеет терминалов : T[N]
Права на запрос :
A[1]  B[1]
A[2]  B[2]
  ...
A[K]  B[K]
 0    0


A[i] и В[i] - номера ЭВМ, последняя строка '0 0' обозначает конец списка прав на запрос, каждая пара A[i] B[i] обозначает, что ЭВМ с номеров A[i] имеет право запрашивать информацию у ЭВМ с номером B[i] (A[i] не равно B[i]).

При вводе числа N и T[i] - натуральные, T[i] <=1000, N<=50, K<=2450.

Входные данные соответствуют приведенным условиям.

Формат вывода.
Номера     захватываемых    ЭВМ  : С[1] C[2] ... С[M].
Количество  захватываемых   ЭВМ  : <M>

Пример.

Input.txt
5
100
2
1
3
10
1 3
3 2
4 3
4 5
5 4
0 0

Output.txt
1 4
2



СКРУДЖ МАК-ДАК


Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 10 секунд
Тесты к задаче: Скачать



Скрудж Мак-Дак решил сделать прибор для управления самолетом. Как известно, положение штурвала зависит от состояния входных датчиков, но эта функция довольно сложна.

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

Формат ввода:
1 строка: <общее количество функций N> (N<50) <имя функции, которую небходимо вычислить>
2 строка: <имя функции> <кол-во параметров> [<список имен параметров>]
...
N+1 строка: <имя функции> <кол-во параметров> [<список имен параметров>]



Формат вывода:
Размер памяти (в ячейках)
имя 1-й вычисляемой функции
имя 2-й вычисляемой функции
...
имя функции, которую необходимо вычислить
Примечание: имя функции есть натуральное число от 1 до N.



Пример.

Ввод
5 1
1 2 2 3
2 0
3 2 4 5
4 0
5 0

Вывод
2
4
5
3
2
1



СТРОКА


Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 30 секунд
Тесты к задаче: Скачать



Задана строка длиной не более 127 символов, состоящая из цифр "0123456789", знаков арифметических операций "- + * /", а также знаков "=". Из строки можно удалить подстроку длиной более 1, если она содержит один знак '=', и образует истинное выражение.

Выражение называется истинным, если результат выполнения операций, находящихся справа и слева от знака "=", совпадают. Знак "/" используется в качестве обозначения целочисленной операции деления. Знаки "+" и "-" могут использоваться не только в качестве знаков сложения и вычитания, но и для обозначения знака числа. Приоритет выполнения операций стандартный.

выражение 2+-1=1 считается истинным выражением



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

Выходные параметры:
Длина итоговой строки
Итоговая строка



Пример.

Входной файл:
-117/2=+8=-1+9**


Результат:
4
+9**


Комментарий к примеру.

Сначала удаляется подстрока 17/2=+8, получаем строку -1=-1+9**. Из этой строки удаляем подстроку -1=-1 и получаем ответ +9**.

                      1996 рік. Умови олімпіадних завдань з інформатики

ТОЧКИ


Входной файл: input1.txt
Выходной файл: output1.txt
Время на тест: 10 секунд
Автор задачи: Волков И.А.
Тесты к задаче: Скачать



На оси Ох заданы N точек с целочисленными координатами. Некоторые точки могут иметь одинаковые координаты. Были измеряны и записаны всевозможные расстояния между этими точками. Расстояние между двумя точками мы храним только один раз, расстояние от точки до нее самой (равное 0) не хранится, поэтому расстояний всего N(N-1)/2.

Необходимо по введенной последовательности из N(N-1)/2 расстояний найти одно из возможных расположений точек на прямой или указать, что такого не существует.

Структура файла ввода:
1-ая строка - число N (натуральное, меньше 51)
2-ая - N(N-1)/2+1 строки: расстояние (по одному в строке)



Структура выходного файла:

"Расположение не существует" или же "Расположение существует"
Если решение существет, сформировать строки:
2-ая строка - число N
3-ая - N+1 - ая строки: координаты точек (по одной в строке)

Пример

Файл ввода:
4
1
2
1
0
1
1

Файл вывода
расположение существует
4
0
1
1
2

ПИРАМИДА ХЕОПСА


Входной файл: input2.txt
Выходной файл: output2.txt
Время на тест: 10 секунд
Автор задачи: Котов В.М.
Тесты к задаче: Скачать

Внутри пирамиды Хеопса есть N комнат, в которых установлены 2М модулей, составляющих М устройств. каждое устройство состоит из двух модулей, которые располагаются в разных комнатах, и предназначено для перемещения между парой комнат, в которых установлены эти модули. Перемещение происходит за 0.5 условных единицы времени. В начальный момент времени модули всех устройств переходят в "подготовительный режим". Каждый из модулей имеет некоторый свой целочисленный период времени, в течение которого он находится в "подготовительном режиме". По истечении этого времени модуль мгоновенно "срабатывает" после чего опять переходит в "подготовительный режим". Устройством можно воспользоваться только в тот момент, когда одновременно "срабатывают" оба его модуля.

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

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

Формат ввода:
N
M
R11 T11 R12 T12
...
RM1 TM1 RM2 TM2
где
N (2<=N<=100) - количество комнат
M (M<=100) - количество устройств
Ri1 и Ri2 - номера комнат, в которых располагаются модули устройства i
Ti1, Ti2 (Ti1,Ti2<=1000) - периоды времени, через которые срабатывают эти модули
Все числа - натуральные.

Пример ввода
4
5
1 5 3 2
1 1 2 1
2 5 3 5
4 4 3 2
3 5 4 5

Пример вывода
Оптимальное время: 8.5
искомая последовательность: 2 3 4



ЗАПОЛНИ МАССИВ


Входной файл: нет
Выходной файл: output3.txt
Время на тест: 10 секунд
Автор задачи: Омельянчук С.Н.
Тесты к задаче: Скачать

Заполнить массив A из 27 элементов следующим набором из 27 цифр: 1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7,7,8,8,8,9,9,9, так, чтобы для каждой цифры К (1...9) между элементом со значением К и следующим элементом со значением К было ровно К элементов. Например, между элементом со значением 3 и следующим элементм со значением 3 должно быть ровно 3 других элемента.

Требуется найти число N возможных вариантов и записать в файл все возможные варианты в следующем формате:
N                         - количество вариантов
A[1] A[2] ... A[27]       - первый вариант
...
A[1] A[2] ... A[27]       - N-ый вариант




МЕТОДИСТ О.Г.


Входной файл: input4.txt
Выходной файл: output4.txt
Время на тест: 10 секунд
Автор задачи: Котов В.М.


Тесты к задаче: Скачать

Методист по информатике О.Г. живет на N-ом этаже 9-этажного дома с лифтом, который может останавливаться на каждом этаже. Между соседними этажами дома имеется лестница из 2-х пролетов, разделенных площадкой, по К ступенек в каждом пролете. Сколькими способами О.Г. может подняться на свой этаж, если поднимаясь по лестнице можно становиться на следующую ступеньку или через одну ступеньку ?

Ввод
N K
где N, K - натуральные (N<=9, K<=15)

Вывод
S - число способов








ДВОИЧНЫЕ ЧИСЛА


Входной файл: input1.txt
Выходной файл: output1.txt
Время на тест: 2 секунды
Автор задачи: Волков И.А.
Тесты к задаче: Скачать

Среди всех N-битных двоичных чисел указать количество тех, у которых в двоичной записи нет подряд идущих К единиц. Сами числа выдавать не надо! N и K - натуральные, K<=N<=60

Ввод
N K

Вывод
M        - искомое количество

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

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

Действительно среди всех 3-битных двоичных чисел
    000 001 010 011 100 101 110 111
есть 5 чисел
    000 001 010 100 101
у которых в записи 2 единицы не идут подряд.



ДИСК И ЛОМАННАЯ


Входной файл: input2.txt
Выходной файл: output2.txt
Время на тест: 5 секунд
Авторы задачи: Котов В.М., Волков И.А.
Тесты к задаче: Скачать

На оси Ох стоит диск радиуса R с центром в точке (0,R). он начинает двигаться вдоль оси Ох вправо до тех пор, пока не встретит препятствие, которое представляет собой ломаную линию. Определить расстояние, которое пройдет центр диска до встречи диска с препятствием. Координаты X(i), Y(i) вершин ломаной определяются массивами X и Y с N элементами.

Ввод
R
N
X[1] Y[1]  (по 2 числа в строке)
...
X[N] Y[N]

где X[i] Y[i] - действительные < 10000
    R         - действительное <=10000
    N         - натуральное    <=100


Вывод
L             - действительное с абсолютной точностью 0.01
либо сообщение "NON STOP"



ВИДЕОСАЛОН


Входной файл: input3.txt
Выходной файл: output3.txt
Время на тест: 10 секунд
Автор задачи: Котов В.М.
Тесты к задаче: Скачать

Владелец видеосалона решил получить максимальный доход от своего бизнеса. В видеосалоне имеется неограниченное количество пустых видеокассет. Продолжительность каждой видеокассеты равна L. У владельца есть возможность записать на видеокассеты N фильмов, продолжительностью A(1), ..., A(N), A(i)<L. При этом он не может записывать на одну видеокассету один фильм дважды и не может оставить на кассете такое пустое место, на которое помещается целиком один из фильмов, не записанных на этой кассете. Фильмы на кассету пишутся целиком. Владелец видеосалона стремится таким образом записать фильм на кассеты, чтобы для просмотра всех фильмов клиент был вынужден взять на прокат наибольшее число кассет. Определить это число К.

Ввод
L
N
A[1]
...
A[N]

где A[i], L, N - натуральные, L<=1000, N<=100

Вывод
K


Пример ввода:
11
10
1
2
3
4
5
6
7
8
9
10

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

ШИФРОВКА

---

Входной файл: input4.txt
Выходной файл: output4.txt
Время на тест: 10 секунд
Автор задачи: Лобов Сергей Дмитриевич, Брест
Тесты к задаче: Скачать

Даны два текста A и B. С помощью текста B осуществляется шифровка текста A по следующим правилам:

берут два первых слова из каждого текста

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

затем вторая чать слова текста A склеивается с превой частью слова из текста B, образуя первое слово из зашифрованного текста S

аналогично вторая чать слова из текста B склеивается с первой частью слова из текста A, образуя второе слово текста S

далее аналогично берется следующая пара слов из текста A и B и так далее

в случает если в тексте B нет больше слов, то берется снова первое слово из текста B

процесс шифровки заканчивается по исчерпании слов текста А

Замечания :

слова состоят только из строчных букв кириллицы (русского алфавита)

слова в текстах A и B разделяются единственным пробелом

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

длина каждого из текстов A и B не превышает 40 символов

Зашифрованный текст S и шифр B располагаются в одной строке

Требуется по введенному зашифрованному тексту S и шифру B восстановить исходный текст A.

Тексты S и B начинаются со знака "<" и заканчиваются знаком ">". В случае, если расшифровка текста неоднозначна, вывести как можно большее число различных вариантов слова. Различные варианты слова разделяются запятой

Имя входного файла

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

S
B

Вывод в файл

A         (исходный текст)

Пример 1: Вход <ааа> <аад сааа> Выход дсаа, адса, аадс

Пример 2: Вход <дом> <ом> Выход д