Последовательность строк

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Пусть A - последовательность строк. Положим A1="A", A2="AB", A_K+2=A_K+A_K+1 для всех натуральных K, где плюс обозначает конкатенацию (запись подряд) двух строк. Например, A3="AAB", A4="ABAAB", A5="AABABAAB". Ваша задача узнать какой символ стоит в позиции M строки AN.

Входные данные

В первой строке записано число натуральное число Q (1 <= Q <= 100) - число тестов в файле. Далее следует Q строк, в каждой из которых записано по два числа M и N (1 <= M <= 10^9, 1 <= N <= 60).

Выходные данные

Выведите Q строк. В строке выводите искомый символ ("A" или "B") или фразу No solution, если в строке AN менее M символов.

Пример

Ввод

3
2 5
3 5
1024 5

Вывод

A
B
No solution

Двойная решетка

ограничение времени на тест: 2 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Две бесконечные равномерные прямоугольные решетки заданы размерами ячеек x1, y1 и x2, y2. Все размеры - целые в диапазоне от 1 до 100. Решетки расположены на плоскости параллельно друг другу так, что целочисленное смещение одного из узлов второй решетки относительно узла первой составляет 0 <= dx < x1 по горизонтали и 0 <= dy < y1 по вертикали. В результате наложения образуется новая "составная" решетка с более мелкими ячейками различного размера. Требуется вывести в порядке возрастания все различные площади ячеек составной решетки.

Входные данные

Во входном файле указаны числа x1, y1, x2, y2, dx, dy. Все числа -- целые.

Выходные данные

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

Пример

Ввод

20 20 12 10 2 0

Вывод

4
20
60
100
120

333. A+B=C

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Дан массив A[1..N] различных целых чисел (все элементы по модулю не превосходят 15*10^6). Ваша задача найти количество различных троек различных чисел (p,q,r) таких, что A[p]+A[q]=A[r]. Заметим, что тройки (1,2,3) и (2,1,3) следует считать различными.

Входные данные

В первой строке записано натуральное число N (1 <= N <= 3500). Далее записаны числа A[1], A[2],..., A[N] через пробелы.

Выходные данные

Выведите единственное число - ответ на поставленную задачу.

Пример

Ввод

4
3 2 4 1

Вывод

4

Сложение в фибоначчиевой системе счисления

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Числа Фибоначчи хорошо известны. Они определяются рекуррентным соотношением:
F0=0, F1=1, Fn=Fn-1+Fn-2 для n > 1.
Фибоначчиева система счисления (ФСС) основана на теореме Цеккендорфа, утверждающей, что любое целое положительное число имеет единственное представление вида
N=F_k1+F_k2+...+F_kr, где F_ki - числа Фибоначчи, а k1 >> k2 >>... >> kr >> 0.
Здесь i >> j означает, что i >= j+2. Целое неотрицательное число можно записать в виде последовательности нулей и единиц:
N=(b_mb_m-1...b₂)_F <=> N = SUM(b_kF_k), k = 2,..., m, где bi = 1, если Fi входит в представление, и 0, в противном случае.
Например, 1000000 = 832040 + 121393 + 46368 + 144 + 55 = F30 + F26 + F24 + F12 + F10 или (1000000)₁₀=(10001010000000000010100000000)_F. Эта система счисления напоминает двоичное представление, за исключением того, что в ней никогда не встречаются две 1 подряд. При прибавлении 1 к числу в ФСС возникают два случая. Если младший разряд есть 0, он заменяется на 1 (так как F2=1), в противном случае в двух младших разрядах будет 01, и они заменяются на 10 (так как F3=F2+1). Затем мы должны заменять набор цифр 011 на 100 (так как Fn=Fn-1+Fn-2), до тех пор, пока в строке цифр имеются две рядом стоящие единицы. Напишите программу для сложения двух чисел в ФСС.

Входные данные

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

Выходные данные

В выходной файл вывести результат сложения этих двух чисел также в ФСС.

Пример

Ввод

1010
100

Вывод

10010

Мы делили шоколад

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Плитка шоколада имеет прямоугольную форму и состоит из NxM долек (N рядов по M долек в каждом). Каждая долька весит 1 грамм. Требуется определить, возможно ли с помощью последовательности разламываний плитки (последовательность может иметь нулевую длину) отделить кусок весом P грамм. Искомый кусок должен быть цельным, а разламывания производятся вдоль линии раздела долек на всю длину текущего куска.

Входные данные

В первой строке входного файла записано число Q (1 <= Q <= 100) -- количество плиток шоколада. Далее следует Q строк содержащих по три числа N, M и P. Числа в одной строке разделяются пробелами. Все числа во входном файле натуральные, не превосходящие 1000.

Выходные данные

Выведите Q строк. Выдайте слово "Yes", если возможно выполнить поставленную задачу для соответствующей по порядку шоколадки и "No" в противном случае.

Пример

Ввод

2
3 3 4
4 4 7

Вывод

Yes
No

В разведку

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

N солдат стоят в шеренге. Генерал хочет отобрать трёх человек на разведку. Отбор он производит следующим образом: если в шеренге стоит более 3 человек, тогда все солдаты стоящие на четных или нечетных местах (по выбору генерала) освобождаются и выходят из шеренги. Так продолжается пока количество человек в шеренге не станет 3 или менее. Требуется узнать количество различных троек, которых он может выбрать таким образом.

Входные данные

Во входном файле записано натуральное число N (1<=N<=100000000).

Выходные данные

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

Пример

Ввод

Test #1
10
Test #2
4

Вывод

Test #1
2
Test #2
0

Склад

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

На склад поступило N лыж. Их длины A1, A2,...,AN. Требуется узнать какое наибольшее количество комплектов на продажу можно составить, если в комплект обязательно входит 2 лыжи и сумма их длин должна быть равна строго Q.

Входные данные

В первой строке записаны натуральные числа N (1 <= N <= 10000) и Q (1 <= Q <= 2000). Далее следует N чисел A1, A2,..., AN (все длины - натуральные, не превосходящие 1000).

Выходные данные

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

Пример

Ввод

7 5
1 2 1 4 3 1 3

Вывод

2

Таблица

ограничение времени на тест: 1 сек.
ограничение памяти на тест: 1024 KB.

ввод: input.txt
вывод: output.txt

 

Дана таблица A размером NxM в каждой клетке которой стоит либо "1", либо "0". Расстоянием между двумя клетками (r0,c0) и (r,c) будем называть abs(r-r0)+abs(c-c0). Ваша задача построить новую таблицу, в которой в каждой клетке (r,c) записано расстояние от (r,c) до ближайшей "1" в таблице A.

Входные данные

В первой строке записаны два натуральных числа N и M (0<N,M<183). Далее в каждой из последующих N строк записано по M символов (единиц или нулей). Так задается таблица А. В таблице есть хотя бы одна "1".

Выходные данные

Выведите таблицу В в формате: N строк по M чисел через пробелы.

Пример

Ввод

3 4
0001
0011
0111

Вывод

3 2 1 0
2 1 0 0
1 0 0 0