Выбрано 2 задачи 
Убрать все задачи
Задана квадратная доска размером N×N. Известно, что на ней играли в интеллектуальную игру, вследствие чего клеточки оказались окрашенными в белый, чёрный и зеленый цвета. Раскраска клеточек может быть разной (ведь это интеллектуальная игра!), но все клеточки самого верхнего ряда белые, а самого нижнего - чёрные.
Чтобы выявить победителя, необходимо подсчитать количество клеточек в белой и количество клеточек в черной области. Белая область - это как можно большая (по количеству клеточек) часть квадрата, которая ограничена сверху верхней стороной квадрата, а с других сторон - непрерывной границей, которая проходит только через белые клеточки и никакая клеточка не встречается больше одного раза. Белая граница представляет собой последовательность белых соседних клеточек (соседние клеточки имеют общую сторону). Концами этой границы должны быть левая верхняя и правая верхняя клеточки квадрата.
Определение чёрной области выглядит аналогично: она ограничена снизу нижней стороной квадрата, с других сторон - чёрной границей, которая проходит только через чёрные клеточки, а концы этой границы - левая нижняя и правая нижняя клеточки квадрата.
Задание
Напишите программу SCORE, которая по раскраске квадрата находит количество клеточек в белой и чёрной областях.
Входные данные
Первая строка входного файла SCORE.DAT содержит единственное целое число N - размер квадрата (5≤N?250). Каждая из следующих N строк содержит по N символов "G", "W" или "B" (записанных без пробелов), которые обозначают зелёный, белый и чёрный цвет, соответственно.
Выходные данные
Первая строка выходного файла SCORE.SOL должна содержать количество клеточек в белой области, а вторая строка - количество клеточек в чёрной области.
Пример входных и выходных данных
|
SCORE.DAT |
SCORE.SOL |
|
7 WWWWWWW WGWWBWG WWWWGWW BBGWWWB GWBBWGB BBBBGBB BBBBBBB |
22 15 |
Вид белой и чёрной областей для примера из условия представлен на рисунке.
В треугольнике ABC точка M лежит на стороне AC, а точка L на стороне BC расположена так, что BL : LC = 2 : 5. Прямая, проходящая через точку L параллельно стороне AB, пересекает отрезок BM в точке O, причём BO : OM = 7 : 4. Найдите отношение, в котором точка M делит сторону AC.
|
|
 |
Условие
Сколькими способами можно поставить на шахматную доску белого и чёрного королей так, чтобы получилась допустимая правилами игры позиция?
Решение
Белого короля можно поставить на любое из 64 полей. Однако количество полей, которые он при этом будет бить, зависит от его расположения. Поэтому необходимо разобрать три случая:
1) если белый король стоит в углу (углов всего 4), то он бьёт 4 поля (включая то, на котором стоит), и остается 60 полей, на которые можно поставить чёрного короля;
2) если белый король стоит на краю доски, но не в углу (таких полей – 24), то он бьёт 6 полей, и для чёрного короля остается 58 возможных полей;
3) если же белый король стоит не на краю доски (таких полей – 36), то он бьёт 9 полей, и для чёрного короля остается 55 возможных полей.
Таким образом, всего есть 4·60 + 24·58 + 36·55 = 3612 способов расстановки королей.
Ответ
3612 способами.
Источники и прецеденты использования
| книга | |
| Автор | Генкин С.А., Итенберг И.В., Фомин Д.В. |
| Год издания | 1994 |
| Название | Ленинградские математические кружки |
| Издательство | Киров: "АСА" |
| Издание | 1 |
| глава | |
| Номер | 3 |
| Название | Комбинаторика-1 |
| Тема | Классическая комбинаторика |
| задача | |
| Номер | 014 |
