--->
232 задач
<---
Источники
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Мальчику Васе очень нравится известная игра "Сапер" ("Minesweeper").
В "Сапер" играет один человек. Игра идет на клетчатом поле (далее будем называть его картой) NxM (N строк, M столбцов). В K клетках поля стоят мины, в остальных клетках записано либо число от 1 до 8 - количество мин в соседних клетках, либо ничего не написано, если в соседних клетках мин нет. Клетки являются соседними, если они имеют хотя бы одну общую точку, в одной клетке не может стоять более одной мины. Изначально все клетки поля закрыты. Игрок за один ход может открыть какую-нибудь клетку. Если в открытой им клетке оказывается мина - он проигрывает, иначе игроку показывается число, которое стоит в этой клетке, и игра продолжается. Цель игры — открыть все клетки, в которых нет мин.
У Васи на компьютере есть эта игра, но ему кажется, что все карты, которые в ней есть, некрасивые и неинтересные. Поэтому он решил нарисовать свои. Однако фантазия у него богатая, а времени мало, и он хочет успеть нарисовать как можно больше карт. Поэтому он просто выбирает N, M и K и расставляет мины на поле, после чего все остальные клетки могут быть однозначно определены. Однако на определение остальных клеток он не хочет тратить свое драгоценное время. Помогите ему!
По заданным N, M, K и координатам мин восстановите полную карту.
Входные данные
В первой строке входного файла содержатся числа N, M и K (1 ≤ N, M, K ≤ 10). Далее идут K строк, в каждой из которых содержится по два числа, задающих координаты мин. Первое число в каждой строке задает номер строки клетки, где находится мина, второе число - номер столбца. Левая верхняя клетка поля имеет координаты (1,1), правая нижняя - координаты (N, M).
Выходные данные
Выходной файл должен содержать N строк по M символов, разделенных пробелами - соответствующие строки карты. j-й символ i-й строки должен содержать символ ‘*‘ (звездочка) если в клетке (i, j) стоит мина, цифру от 1 до 8, если в этой клетке стоит соответствующее число, либо ‘.‘ (точка), если клетка (i, j) пустая и у нее нет мин-соседей.
Примеры
Входные данные
4 4 2 2 2 2 3
Выходные данные
1 2 2 1 1 * * 1 1 2 2 1 . . . .
#3711
ограничение по времени на тест
6.0 second;
ограничение по памяти на тест
256 megabytes
В прямоугольной таблице клетки раскрашены в белый и черный цвета. Найти в ней прямоугольную область белого цвета, состоящую из наибольшего количества ячеек.
Входные данные
Во входном файле записана сначала высота \((N)\), а затем ширина \((M)\) таблицы \(((1 \le N \le 5000)\), \((1 \le M \le 5000))\), а затем записано \((N)\) строк по \((M )\) чисел в каждой строке, где \(0\) означает, что соответствующая клетка таблицы выкрашена в белый цвет, а \(1\) – что в черный.
Выходные данные
В выходной файл вывести одно число — количество клеток, содержащихся в наибольшем по площади белом прямоугольнике.
Примеры
Входные данные
5 6 1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
Выходные данные
9
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
256 megabytes
Дан список чисел, который может содержать до 100000 чисел. Определите, сколько в нем встречается различных чисел.
Примечание. Эту задачу на Питоне можно решить в одну строчку.
Входные данные
Вводится список целых чисел. Все числа списка находятся на одной строке.
Выходные данные
Выведите ответ на задачу.
Примеры
Входные данные
1 2 3 2 1
Выходные данные
3
Входные данные
1 2 3 4 5 6 7 8 9 10
Выходные данные
10
Входные данные
1 2 3 4 5 1 2 1 2 7 3
Выходные данные
6
#3788
Темы:
[Одномерные массивы]
Источники:
[
Личные олимпиады,
Всероссийская олимпиада школьников,
Муниципальный этап,
Московская область,
Очный этап,
2011,
Задача C
]
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
ООО «Симптотика» собирается наладить выпуск обучающих игр для детей младшего дошкольного возраста. Одной из придуманных игр был набор кубиков, из которых можно было собирать различные фигуры. Кубики упаковывались в коробку размером N × N × 1 кубиков.
Однако, многочисленные маркетинговые исследования показали, что детям неинтересно просто собирать различные фигурки. Гораздо интереснее складывать некоторый набор кубиков на дно коробки в столбики, а после этого переворачивать коробку на 90 градусов по часовой стрелке и смотреть, как именно меняется их расположение. Будем для простоты считать, что коробка поворачивается мгновенно, после чего все кубики падают на дно. На следующем рисунке продемонстрировано, как выглядит расположение кубиков в коробке до и после поворота на 90 градусов.
Разумеется, многим детям становится интересно, как будет выглядеть расположение кубиков после K поворотов в том же направлении. Требуется написать программу, которая вычисляет итоговое положение кубиков в коробке после K поворотов.
Входные данные
Сначала вводятся целые числа N и K (1 ≤ N ≤ 10, 0 ≤ K ≤ 109). После этого, во второй строке вводятся N неотрицательных чисел, не превышающих N. i-ое число обозначает количество кубиков в столбце под номером i.
Выходные данные
Необходимо вывести N чисел через пробел, i-ое из которых обозначает количество чисел в i-ом столбце в полученном после K поворотов расположении кубиков.
Примечание
Пример соответствует иллюстрации из условия.
Примеры
Входные данные
5 1 1 3 4 0 1
Выходные данные
4 2 2 1 0
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Пусть дан одномерный массив из N· M· K элементов. Все его элементы взяли и записали с конца в трехмерный массив размера N × M × K. В результате первый элемент одномерного массива оказался в клетке с координатами (n, m, k), второй — в клетке с координатами (n, m, k - 1) и т.д, (k + 1)-ый элемент оказался в клетке с координатами (n, m - 1, k), (k + 2)-ой элемент оказался в клетке с координатами (n, m - 1, k - 1) и т.д., а (n· m· k)-ый элемент — в клетке с координатами (1, 1, 1). Пусть в одномерном массиве элемент имел порядковый номер i, тогда найдите координаты этого элемента в трехмерном массиве и выведите сам элемент.
Входные данные
В первой строке входного файла даны четыре натуральных числа N, M, K, i (i ≤ N· M· K), не превосходящие 10. В последующих строках задан трехмерный массив следующим образом: даны N наборов чисел, записанных в M строк по K чисел в каждой строчке. Наборы чисел разделены пустыми строками, все числа целые, неотрицательные и не превышают 1000.
Выходные данные
В выходной файл требуется вывести координаты i-ого элемента и его значение.
Примеры
Входные данные
2 2 2 3 1 2 3 4 5 6 7 8
Выходные данные
2 1 2 6
Выбрано
:
|