Темы --> Информатика --> Язык программирования
    Процедуры и функции(96 задач)
    Массивы(232 задач)
    Типы данных(356 задач)
    Циклы(177 задач)
    Условный оператор (if)(164 задач)
    Python(260 задач)
    Standard Template Library(2 задач)
---> 2 задач <---
Источники --> Командные олимпиады --> Кировские командные турниры
    2001(8 задач)
Страница: 1 Отображать по:
#1131
Ковролин для минотавра
  
ограничение по времени на тест
2.0 second;
ограничение по памяти на тест
64 megabytes
Задан лабиринт. Необходимо застелить все проходимые клетки ковролином. Ковролин в рулонах длины S и ширины 1. Необходимо минимизировать количество разрезов рулона.

«Что за свинья прошла здесь - корова, что ли?»

Под дворцом царя Миноса размером NxM построен одноэтажный лабиринт размером NxMx1. Некоторые из кубов 1x1x1 в этом лабиринте пустые, а некоторые — гранитные (сквозь них ходить нельзя). Количество пустых кубов в лабиринте S. Минотавр, гуляя в этом лабиринте только по пустым кубам, может дойти от любого пустого куба до любого другого пустого.

К сожалению, минотавр очень громко топает, поэтому выбранная им жертва успевает испугаться и убежать. Для того, чтобы этого избежать, фирма «Минос, минотавр and Co» закупила ковролин, которым собирается застелить пол пустых кубов, чтобы минотавр мог подбираться к жертве бесшумно. Рулон ковролина имеет размеры 1хS.

Рабочие хотят застелить пол лабиринта, сделав как можно меньше разрезов ковролина (разрезы разрешается делать только параллельно стороне рулона, имеющей длину 1).

Напишите программу, вычисляющую это минимальное число разрезов.

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

Во входном файле записано сначала число N, затем число M, задающие размеры лабиринта (1N10, 1M10). Далее идет N строк, по M чисел в каждой, задающих лабиринт. Каждое из этих чисел 0 или 1 — 0 означает пустой куб, а 1 — гранитный.

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

В выходной файл выведите одно число — минимальное возможное количество разрезов, которое нужно сделать в рулоне, чтобы застелить все пустые клетки лабиринта.

Примеры
Входные данные
1 10
1 1 1 1 1 0 0 0 0 0
Выходные данные
0
Входные данные
2 2
1 0
0 0
Выходные данные
1
#1132
Шахматы
  
ограничение по времени на тест
1.0 second;
ограничение по памяти на тест
64 megabytes
На доске стоят слоны и ладьи. Необходимо подсчитать, сколько клеток не бьет ни одна из фигур.

На шахматной доске стоит несколько офицеров и ладей. Требуется посчитать количество свободных клеток, которые не находятся под боем ни одной из фигур.

Замечание для тех, кто не умеет играть в шахматы:

Шахматная доска имеет размеры 8*8. Ладья бьет все клетки горизонтали и вертикали, проходящих через клетку, где она стоит, до первой встретившейся фигуры. Офицер бьет все клетки обеих диагоналей, проходящих через клетку, где он стоит, до первой встретившейся фигуры.

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

В первых восьми строках входного файла описывается шахматная доска. Первые восемь символов каждой из этих строк описывают состояние соответствующей горизонтали: символ B (заглавная латинская буква) означает, что в клетке стоит офицер, символ R — ладья, символ * — что клетка пуста. После описания горизонтали в строке могут идти пробелы, однако длина каждой строки не превышает 250 символов. После описания доски в файле могут быть пустые строки.

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

В выходной файл выведите количество пустых клеток, которые не бьются ни одной из фигур.

Примеры
Входные данные
********
********
*R******
********
********
********
********
********
Выходные данные
49
Входные данные
********
********
******B*
********
********
********
********
********
Выходные данные
54
Страница: 1 Отображать по:
Выбрано
:
Отменить
|
Добавить в контест