ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Информатика
>>
Книги, журналы
>>
Беров В., Лапунов А., Матюхин В., Пономарев А., Особенности национальных задач по информатике
главы:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Версия для печати
Убрать все задачи На квадратной доске расставлены целые неотрицательные числа. Черепашка, находящаяся в левом верхнем углу, мечтает попасть в правый нижний. При этом она может переползать только в клетку справа или снизу и хочет, чтобы сумма всех чисел, оказавшихся у нее на пути, была бы максимальной. Определить эту сумму. Формат входных данных Первая строка N размер доски. Далее следует N строк, каждая из которых содержит N целых чисел, представляющие доску. Формат выходных данных Одно число максимальная сумма. Решение Задан ориентированный ациклический граф. Требуется построить наименьшее количество путей, покрывающих все вершины этого графа и не пересекающихся ни по одной из вершин. Входные данные В первой строке входного файла записано количество вершин графа N (1 ≤ N ≤ 25). Далее перечислены ребра графа, заданные номерами начальной и конечной вершин. Выходные данные Выведите в первую строку выходного файла число K – наименьшее количество путей, которыми можно покрыть все вершины графа. Далее выведите сами эти пути (по одному в каждой строке), задавая их номерами вершин в порядке посещения. Пример входного файла 4 1 2 1 3 2 3 2 4 Пример выходного файла 2 1 2 4 3 Решение |
Страница: << 4 5 6 7 8 9 10 >> [Всего задач: 67]
Напишите программу, которая определяет план достижения цели за
минимально возможное число ходов, либо сообщает, что цели достичь нельзя.
Требуется найти такой путь движения кубика между двумя заданными
полями доски, при котором вычисленная сумма будет минимальной. Числа,
стоящие в основании кубика в начальной и конечной позициях, также входят в
сумму.
Будем считать, что поверхность болота ровная, а веревка достаточно длинная и не может ни за что зацепиться либо запутаться. Иванушка должен, держа в руках конец этой веревки, проскакать по кочкам так, чтобы размотать царевну и вернуться на начальную кочку. Так как царевна очень изнежена, то она ни в какой момент времени не должна быть обмотана веревкой более десяти раз (иначе веревка поранит царевну). Требуется определить такой маршрут движения Иванушки, при котором за
его ноги зацепится минимально возможное количество водорослей.
В следующих N строках записана матрица N × N, составленная из
вещественных чисел. Число в i-й строке и j-м столбце этой матрицы означает
количество водорослей, цепляющихся за ноги Иванушки при прыжке с i-й
кочки на j-ю.
Входные данные В первой строке входного файла записано количество вершин графа N (1 ≤ N ≤ 25). Далее перечислены ребра графа, заданные номерами начальной и конечной вершин. Выходные данные Выведите в первую строку выходного файла число K – наименьшее количество путей, которыми можно покрыть все вершины графа. Далее выведите сами эти пути (по одному в каждой строке), задавая их номерами вершин в порядке посещения. Пример входного файла 4 1 2 1 3 2 3 2 4 Пример выходного файла 2 1 2 4 3
Пояснения для тех, кто плохо учил в школе физику:
Как следствие, получаем следующие формулы:
Страница: << 4 5 6 7 8 9 10 >> [Всего задач: 67] |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|