Цветной дождь

В Банановой республике очень много холмов, соединенных мостами.
На химическом заводе произошла авария, в результате чего испарилось
экспериментальное удобрение "зован". На следующий день выпал
цветной дождь, причем он прошел только над холмами, в некоторых местах
падали красные капли, в некоторых -  синие, а в остальных - зеленые,
в результате чего холмы стали соответствующего цвета. Президенту Банановой
республики это понравилось, но ему захотелось покрасить мосты между вершинами
холмов так, чтобы мосты были покрашены в цвет холмов, которые они соединяют.
К сожалению, если холмы разного цвета, то покрасить мост таким образом не
удастся. Посчитать количество таких "плохих" мостов.

Входные данные. В файле INPUT.TXT в первой строке записано N
(0<N<=100) - число холмов. Далее идет матрица смежности,
описывающая наличие мостов между холмами (1-мост есть, 0-нет).
В последней строке записано N чисел, обозначающих цвет холмов:
1 - красный; 2 - синий; 3 - зеленый.

Выходные данные. В файл OUTPUT.TXT вывести количество "плохих" мостов.

Пример файла INPUT.TXT	
7
0 1 0 0 0 1 1
1 0 1 0 0 0 0
0 1 0 0 1 1 0
0 0 0 0 0 0 0
0 0 1 0 0 1 0
1 0 1 0 1 0 0
1 0 0 0 0 0 0

1 1 1 1 1 3 3	

Пример файла OUTPUT.TXT
4

   Решение

Страница: 1 2 >> [Всего задач: 6]      

а) В выпуклом n-угольнике проведены все диагонали. Они разбивают его на несколько многоугольников. Докажите, что у каждого из них не более n сторон.
б) Докажите, что если n чётно, то у каждого из полученных многоугольников не более n - 1 сторон.

Прислать комментарий

Решение

Докажите, что если n-угольник разрезан произвольным образом на k треугольников, то kn - 2.

Прислать комментарий

Решение

На квадратном листе бумаги нарисовано n прямоугольников со сторонами, параллельными сторонам листа. Никакие два из этих прямоугольников не имеют общих внутренних точек. Докажите, что если вырезать эти прямоугольники, то количество кусков, на которые распадается оставшаяся часть листа, не более n + 1.

Прислать комментарий

Решение

Докажите, что если выпуклый четырёхугольник ABCD можно разрезать на два подобных четырёхугольника, то ABCD – трапеция или параллелограмм.

Прислать комментарий

Решение

В квадрате со стороной 1 проведено конечное число отрезков, параллельных его сторонам, причем эти отрезки могут пересекать друг друга. Сумма длин отрезков равна 18. Докажите, что площадь одной из частей, на которые разбит квадрат, не меньше 0,01.

Прислать комментарий

Решение

Страница: 1 2 >> [Всего задач: 6]