(max – 45 баллов)

Задача 1. “Проверка на симпатичность” – 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-ой строке описания набора входных данных — элемент a_ij соответствующей таблицы. Гарантируется, что все a_ij равны либо нулю, либо единице.

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

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

Пример

Задача 2. “Деление с остатком” – 10 баллов

Тип задачи: Задача по программированию. Целочисленная арифметика

Задание рассчитано на написание программы на любом языке программирования.

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

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

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

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

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

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

Примеры

Задача 3. “Лягушки” – 15 баллов

Тип задачи: Задача по программированию. Условный оператор

Задание рассчитано на написание программы на любом языке программирования.

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

Ваня наблюдает за лягушкой. Изначально она сидит в точке 0 числовой прямой. Каждую секунду она прыгает на 1 вправо, пока не достигнет точки K .Затем она начинает каждую секунду прыгать на 1 влево, пока не вернется в точку 0,затем – опять вправо и т.д. Требуется определить, где окажется лягушка через T секунд.

Формат входных данных

Во входном файле input.txt в двух строках находятся два числа K и T, разделенные пробелом. Оба

числа натуральные и не превосходят 1 000 000 000.

Формат выходных данных

Вывести в выходной файл output.txt одно число – координату лягушки в момент времени T.

Пример

82

Примечание

Программа не должна выводить никаких дополнительных сообщений, а также не может содержать операторов, вызывающих задержку выполнения программы (например, readln в конце программы)

Ключи

к заданиям первого (школьного) этапа Всероссийской предметной олимпиады школьников

по информатике и ИКТ 2016/2017 учебный год

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

Задача 1. “Проверка на симпатичность” – 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. Такой алгоритм немного сложнее для реализации, но более экономичен по используемой памяти, что иногда не менее важно.

Задача 2. “Деление с остатком” – 10 баллов

Тип задачи: Задача по программированию. Целочисленная арифметика

Задание рассчитано на написание программы на любом языке программирования.

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

Решение данной задачи похоже на решение задачи «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);

Задача 3. “Лягушки” – 15 баллов

Тип задачи: Задача по программированию. Условный оператор

Задание рассчитано на написание программы на любом языке программирования.

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

program A;

var

k, t: integer;

begin

assign(input, ‘input.txt’); reset(input);

assign(output, ‘output.txt’); rewrite(output);

ReadLn(k, t);

if (t div k mod 2 = 0) then

WriteLn(t mod k)

else

WriteLn(k — t mod k);

close(input); close(output);

end.