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

Строка – это последовательность из 0 или более символов, заканчивающаяся символом перехода на новую строку (т.е. последним символом входного файла будет символ перехода на новую строку).

Время теста указано для тестирующего компьютера жюри Pentium-100МГц.

1. Прямоугольники (40 сек на тест)

В текстовом файле содержится некоторое изображение, состоящее из вертикальных и горизонтальных линий. Горизонтальные линии изображаются с помощью символа ‘–‘ (минус), вертикальные линии – с помощью символа ‘|’ (вертикальная черта). Пересечение вертикальной и горизонтальной линии обозначается символом ‘+’ (плюс). Пробелом кодируется пустое место.

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

Во входном файле содержится не более 2000 строк длиной не более 250 символов. В строке содержатся только символы ‘+’,’–‘,’|’ и пробелы.

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

Пример INPUT.TXT:

+--+ +-+

| | +-+

+--+

+--|--+

+--+

OUTPUT.TXT для примера:

4

2. Батон с изюмом (10 сек на тест)

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

Во входном файле в первой строке содержится число N (3<=N<=100). Далее следует N строк, в каждой строке целое число x_i – положение i-ой изюминки в батоне (–10⁶< x₁< x₂< …<x_N <10⁶).

В выходной файл вывести одно число – максимально возможную толщину ломтиков с точностью ±0.001.

Пример INPUT.TXT:

4

1

2

3

4

OUTPUT.TXT для примера:

1.500

3. Зашифрованное слово (5 сек на тест)

Некоторое слово кодируется с помощью нескольких слов-кодов следующим образом. Если буква кодируемого слова есть в слове-коде, то в соответствующей позиции кодируемого слова ставится символ ‘+’ (плюс). Если буквы нет, то ставится символ ‘–‘ (минус). Длина кодируемого слова равна L (1<=L<=30). Длина слов-кодов от 1 до 30 букв. Все слова состоят из прописных букв русского алфавита (коды символов от 80₁₆ до 9F₁₆).

Во входном файле содержится от 1 до 30 строк. В каждой строке содержится L символов ‘+’ или ‘–‘ (код зашифрованного слова), затем один пробел и слово, использованное для кодирования.

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

Пример INPUT.TXT:

-++-+ ЛЕТО

--+-+ КОД

+--+- СВЕТ

++--- СИГНАЛ

--+++ ОТВЕТ

OUTPUT.TXT для примера:

СЛОВО

4. Счастливый номер (5 сек на тест)

Номер состоит из N (1<=N<=1000) цифр, часть этих цифр неизвестна и заменена на символ ‘?’. Необходимо подставить на место символов ‘?’ цифры от 0 до 9 таким образом, чтобы получился счастливый номер, т.е. сумма первых [N/2] цифр должна стать равной сумме последних [N/2] цифр. Если возможно несколько вариантов счастливого номера, то выбрать из них наименьший номер. Номер может содержать ведущие нули.

Во входном файле в первой строке содержится шаблон номера, состоящий из цифр от 0 до 9 и символов ‘?’.

В выходной файл вывести наименьший счастливый номер или NO SOLUTION, если получить счастливый номер невозможно.

Пример INPUT.TXT:

1235??

OUTPUT.TXT для примера:

123501

5. 18,000 Seconds Remaining (ACM362) (5 сек на тест)

A feature of many file transfer programs is the ability to estimate the amount of time remaining in the transfer. These programs estimate the time remaining based on the number of bytes left to be transferred and the rate of transfer in previous seconds. You are to write a program to simulate this behavior.

The input will be a series of data sets, each set describing one file transfer. The first line of each data set will be a single non-negative integer, telling the size of the file in bytes. The subsequent lines will be the number of bytes transmitted in each second (all non-negative integers). The sum of the bytes transmitted will equal the number of bytes in the file.

The end of input will be indicated by a file size of 0 bytes. This data set should not be processed.

The output for each data set should begin with a line with the number of the data set and the size of the file being transferred. Then, there should be update lines estimating how many seconds remain, issued once every 5 seconds during the transfer.

To estimate the number of seconds remaining, first determine the transfer rate (bytes/second) for the previous 5 seconds. If no bytes were transferred during this time, then the transfer is stalled, and your program should report this. Otherwise, divide the number of bytes remaining to be transferred by the transfer rate for the previous 5 seconds to estimate the number of seconds remaining.

Report the number of seconds remaining as an integer. Always round up in reporting how much time is remaining (so if there are 12.2 seconds remaining, you should report there are 13 seconds remaining).

At the end of the transfer, print a line telling how many seconds the transfer took. Use the format in the sample.

There should be one blank line after the output from each data set.

Sample INPUT.TXT

100
10
20
20
0
10
0
10
0
10
0
20
200
60
30
100
10
50
5
5
5
5
25
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
0

Sample OUTPUT.TXT

Output for data set 1, 100 bytes:
 Time remaining: 4 seconds
 Time remaining: 5 seconds
Total time: 11 seconds
 
Output for data set 2, 200 bytes:
Total time: 4 seconds
 
Output for data set 3, 50 bytes:
 Time remaining: 1 seconds
 Time remaining: stalled
 Time remaining: stalled
 Time remaining: 0 seconds
Total time: 20 seconds