ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Фильтр
Сложность с по   Класс с по  
Выбрана 1 задача
Версия для печати
Убрать все задачи

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

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

Входные данные. В файле 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

   Решение

Задачи

Страница: << 2 3 4 5 6 7 8 >> [Всего задач: 51]      



Задача 64173

Тема:   [ Многомерные массивы ]
Сложность: 2
Классы: 8

Хождение за золотом - 2

Задача такая же, как и предыдущая, только мудрец мог более одного
раза проходить по одной и той же клетке. Золото с нее он брал при этом
только один раз - когда проходил по клетке в первый раз.

Входные и выходные данные такие же, как в предыдущей задаче.
Дополнительное ограничение: число пройденных мудрецом клеток
не превышает 10000.

Пример входного файла
3 4
1 2 3 4
5 6 7 8
9 10 11 12
9
1 1
2 1
2 2
2 3
1 3
1 2
1 1
1 2
2 2

Пример выходного файла
30
Прислать комментарий     Решение

Задача 64174

Тема:   [ Многомерные массивы ]
Сложность: 2
Классы: 8

Хождение за золотом - 3

Задача такая же, как и предыдущая, только передвижения мудреца задаются
другим способом:

Входные данные
Во входном файле записано план комнаты. Сначала записано количество
строк N, затем - количество столбцов M (1<=N<=20,1<=M<=20).
Затем записано N строк по M чисел в каждой - количество килограммов
золота, которое лежит в данной клетке (число от 0 до 50).
Далее записано число X - сколько клеток обошел мудрец.
1<=X<=10000.

Известно, что мудрец начал с клетки с координатами (1,1).
Далее записано X-1 число: куда перемещался мудрец:
число 1 обозначает, что мудрец делал шаг вправо,
число 2 обозначает, что мудрец делал шаг вверх,
число 3 обозначает, что мудрец делал шаг влево,
число 4 обозначает, что мудрец делал шаг вниз.

Известно, что мудрец не выходил из лабиринта, при этом он мог
через одну и ту же клетку пройти несколько раз.

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

3 4
1 2 3 4
5 6 7 8
9 10 11 12
9
4 1 1 2 3 3 1 4
Прислать комментарий     Решение

Задача 64178

Тема:   [ Одномерные массивы ]
Сложность: 2
Классы: 8

Светофорчики

В подземелье M тоннелей и N перекрестков, каждый тоннель
соединяет какие-то два перекрестка. Мышиный король решил поставить
по светофору в каждом тоннеле перед каждым перекрестком. Напишите
программу, которая посчитает, сколько светофоров должно быть
установлено на каждом из перекрестков. Перекрестки пронумерованы числами
от 1 до N.

Входные данные. В файле INPUT.TXT записано два числа N и M (0<N<=100,
0<=M<=N*(N-1)/2 ). В следующих M строках записаны по два числа i и j
(1<=i,j<=N ), которые означают, что перекрестки i и j соединены тоннелем.

Выходные данные. В файл OUTPUT.TXT вывести N чисел:
k-ое число означает количество светофоров на k-ом перекрестке.

Примечание. Можно считать, что любые два перекрестка соединены не более,
чем одним тоннелем. Нет тоннелей от перекрестка i до него самого.

Пример файла INPUT.TXT	
7 10
5 1
3 2
7 1
5 2
7 4
6 5
6 4
7 5
2 1
5 3	

Пример файла OUTPUT.TXT
3 3 2 2 5 2 3
Прислать комментарий     Решение

Задача 64179

Тема:   [ Одномерные массивы ]
Сложность: 2
Классы: 8

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

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

Входные данные. В файле 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
Прислать комментарий     Решение

Задача 64180

Темы:   [ Одномерные массивы ]
[ Вложенные циклы ]
Сложность: 2
Классы: 8

Издевательство

Эпиграф:
Штирлиц ехал на машине, увидел голосующего Бормана, и проехал мимо.
Через некоторое время он снова увидел голосующего Бормана,
и снова проехал мимо. Вскоре он опять увидел голосующего Бормана.
-Издевается! - подумал Борман.
-Кольцевая! - догадался Штирлиц.

В городе N площадей. Любые две площади соединены между собой ровно одной
дорогой с двусторонним движением. В этом городе живет Штирлиц.
У Штирлица есть хобби - он любит воскресным утром выйти из дома,
сесть в машину, выбрать какой-нибудь кольцевой маршрут, проходящий ровно
по трем площадям (то есть сначала он едет с какой-то площади на
какую-то другую, потом - на третью, затем возвращается на начальную,
и опять едет по этому маршруту). Он воображает, что где-то на этом
пути стоит Борман. И так вот ездит Штирлиц все воскресенье, пока голова
не закружится, и радуется...
Естественно, что Штирлицу хочется проезжать мимо точки, в которой,
как он воображает, стоит Борман, как можно чаще. Для этого, естественно,
выбранный Штирлицем маршрут должен быть как можно короче. Напишите
программу, которая выберет оптимальный для Штирлица маршрут.

Входные данные
Во входном файле INPUT.TXT записано сначала число N (3<=N<=100), а затем
матрица NxN расстояний между площадями (число в позиции i,j
обозначает длину дороги, соединяющей i-ую и j-ую площади).
Все числа в матрице (кроме стоящих на главной диагонали) - натуральные,
не превышающие 1000.  Матрица симметрична относительно главной диагонали,
на главной диагонали стоят 0.

Выходные данные
В выходной файл OUTPUT.TXT выведите номера площадей в оптимальном маршруте.
Если маршрутов несколько, выведите любой из них.

Пример файла INPUT.TXT	
5
0  20 10   30 40
20 0  30   1  2
10 30 0    40 1000
30 1  40   0  21
40 2  1000 21 0	

Пример файла OUTPUT.TXT
4 5 2
Прислать комментарий     Решение

Страница: << 2 3 4 5 6 7 8 >> [Всего задач: 51]      



© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .