Задача A. Грузоперевозки

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

Условие

Стивен устроился на работу программистом в новую транспортную компанию. В его обязанности входит оптимизация стоимости грузоперевозок из одной страны в другую.

В базе данных компании содержатся N городов, пронумерованных от 1 до N, и M односторонних дорог между некоторыми из них. Дорога номер i характеризуется тремя числами ui vi li — начальным городом, конечным городом и длиной дороги. Гарантируется, что ui ≠ vi, и не существует двух разных дорог i, j, для которых ui = uj, vi = vj.

Страна представляет из себя такое множество из одного или более городов, что:

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

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

Запрос на перевозку определяется парой чисел sj fj — номерами города отправления и города назначения j-го груза. Напишите программу, которая для каждого из Q запросов определяет наименьшую возможную стоимость перевозки груза.

В тесте из примера имеется две страны. Одна состоит из городов 1, 2, 3, другая — из городов 4, 5.

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

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

Далее следует M троек целых чисел ui vi li — начальный город, конечный город и длина i-й дороги.

Далее следует целое число Q, за котором идут Q запросов по два целых числа sj fj — город отправления и город назначения j-го груза.

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

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

Ограничения

1 ≤ N ≤ 300; 0 ≤ M ≤ N(N − 1); 1 ≤ Q ≤ 105; 1 ≤ ui, vi, sj, fj ≤ N; 0 ≤ li ≤ 106

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

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

Задача B. Дед Мазай и зайцы

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

Условие

Дед Мазай давно живёт в деревне Малые Вежи. Так давно, что он составил карту высот окрестностей.

Карта представляет собой прямоугольник n × m клеток (n клеток в высоту и m клеток в ширину). Для клетки, находящейся в i-ом ряду на j-ой колонке, отмечена высота hi,j местности в этой клетке над уровнем реки (в метрах). Известно, что для всех i выполняется соотношение hi,1 = 0. То есть, изначально рекой затоплены те и только те клетки, которые располагаются в самом левом столбце карты.

На реке начался паводок. Уровень реки поднимается на 1 метр каждую минуту, затопляя окрестности. А именно, если клетка (i, j) соседствует с клеткой, затопленой рекой, и уровень реки уже достиг или превысил hi,j, то считается, что клетка (i, j) также затоплена рекой. Клетки считаются соседними, если у них имеется одна общая сторона.

В начале паводка дед Мазай в своей лодке находится в клетке (1; 1) — в левом верхнем углу карты. За одну минуту дед Мазай может перебраться на соседнюю клетку, если она уже затоплена рекой или будет затоплена рекой к моменту окончания перехода.

Зайцы в начале паводка располагаются в клетке (ir, jr), jr > 1. Обычно зайцы стоят на месте, но если на следующей минуте их клетка окажется затоплена рекой, то они пытаются перейти на соседнюю клетку, которая не будет затоплена рекой. Если таких клеток несколько, то они выбирают из них первую в следующем списке: верхняя, правая, нижняя, левая. Если соседних клеток, которые на следующей минуте не будут затоплены рекой, не существует, то зайцы утонут.

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

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

Зайцы никогда не выходят за пределы карты. Деду Мазаю также не разрешается выводить свою лодку за пределы карты.

В первом примере дед Мазай подплывает к зайцам через 4 минуты. Уровень реки в этот момент равен 4 метрам, и в следующую минуту река затопит всю местность. Зайцы оказываются спасены.

Во втором примере дед Мазай перемещается на одну клетку вправо и ждёт пока зайцы сами окажутся рядом с ним, спасаясь от потопа.

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

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

В начале входного файла записаны целые числа n, m, ir, jr. Далее следует nm целых чисел hi,j — карта.

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

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

Если зайцев спасти невозможно, выведите единственное слово "NO".

Ограничения

1 ≤ n, m ≤ 500;

1 ≤ ir ≤ n;

2 ≤ jr ≤ m;

1 ≤ hi,j ≤ 105 при j > 2;

hi,1 = 0;

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

Входной файл (input.txt) Выходной файл (output.txt)
1
3 3 2 3
0 5 5
0 5 5
0 1 1
DDRR
2
5 4 5 2
0 1 1 1
0 4 5 6
0 3 1 1
0 2 1 1
0 1 1 1
RSS
3
4 2 2 2
0 1
0 1
0 2
0 3
NO

Problem C. Knuth-Morris-Pratt

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 two strings and finds position where the second string appears in the first one as a substring.

Input file format

First and second lines of input file contain given strings. Each string is a sequence of lower-case Latin letters from 'a' to 'z' and spaces.

Output file format

Output file must contain a single integer — position of the first occurrence of the substring in a string, or  − 1 if there is none. Positions are numbered from 1.

Constraints

Length of each string does not exceed 100000 characters.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
yezhiki nachinayut i vyygryvayut
yut
16

Problem D. Fibonacci level

Author:M. Sporyshev, A. Klenin, A. Baranov   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

For arbitrary non-empty strings S1 and S2, the Fibonacci sequence of strings is defined by a recurrence Si + 2 = Si + 1 + Si, where the '+' sign denotes string concatenation.

Let's say that string T has Fibonacci level n if there exists some Fibonacci sequence of strings which contains Sn = T. Note that any string of length 2 or more has Fibonacci level 3.

Your program must, given a string T, find its maximum Fibonacci level n as well as two starting strings S1 and S2 of corresponding Fibonacci sequence of strings.

Input file format

Input file contains a single string T, consisting of lowercase Latin letters.

Output file format

Output file must contain 3 lines: integer n followed by strings S1 and S2.

If there are several optimal solutions, output any of them.

Constraints

2 ≤ |T| ≤ 106

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
oxax
3
xax
o
2
cabccab
5
ab
c
3
axaxax
4
ax
ax

Задача E. Поврежденный XML

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

Условие

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

XML-строка состоит из открывающих и закрывающих тегов.

Открывающий тег начинается с открывающей угловой скобки < (ASCII 60), за ней следует имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка > (ASCII 62). Примеры открывающих тегов: <a>, <dog>.

Закрывающий тег начинается с открывающей угловой скобки, за ней следует прямой слеш / (ASCII 47), затем имя тега — непустая строка из строчных букв латинского алфавита, а затем закрывающая угловая скобка. Примеры закрывающихся тегов: </a>, </dog>.

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

Например, представленные ниже строки:

являются корректными XML-строками, а такие строки как: не являются корректными XML-строками.

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

Требуется написать программу, которая по строке, которую получил Петров, восстановит исходную XML-строку, которую отправлял Иванов.

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

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

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

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

Ограничения

Длина строки лежит в пределах от 7 до 1000, включительно. Строка содержит только строчные буквы латинского алфавита и символы <, > и /.

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

Входной файл (xml.in) Выходной файл (xml.out)
1
<a></b>
&lt;b&gt;&lt;/b&gt;
2
<a><aa>
&lt;a&gt;&lt;/a&gt;
3
<a><>a>
&lt;a&gt;&lt;/a&gt;
4
<a/</a>
&lt;a&gt;&lt;/a&gt;

0.798s 0.031s 21