ЗАДАЧА 1

ЗАДАЧА 1 . Хокку, танка, бронетранспортеры (10 сек.)

В средневековой Японии в большом почете было искусство написания (часто экспромтом) коротких "белых" (без рифмы) n-стиший - хокку,  танка, хайко и т.п.  Готовые n-стишия такого рода могут быть найдены в текстах, написанных  с другими целями, например в сообщениях программ об ошибках.  Фраза  считается соответствующей размеру n-стишия, если ее можно разбить на  n строк так, чтобы в каждой строке было ровно заданное количество гласных букв.  Заметим, что если фраза содержит слово без гласных букв, то она не соответствует формату. Разумеется, разбивать слова и переносить их части между строками  нельзя.  Запрещается также переставлять слова.

Напоминаем, что к гласным буквам относятся следующие символы набора ASCII:

 A, E, I, O, U, Y, a, e, i, o, u, y . 

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

Первая строка входного файла содержит N + 1 целых чисел, записанных через пробел (0 < N < 11), которые задают размер стихотворения. Первое число из них - количество строк в стихотворении N. После него N чисел по порядку определяют количество гласных в соответствующих строках.  Далее следуют фразы, которые необходимо проверить на соответствие размеру.  Фраза занимает ровно одну строку. Ее длина не превышает 255 литер. В тексте используются только символы набора ASCII с кодами, не превышающими 127. Разделителем между словами считается только символ пробела.

Количество фраз во входном файле £ 1000.

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

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

Пример

Входной файл: input.txt

3 5 7 5

The users in the domain could not be enumerated.

jafbashjfhfjgbakgb fhdgbsjhfdgbfgbskfgbjhf gfshdgbjhfdgbsjhdgsfdjh

Выходной файл: output.txt

The users in the

domain could not be

enumerated.

 

 

В примере задается формат хайку: 3 строки, в первой строке 5 гласных букв, во второй - 7, и в третьей - 5. Затем приведены две фразы. Первая фраза удовлетворяет заданному формату, поэтому она записана в выходной файл в соответствующем виде. Вторая фраза, очевидно, этому формату не удовлетворяет.

ЗАДАЧА 2. Лыжные маршруты (5 сек.)

В окрестностях Новосибирска решили провести Открытый чемпионат Мира по лыжным гонкам. Желающих участвовать в нем очень много (особенно многочисленные команды приедут из Сибири, Канады и Африки), поэтому необходимо в короткое время провести отбор основных участников. Это значит, что соревнования нужно проводить одновременно на нескольких лыжных трассах. В тайге разместили N баз, куда участников соревнований должен доставлять вертолет. Между этими базами необходимо проложить лыжные маршруты так, чтобы два разных маршрута не пересекались. Между двумя различными базами может проходить только один маршрут. Любой маршрут должен начинаться на одной базе, а заканчиваться на другой, не проходя при этом через третью.

Организаторов соревнований интересует, какое максимальное количество лыжных трасс можно проложить.

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

Во входном файле записано одно целое число N (2 £  N £ 10000) количество лыжных баз.

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

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

Пример

Входной файл: input.txt

Выходной файл: output.txt

3

3

5

9

 

ЗАДАЧА  3. Сотовая связь (20 сек.)

            Сеть сотовой связи состоит из нескольких базовых станций.  Сигнал каждой из станций принимается на определенной территории, называемой зоной приема. Зоны приема станций частично пересекаются.  Их объединение образует зону приема сети в целом.  Размещение базовых станций определяется различными соображениями, прежде всего - рельефом местности и ожидаемым количеством абонентов на данной территории. При этом никакие две станции с пересекающимися зонами приема не могут работать в одном частотном диапазоне.  Оператор сотовой связи оплачивает занятые им частотные диапазоны, поэтому заинтересован в минимизации их количества.

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

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

Первая строка входного файла содержит целое число N -  количество базовых станций (0 < N < 15).

Следующие N строк содержат описания каждой станции: координаты X и Y и радиус зоны приема R, разделенные пробелами.  Все координаты целочисленные, 0 < X, Y, R < 16000. 

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

В выходной файл нужно вывести одно целое число - минимальное количество частотных каналов.

Пример

Входной файл: input.txt

Выходной файл: output.txt

3

1 1 80

100 100 80

50 80 80

3

 

ЗАДАЧА 4. Наполеоны (10 сек.)

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

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

В первой строке входного файла записано целое число N - количество горок (3 £ N £ 1000),

 и в последующих N строках - координаты этих горок x,y (пары целых чисел -30000 £ x,y £ 30000) через пробел.

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

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

Пример

Входной файл: input.txt

Выходной файл: output.txt

6

5 3

3 6

7 1

2 1

5 6

7 7

15.00

ЗАДАЧА 5. Династия фараонов (5 сек.)

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

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

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

Во входном файле описывается родовое дерево фараонов, а также догадки археологов об их возможных именах. В первой строке содержится число N - количество фараонов в династии (N £ 50).  Для удобства общения с археологами все фараоны  пронумерованы числами от 1 до N.

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

В следующих N строках содержится информация о том, какие имена могли иметь фараоны, судя по остаткам надписей на стенах гробницы. В каждой строке перечисляются через пробел возможные имена фараона, имеющего соответствующий номер. Имена представляют собой последовательность символов латинского алфавита. Длина каждого имени не может быть больше 20. Регистр значения не имеет. Длина каждой строки с возможными именами фараонов не превосходит 255 символов.

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

В выходной файл нужно вывести имена фараонов в порядке, соответствующем их номерам. Каждое имя на отдельной строке.

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

 

Пример

Входной файл: input.txt

Выходной файл: output.txt

3

1 2 2 3

0 0

Tutmos Totmos

Totmos Tatmos

Tatmos

Tutmos

Totmos

Tatmos

3

2 1 2 3

0 0

Iakis Tukis

Tukis Pokis

Iakis Pokis

NO

4

3 1 3 2 1 4

0 0

Laps Taps

Laps

Maps Shnaps

Taps

NO

 

ЗАДАЧА 6. Квадрат (5 сек.)

В центре координатной плоскости находится квадрат со стороной 3 и координатами нижнего левого угла (-1.5, -1.5) и правого верхнего угла (1.5, 1.5).  Этот квадрат разделен на девять квадратов со стороной 1, пронумерованных в соответствии со схемой:

 

1

2

3

4

5

6

7

8

9

 

Еще один квадрат со стороной 1 размещен таким образом, что его центр находится внутри квадрата ©5.  Этот маленький квадрат повернут относительно осей координат на некоторый угол. Требуется указать номера квадратов, которые он пересекает.

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

Входной файл состоит из одной строки, которая содержит три числа. Первые два числа - координаты центра маленького квадрата X и Y ( -0.5 £  X, Y £  0.5). Это действительные числа, заданные с точностью до трех знаков после десятичной точки.  Третье - целое число U (0 £ U < 90), задающее в градусах угол наклона стороны этого квадрата по отношению к вертикали по часовой стрелке.

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

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

 Примечание:

Пересечением считается пересечение сторон. Если одна из вершин данного квадрата лежит на стороне одного из пронумерованных, то это считается пересечением.

Пример

Входной файл: input.txt

Выходной файл: output.txt

0.4 0.4 0

2 3 5 6

 

ЗАДАЧА 7. Оптимизация линейной программы (5 сек.)

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

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

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

Описание входного языка:

1.      Программа - это последовательность строк, каждая из которых содержит одну команду. Команды исполняются в порядке их записи в программы.

2.      Общий формат команды:
  <имя команды> <регистр-результат> <операнд1> [<операнд2>]
где
      <операнд> - это <регистр> или <константа>,
      <регистр> - это латинская буква от A до Z,
      <константа> - это целое десятичное число в диапазоне [-231 .. 231-1].
Все слова в команде разделяются произвольным числом пробелов.
Строчные и прописные буквы не различаются.

3.      Набор команд:
      MOV  reg op1       à   reg := op1
  ADD  reg op1 op2   à   reg := op1 + op2
  SUB  reg op1 op2   à   reg := op1 - op2
  MUL  reg op1 op2   à   reg := op1 * op2
Все вычисления ведутся в диапазоне [ -231.. 231-1] по модулю 232 , без ошибок переполнения.

4.      Регистры, в которые не производится засылка значений до первого использования в программе, считаются входными аргументами программы. Их значения определены, но неизвестны.

5.      Последней строкой программы считается список значимых результатов в виде:
      RES  [reg1 [reg2 [...]]]                       список регистров - результатов программы

6.      Программа исполняется в последовательности записи команд.

 

Описание оптимизирующих преобразований:

1.  Просачивание константы. Если операнд-регистр в некоторой команде содержит известное значение, операнд-регистр заменяется на операнд-константу, представляющую это значение:
      MOV R 8
  ADD P Q R     à   ADD P Q 8

2.      Константное вычисление. Если результат арифметической команды может быть вычислен, исходя из известных значений ее аргументов или при любых аргументах, команда заменяется на засылку вычисленного значения:
      ADD R 8 5     à   MOV R 13

     ADD P Q 0     à   MOV P Q

     MUL S 1 T     à   MOV S T

     SUB D A A     à   MOV D 0    

(см.также последнюю строку в примере на преобразование 4).

3.      Удаление бесполезного вычисления. Если результат вычисления или засылки не используется в дальнейшем, и регистр не указан в списке результатов программы, команда удаляется:
  SUB R 9 P     à   удалить

{код, не использующий R}

{команда с результатом R}

4.  Удаление бесполезной пересылки. Если в регистр засылается значение, тождественное его собственному, команда засылки удаляется. Два значения считаются тождественными, если: а) они известны и численно равны; б) они оба получены в результате цепочки пересылок одного и того же неизвестного значения.
      MOV Е Е                  à        удалить, т.к. одно и то же значение
      MOV P A
      MOV A P                  à        удалить, т.к. P = A
      MOV Q P
      MOV R Q
{команды, не перевычисляющие P, Q, R}
      MOV R Q                  à        удалить, т.к. R = Q
{команды, не перевычисляющие P, R}
      MOV R P                  à        удалить, т.к. R = P
      SUB Z R Q             à        MOV Z 0 , т.к. R = Q

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

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

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

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

 

Пример

Входной файл: input.txt

Выходной файл: output.txt

MOV T A

MOV C 8

ADD X T C

MOV D 4

ADD D D D

SUB R X D

RES R

MOV T A

ADD X T 8

SUB R X 8

RES R

 

Комментарий:

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

MOV R A

RES R

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

 

ЗАДАЧА 8. Аппроксимация (10 сек.)

Василий Иванович - человек прямой. По этой причине он только прямые линии и умеет рисовать. Но уж прямые-то он рисует мастерски. Просто загляденье. Какую хочешь, такую и проведет. А Петька ему все какие-то неправильные функции подсовывает - то кубическую параболу, то вида c*exp(k*x), то еще чего. И вынужден бедный Василий Иванович прямыми Петькину функцию как можно лучше и как можно дальше приближать, не выходя при этом за рамки дозволенной суммы квадратов отклонений в заданных точках xi. Так и мается, бедняга. Помогите ему.

       Итак, заданы точки xi = x0+h*i (0 £ i £ N, 0 < N £ 200000, 0.1 £ h £ 1, 0 £ x0 £ 103) и значения аппроксимируемой функции FA в этих точках.  Необходимо провести аппроксимирующую прямую FL(x) на как можно более длинном начальном участке x0 ... xm,  так, чтобы сумма квадратов отклонений в этих точках исходной и аппроксимирующей функции была не больше заданной погрешности  E  (0.1 £ E £ 1):

.

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

Первая строка входного файла содержит четыре числа Е, x0, N, h, записанные через пробел. Е, x0  и h задаются с точностью до двух знаков после запятой. Далее в  N +1 строках задаются значения исходной функции FA в соответствующих точках по порядку от x0 до xN с точностью до 5 знаков после запятой (-10 £  FA(xi)£  10, 0 £ i £ N ).

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

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

Пример

Входной файл: input.txt

Выходной файл: output.txt

0.1 0 4 1

0

1.0

2

3.00001

6

3