Задачи командных соревнований университета 1999

Дисковое пространство поделено на так называемые кластеры. При записи на диск файлы разделяются на части размером с кластер. Если все части файла размещены последовательно в последовательных кластерах диска, то последовательное чтение файла происходит максимально быстро. При изменении файла отдельные его части (фрагменты) могут оказаться разбросанными по всему диску в произвольном порядке, т. е. файл становится фрагментированным. При этом быстродействие компьютера снижается. Обычно дефраментация проводится, когда число фрагментированных файлов составляет 10-20% или более от числа всех файлов. Для определения степени фрагментации можно использовать таблицу размещения файлов FAT (File Allocation Table). Упрощенно ее можно описать следующим образом. Дисковое пространство делится на `M` кластеров, нумерующихся с 1 до `M`. В таблице FAT для каждого кластера диска записывается число 0, если соответствующий кластер свободен, или число `-1`, если это последний кластер файла, или число от 1 до `M`, указывающее на следующий кластер, занятый файлом.

Во входном файле в первой строке содержится количество кластеров на диске `M` (`1\ ≤\ M\ ≤\ 10000`), в последующих `M` строках – таблица FAT. Данные корректны, т.е. не содержат циклов и пересечений.

В выходной файл вывести в первой строке вывести общее число файлов на диске, во второй строке – число фрагментированных файлов. Файл будем считать не фрагментированным, если для всех частей файла верно, что `i` часть файла занимает `b+i-1` кластер, где `b` – первый кластер файла.

5
3
0
-1
5
-1

2
1

Дисковое пространство поделено на так называемые кластеры. При записи на диск файлы разделяются на части размером с кластер. Если все части файла размещены последовательно в последовательных кластерах диска, то последовательное чтение файла происходит максимально быстро. При изменении файла отдельные его части (фрагменты) могут оказаться разбросанными по всему диску в произвольном порядке, т. е. файл становится фрагментированным. При этом быстродействие компьютера снижается. Обычно дефраментация проводится, когда число фрагментированных файлов составляет 10-20% или более от числа всех файлов. Для определения степени фрагментации можно использовать таблицу размещения файлов FAT (File Allocation Table). Упрощенно ее можно описать следующим образом. Дисковое пространство делится на `M` кластеров, нумерующихся с 1 до `M`. В таблице FAT для каждого кластера диска записывается число 0, если соответствующий кластер свободен, или число `-1`, если это последний кластер файла, или число от 1 до `M`, указывающее на следующий кластер, занятый файлом.

Во входном файле в первой строке содержится количество кластеров на диске `M` (`1\ ≤\ M\ ≤\ 500000`), в последующих `M` строках – таблица FAT. Данные корректны, т.е. не содержат циклов и пересечений.

В выходной файл вывести в первой строке вывести общее число файлов на диске, во второй строке – число фрагментированных файлов. Файл будем считать не фрагментированным, если для всех частей файла верно, что `i` часть файла занимает `b+i-1` кластер, где `b` – первый кластер файла.

5
3
0
-1
5
-1

2
1

Предположим, что робот передал в качестве запроса последовательность из 0 и 1 длиной `L`. В качестве ответа необходим некоторый код также длиной `L`. В принципе можно последовательно передать все `2^L` возможных кодов, то есть `L*2^L` битов, но на это может не хватить времени. Лучше передать более короткую последовательность, которая также будет содержать все возможные коды длиной `L`.

Во входном файле указана длина кода `L` (`1\ ≤\ L\ ≤\ 10`).

В выходной файл вывести в первой строке длину минимальной последовательности, содержащую все возможные коды длиной `L`, во второй строке саму последовательность.

3

10
0001110100

АККВАРКУД
КВАРКТАВЕ
ВМУИВАЛКА
АРТЕТДРАТ

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

Во входном файле в первой строке содержится слово длиной не более 15 букв, которое нужно найти. Далее до конца файла идет сетка кроссворда. Размеры кроссворда не превышают 20x20 символов. Используются только прописные русские буквы. Слово обязательно присутствует в кроссворде.

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

АКВАРИУМ
АККВАРКУД
КВАРКТАВЕ
ВМУИВАЛКА
АРТЕТДРАТ

(1,1)
(1,2)
(2,2)
(2,3)
(2,4)
(3,4)
(3,3)
(3,2)

Игра рендзю (го-моку) похожа на обычные крестики-нолики, но игра ведется на доске 15x15 и нужно поставить 5 камней своего цвета в ряд (по вертикали, горизонтали или диагонали). Компьютер играет за черных и ходит первым. Ваша программа должна помочь компьютеру найти последний выигрывающий ход.

Во входном файле содержится 15 строк по 15 символов. "X" (латинская буква X) означает черный камень, "O" (латинская буква O) – белый камень, "." (точка) – пустое место.

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

OXXXX...XXO....
.O..XO.........
..O.X..........
...O...........
...............
...............
......O........
.......X.......
...............
...............
...............
...............
...............
...............
...............

A6

In 1742, Christian Goldbach, a German amateur mathematician, sent a letter to Leonhard Euler in which he made the following conjecture:

For example:

8 = 3 + 5. Both 3 and 5 are odd prime numbers.

20 = 3 + 17 = 7 + 13.

42 = 5 + 37 = 11 + 31 = 13 + 29 = 19 + 23.

Today it is still unproven whether the conjecture is right. (Oh wait, I have the proof of course, but it is too long to write it on the margin of this page.)

Anyway, your task is now to verify Goldbach's conjecture for all even numbers less than a million.

The input file will contain one or more test cases. Each test case consists of one even integer `n` with `6\ ≤\ n\ <\ 1000000`. Input will be terminated by a value of 0 for `n`.

For each test case, print one line of the form `n\ =\ a\ +\ b`, where `a` and `b` are odd primes. Numbers and operators should be separated by exactly one blank like in the sample output below. If there is more than one pair of odd primes adding up to `n`, choose the pair where the difference `b\ -\ a` is maximized. If there is no such pair, print a line saying "Goldbach's conjecture is wrong."

8
20
42
0

8 = 3 + 5
20 = 3 + 17
42 = 5 + 37

You have decided that PGP encryption is not strong enough for your email. You have decided to use Pig Latin encryption.

You are to write a program that will take in an arbitrary number of lines of text and output it in Pig Latin. Each line of text will contain one or more words. A "word" is defined as a consecutive sequence of letters (upper and/or lower case). Words should be converted to Pig Latin according to the following rules (non-words should be output exactly as they appear in the input):

1. Words that begin with a vowel (a, e, i, o, or u, and the capital versions of these) should just have the string "ay" (not including the quotes) appended to it. For example, "apple" becomes "appleay".

2. Words that begin with a consonant (any letter than is not A, a, E, e, I, i, O, o, U or u) should have the first consonant removed and appended to the end of the word, and then appending "ay" as well. For example, "hello" becomes "ellohay".

3. Do not change the case of any letter.

This is the input.

hisTay isay hetay inputay.