Задача A. Строки в книге

Автор:Московская олимпиада для 7-9 кл., 2005   Ограничение времени:3 сек
Входной файл:a.in   Ограничение памяти:64 Мб
Выходной файл:a.out  

Условие

В книге на одной странице помещается K строк. Таким образом, на 1-й странице печатаются строки с 1-й по K-ю, на второй - с (K + 1)-й по (2 × K)-ю и т.д. Напишите программу, которая по номеру строки в тексте определяет номер страницы, на которой будет напечатана эта строка, и порядковый номер этой строки на странице.

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

Входной файл содержит число K — количество строк, которое печатается на странице, и число N — номер строки

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

В выходной файл выведите два числа — номер страницы, на которой будет напечатана эта строка и номер строки на странице

Ограничения

1 ≤ K ≤ 200, 1 ≤ N ≤ 20000

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

Входной файл (a.in) Выходной файл (a.out)
1
50 1
1 1
2
20 25
2 5
3
15 43
3 13

Задача B. Симметричная последовательность

Автор:Московская олимпиада для 7-9 кл., 2005   Ограничение времени:3 сек
Входной файл:b.in   Ограничение памяти:64 Мб
Выходной файл:b.out  

Условие

Последовательность чисел назовем симметричной, если она одинаково читается как слева направо, так и справа налево. Например, следующие последовательности являются симметричными:

1 2 3 4 5 4 3 2 1
1 2 1 2 2 1 2 1
Вашей программе будет дана последовательность чисел. Требуется определить, какое минимальное количество и каких чисел надо приписать в конец этой последовательности, чтобы она стала симметричной.

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

Во входном файле записано сначала число N — количество элементов исходной последовательности. Далее записано N чисел — элементы этой последовательности. Элементы последовательности — натуральные числа от 1 до 9.

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

В выходной файл выведите сначала число M — минимальное количество элементов, которое надо дописать к последовательности, а потом M чисел (каждое - от 1 до 9) — числа, которые надо дописать к последовательности.

Ограничения

1 ≤ N ≤ 100

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

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

Задача C. Кинотеатр

Автор:Московская олимпиада для 7-9 кл., 2005   Ограничение времени:3 сек
Входной файл:c.in   Ограничение памяти:64 Мб
Выходной файл:c.out  

Условие

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

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

Во входном файле записаны два числа — X и Y (оба числа натуральные).

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

В выходной файл выведите какую-нибудь строку, в которой будет ровно X символов B (обозначающих мальчиков) и Y символов G (обозначающих девочек), удовлетворяющую условию задачи. Пробелы между символами выводить не нужно.

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

Ограничения

1 ≤ X, Y ≤ 100

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

Входной файл (c.in) Выходной файл (c.out)
1
5 5
BGBGBGBGBG
2
5 3
BGBGBBGB
3
100 1
NO SOLUTION

Задача D. Количество слов

Автор:Московская олимпиада для 7-9 кл., 2005   Ограничение времени:3 сек
Входной файл:d.in   Ограничение памяти:64 Мб
Выходной файл:d.out  

Условие

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

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

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

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

Во входном файле записана строка.

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

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

Ограничения

Входная строка имеет длину не более 200 символов.

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

Входной файл (d.in) Выходной файл (d.out)
1
Hello , world!
2
2
www.olympiads.ru
3
3
Gyro-compass - this is a ...
4

Задача E. Метро

Автор:Московская олимпиада для 7-9 кл., 2005   Ограничение времени:3 сек
Входной файл:e.in   Ограничение памяти:64 Мб
Выходной файл:e.out  

Условие

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

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

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

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

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

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

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

Ограничения

2 ≤ N ≤ 100, 1 ≤ M ≤ 20, 2 ≤ Pi ≤ 50.

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

Входной файл (e.in) Выходной файл (e.out)
1
5 2
4 1 2 3 4
2 5 3
3 1
0
2
5 5
2 1 2
2 1 3
2 2 3
2 3 4
2 4 5
1 5
2
3
10 2
6 1 3 5 7 4 9
6 2 4 6 8 10 7
3 8
1
4
4 2
2 1 2
2 3 4
1 3
-1

Problem F. Divide by Squares

Author:Южно-Уральский открытый командный чемпионат   Time limit:5 sec
Input file:input.txt   Memory limit:64 Mb
Output file:output.txt  

Statement

Divide by Squares is played on a rectangular grid. Some of the squares in the grid are numbered. The objective is to divide the grid into rectangular and square pieces such that each piece contains exactly one number, and that number represents the area of the rectangle (from Wikipedia).

On the pictures you can see a sample of the puzzle and its solution.

You are to write program that solves this puzzle.

Input file format

The first line of the input file contains three integers, separated by spaces — the height H, the width W of the grid, and total amount K of numbers on the grid. Each of the next K lines contains three integers, separated by spaces — position (i, j) of the number and the number itself. The puzzle in the input has at least one solution.

Output file format

The output file must contain K lines. For each number in the input you should print four integers on corresponding line — coordinates of left upper corner of the rectangle that contains this number and its height and width. You have to print arbitrary solution.

Constraints

1 ≤ H ≤ 10, 1 ≤ W ≤ 10, 1 ≤ K ≤ W * H

Sample tests

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

0.424s 0.011s 25