Задания первого (школьного) этапа Всероссийской предметной олимпиады школьников
по информатике и ИКТ 2013/2014 учебный год
10-11 класс (max – 100 баллов)
Проверка на симпатичность. (Двумерные массивы) – (40 баллов)
Рассмотрим таблицу, содержащую 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 | YES |
Значение ячейки. (20 баллов)
Вот два изображения одной и той же таблицы MS Excel: одно в режиме отображения формул,
другое - в режиме отображения значений.
Запишите в качестве ответа то число, которое выводится красным цветом на красном фоне в ячейке А8.
Измерение кол-ва информации. (25 баллов)
Книга, состоящая из 1360 страниц, занимает объем 40 Мбайт. Часть страниц книги является цветными изображениями в формате 320 * 640 точек. На одной странице книги с текстом размещается 1024 символа. Каждый символ закодирован 1 байтом. Количество страниц с текстом на 560 больше количества страниц с цветными изображениями. Сколько цветов используется для представления изображений книги? Ответ запишите в виде целого числа.
Шаблон. (15 баллов)
Даны 4 шаблона имён файлов:
P????P???.???
*TUPI*V. V*
*_?.*Z
*OS*.*U*
Укажите в качестве ответа самое короткое имя файла, удовлетворяющее всем указанным шаблонам. Регистр не важен.
Ключи
к заданиям первого (школьного) этапа Всероссийской предметной олимпиады школьников
по информатике и ИКТ 2013/2014 учебный год
10-11 класс (max – 100 баллов)
Проверка на симпатичность. (Двумерные массивы) – (40 баллов)В этой задаче необходимо последовательно считывать в двумерный массив все представленные матрицы и проверять их на симпатичность, результат проверки выводить в выходной файл. Для проверки текущей матрицы на симпатичность можно в двойном цикле перебрать всевозможные подмассивы 2х2 и проверить: существует ли среди них хотя бы один, состоящий из одинаковых элементов. Если - да, то в файл нужно вывести "NO" и "YES" в противном случае. Механизм проверки одной матрицы на симпатичность можно описать следующим образом:
Ok:=true;
for i=1 to n-1 do
for j=1 to m-1 do
if (a[i, j]+a[i, j+1]+a[i+1,j]+a[i+1,j+1]) mod 4 == 0 then Ok:=false;
if (Ok) then write("YES") else write("NO");
Следует заметить, что использование двумерного массива вовсе не обязательно. Здесь не обязательно запоминать все элементы матрицы, достаточно помнить предыдущую и текущую строчку и в процессе считывания данных проверять подмассивы 2х2. Такой алгоритм немного сложнее для реализации, но более экономичен по используемой памяти, что иногда не менее важно.
Ответ: 16
Шаблон. (15 баллов)