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