Задача 1. Пересечение двух прямых

Автор:StdAlg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:128 Мб
Выходной файл:output.txt  

Условие

Прямая a проходит через точки A1 (aX1; aY1) и A2 (aX2; aY2). Прямая b проходит через точки B1 (bX1; bY1) и B2 (bX2; bY2).

Требуется найти точку пересечения прямых a и b или установить что прямые параллельны.

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

Во входном файле содержаться восемь целых чисел — aX1, aY1, aX2, aY2, bX1, bY1, bX2, bY2

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

Выходной файл должен содержать:

Ограничения

0 ≤ |aXk|, |aYk|, |bXk|, |bYk| ≤ 105

A1 ≠ A2

B1 ≠ B2

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

Входной файл (input.txt) Выходной файл (output.txt)
1
0 0  2 2  1 1  3 3
-1
2
0 0  1 1
2 3  5 6
0
3
1 1
3 5
-1 5
8 -1
2.000000000 3.000000000

Задача 2. Поворот отрезка

Автор:StdAlg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:128 Мб
Выходной файл:output.txt  

Условие

Вершины отрезка AB имеют координаты (Xa; Ya) и (Xb; Yb).

Требуется найти координаты вершин отрезка A *  B *  (X * a; Y * a) и (X * b; Y * b), полученного путём поворота отрезка AB вокруг точки O (Xo; Yo) на β градусов.

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

Входной файл содержит целые числа Xa, Ya, Xb, Yb, Xo, Yo, β

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

Выходной файл должен содержать четыре вещественных числа X * a, Y * a, X * b, Y * b с точностью 10 − 3.

Ограничения

0 ≤ |Xa|, |Ya|, |Xb|, |Yb|, |Xo|, |Yo| ≤ 105

0 ≤ β ≤ 360

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1  2 2  0 0  90
-1.000000000 1.000000000 -2.000000000 2.000000000
2
1 1  2 2
0 0
45
0.000000000 1.414213562 0.000000000 2.828427125
3
7 5
11 11
9 8
180
11.000000000 11.000000000 7.000000000 5.000000000

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

Автор:А. Жуплев   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

Оба программиста живут за городом. Их дома расположены в точках с координатами (XA; YA) и (XB; YB).

В этом районе есть только одна асфальтированная дорога, представимая в виде отрезка с координатами начала (XS; YS) и конца (XE; YE). Дорога является платной: за любой въезд на дорогу (проезд по произвольному участку дороги или только пересечение — не имеет значения) взимается плата в размере CR. Остальная местность занята полями, которые (в связи со скорым Хэллоуином) сплошь засажены тыквами. При движении на автомобиле по полю взимается плата в размере CF за каждый километр пути — ущерб за раздавленные тыквы.

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

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

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

Во входном файле содержатся десять целых чисел: XA YA XB YB XS YS XE YE CF CR

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

Выходной файл должен содержать единственное число — минимальные затраты при перемещении из A в B с абсолютной ошибкой не более 10 − 3.

Ограничения

 − 103 ≤ XA, YA, XB, YB, XS, YS, XE, YE ≤ 103

1 ≤ CF ≤ 103

1 ≤ CR ≤ 106

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
1 1 2 2 0 3 3 0 1 1
2.414213562373095
2
1 5 4 0
-2 -2 10 10
1 2
7.656854249492381
3
10 10 25 19
15 13 20 16
1 1000000
17.492855684535900

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

Автор:А. Кленин   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

Во входном файле содержатся вещественные числа a и b, разделенные пробелами.

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

В выходном файле должны содержаться два вещественных числа, x и y, представляющие координаты объекта с точностью до 4 знаков после запятой. Если определить координаты невозможно, следует вывести два числа 0 (нуль).

Ограничения

0 ≤ a, b ≤ 360

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

Входной файл (input.txt) Выходной файл (output.txt)
1
45.1 135.0
49.9127 50.0873
2
135.0 45.0
0 0

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

Автор:StdAlg   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

Во входном файле содержатся целые числа XA YA XB YB XC YC — координаты точек A, B, C соответственно.

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

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

Ограничения

0 ≤ |XA|, |YA|, |XB|, |YB|, |XC|, |YC| ≤ 105

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 2 0 0 2 2
2 2
2
-2 -3 1 3 4 -2
1.30120904214632 -0.720188590098661

Задача 6. Почти квадрат

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

Входной файл содержит вещественные числа x1 y1 x2 y2 x3 y3 x4 y4 — координаты вершин четырёхугольника, перечисленные в порядке обхода.

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

Выходной файл должен содержать числа M x y, где целое M — номер вершины, которую следует перенести (1 ≤ M ≤ 4), а вещественные (x, y) — её новые координаты, c абсолютной ошибкой не более 10 − 3. Если решения не существует, вывести единственное число 0 (ноль). Если существует несколько решений, вывести решение с наименьшим значением M.

Ограничения

 − 1000 ≤ x, y ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
0.0 0.0  10.0 0.0  10.0 10.0  0.0 10.0
1 0.0 0.0
2
0.0 0.0  9.5 0.0  10.0 10.0  0.0 10.0
2 10.0 0.0
3
0.0 0.0  9.5 0.0  10.0 10.0  -0.1 10.0
0

Задача 7. Задача Пифагора

Автор:Южно-Уральский открытый командный чемпионат   Ограничение времени:5 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

Все числа вещественные, больше 0 и меньше 1000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10.0 10.0 10.0
25.00000

Задача 8. Палка, палка, огуречик...

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

Рисунок как землянина, так и марсианина состоит из окружности и пяти отрезков. Назовём отрезок торчащим из окружности, если один его конец лежит внутри или на границе окружности, а другой — снаружи.

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

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

Напишите программу, которая по данному рисунку определит, кто на нём изображён.

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

Входной файл содержит описание окружности, состоящее из трёх целых чисел xc yc r — координаты центра и радиус. Далее идут пять описаний отрезков, каждое из четырёх целых чисел x1 y1 x2 y2 — координаты начала и конца отрезка.

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

Выходной файл должен содержать единственную строку: TERRAN, если на рисунке землянин, MARTIAN, если на рисунке марсианин и UNKNOWN, если нарисовано ни то, ни другое.

Ограничения

 − 10000 ≤ xi, yi ≤ 10000, 1 ≤ r ≤ 10000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
100 100 50
80 130 80 200
90 130 90 200
100 130 100 200
110 130 110 200
120 130 120 200
MARTIAN
2
100 100 50
100 130 100 220
50 180 110 190
150 180 90 190
50 260 110 210
150 260 90 210
TERRAN

Problem A. Breadth First Search

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

You are to write a program that receives an unweighted undirected graph and writes all its vertices in order of increasing distance from given vertex S. Distance between vertices A and B is the length of the shortest path from A to B. If there are several vertices such that their distances to S are equal, they may be printed in arbitrary order.

Input file format

Input file contains three integers N, M and S, where M is the number of edges, S is the starting vertex. Vertices are numbered with integer numbers from 1 to N. Each of next M lines contains a pair of integers — numbers of vertices connected by an edge.

Output file format

Output file must contain sequence of vertex numbers sorted by increasing distance from S. If some vertex is not reachable from S, output a single number  − 1.

Constraints

0 ≤ N, M ≤ 100000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 2 1
1 2
2 3
1 2 3

Задача B. Лабиринт

Автор:Кленин А.   Ограничение времени:4 сек
Входной файл:input.txt   Ограничение памяти:16 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 1500, левый верхний угол лабиринта всегда свободен.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
.#
..
2
2
2
.#
#.
-1

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

Автор:Центральная предметно-методическая комиссия по информатике   Ограничение времени:2 сек
Входной файл:details.in   Ограничение памяти:256 Мб
Выходной файл:details.out  

Условие

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

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

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

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

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

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

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

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

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

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

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

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

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

Ограничения

1 ≤ n ≤ 100000, 1 ≤ pi ≤ 109

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

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

Входной файл (details.in) Выходной файл (details.out)
1
3
100 200 300
1 2
0
2 2 1
300 2
2 1
2
2
2 3
1 2
0
5 2
2 1
3
4
2 3 4 5
2 3 2
1 3
0
2 1 3
9 3
3 2 1

Задача D. КПК

Автор:И. Олейников, Т. Чистяков   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:8 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Выходной файл содержит сначала число K1 — количество проводов, которые нужно оставить в схеме, затем K1 пар чисел ai aj — описание проводов. После этого следует число K2 — число проводов, которые нужно добавить в схему, затем K2 пар чисел ai aj — описание проводов. Если решений несколько, выведите любое из них.

Ограничения

1 ≤ N ≤ 1000, 0 ≤ M ≤ 106

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1
2 3
1
2 3
1
1 2

Задача E. Модули

Автор:И. Олейников   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

Ограничения

1 ≤ N ≤ 100000, 0 ≤ M ≤ 106

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 1
2 3
2

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

Автор:А. Кленин, краевая олимпиада 2001 г.   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:64 Мб
Выходной файл:output.txt  

Условие

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

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

Дано E — вес пустой копилки, F — вес копилки с монетами, N — количество достоинств монет, Ci и Wi — достоинство и вес каждого вида монет (1 ≤ i ≤ N). Требуется определить минимальную сумму, которая может содержаться в копилке.

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

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

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

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

Ограничения

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

1 ≤ Ci ≤ 10000; 1 ≤ Wi ≤ 10000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
10 110 2
1 1
30 50
60
2
10 110 2
1 1
50 30
100
3
1 6 2
10 3
20 4
-1

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

Автор:Г. Гренкин   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

Входной файл содержит целые числа N M, за которыми следуют N целых чисел a1 a2... aN.

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

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

Ограничения

1 ≤ N ≤ 1000

0 ≤ M ≤ 5000

0 ≤ ai ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
7 1
1 2 3 4 5 6 7
8
2
7 2
1 2 3 4 5 6 7
14
3
5 2
5 0 10 1 6
25

Задача H. Восстановление скобок

Входной файл:input.txt   Ограничение времени:2 сек
Выходной файл:output.txt   Ограничение памяти:64 Мб

Условие

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

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

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

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

Выведите в выходной файл искомое количество способов. Исходные данные будут таковы, что это количество не превзойдет 2 * 109.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
????(?
2

Задача I. Наибольшая общая подпоследовательность

Автор:-   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Найдите наибольшую общую подпоследовательность двух строк.

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

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

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

Вывести наибольшую общую подпоследовательность. Если решений несколько, вывести любое.

Ограничения

Длина каждой строки не менее 1 и не превосходят 1000.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
ababaca
acaba
aaba


Problem J. Dijkstra

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:16 Mb
Output file:output.txt  

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

First line of input file contains three integers N M and S, where M is the number of edges. Next M lines contain three integers each — starting vertex number, ending vertex number and weight of some edge respectively. All weights are positive. There is at most one edge connecting two vertices in every direction.

Output file format

Output file must contain N integers — distances from source vertex to all vertices. If some vertices are not reachable from S, corresponding numbers must be −1.

Constraints

1 ≤ N ≤ 1000. All weights are less or equal than 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 3 1
1 2 5
1 3 7
3 4 10
0 5 7 17 -1

Problem K. Fast Dijkstra

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that receives a weighted directed graph and finds all distances from fixed 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 arcs.

Input file format

Input file contains two integers N, M and S. Vertices are numbered with integer numbers from 1 to N. S is the number of source vertex. M is the number of arcs. Each of next M lines contain three integers — numbers of starting and ending vertices of some arc and its weight respectively. All weights are positive. There is at most one arc connecting two vertices in every direction.

Output file format

Output file must contain N numbers. Each I-th number is the distance from vertex S to vertex I. If some vertices are not reachable from S, corresponding numbers must be −1.

Constraints

1 ≤ N, M ≤ 100000 All weights are less or equal 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5 3 1
1 2 5
1 3 7
3 4 10
0 5 7 17 -1

Problem L. Ford-Bellman

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that finds shortest distances from vertex S to all other vertices in a given directed weighted graph. Graph consists of N vertices, numbered from 1 to N, and M edges.

Input file format

Input file contains two integers N M S, followed my M triplets of integers ui vi wi — starting vertex, ending vertex and weight or the edge. There is at most one edge connecting any two vertices in every direction. There are no cycles of negative weight.

Output file format

Output file must contain a vector of N integers — distances from vertex S to other vertices. The distance from any vertex to itself is considered to be 0. If some vertex is not reachable from S, corresponding cell of the vector must contain empty space.

Constraints

0 ≤ N, M ≤ 1000. All weights are less than 1000 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3 1
1 2 5
1 3 10
2 3 2
0 5 7

Задача M. Парное упражение

Автор:И. Туфанов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Однажды учитель физкультуры решил провести на уроке новое упражнение. Ученики выполняют упражнение в парах. При этом важно, чтобы рост учеников в паре отличался не более чем на k сантиметров.

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

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

В первом примере имеется 7 учеников. Учитель может вызвать учеников 2 и 3 (их рост 175 и 170, разница не превосходит k = 5), после чего они выйдут из строя, и останутся ученики с номерами 1, 4, 5, 6, 7. Вторую пару составляют ученики 1 и 4, имеющие нулевую разницу в росте (рост обоих равен 180). Ученики с номерами 5 и 7 имеют один и тот же рост 200, но учитель не может их вызвать, поскольку они стоят не рядом друг с другом. Если бы учитель вызвал сначала учеников 1 и 2, то оставшиеся ученики не смогли бы образовать ни одной пары.

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

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

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

Во начале входного файла записаны целые числа n и k. Далее следует n целых чисел hi. Число hi обозначает рост ученика, стоящего в строю i-ым.

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

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

Ограничения

1 ≤ n ≤ 500;

100 ≤ hi ≤ 300;

0 ≤ k ≤ 200;

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

Входной файл (input.txt) Выходной файл (output.txt)
1
7 5
180 175 170 180 200 150 200
2
2 3
1 4
2
3 0
180 170 170 
1
2 3

Problem N. Floyd-Warshall

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that finds shortest distances between all pairs of vertices in a directed weighted graph. Graph consists of N vertices, numbered from 1 to N, and M edges.

Input file format

Input file contains two integers N and M, followed my M triplets of integers ui vi wi — starting vertex, ending vertex and weight or the edge. There is at most one edge connecting two vertices in every direction. There are no cycles of negative weight.

Output file format

Output file must contain a matrix of size NxN. Element in the j-th column of i-th row mush be the shortest distance between vertices i and j. The distance from the vertex to itself is considered to be 0. If some vertex is not reachable from some other, there must be empty space in corresponding cell of matrix.

Constraints

0 ≤ N ≤ 100. All weights are less than 1000 by absolute value.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2 5
1 3 10
2 3 2
0 5 7
  0 2
    0

Задача O. Светофоры

Автор:М. Спорышев   Ограничение времени:3 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Студент Вася каждый день ездит на машине в университет учиться. Система дорог города, в котором живет Вася, представляет собой на карте прямоугольную сетку состоящую из N × M перекрестков. Дом, от которого отъезжает Вася, находится в левом верхнем углу карты, а университет — в правом нижнем углу.

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

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

Итак, Васе нужно успеть на первую пару! Но Вася — порядочный гражданин и не станет проезжать на красный свет. В то же время, скорость автомобиля и состояние дорог в городе позволяют ему перемещаться между светофорами настолько быстро, что временем перемещения можно пренебречь. (Т. е. время проезда между перекрёстками равно нулю).

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

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

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

Далее следует N × M расписаний светофоров, перечисленных в порядке обхода карты построчно. Первое число i − го расписания ci — количество временных отрезков i − го светофора, за которым следует ci пар целых чисел  — временные отрезки, когда i − ый светофор светит красным. Отрезки не пересекаются и отсортированы по возрастанию левой границы.

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

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

Ограничения

1 ≤ N × M ≤ 1000; 0 ≤ aij ≤ 1000000; 1 ≤ ci ≤ 100

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2 2
1 0 1
1 0 1
1 0 1
1 0 1
1
2
2 3
2 0 1 4 10
2 0 3 4 10
2 0 1 3 10
1 0 100
1 0 100   
1 0 100 
10

Problem P. SST for sparse graph

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:8 Mb
Output file:output.txt  

Statement

You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.

Input file format

Input file contains two integers N, M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are positive. There is at most one edge connecting two vertices.

Output file format

Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree, output file must contain −1.

Constraints

1 ≤ N, M ≤ 100000 All weights are less or equal 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2 10
2 3 10
3 1 10
20

Problem Q. Shortest Spanning Tree

Author:StdAlg   Time limit:1 sec
Input file:input.txt   Memory limit:16 Mb
Output file:output.txt  

Statement

You are to write a program that receives a weighted undirected graph and finds length of its shortest spanning tree.

Input file format

Input file contains two integers N, M. Vertices are numbered with integer numbers from 1 to N. M is the number of edges. Each of next M lines contain three integers describing an edge — numbers of vertices, connected by an edge and its weight respectively. All weights are positive. There is at most one edge connecting two vertices.

Output file format

Output file must contain a signle integer number — length of the SST. If it is impossible to construct spanning tree, output file must contain −1.

Constraints

1 ≤ N ≤ 1000 All weights are less or equal 1000.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
3 3
1 2 10
2 3 10
3 1 10
20

Задача R. Lode Runner возвращается

Автор:И. Туфанов, А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Компания-разработчик компьютерных игр решила выпустить обновлённую версии классической аркадной игры Lode Runner.

Игра проходит в лабиринте, состоящем из горизонтальных платформ, соединённых лестницами. Лабиринт изображается в виде поля шириной W и высотой H клеток, каждая клетка которого содержит один из символов "." (ASCII 46) — свободное место, "X" (ASCII 88) — платформа и "#" (ASCII 35) — лестница.

По правилам игры, все платформы должны быть строго горизонтальными и не соприкасаться друг с другом (т.е. два символа "X" могут соседствовать только по горизонтали). Каждая лестница должна быть строго вертикальной и соединять две платформы (т.е. представлять собой вертикальную полосу из символов "#", над верхним и под нижним символом которой находятся символы "X"). Лестницы могут соприкасаться друг с другом, находясь на соседних вертикалях.

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

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

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

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

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

Первая строка входного файла содержит целые числа W H. Следующие H строк содержат по W символов каждая — описание уровня.

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

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

Ограничения

1 ≤ W, H ≤ 1000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
6 4
.XX.X.
......
#.#...
XXXXX.

.XX.X.
..#.#.
..#.#.
XXXXX.

Задача S. Матрешки

Входной файл:input.txt   Ограничение времени:1 сек
Выходной файл:output.txt   Ограничение памяти:128 Мб

Условие

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

За один такт автомат может взять две матрешки и вложить меньшую в большую, причем если в матрешках уже содержаться другие матрешки, то они все вкладываются в самую большую, при этом номера матрешек остаются прежними. Если матрешка уже вложена в другую, то автомат упаковывает ту матрешку в которую она вложена. Программа автомата состоит из чисел N, K и следующих за ними K пар чисел ai, bi — номера матрешек, которые автомат упакует за i-тый такт.

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

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

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

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

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

Ограничения

0 ≤ N, K ≤ 100000

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

Входной файл (input.txt) Выходной файл (output.txt)
1
4 3
1 2
2 3
1 3
1 1 1 4

Задача T. Пицца

Автор:А. Усманов   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

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

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

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

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

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

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

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

Далее следует N различных целых чисел ai — размеры кусочков пиццы, перечисленные в порядке обхода по кругу.

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

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

Ограничения

1 ≤ N ≤ 105

1 ≤ ai ≤ 109

Описание подзадач и системы оценивания

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
n
1211 ≤ n ≤ 3
2311 ≤ n ≤ 1031
3481 ≤ n ≤ 1051, 2

Получение информации о результатах окончательной проверки

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3
1 2 3
1
2
5
8 5 6 10 3
5
3
1
1000000000
1000000000

Задача U. Тест ТЮП 2017

Автор:А. Кленин   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Данная задача — тест. Требуется ответить на приведённые вопросы и отправить ответ в тестирующую систему в указанном ниже формате. За каждый правильный ответ будут начисляться баллы. Баллы за все вопросы, кроме нулевого, будут видны после окончания тура.

Вопрос 0

Сколько будет 2 + 4?

Вопрос 1

На диаграмме показано количество участников олимпиады по трём предметам в трёх регионах России

0102030405060708090100110120130140150160 ФизикаГеографияИнформатика ЯкутияУдмуртияБурятия
Какая из диаграмм правильно отражает соотношение участников из всех регионов по каждому предмету?

Вопрос 2

Сколько шестерок в семеричной записи числа 3432019 + 24012022 - 343?

Вопрос 3

Укажите наименьшее основание системы счисления, в которой запись числа 321 трёхзначна.

Вопрос 4

Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:

Чему равно значение функции F(7)? В ответе запишите только натуральное число.

Вопрос 5

У Дмитрия есть доступ к сети Интернет по высокоскоростному одностороннему радиоканалу, обеспечивающему скорость получения информации 220 бит в секунду. У Глафиры нет скоростного доступа в Интернет, но есть возможность получать информацию от Дмитрия по телефонному каналу со средней скоростью 212 бит в секунду. Глафира договорилась с Дмитрием, что он скачает для него данные объемом 10 Мбайт по высокоскоростному каналу и ретранслирует их Глафире по низкоскоростному каналу.

Компьютер Дмитрия может начать ретрансляцию данных не раньше, чем им будут получены первые 1024 Кбайт этих данных. Каков минимально возможный промежуток времени (в секундах) с момента начала скачивания Дмитрием данных до полного их получения Глафирой?

В ответе укажите только число, слово «секунд» или букву «с» добавлять не нужно.

Вопрос 6

Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 8. Система команд Кузнечика:
Вперед 85 – Кузнечик прыгает вперёд на 85 единиц,
Назад 45 – Кузнечик прыгает назад на 45 единиц.
Какое наименьшее количество раз должна встретиться в программе команда «Назад 45», чтобы Кузнечик оказался в точке 18?

Вопрос 7

Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам.

  1. Складываются первая и вторая, а также вторая и третья цифры исходного числа.
  2. Полученные два числа записываются друг за другом в порядке возрастания (без разделителей).
Пример. Исходное число: 348. Суммы: 3+4 = 7; 4+8 = 12. Результат: 712.
Укажите наименьшее число, в результате обработки которого автомат выдаст число 1216.

Вопрос 8

Ниже на че­ты­рех язы­ках про­грам­ми­ро­ва­ния за­пи­сан ре­кур­сив­ный ал­го­ритм F

БейсикАлгоритмический
FUNCTION F(k)
  PRINT k
  IF k < 5 THEN
    F(k + 1)
    F(k + 2)
    F(k + 3)
  END IF
END FUNCTION
алг цел F(цел k)
нач
  вывод k
  если k < 5 то
    F(k + 1)
    F(k + 2)
    F(k + 3)
  все
кон
ПаскальСи
function F(k: integer): integer;
begin
  write(k);
  if k < 5 then begin
    F(k + 1);
    F(k + 2);
    F(k + 3);
  end;
end;
int F(int k) {
  int F;
  print(k);
  if (k < 5) {
    F(k + 1);
    F(k + 2);
    F(k + 3);
  }
  return F;
}
Че­му бу­дет рав­на сум­ма всех чи­сел, на­пе­ча­тан­ных на экра­не при вы­пол­не­нии вы­зо­ва F(1)

Вопрос 9

В детскую игрушку «Набор юного шпиона» входят два одинаковых комплекта из 3 флажков различных цветов. Сколько различных тайных сообщений можно передать этими флажками, условившись менять выставленный флажок каждые 8 минут и наблюдая за процессом 56 минут? Наблюдатель видит вынос первого флажка и 6 перемен флажка. При этом возможна смена флажка на флажок того же цвета.

Вопрос 10

Запись десятичного числа в системах счисления с основаниями 13 и 17 в обоих случаях имеет последней цифрой 0. Какое минимальное натуральное десятичное число удовлетворяет этому требованию?

Вопрос 11

У исполнителя Калькулятор три команды, которым присвоены номера:

  1. прибавить 1
  2. умножить на 5
  3. умножить на 3
Сколько есть программ, которые число 1 преобразуют в число 26?

Вопрос 12

Определите асимптотическую сложность следующего алгоритма:

СиБейсик
for (i = 0; i <= pow(n, 3); ++i)
  for (j = 0; j <= pow(n, 2); ++j){
    for (b = 0; b <= n; ++b){
      a = pow(n, 2);
      for (jk = 0; jk <= pow(a, 3); ++jk)
        print(b, jk, j, i);
    }
    if (i % pow(n, 2) == 0)
      for (bi = 0; bi <= pow(b, 3); ++bi){
        k = pow(a, 3);
        for (bk = 0; bk <= k; ++bk)
          print(bk, bi, j, i);
      }
  }
FOR i = 0 TO n ^ 3
  FOR j = 0 TO n ^ 2
    FOR b = 0 TO n
      a = n ^ 2
      FOR jk = 0 TO a ^ 3
        PRINT b, jk, j, i
      NEXT jk
    NEXT b
    IF i MOD n ^ 2 = 0 THEN FOR bi = 0 TO b ^ 3
      k = a ^ 3
      FOR bk = 0 TO k
        PRINT bk, bi, j, i
      NEXT bk
    NEXT bi
  NEXT j
NEXT i
ПаскальАлгоритмический
for i := 0 to n ** 3 do
  for j := 0 to n ** 2 do begin
    for b := 0 to n do begin
      a := n ** 2;
      for jk := 0 to a ** 3 do
        write(b, jk, j, i);
    end;
    if i mod n ** 2 = 0 then
      for bi := 0 to b ** 3 do begin
        k := a ** 3;
        for bk := 0 to k do
          write(bk, bi, j, i);
      end;
  end;
нц для i от 0 до n ** 3
  нц для j от 0 до n ** 2
    нц для b от 0 до n
      a := n ** 2
      нц для jk от 0 до a ** 3
        вывод b, jk, j, i
      кц
    кц
    если mod(i, n ** 2) = 0 то
      нц для bi от 0 до b ** 3
        k := a ** 3
        нц для bk от 0 до k
          вывод bk, bi, j, i
        кц
      кц
    все
  кц
кц
  1. Θ(n3)
  2. Θ(n5)
  3. Θ(n12)
  4. Θ(n2)

Вопрос 13

Определите количество вызовов функции f при исполнении следующего алгоритма:

Прим. Пренебречь размерностью целочисленных переменных.

СиБейсик
int f(int n) {
  int f;
  if (n >= 32258064516)
    f = f(n / 3) + 1;
  if (n < 32258064516 && n >= 666666666)
    f = f(n - 5) + 1;
  if (n < 666666666)
    f = 1;
  return f;
}

print(f(1000000000000));
FUNCTION f(n)
  IF n >= 32258064516 THEN f = f(n / 3) + 1
  IF n < 32258064516 AND n >= 666666666 THEN f = f(n - 5) + 1
  IF n < 666666666 THEN f = 1
END FUNCTION

PRINT f(1000000000000)
ПаскальАлгоритмический
function f(n: integer): integer;
begin
  if n >= 32258064516 then
    f := f(n div 3) + 1;
  if (n < 32258064516) and (n >= 666666666) then
    f := f(n - 5) + 1;
  if n < 666666666 then
    f := 1;
end;

write(f(1000000000000));
алг цел f(цел n)
нач
  если n >= 32258064516 то
    f := f(n / 3) + 1
  все
  если n < 32258064516 и n >= 666666666 то
    f := f(n - 5) + 1
  все
  если n < 666666666 то
    f := 1
  все
кон

вывод f(1000000000000)

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

В качестве решения принимается текстовый файл, содержащий по одному числу в строке — ответы на каждый из вопросов. При отправке файла следует выбрать в тестирующей системе среду разработки "Answer text". Если вы не знаете ответа на какой-то из вопросов, укажите вместо ответа число 0.


Задача V. Карта сокровищ

Автор:А. Усманов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

У Ильи имеется карта сокровищ размера H × W клеток.

Маленький брат Ильи — Никита, взял эту карту "поиграть". Игра заключалась в следующем: какое-то количество раз карта была сложена вдвое по вертикали или по горизонтали. Складывая карту по вертикали, Никита брал её за нижнюю сторону, по горизонтали — за правую сторону. После этого он соединял взятую сторону с противоположной стороной. При этом верхний левый угол карты всегда оставался неподвижным. Линия сгиба всегда проходила точно по границе между клетками. В итоге сложенная карта оказалось размером N × M клеток.

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

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

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

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

Вторая строка входного файла содержит два целых числа N и M — высоту и ширину сложенной карты.

Далее следует N строк по M символов в каждой — описание карты. Символом 'X' (ASCII 88) отмечается клетка, которую проткнул Никита, символом '.' (ASCII 46) отмечается нетронутая клетка.

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

Далее в Q строках содержится по четыре числа в каждой. xi, yi, ui, vi — описание i-й прямоугольной области карты. xi, yi — координаты левого верхнего угла прямоугольника, ui, vi — координаты правого нижнего угла прямоугольника.

Нумерация клеток по вертикали сверху вниз с 1 до H, нумерация клеток по горизонтали слева направо с 1 до W.

Гарантируется, что свёрнутая карта получена из исходной путём преобразований, описанных в задаче. То есть существую такие целые числа a и b, что N × 2a = H и M × 2b = W.

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

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

Ограничения

1 ≤ H, W ≤ 109

1 ≤ N, M ≤ 103

1 ≤ Q ≤ 105

1 ≤ xi ≤ ui ≤ H, 1 ≤ yi ≤ vi ≤ W

Описание подзадач и системы оценивания

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
H, Wxi, yi, ui, viQ
1121 ≤ H, W ≤ 103xi = ui, yi = vi1 ≤ Q ≤ 105
281 ≤ H, W ≤ 1031 ≤ Q ≤ 102
3141 ≤ H, W ≤ 1031 ≤ Q ≤ 1051-2
4111 ≤ H, W ≤ 109xi = ui, yi = vi1 ≤ Q ≤ 1051
591 ≤ H, W ≤ 109(ui − xi + 1)(vi − yi + 1) ≤ 106Q = 1
6161 ≤ H, W ≤ 109(ui − xi + 1)(vi − yi + 1) ≤ 1061 ≤ Q ≤ 1022, 5
7171 ≤ H, W ≤ 1091 ≤ Q ≤ 1022, 5-6
8131 ≤ H, W ≤ 1091 ≤ Q ≤ 1051-7

Получение информации о результатах окончательной проверки

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

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

Входной файл (input.txt) Выходной файл (output.txt)
1
6 6
3 3
...
.X.
...
5
2 2 2 2
5 2 5 2
2 5 2 5
5 5 5 5
6 6 6 6
1
1
1
1
0
2
4 3
2 3
X.X
.X.
12
1 1 1 1
1 2 1 2
1 3 1 3
2 1 2 1
2 2 2 2
2 3 2 3
3 1 3 1
3 2 3 2
3 3 3 3
4 1 4 1
4 2 4 2
4 3 4 3
1
0
1
0
1
0
0
1
0
1
0
1
3
640 896
5 7
.......
.......
..X....
.......
.......
2
543 782 543 782
543 783 543 783
1
0
4
10 10
5 5
XX...
.XXX.
...X.
.XX..
XX.X.
5
2 8 10 10
2 10 7 10
4 8 7 10
2 8 7 9
2 4 10 9
14
2
8
8
23
5
640 960
5 15
.XX..X..XXX..XX
X...X.X..X..X..
X...X.X..X...X.
X...XXX..X....X
.XX.X.X..X..XX.
2
1 1 640 960
333 121 634 932
253952
101336

Задача W. Сумма равна произведению

Автор:И. Блинов   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

Учитель математики придумал игру для развития навыков устного счёта. Учитель записывает на доске таблицу A из N × N натуральных чисел. Затем он вызывает к доске двух учеников, и указывает одно из чисел в таблице (Aij). Первый ученик должен выбрать другое число в той же строке, что и указанное учителем (Aiq, q ≠ j), и сложить с указанным числом. Второй ученик должен выбрать другое число в той же столбце, что и указанное учителем (Apj, p ≠ i), и перемножить с указанным числом.

Если результаты вычислений у двух учеников совпали (Aij + Aiq = Aij × Apj), то ученики получают пятёрки. Чтобы игра была честной, учитель указывает только на такие элементы, для которых существует хотя бы одна подходящая пара чисел. Учитель хочет вызвать как можно больше учеников, указывая каждым на ранее не использованный элемент в таблице.

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

По втором примере учитель может выбрать число. 2 (2 + 8 = 2 × 5), 4 (4 + 8 = 4 × 3) либо 3 (3 + 9 = 3 × 4). Если вместо 13 поставить число 5, ответ не изменится, хотя для числа 2 появится второй способ выбора подходящей пары чисел.

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

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

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

Выходной файл должен содержать единственное целое число — количество элементов Aij, для которых существуют p ≠ i, q ≠ j, такие что Aij + Aiq = Aij × Apj.

Ограничения

1 ≤ N ≤ 500,

1 ≤ Aij ≤ 109

Описание подзадач и системы оценивания

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
Naij
1151 ≤ N ≤ 101 ≤ Aij ≤ 30
2161 ≤ N ≤ 1001 ≤ Aij ≤ 10001
3221 ≤ N ≤ 2001 ≤ Aij ≤ 10002
4471 ≤ N ≤ 5001 ≤ Aij ≤ 1093

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
2 2
2 2
4
2
4
2  8  12 4
5  6  7  1
9  10 11 3
13 14 15 16 
3
3
2
1000 1000
1000 1000
0

Задача X. Отрезок деревьев

Автор:А. Усманов   Ограничение времени:10 сек
Ввод / вывод:интерактивный   Ограничение памяти:256 Мб

Условие

Данная задача является интерактивной.

После просмотра нескольких документальных фильмов о природе, лесник Шон очень беспокоится о местонахождении деревьев в своём лесу. Дело в том, что в одном из таких фильмов деревья просто так взяли и ушли. Конечно это было необходимо из-за событий, которые происходили в фильме. Но Шон абсолютно уверен, что в реальности такие события не могут случиться по ряду обстоятельств. Поэтому он считает, что у деревьев в его лесу нет никакой уважительной причины, чтобы отлучаться. То есть деревьям нельзя просто так взять и уйти.

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

Всего в лесу растёт N деревьев. Лес является непрерывным отрезком на прямой от 1 до L. Все деревья растут в разных целочисленных точках.

У Шона есть сканер, который позволяет определить наличие хотя бы одного дерева на каком-то участке леса. К сожалению, заряда сканера хватит только на K сканирований.

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

Протокол взаимодействия

Сначала на вход программе-решению подаётся целое число L — длина леса.

Для каждого теста жюри зафиксировало числа N и K — количество деревьев и максимальное количество запросов на сканирование участка леса. Гарантируется, что K запросов достаточно, чтобы решить задачу. Эти числа не сообщаются программе-решению. Ограничения на N и K в различных подзадачах приведены в таблице системы оценивания. Если решение делает более K запросов к программе жюри, то на этом тесте оно получает в качестве результата тестирования "Wrong answer".

Чтобы сделать запрос программа-решение должна вывести строку вида "? l r", где l и r (1 ≤ l ≤ r ≤ L) — целые числа, крайние левая и правая точка сканируемого участка леса. В ответ на запрос программа жюри подаёт на вход программе-решению либо строку "Yes", либо строку "No", в зависимости от того, есть ли хотя бы одно дерево в запрашиваемом участке.

Если программа-решение определила ответ на задачу, она должна вывести две строки: в первой "ok?", во второй N целых чисел — список точек, в которых растут деревья в порядке возрастания координат. После этого программа-решение должна завершиться.

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

После каждого запроса и вывода ответа необходимо выполнить сброс буфера. Например, в Pascal необходимо написать flush(output), в C++ — cout.flush().

Ограничения

1 ≤ N ≤ 103

1 ≤ L ≤ 109

1 ≤ xi ≤ L

Описание подзадач и системы оценивания

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

Подзадача Баллы Дополнительные ограничения Необходимые подзадачи
NLK
114N = 11 ≤ L ≤ 2500K = 100
212N = 11 ≤ L ≤ 106K = 471
317N = 11 ≤ L ≤ 109K = 371-2
41535 ≤ N ≤ 10035 ≤ L ≤ 103K = N2
5111 ≤ N ≤ 1031 ≤ L ≤ 104K = 100 + 100 * N1, 4
6131 ≤ N ≤ 1031 ≤ L ≤ 106K = 43 * N1-2, 4-5
7181 ≤ N ≤ 1031 ≤ L ≤ 109K = 33 * N1-6

Получение информации о результатах окончательной проверки

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

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

Стандартный вход Стандартный выход
1
5

Yes

No

Yes

No


ok



? 1 5

? 1 2

? 3 3

? 4 5

ok?
3
2
6

Yes

No

Yes

No

Yes

Yes

Yes


ok

? 1 2

? 1 1

? 2 2

? 3 4

? 5 6

? 5 5

? 6 6

ok?
2 5 6

Задача Y. Обработка картинок

Автор:М. Спорышев   Ограничение времени:10 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  

Условие

У юного программиста Васи есть младший брат Петя.

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

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

Картинка представляет из себя набор из N строк по M символов в каждом. Каждый символ может принимать значения с кодами от 33 до 126 в кодировке ASCII.

Петя и Вася решили искать на картинке ромбы специального вида. Контур таких ромбов можно задать уравнением |x − a| + |y − b| = r, где a  — номер столбца центра фигуры, b — номер строки центра фигуры, а r  — ее радиус. Фигура засчитывается только в том случае, если все клетки ее контура содержат один и тот же символ, а также не вылезают за границы картинки. Также не учитываются фигуры, радиус r которых равен 0.

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

Отправка решения и тестирование

Данная задача будет проверяться на ОДНОМ входном файле, содержащем все тесты. Этот файл можно скачать ЗДЕСЬ.

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

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

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

Первая строка входного файла содержит целое число T — количество тестов. Следующие строки содержат описания тестов.

Первая строка каждого теста содержит два целых числа N, M — размеры картинки.

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

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

Выходной файл должен содержать T ответов на тесты. Каждый ответ состоит из одной или двух строк.

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

В случае, если ответ на тест найти не удалось, выведите для этого теста одну строку с  − 1.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
7 7
1111111
1~~A~~1
1.A.A.1
1A...A1
1~A~A~1
1~~A~~1
1111111
7 7
1111111
1~~A~~1
1.A.A.1
1A...A1
1BA~AB1
B~BAB~B
1B111B1
1
4 4 2 A
3
4 4 2 A 6 2 1 B 6 6 1 B

1.265s 0.012s 89