Информатика
>>
Книги, журналы
>>
Беров В., Лапунов А., Матюхин В., Пономарев А., Особенности национальных задач по информатике
-
глава 1. Динамическое программирование
(14 задач)
глава 2. Перебор с возвратом
(10 задач)
глава 3. Алгоритмы на графах
(17 задач)
глава 4. Вычислительная геометрия
(12 задач)
глава 5. Комбинаторные алгоритмы
(3 задачи)
глава 6. Задачи на разные темы
(12 задач)
Фильтр
Задачи
Задача 102889[Хамелеон ] |
|
|
| Х | А | М |
| Е | Л | Е |
| О | Н |
Напишите программу, которая определяет план достижения цели за
минимально возможное число ходов, либо сообщает, что цели достичь нельзя.
Входные данные
Во входном файле находится матрица
3 × 3, составленная из больших букв русского алфавита.
Выходные данные
Ваша программа должна вывести в первую строку выходного файла искомое
число ходов, а в последующие – их список. Каждый ход задается
координатами той фишки, которая перемещается. Если плана не существует,
выведите в выходной файл сообщение «Нет решения».
Пример входного файла
ХАМ
Е Е
ОЛН
Пример выходного файла
2
3 2
3 3
|
|
Решение |
Задача 102891[Катаем кубик ] |
|
|
Требуется найти такой путь движения кубика между двумя заданными
полями доски, при котором вычисленная сумма будет минимальной. Числа,
стоящие в основании кубика в начальной и конечной позициях, также входят в
сумму.
Входные данные
Во входном файле через пробел записаны координаты начального и конечного
полей и 6 чисел, написанных на передней (в начальный момент), задней,
верхней, правой, нижней и левой гранях кубика соответственно. Координаты
полей указываются в стандартной шахматной нотации (см. пример). Начальное
и конечное поля различны.
Выходные данные
Выведите в выходной файл минимально возможную сумму и соответствующий
ей путь. Путь должен быть задан последовательным перечислением координат
полей, по которым движется кубик (включая начальное и конечное поля).
Координаты полей записываются в том же формате, что и во входных данных, и
разделяются пробелом.
Пример входного файла
e2 e3 0 8 1 2 1 1
Пример выходного файла
5 e2 d2 d1 e1 e2 e3
|
|
|
Решение |
Задача 102892[Иванушка и царевна ] |
|
|
Будем считать, что поверхность болота ровная, а веревка достаточно длинная и не может ни за что зацепиться либо запутаться. Иванушка должен, держа в руках конец этой веревки, проскакать по кочкам так, чтобы размотать царевну и вернуться на начальную кочку. Так как царевна очень изнежена, то она ни в какой момент времени не должна быть обмотана веревкой более десяти раз (иначе веревка поранит царевну).
Требуется определить такой маршрут движения Иванушки, при котором за
его ноги зацепится минимально возможное количество водорослей.
Входные данные
Первая строка входного файла содержит три целых числа: 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
|
|
|
Решение |
Задача 102897[Покрытие путями ] |
|
|
Входные данные
В первой строке входного файла записано количество вершин графа N (1 ≤ N ≤ 25). Далее перечислены ребра графа, заданные номерами начальной и конечной вершин.
Выходные данные
Выведите в первую строку выходного файла число K – наименьшее количество путей, которыми можно покрыть все вершины графа. Далее выведите сами эти пути (по одному в каждой строке), задавая их номерами вершин в порядке посещения.
Пример входного файла
4
1 2
1 3
2 3
2 4
Пример выходного файла
2
1 2 4
3
|
|
|
Решение |
Задача 102900[Сопротивление ] |
|
|
Пояснения для тех, кто плохо учил в школе физику:
1. Сила тока равна напряжению, поделенному на сопротивление: I = U
/
R.
2. Сумма токов, втекающих в узел, равна сумме токов, вытекающих из него.
3. Сумма падений напряжений I · R на отдельных участках произвольного
замкнутого контура равна сумме всех ЭДС в этом контуре.
Как следствие, получаем следующие формулы:
1. При последовательном соединении резисторов с сопротивлениями R1
и R2 общее сопротивление R вычисляется по формуле R = R1
+
R2;
2. При параллельном соединении резисторов с сопротивлениями R1
и R2
общее сопротивление R вычисляется по формуле 1
/
R = 1
/
R1
+
1
/
R2.
Входные данные
В первой строке входного файла содержится целое число N – количество
резисторов в схеме (1 ≤ N ≤ 50). Во второй строке записаны номера узлов A и B
(узлы нумеруются начиная с 1). Каждая из следующих N строк содержит
описание очередного резистора в виде тройки целых чисел из диапазона
[0, 32767], записанных через пробел. Первые два числа задают номера двух
различных узлов схемы, которые этот резистор соединяет, а третье – его
сопротивление. Между двумя узлами схемы могут располагаться несколько
резисторов.
Выходные данные
Выведите в выходной файл искомое сопротивление не менее чем с 6 верными
значащими цифрами.
Пример входного файла
4
1 2
1 3 1
3 4 1
4 3 1
2 4 1
Пример выходного файла
2.50
|
|
|
Решение |
Страница: << 4 5 6 7 8 9 10 >> [Всего задач: 67]
