uzluga.ru
добавить свой файл
1

VIP-турнир 2011 стр. из

Задача A. «Провода»

Входной файл: wires.in

Выходной файл: wires.out

Ограничение памяти: 64 М байт

Ограничение времени: 1 секунда на тест


В компьютерном классе n компьютеров. Их надо соединить в сеть. Известно, какие компьютеру нужно соединить проводами для правильной работы сети. Осталось расставить компьютеры так, чтобы каждый компьютер находился в точке с положительными целочисленными координатами, и никакие два провода не пересекались. Компьютеры для простоты будем считать точками, а провода – отрезками. Сеть является связной, то есть любые два компьютера соединены некоторой последовательностью проводов.


Вход

В первой строке входного файла записано количество компьютеров n (1 <= n <= 1000). Далее идёт n-1 строка, в каждой из которых записано два числа ai, bi – номера компьютеров, которые нужно соединить проводом (1 <= ai, bi <= n, ai ≠ bi).

Выход

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


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

wires.in

wires.out

3

1 2

2 3

1 1

2 2

3 3



Задача E. «Цифры»

Входной файл: digits.in

Выходной файл: digits.out

Ограничение по времени: 1 секунда на тест

Ограничение по памяти: 64M байт


Запишем последовательно и без пробелов натуральные числа от 1 до N. Например, для N = 13 мы получим последовательность 12345678910111213. А теперь посчитаем, сколько раз каждая цифра входит в эту последовательность. Цифра 0 входит 1 раз, цифра 1 – 6 раз, цифра 2 – 2 раза и так далее. Напишите программу, которая для заданного N будет находить количество вхождений в такую последовательность для всех цифр от 0 до 9.


Вход

Во входном файле записано натуральное число N (1 <= N <= 108).


Выход

Запишите в выходной файл через пробел десять чисел – количество вхождений цифр 0, 1, …, 9 в получившуюся последовательность.


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

digits.in

digits.out

3

0 1 1 1 0 0 0 0 0 0

13

1 6 2 2 1 1 1 1 1 1

Задача B. «Ниндзя»

Входной файл: ninja.in

Выходной файл: ninja.out

Ограничение времени: 1 секунда на тест

Ограничение памяти: 64 М байт


Как вам известно, ниндзя перемещаются, прыгая с вершины одного дерева на вершину другого дерева. Клан ниндзя планирует высадить целую аллею из N деревьев для проведения тренировок. В процессе тренировки ниндзя влезает на вершину самого низкого дерева, затем перепрыгивает на вершину следующего по высоте дерева, и так далее, пока не окажется на вершине самого высокого дерева, выполнив N-1 прыжок и побывав на каждом дереве ровно один раз. Ниндзя могут совершать прыжки не более чем на D метров по горизонтали (разность высот деревьев при этом не имеет значения – так уж устроены ниндзя). Чтобы сделать тренировку максимально приятной, ниндзя хотят максимизировать расстояние между самым низким и самым высоким деревом. Они уже закупили N деревьев различной высоты и пронумеровали их. Учтите, что деревья пронумерованы вовсе не в порядке возрастания высоты, а исходя из других соображений, понятных лишь ниндзям. Деревья должны быть высажены с соблюдением следующих правил:

· деревья высаживаются вдоль прямой линии;

· деревья высаживаются в точках с целочисленными координатами;

· координаты всех деревьев различны;

· деревья высаживаются строго в порядке возрастания номеров.

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


Вход


В первой строке входного файла записаны два целых числа – количество деревьев N (1 ≤ N ≤ 105) и максимальная горизонтальная проекция прыжка ниндзя D (1 ≤ D ≤ 106). В остальных строках записаны высоты деревьев в порядке возрастания номеров. Все высоты – попарно различные положительные целые числа, не превосходящие 106.


Выход


Запишите в выходной файл максимально возможное расстояние между самым низким и самым высоким деревьями. Если задача не имеет решения, запишите в выходной файл число -1 (минус единица).


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

ninja.in

ninja.out

4 4

20 30 10 40

3


5 6

20 34 54 10 15

3


4 2

10 20 16 13

-1


Задача C. “Данные”

Входной файл: data.in

Выходной файл: data.out

Ограничение времени: 1 секунда на тест

Ограничение памяти: 64 М байт

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

Таким образом, важнейшей задачей оказалось надёжное определение количества городов на планете Плюк, и эта задача поручена вам!

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



A B C D E F

Квадрат A – пустой, квадраты B-E частично заняты городом, квадрат F – полностью занят городом. Если два квадрата имеют общую сторону, и эта сторона в обоих квадратах принадлежит городу, то в обоих квадратах расположен один и тот же город. На рисунке показан снимок, содержащий три города:



Вход

В первой строке входного файла записаны натуральные числа N и M (1 £ N, M £ 1000). В следующих N строках записано по M символов “A”, “B”, “C”, “D”, “E” или “F”.

Выход

Запишите в выходной файл количество городов на планете Плюк.

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

data.in

data.out

1 2

DD

2

2 2

FB

DF

1

2 3

FAA

AFB

2

4 4

AACB

CAFD

AFCE

AACA

6


Задача D. «Игра»

Входной файл: game.in

Выходной файл: game.out

Ограничение по времени: 1 секунда на тест

Ограничение по памяти: 64M байт


Всем известна игра 15, где надо выстроить изначально неупорядоченную последовательность чисел, перемещая фишки с нанесёнными числами от 1 до 15 в квадрате 4x4. На основе данной игры была разработана другая – поле в ней имеет размер лишь 4 на 2 клетки, на поле 7 фишек, на фишках изображены буквы латинского алфавита и арабские цифры (на каждой фишке – один символ, но на разных фишках могут быть одинаковые символы). Цель игры прежняя – упорядочить в соответствии с образцом стартовую расстановку фишек за минимальное количество ходов. Свободная клетка обозначается специальным символом # и используется для перемещения фишек по полю. Перемещать фишки на свободную клетку разрешается из соседних клеток, имеющих общую грань со свободной. Например, на рисунке более правый символ 0 можно переместить вниз на свободную клетку, тогда 0 будет в нижней клетке, а пустой станет верхняя клетка, либо в свободную клетку переместить букву C или цифру 2.


M

0

0

A

8

C

#

2



Вход

Входной файл содержит четыре строки: две первые строки содержат стартовую комбинацию символов, следующие две - образец. Каждая строка содержит 4 символа (латинский алфавит и арабские цифры), пустая клетка обозначается символом #.


Выход

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


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

game.in

game.out

ACM8

002#

ACM#

2008

17

rogp

mar#

prog

ram#

26



Задача F. «Треугольная игра»

Входной файл: trigame.in

Выходной файл: trigame.out

Ограничение времени: 2 секунды на тест

Ограничение памяти: 64 М байт


Вася и Петя играют в игру на треугольном поле. Поле состоит из кружочков, расположенных как показано на рисунке. Каждый кружочек определяется тремя барицентрическими координатами X, Y и Z.

Координата X увеличивается слева направо, координата Y увеличивается справа налево, а координата Z – снизу вверх. Для каждого кружочка сумма трёх координат одинакова и равна натуральному числу N, называемому размером поля. Поле размера N состоит из (N+2)(N+1)/2 кружочков. Кружочки, у которых X=0, образуют X-сторону поля, кружочки с Y=0 образуют Y-сторону, и кружочки с Z=0 образуют Z-сторону поля. В процессе игры Вася ставит на некоторые кружочки чёрные фишки, а Петя – белые фишки. На каждом кружочке может стоять не более одной фишки. Правила игры очень сложные, мы не будем их здесь описывать. Но в момент окончания игры на каждом кружочке находится фишка – чёрная или белая. Победителем игры признаётся тот игрок, чьи фишки образуют связную область, включающую хотя бы по одному кружочку с каждой из трёх сторон поля. На рисунке показано состояние поля в конце игры, в которой победил Вася. Если поле невелико, довольно легко определить победителя. Но на большом поле эта задача становится не такой уж простой. Вася и Петя просят вас написать программу, которая будет получать состояние поля и определять победителя игры.

Вход

В первой строке входного файла записано два целых числа N – размер поля и M – количество чёрных фишек (0 ≤ N ≤ 2000, 0 ≤ M ≤ (N+2)(N+1)/2). В каждой из следующих M строк записано по три целых числа x, y, z – координаты чёрных фишек (0 ≤ x, y, zN, x+y+z = N). Гарантируется, что каждая фишка указана один раз.

Выход

Запишите в выходной файл число 1, если победил Вася, число 2, если победил Петя, и число 0, если не победил никто.


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

trigame.in

trigame.out

3 5

0 1 2

1 0 2

3 0 0

1 1 1

1 2 0

1

2 3

0 0 2

1 0 1

0 2 0

2

1 1

1 0 0

2


Задача G. «Судьба»

Входной файл: fate.in

Выходной файл: fate.out

Ограничение времени: 1 секунда на тест

Ограничение памяти: 64 М байт


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

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


Вход

В первой строке входного файла записаны три целых числа: N – количество флатландцев в группе, B, H – размеры Флатландии (1 ≤ N ≤ 100, 2 ≤ B, H ≤ 100). Напоминаем, что Флатландия есть прямоугольник со сторонами, параллельными осям координат, и координатами противоположных углов (0, 0) и (B, H). В каждой из следующих N строк записано по четыре целых числа x0, y0координаты точки, где родился флатландец, x1, y1 – координаты точки на краю Флатландии, в которую он первоначально двигался (0 ≤ x0, x1B, 0 ≤ y0, y1H), и символьная строка, содержащая не более 10 маленьких латинских букв - имя этого флатландца. Начальные координаты флатландцев попарно различны. Имена также уникальны. Все данные в строке разделены ровно одним пробелом.


Выход

Запишите в выходной файл имя флатландца, который умрёт последним. Если последними одновременно закончат свой путь несколько флатландцев, запишите в выходной файл лексикографически последнее из их имён.


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

fate.in

fate.out

2 20 23

1 1 0 0 BOB

^ 3 3 3 0 ALICE

ALICE

3 20 23

2 2 3 0 ALICE

4 2 2 0 BOB

1 3 0 3 CHARLES

BOB


Задача H. «Предпочтения»

Входной файл: preference.in

Выходной файл: preference.out

Ограничение времени: 1 секунда на тест

Ограничение памяти: 64 М байт


«Брачное агентство Exclusive предлагает быстро, удобно, конфиденциально

подобрать себе партнера для создания семьи, который гарантировано

будет подходить вам по характеру, телосложению, цвете волос и прочих

параметрах. Всех клиентов Брачное агентство тестирует, опытный

психолог составляет психологический портрет и уже на его основе в

совокупности с личных предпочтений и пожеланий, подбираеться

потенциальный партнер» - из сети.


Брачное агентство – выгодный бизнес. Однако «подобрать по цвете волос и других параметрах» - это прошлый век. Продвинутые агентства теперь работают по-другому. Каждый клиент опрашивается на предмет его предпочтений, и определяются приоритеты клиента. Например, между ценностями «выпить пива» и «театр» клиент выбирает «выпить пива». А между «театр» и «чистота в доме» он выбирает «театр». Агентство полагает, что подробный опрос клиента даёт достаточно точный психологический портрет, и два человека с непротиворечивыми системами предпочтений всегда будут психологически совместимы.

Формализуем понятие «непротиворечивые системы предпочтений». Пусть первый клиент заявил, что из двух ценностей A и B он предпочитает A, из B и C предпочитает B, и из D и E предпочитает D. Его психологический портрет в этом случае имеет вид A > B > C, D > E. Обратите внимание, что психологический портрет каждого клиента непротиворечив, так, например предпочтение C > A несовместимо с предпочтениями A > B, B > C, так как из этих трёх предпочтений можно вывести A > A, что невозможно. Пусть психологический портрет второго клиента содержит предпочтения Z > A, C > E > F. В этом случае два клиента считаются полностью совместимыми, так как существует такая система предпочтений, в которую целиком входят системы предпочтений обоих клиентов. В данном примере это Z > A > B > C > D > E > F. Бизнес есть бизнес, поэтому агентство решило не обязательно достигать полной психологической совместимости. Ведь вполне себе счастливая семейная пара может получиться и при частичной совместимости. Считается, что два клиента частично совместимы, если их системы предпочтений станут непротиворечивыми после удаления какого-нибудь одного предпочтения одного из клиентов. Такой подход сразу повысил прибыльность бизнеса, но потребовал специального программного обеспечения.

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


Вход

В первой строке входного файла записано натуральное число N – суммарное количество ценностей, упомянутых первым и вторым клиентом (1 ≤ N ≤ 100). Все ценности для простоты пронумерованы натуральными числами от 1 до N. Во второй строке входного файла записан психологический портрет первого клиента в формате

a11>a12>…>a1m1; a21>a22>…>a2m2;… at1>at2>…>atmt.

где aij – номер ценности, mi > 1. Строка может содержать пробелы в любом месте (только не внутри числовых констант), в том числе и после точки. В третьей строке в таком же формате записан психологический портрет второго клиента.


Выход

Запишите в выходной файл символ “F”, если клиенты полностью совместимы, “P”, если клиенты частично совместимы, или символ “N”, если клиенты не совместимы.


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

preference.in

preference.out

7

1>2>3; 2>4; 3>5>7.

2>6>7; 1>4.

F

7

1>2>3; 2>4; 3>5>7.

2>6>7; 1>4; 5>1.

P

7

1>2>3; 2>4; 3>5>7.

2>6>7; 1>4; 7>5>1.

N



Задача I. «Рассадка»

Входной файл: seats.in

Выходной файл: seats.out

Ограничение времени: 1 секунда на тест

Ограничение памяти: 64 М байт


Однажды N2 программистов решили пойти в кино. К счастью, зрительный зал кинотеатра вмещает ровно N рядов по N кресел в каждом, так что всем программистам хватило билетов. Но программисты не могут расположиться в зале, как попало. Вы знаете, что одни программисты предпочитают язык Паскаль, другие – С++, третьи – java, четвёртые презирают всё, кроме QBasic4.5, и так далее. В общем, программисты делятся на группы единомышленников, непримиримые по отношению ко всем другим группам. И, конечно, в кино каждая группа хочет сидеть вместе. Более того, каждая группа согласна занять только некоторую прямоугольную область зала. Предводители групп пришли в зал заранее и заняли места. Теперь на подходе основная масса программистов, и вам необходимо написать программу для нахождения правильной рассадки.


Вход

В первой строке входного файла записано натуральное число N (1 ≤ N ≤ 10). В следующих N строках записан план зрительного зала – по N символов в строке. Символ «.» (точка) означает пустое кресло, а символы «1», «2», …, «9» - кресло, где сидит предводитель группы, включающей, соответственно, 1, 2, …, 9 программистов. Предводителей в зале не более 26.


Выход

Запишите в выходной файл план рассадки программистов. Программистов одной группы обозначайте одной из заглавных латинских букв (любой). Но каждую букву используйте только для одной группы. Учтите также, что предводители не согласны пересаживаться. Если программистов рассадить невозможно, запишите в выходной файл строку “no solution”.


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

seats.in

seats.out

3

3.4

...

.2.

ABB

ABB

ACC

3

33.

.3.

...

no solution