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

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

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

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-ой строке описания набора входных данных - элемент aij соответствующей таблицы. Гарантируется, что все aij равны либо нулю, либо единице.

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

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

Пример

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

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

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

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

*TUPI*V.V*

*_?.*Z

*OS*.*U*

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

Ключи 

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

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

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

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. Деление с остатком.  (Длинная арифметика)  (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);

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

Ответ: пилот

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

Ответ: POSTUPI_V.VUZ