10 класс (max – 65 баллов)

Проверка на симпатичность. (Двумерные массивы) – (20 баллов)

Рассмотрим таблицу, содержащую n строк и m столбцов, в каждой клетке которой расположен ноль или единица. Назовем такую таблицу симпатичной, если в ней нет ни одного квадрата 2 на 2, заполненного целиком нулями или целиком единицами.

Так, например, таблица 4 на 4, расположенная слева, является симпатичной, а расположенная справа таблица 3 на 3 - не является.

Задано несколько таблиц. Необходимо для каждой из них выяснить, является ли она симпатичной.

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

Первая строка входного файла INPUT.TXT содержит количество t (1 ≤ t ≤ 10) наборов входных данных. Далее следуют описания этих наборов. Описание каждого набора состоит из строки, содержащей числа n и m (1 ≤ n,m ≤ 100), и n строк, каждая из которых содержит по m чисел, разделенных пробелами. j-ое число в i+1-ой строке описания набора входных данных - элемент aij соответствующей таблицы. Гарантируется, что все aij равны либо нулю, либо единице.

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

Для каждого набора входных данных выведите в файл OUTPUT.TXT единственную строку, содержащую слово «YES», если соответствующая таблица является симпатичной, и слово «NO» - в противном случае.

Пример

№


INPUT.TXT


OUTPUT.TXT

1


3
1 1
0
4 4
1 0 1 0
1 1 1 0
0 1 0 1
0 0 0 0
3 3
0 0 1
0 0 1
1 1 1


YES
YES
NO

Деление с остатком. (Длинная арифметика) (30 баллов)

Заданы два числа: N и K. Необходимо найти остаток от деления N на K.

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

Входной файл INPUT.TXT содержит два целых числа: N и K (1 <= N <= 10100, 1 <= K <= 109).

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

В выходной файл OUTPUT.TXT выведите остаток от деления N на K.

Примеры

№


INPUT.TXT


OUTPUT.TXT

1


239 16


15

2


4638746747645731289347483927 6784789


1001783

Сложная задача. (Логика) (10 баллов)

В авиационном подразделении служат Потапов, Щедрин, Семенов, Коновалов и Самойлов.

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

Щедрин и Коновалов не умеют управлять самолетом.
Потапов и Коновалов готовятся стать штурманами.
Щедрин и Самойлов живут в одном доме с радистом.
Семенов был в доме отдыха вместе со Щедриным и сыном синоптика.
Потапов и Щедрин в свободное время любят играть в шахматы с бортмехаником.
Коновалов, Семенов и синоптик увлекаются боксом.
Радист боксом не увлекается.

Какую специальность имеет Семенов? Ответ приведите в именительном падеже.

Комментарий по вводу ответа: ответ введите только маленькими буквами.

Шаблон. (5 баллов)

Даны 4 шаблона имён файлов:

P????P???.???

*TUPI*V.V*

*_?.*Z

*OS*.*U*

Укажите в качестве ответа самое короткое имя файла, удовлетворяющее всем указанным шаблонам. Регистр не важен.

Ключи
к заданиям первого (школьного) этапа Всероссийской предметной олимпиады школьников
по информатике и ИКТ 2011/2012 учебный год

класс (max – 65 баллов)

Проверка на симпатичность. (Двумерные массивы) – (20 баллов)

В этой задаче необходимо последовательно считывать в двумерный массив все представленные матрицы и проверять их на симпатичность, результат проверки выводить в выходной файл. Для проверки текущей матрицы на симпатичность можно в двойном цикле перебрать всевозможные подмассивы 2х2 и проверить: существует ли среди них хотя бы один, состоящий из одинаковых элементов. Если - да, то в файл нужно вывести "NO" и "YES" в противном случае. Механизм проверки одной матрицы на симпатичность можно описать следующим образом:

Ok=true;

for i=1..n-1{

for j=1..m-1{

if( (a[i][j]+a[i][j+1]+a[i+1][j]+a[i+1][j+1]) mod 4 == 0 ) Ok=false;

}

}

if(Ok) write("YES") else write("NO");

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

Деление с остатком. (Длинная арифметика) (30 баллов)

Решение данной задачи похоже на решение задачи "A div B". Здесь следует учесть, что делимое - достаточно большое число и в процессе вычисления текущее значение может превосходить максимально возможное для 4-байтного целого, поэтому нужно использовать другие типы (например, int64 или __int64 в паскале).

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

const maxsize=101;

int a[maxsize], b;

int64 x;

readlong(a);

read(b);

x=0; k=0;

for i=a[0]..1{

x = x*10+a[i];

if(x < b and k=0 and i > 1) continue;

k=1;

x = x mod b;

}

write(x);

Сложная задача. (Логика) (10 баллов)

Ответ: пилот

Шаблон. (5 баллов)

Ответ: POSTUPI_V.VUZ