Задача A. Столкновение шариков ≡

Условие

По горизонтальной плоской поверхности катятся два шарика радиуса R метров каждый. В начальный момент времени шарики имеют координаты центров (x₁, y₁) и (x₂, y₂) метров, а также проекции скоростей на координатные оси (dx₁, dy₁) и (dx₂, dy₂) метров в секунду соответственно.

Требуется найти время в секундах, спустя которое шарики столкнутся, или определить, что этого не произойдёт.

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

1
0 0 10 0
50 0 -10 0

2.4

Задача B. Пеленг НЛО ≡

Условие

Два радара, расположенные в точках с координатами (0, 0) и (100, 0), обнаружили неопознанный объект. По таинственной причине, связанной, возможно, с внеземной природой объекта, радары оказались способны определить только направление на объект (пеленг), но не расстояние до объекта. Пеленг измеряется в градусах, против часовой стрелки, начиная от направления "на восток" (т. е. пеленг второго радара относительно первого равен 0°, пеленг первого радара относительно второго — 180°).

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

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

45.1 135.0

49.9127 50.0873

135.0 45.0

0 0

Задача C. Поездка на Хэллоуин ≡

Условие

Владивостокский программист приглашает коллегу к себе домой в гости на празднование Хэллоуина.

Оба программиста живут за городом. Их дома расположены в точках с координатами (X_A; Y_A) и (X_B; Y_B).

В этом районе есть только одна асфальтированная дорога, представимая в виде отрезка с координатами начала (X_S; Y_S) и конца (X_E; Y_E). Дорога является платной: за любой въезд на дорогу (проезд по произвольному участку дороги или только пересечение — не имеет значения) взимается плата в размере C_R. Остальная местность занята полями, которые (в связи со скорым Хэллоуином) сплошь засажены тыквами. При движении на автомобиле по полю взимается плата в размере C_F за каждый километр пути — ущерб за раздавленные тыквы.

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

Обратите внимание, при сколь угодно малом приближении к дороге плата за въезд на неё не взимается. Смотрите пример №3.

Формат входного файла

Формат выходного файла

Ограничения

−10³ ≤ X_A, Y_A, X_B, Y_B, X_S, Y_S, X_E, Y_E ≤ 10³

1 ≤ C_F ≤ 10³

1 ≤ C_R ≤ 10⁶

Дома программистов находятся в разных точках и не находятся на дороге

Примеры тестов

1 1 2 2 0 3 3 0 1 1

2.414213562373095

1 5 4 0
-2 -2 10 10
1 2

7.656854249492381

10 10 25 19
15 13 20 16
1 1000000

17.492855684535900

Задача D. Точка Ферма-Торричелли ≡

Условие

Для заданных трёх точек A, B, C найти такую точку O, что AO + BO + CO — минимально.

Формат входного файла

Во входном файле содержатся целые числа X_A Y_A X_B Y_B X_C Y_C — координаты точек A, B, C соответственно.

Формат выходного файла

Выходной файл должен содержать два числа X_O Y_O — координаты точки O с точностью до 3-х знаков после запятой.

Ограничения

0 ≤ |X_A|, |Y_A|, |X_B|, |Y_B|, |X_C|, |Y_C| ≤ 10⁵

Никакие две точки не совпадают

Примеры тестов

4 2 0 0 2 2

2 2

-2 -3 1 3 4 -2

1.30120904214632 -0.720188590098661

Задача E. Выпуклая оболочка ≡

Условие

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

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

Углом называется геометрическая фигура, образованная двумя лучами, выходящими из одной точки. Эта точка называется вершиной угла.

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

Формат входного файла

Первая строка входного файла содержит число n — количество углов. Каждая из следующих n строк описывает углы. Каждый угол описывается координатами трех точек: вершины и двух отличных от вершины точек — по одной на каждом из лучей.

Формат выходного файла

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

На первой строке выведите l — количество объектов в ответе. Следующие l строк должны со- держать описание объектов. Объекты описываются следующим образом:

• Отрезок: "segment x₁ y₁ x₂ y₂", где (x₁, y₁) и (x₂, y₂) — концы отрезка, отрезок считается направленным от (x₁, y₁) к (x₂, y₂).
• Луч, направленный от начала: "outray x₁ y₁ x₂ y₂", где (x₁, y₁) — начало луча, а (x₂, y₂) — произвольная точка на луче, отличная от начала.
• Луч, направленный к началу: "inray x₁ y₁ x₂ y₂", где (x₂, y₂) — начало луча, а (x₁, y₁) — произвольная точка на луче, отличная от начала.
• Прямая: "line x₁ y₁ x₂ y₂", где (x₁, y₁) и (x₂, y₂) — две точки на прямой, причем при движении вдоль прямой в ее направлении точка (x₁, y₁) следует ранее точки (x₂, y₂).

Если выпуклой оболочкой является вся плоскость, то выведите l = 0.

Ограничения

1 ≤ n ≤ 1000

Все координаты целые и не превышают 10⁴ по абсолютной величине. Величина угла находится в диапазоне от 0 до 180 градусов, не включительно.

Примеры тестов

2
3 1 4 1 4 4
2 2 4 3 3 4

3
inray 4 1 3 1
segment 3 1 2 2
outray 2 2 3 5

2
0 0 1 0 0 1
0 0 -1 0 0 1

1
line 1 0 -1 0

2
0 0 1 0 0 1
0 0 -1 0 0 -1

0

Problem F. Aerodynamics ≡

Statement

Bill is working in a secret laboratory. He is developing missiles for national security projects. Bill is the head of the aerodynamics department.

Input file format

Output file format

Constraints

4 ≤ n ≤ 100

0 ≤ z_min ≤ z_max ≤ 100

Sample tests

9 0 5
0 0 5
-3 0 2
0 -1 2
3 0 2
0 1 2
2 2 0
2 -2 0
-2 -2 0
-2 2 0

16.00000
14.92000
10.08000
4.48000
1.12000
0.00000

Задача G. Водовод на о. Русский ≡

Условие

При строительстве нового кампуса ДВФУ на о. Русском по дну пролива был проложен водовод с материка на остров. К сожалению, после завершения строительства все чертежи были утеряны, а строители разъехались. Чтобы восстановить карту водовода, были проведены гидрографические работы.

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

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

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

Формат входного файла

Первая строка входного файла содержит размеры карты — высоту H и ширину W. Далее следует H строк по W символов в каждой — карта.

Формат выходного файла

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

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

Если водовод восстановить невозможно, выведите единственное слово NO.

Ограничения

2 ≤ H, W ≤ 200

Примеры тестов

4 5
...##
##...
.####
...#.

YES
6  2 1  2 2  3 2  3 3  3 4  3 5 

3 6
#.###.
###.##
......

MULTIPLE
9  1 1  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6

3 6
..###.
###.##
..###.

MULTIPLE
8  2 1  2 2  2 3  1 3  1 4  1 5  2 5  2 6
8  2 1  2 2  2 3  3 3  3 4  3 5  2 5  2 6

3 3
...
.##
...

NO

Problem H. Breadth First Search ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 2 1
1 2
2 3

1 2 3

Задача I. Лабиринт ≡

Условие

Лабиринт размером N x N клеток задан массивом символов. Символ '#' обозначеет стену, символ '.' — проход. Передвигаться по лабиринту можно шагами по горизонтали или вертикали, но не по диагонали.

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

Формат входного файла

Первая строка входного файла содержит размер лабиринта N.

Следующие N строк содержат по N символов — описание лабиринта.

Формат выходного файла

Выходной файл должен содержать единственное целое число — длину кратчайшего пути, либо −1, если пути не существует

Ограничения

Примеры тестов

2
.#
..

2

2
.#
#.

-1

Задача J. Производство деталей ≡

Условие

Предприятие «Авто-2010» выпускает двигатели для известных во всем мире автомобилей. Двигатель состоит ровно из n деталей, пронумерованных от 1 до n, при этом деталь с номером i изготавливается за p_i секунд. Специфика предприятия «Авто-2010» заключается в том, что там одновременно может изготавливаться лишь одна деталь двигателя. Для производства некоторых деталей необходимо иметь предварительно изготовленный набор других деталей.

Генеральный директор «Авто-2010» поставил перед предприятием амбициозную задачу — за наименьшее время изготовить деталь с номером 1, чтобы представить ее на выставке.

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

Система оценивания

Решения, правильно работающие только для тестов, в которых n не превосходит 10, будут оцениваться из 40 баллов.

Решения, правильно работающие только для тестов, в которых n не превосходит 100, будут оцениваться из 60 баллов.

Решения, правильно работающие только для тестов, в которых n не превосходит 1000, будут оцениваться из 80 баллов.

Формат входного файла

Первая строка входного файла содержит число n — количество деталей двигателя. Вторая строка содержит n натуральных чисел p₁, p₂… p_n, определяющих время изготовления каждой детали в секундах.

Каждая из последующих n строк входного файла описывает характеристики производства деталей. Здесь i-ая строка содержит число деталей k_i, которые требуются для производства детали с номером i, а также их номера.

Известно, что не существует циклических зависимостей в производстве деталей.

Формат выходного файла

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

Ограничения

1 ≤ n ≤ 100000, 1 ≤ p_i ≤ 10⁹

Сумма всех чисел k_i не превосходит 200000.

Примеры тестов

3
100 200 300
1 2
0
2 2 1

300 2
2 1

2
2 3
1 2
0

5 2
2 1

4
2 3 4 5
2 3 2
1 3
0
2 1 3

9 3
3 2 1

Задача K. КПК ≡

Условие

Хакер Вася решил собрать карманный персональный компьютер (КПК). Согласно найденной им в Интернет инструкции компьютер собран правильно тогда, когда ток из каждой микросхемы может пройти в каждую и притом единственным путем.

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

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

3 1
2 3

1
2 3
1
1 2

Задача L. Метро ≡

Условие

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

Напишите программу, которая по данному вам описанию метрополитена определит, с каким минимальным числом пересадок можно добраться со станции A на станцию B. Если данный метрополитен не соединяет все линии в одну систему, то может так получиться, что со станции A на станцию B добраться невозможно, в этом случае ваша программа должна это определить.

Формат входного файла

Во входном файле записано сначала число N — количество станций метро в городе. Далее записано число M — количество линий метро. Далее идет описание M линий. Описание каждой линии состоит из числа P_i — количество станций на этой линии и P_i чисел, задающих номера станций, через которые проходит линия (ни через какую станцию линия не проходит дважды).

В конце файла записаны два различных: числа A — номер начальной станции, и B — номер станции, на которую нам нужно попасть. При этом если через станцию A проходит несколько линий, то мы можем спуститься на любую из них. Так же если через станцию B проходит несколько линий, то нам не важно, по какой линии мы приедем.

Формат выходного файла

Ограничения

Примеры тестов

5 2
4 1 2 3 4
2 5 3
3 1

0

5 5
2 1 2
2 1 3
2 2 3
2 3 4
2 4 5
1 5

2

10 2
6 1 3 5 7 4 9
6 2 4 6 8 10 7
3 8

1

4 2
2 1 2
2 3 4
1 3

-1

Задача M. Модули ≡

Условие

Отдел инновационных технологий фирмы "Division Computers" решил, что повысить производительность в написании программ можно, если использовать модульное программирование, т.е. когда когда каждый программист пишет свою часть отдельно.

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

Формат входного файла

Входной файл содержит числа N и M — соответственно число модулей и связей между ними, за которыми следуют M пар чисел a_i a_j, означающие, что i-тый и j-тый модули не могут функционировать друг без друга.

Формат выходного файла

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

Ограничения

Примеры тестов

3 1
2 3

2

Problem N. Ford-Bellman ≡

Statement

Input file format

Output file format

Constraints

Sample tests

3 3 1
1 2 5
1 3 10
2 3 2

0 5 7

Задача O. Hot-keys ≡

Условие

Формат входного файла

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

Формат выходного файла

Выходной файл должен содержать N строк с одинаковыми заголовками, как и во входном файле. В каждом заголовке, которому была назначена какая-то комбинации, перед самым левым вхождением символа из горячей клавиши необходимо добавить символ '&' (ASCII 38).

Ограничения

1 ≤ N ≤ 10, все заголовки имеют длину от 1 до 10 символов и состоят из строчных латинских букв.

Примеры тестов

3
yes
no
cancel

&yes
&no
&cancel

4
abc
bca
acb
aaaa

&abc
&bca
a&cb
aaaa

Задача P. Слово из кубиков ≡

Условие

Формат входного файла

Формат выходного файла

Ограничения

Примеры тестов

5
TEST
ABCDAB
TTTTTT
STSTST
CREATE
ERRORS

2 5 3 4

Задача Q. Min-cost-max-flow aka В поисках невест ≡

Условие

Однажды король Флатландии решил отправить k своих сыновей на поиски невест. Всем известно, что во Флатландии n городов, некоторые из которых соединены дорогами. Король живет в столице, которая имеет номер 1, а город с номером n знаменит своими невестами.

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

Формат входного файла

В первой строке входного файла находятся числа n, m и k — количество городов и дорог во Флатландии и сыновей короля, соответственно (2 ≤ n ≤ 200, 1 ≤ m ≤ 2000, 1 ≤ k ≤ 100). Следующие m строк содержат по три целых положительных числа каждая — города, которые соединяет соответствующая дорога и время, которое требуется для ее прохождения (время не превышает 10⁶). По дороге можно перемещаться в любом из двух направлений, два города могут быть соединены несколькими дорогами.

Формат выходного файла

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

Примеры тестов

5 8 2
1 2 1
1 3 1
1 4 3
2 5 5
2 3 1
3 5 1
3 4 1
5 4 1

3.00000
3 1 5 6
3 2 7 8

Задача R. Быстрое двудольное паросочетание ≡

Условие

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

Формат входного файла

Входной файл содержит целые числа p, q, m — мощности левой правой доли, а также количество рёбер соответственно.

Далее содержится описание m ребер в виде списка пар целых чисел (u_i, v_i). Наличие пары (u_i, v_i) означает ребро между u_i-ой вершиной левой доли и v_i-ой вершиной правой доли.

Гарантируется, кратных рёбер в графе нет.

Формат выходного файла

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

Ограничения

1 ≤ p, q ≤ 10⁵

1 ≤ m ≤ 2*10⁵

1 ≤ u_i ≤ p

1 ≤ v_i ≤ q

Примеры тестов

3 3 6
1 1
1 2
2 1
2 2
2 3
3 2

3
1 1
2 3
3 2

Problem S. Dijkstra ≡

Statement

You are to write a program that receives a weighted directed graph and finds distances from source vertex S to all other vertices. Distance from S to some vertex W is the minimal length of path going from S to W. Length of path is the sum of weights of its edges.

Vertices are numbered with integers from 1 to N.

Input file format

Output file format

Constraints

Sample tests

5 3 1
1 2 5
1 3 7
3 4 10

0 5 7 17 -1

Problem T. Fast Dijkstra ≡

Statement

Input file format

Output file format

Constraints

Sample tests

5 3 1
1 2 5
1 3 7
3 4 10

0 5 7 17 -1

Задача U. Перетягивание канатов ≡

Условие

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

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

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

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

Формат входного файла

Входной файла содержит целое число N — количество учеников, за которыми следуют N целых чисел a_i — силовые показатели каждого ученика.

Формат выходного файла

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

Ограничения

3 ≤ N ≤ 30.

0 ≤ a_i ≤ 10⁷.

Примеры тестов

3
1 2 3
    

1

3
1 10 10
    

0

Задача V. Свинья-копилка ≡

Условие

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

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

Формат входного файла

В первой строке входного файла содержатся числа E F N. В следующих N строках находятся по два числа — C_i W_i. Все числа во входном файле — целые.

Формат выходного файла

В выходном файле должно содержаться одно число — минимальная сумма, накопленная в копилке. Если заданный вес копилки F не может быть достигнут с монетами заданного типа, то в выходной файл следует записать число −1.

Ограничения

1 ≤ E ≤ F ≤ 10000; 1 ≤ N ≤ 100

1 ≤ Ci ≤ 10000; 1 ≤ Wi ≤ 10000

Примеры тестов

10 110 2
1 1
30 50

60

10 110 2
1 1
50 30

100

1 6 2
10 3
20 4

-1

Задача W. Благотворительность Марфы Геннадьевны ≡

Условие

Однажды Марфа Геннадьевна выиграла в лотерею большую сумму денег и решила потратить часть выигрыша на благотворительность.

Чтобы определить, сколько денег отдать на благотворительность, Марфа Геннадьевна придумала игру. Она записала N чисел a₁, a₂, ..., a_N по кругу (по часовой стрелке).

Начинает Марфа Геннадьевна с числа a₁. Начальная сумма денег равняется a₁. Затем Марфа Геннадьевна кидает игральный кубик (на разных гранях кубика нарисовано 1, 2, 3, 4, 5 и 6 точек). Если на кубике выпало число x, то Марфа Геннадьевна отсчитывает x чисел по часовой стрелке. Например, если выпало число 3, то Марфа Геннадьевна перейдёт от числа a₁ к числу a₄. Число, к которому перешла Марфа Геннадьевна, прибавляется к сумме. Марфа Геннадьевна бросает кубик M раз и каждый раз прибавляет очередное число к сумме.

Марфе Геннадьевне интересно, какая наибольшая сумма денег может получиться при такой игре, поэтому ей нужна программа, вычисляющая наибольшую сумму.

Формат входного файла

Входной файл содержит целые числа N M, за которыми следуют N целых чисел a₁ a₂... a_N.

Формат выходного файла

Требуется вывести в выходной файл целое число — максимальную сумму.

Ограничения

1 ≤ N ≤ 1000

0 ≤ M ≤ 5000

0 ≤ a_i ≤ 1000

Примеры тестов

7 1
1 2 3 4 5 6 7

8

7 2
1 2 3 4 5 6 7

14

5 2
5 0 10 1 6

25

Задача X. Благотворительность Марфы Геннадьевны - 2 ≡

Условие

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

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

Марфа Геннадьевна бросает N игральных кубиков и подсчитывает сумму очков, выпавших на кубиках. Затем она умножает сумму очков на некоторый коэффициент — это и будет сумма пожертвования.

На каждом кубике с одинаковыми вероятностями выпадает одно из чисел от 1 до 6.

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

Формат входного файла

Входной файл содержит единственное целое число N.

Формат выходного файла

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

Вероятности вывести с точностью до 10-ти знаков после запятой.

Ограничения

Примеры тестов

1

1 0.1666666667
2 0.1666666667
3 0.1666666667
4 0.1666666667
5 0.1666666667
6 0.1666666667

2

2 0.0277777778
3 0.0555555556
4 0.0833333333
5 0.1111111111
6 0.1388888889
7 0.1666666667
8 0.1388888889
9 0.1111111111
10 0.0833333333
11 0.0555555556
12 0.0277777778

Задача Y. Методом тряпки ≡

Условие

Школьники плохо написали контрольную работу по признакам делимости на k. Марфа Геннадьевна оставила их после уроков для работы над ошибками. Она написала на доске большое число N и сама на секунду задумалась. А делится ли её число на k?

Марфа Геннадьевна решила, что если её число не делится на k, то она исправит его методом тряпки, т.е. сотрёт несколько цифр в произвольных местах таким образом, чтобы новое число на доске делилось на k. При этом Марфа Геннадьевна не хочет себя утруждать и собирается стереть как можно меньше цифр.

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

В первом примере необходимо стереть цифры 7 и 6. Если стереть цифры 1, 4, 6, то полученное число 7 будет делиться на 7, но этот ответ не оптимален.

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

В третьем примере ничего нельзя поделать.

Система оценивания

Рекомендуется рассмотреть следующие частные случаи:

• N ≤ 10¹⁸;

Формат входного файла

Входной файл содержит целые числа k N.

Формат выходного файла

Выходной файл должен содержать либо число, которое останется на доске, либо слово IMPOSSIBLE, если на доске ничего не останется.

Ограничения

1 ≤ k ≤ 1000;

1 ≤ N ≤ 10¹⁰⁰⁰;

в записи числа N нет лидирующий нулей;

Примеры тестов

7
1746

14

3
106

6

10
256

IMPOSSIBLE