Страница:
<< 1 2
3 4 >> [Всего задач: 17]
|
[Хамелеон
]
|
|
Сложность: 3+
|
Игра «Хамелеон» происходит в квадрате
3 × 3, в клетках которого находятся 8 фишек с буквами этого слова, а одна из клеток пуста. За один ход разрешается
одну из фишек переместить на соседнюю пустую клетку. Цель игры –
достигнуть расположения фишек, указанного на рисунке.
Напишите программу, которая определяет план достижения цели за
минимально возможное число ходов, либо сообщает, что цели достичь нельзя.
Входные данные
Во входном файле находится матрица
3 × 3, составленная из больших букв русского алфавита.
Выходные данные
Ваша программа должна вывести в первую строку выходного файла искомое
число ходов, а в последующие – их список. Каждый ход задается
координатами той фишки, которая перемещается. Если плана не существует,
выведите в выходной файл сообщение «Нет решения».
Пример входного файла
ХАМ
Е Е
ОЛН
Пример выходного файла
2
3 2
3 3
|
[Пиво в розлив]
|
|
Сложность: 3
|
Имеются три пробирки, вместимостью 100 миллилитров каждая. Первые две
пробирки имеют риски, одинаковые на обеих пробирках. Возле каждой риски
надписано целое число миллилитров, которое вмещается в часть пробирки от
дна до этой риски (см. рисунок).
Изначально первая пробирка содержит 100 миллилитров пива, а остальные
две пусты. Требуется написать программу, которая выясняет, можно ли
отделить в третьей пробирке один миллилитр пива, и если да, то находит
минимально необходимое для этого число переливаний. Пиво можно
переливать из одной пробирки в другую до тех пор, пока либо первая из них не
станет пустой, либо одна из пробирок не окажется заполненной до какой-либо
риски.
Входные данные
В первой строке входного файла содержится число рисок N (1 ≤ N ≤ 20),
имеющихся на каждой из первых двух пробирок. Затем в порядке возрастания
следуют N целых чисел V1
, ..., VN (1 ≤ Vi ≤ 100), приписанных рискам. Последняя
риска считается сделанной на верхнем крае пробирок
(VN
= 100).
Выходные данные
В первой строке выходного файла должна содержаться строка «YES», если в
третьей пробирке возможно отделить один миллилитр пива, и «NO» – в
противном случае. В случае ответа «YES» во вторую строку необходимо
вывести искомое количество переливаний.
Пример входного файла
4
13 37 71 100
Пример выходного файла
YES
8
|
[Катаем кубик
]
|
|
Сложность: 3+
|
На шахматной доске стоит кубик, занимая своим основанием в точности одно из
полей доски. На его гранях написаны неотрицательные целые числа, не
превосходящие 1000. Кубик можно перемещать на смежные поля, перекатывая
через соответствующее ребро в основании. При движении кубика вычисляется
сумма чисел, попавших в его основание (каждое число считается столько раз,
сколько раз кубик оказывался лежащим на данной грани).
Требуется найти такой путь движения кубика между двумя заданными
полями доски, при котором вычисленная сумма будет минимальной. Числа,
стоящие в основании кубика в начальной и конечной позициях, также входят в
сумму.
Входные данные
Во входном файле через пробел записаны координаты начального и конечного
полей и 6 чисел, написанных на передней (в начальный момент), задней,
верхней, правой, нижней и левой гранях кубика соответственно. Координаты
полей указываются в стандартной шахматной нотации (см. пример). Начальное
и конечное поля различны.
Выходные данные
Выведите в выходной файл минимально возможную сумму и соответствующий
ей путь. Путь должен быть задан последовательным перечислением координат
полей, по которым движется кубик (включая начальное и конечное поля).
Координаты полей записываются в том же формате, что и во входных данных, и
разделяются пробелом.
Пример входного файла
e2 e3 0 8 1 2 1 1
Пример выходного файла
5 e2 d2 d1 e1 e2 e3
|
[Иванушка и царевна
]
|
|
Сложность: 3+
|
Царевна стоит в центре болота и громко плачет. Злой Кощей привязал ее к
столбу веревкой так, что веревка обмоталась вокруг царевны ровно I раз по
часовой стрелке. Иванушка хочет освободить царевну и взять ее в жены.
Проблема заключается в том, что плавать в болоте невозможно и ему
приходится прыгать по кочкам. При каждом таком прыжке за ноги Иванушки
зацепляется определенное количество зеленых водорослей.
Будем считать, что поверхность болота ровная, а веревка достаточно
длинная и не может ни за что зацепиться либо запутаться. Иванушка должен,
держа в руках конец этой веревки, проскакать по кочкам так, чтобы размотать
царевну и вернуться на начальную кочку. Так как царевна очень изнежена, то
она ни в какой момент времени не должна быть обмотана веревкой более десяти
раз (иначе веревка поранит царевну).
Требуется определить такой маршрут движения Иванушки, при котором за
его ноги зацепится минимально возможное количество водорослей.
Входные данные
Первая строка входного файла содержит три целых числа: N – количество
кочек в болоте (3 ≤ N ≤ 10), I – количество оборотов веревки (1 ≤ I ≤ 6) и S – номер
кочки, на которой в начальный момент стоит Иванушка
(1 ≤ S ≤ N). Каждая из
следующих N строк содержит вещественные координаты одной из кочек,
записанные через пробел. Известно, что никакой отрезок, соединяющий две
кочки, не проходит через центр болота, имеющий по соглашению координаты
(0, 0).
В следующих N строках записана матрица N × N, составленная из
вещественных чисел. Число в i-й строке и j-м столбце этой матрицы означает
количество водорослей, цепляющихся за ноги Иванушки при прыжке с i-й
кочки на j-ю.
Выходные данные
В первую строку выходного файла выведите минимально возможное
количество водорослей, которые зацепятся за ноги Иванушки, с точностью до
двух знаков после десятичной точки. Во вторую строку запишите
соответствующий маршрут Иванушки, заданный номерами кочек, по которым
он должен проскакать. Номера кочек разделяются пробелом.
Пример входного файла
3 1 1
-1 0
0 1
1 -2
0 1 1
1 0 1
1 1 0
Пример выходного файла
3.00
1 3 2 1
Задача
102893
(#10)
[Выгодней некуда
]
|
|
Сложность: 3
|
В стране N городов, в каждом из которых есть аэропорт. Авиакомпания,
занимающаяся перевозкой грузов, имеет самолет и желает максимально
выгодно его использовать. Для некоторых пар городов (A, B) известны время
перелета из A в B и сумма выручки за доставку груза из A в
B. Напишите программу, которая по этим данным находит для самолета замкнутый путь,
максимизирующий среднюю выручку за единицу времени.
Считается, что самолет может вместить не более одного груза, а временем
стоянки самолета в аэропорту следует пренебречь.
Входные данные
В первой строке входного файла содержится число городов N
(1 ≤ N ≤ 100) и число возможных прямых рейсов M. В каждой из следующих M строк записана
четверка чисел (i, j, bij, cij), описывающая возможный рейс между городами i и j
со временем перелета bij
и выручкой cij
. Время перелета и выручка – положительные вещественные числа.
Выходные данные
В первой строке выходного файла должна содержаться максимальная средняя
выручка за единицу времени, а во второй – замкнутый маршрут, заданный
номерами своих вершин в порядке следования, на котором эта максимальная
выручка достигается. Первая и последняя вершины маршрута должны
совпадать. Входные данные будут таковы, что решение заведомо будет
существовать.
Пример входного файла
3 3
1 2 1.0 2.0
2 3 1.0 2.0
3 1 2.0 1.0
Пример выходного файла
1.25
1 2 3 1
Страница:
<< 1 2
3 4 >> [Всего задач: 17]
Информатика
>>
Книги, журналы
>>
Беров В., Лапунов А., Матюхин В., Пономарев А., Особенности национальных задач по информатике
>>
глава 3. Алгоритмы на графах
Решение 
