Решения следует отправить до 0 часов 28 декабря 2009 г.
Чат-консультации
//www.vinnica.ua/netoi
9.12.09 з 18-00 до 18-30
16.12.09 з 18-00 до 18-30
Задача Queen
На обобщенной шахматной доске (размерами не обязательно 8×8)стоит ферзь. Известно, на какой клетке он находится сейчас и в какую клетку ему необходимо добраться. Задача усложняется тем, что некоторые клетки заняты фигурами соперника, но упрощается тем, что сейчас они крепко спят, так что ферзь может
тихонько сделать сколько угодно ходов подряд. Ни перепрыгивать через фигуры соперника, ни бить их нельзя (ибо тогда они проснутся). Напишите программу, определяющую минимальное количество ходов,
необходимых ферзю для такого перемещения.
Технические условия. Программа читает с клавиатуры размеры шахматной доски — сначала количество вертикалей w (2 ≤ w ≤ 26), затем количество горизонталей h (2 ≤ h ≤ 99), затем координаты стартовой и финишной клеток, затем количество фигур соперника К (0 ≤ K ≤ w×h–2),
далее K пар чисел – координаты очередной фигуры соперника. Все числа разделяются пробелом. Координаты всех клеток – натуральные числа, не превосходящие w та h соответственно. Сначала вводится вертикаль, потом горизонталь. Клетки, указанные как начальная и конечная, не содержат
фигур соперника; разные фигуры не могут находиться в одной и той же клетке. Программа должна вывести на экран единственное целое число — либо минимальное количество ходов, необходимых, чтобы дойти от указанной начальной клетки до указанной конечной, либо -1, если дойти невозможно
Примеры
Ввод
8 8 5 2 5 4 1 5 3
Вывод 2
Ввод
20 20 1 20 3 3 3 1 19 2 19 2 20
Вывод-1
Задача Beads
Ожерелье состоит из бусинок 4-х цветов. Владелица решила оставить только 3 цвета. Какое минимальное количество бусинок нужно для этого снять с нитки, если разрез на ней можно сделать только один, а бусинки снимать только подряд, возвращать бусинки назад нельзя, а после разреза нитку связывают.
Технические условия. Программа Beads читает с клавиатуры число бусинок N (4≤N≤5000), а далее в той же строке N чисел через пробел, обозначающих цвет бусинок (1 – желтый, 2-синий, 3- красный, 4-зеленый). Программа выводит на экран единственное число – минимальное количество снятых бусинок.
|
Пример
|
|
Ввод
10 1 2 4 2 3 1 3 4 3 4
Вывод 3
|
Задача Smarand
Значением S(k) функции Смарандаша является такое наименьшее число m, що m! делится на k нацело. Например, S(9) = 6 потому, что число 6! = 720 делится на 9, а никакой меньший факториал на 9 не делится. Напишите программу, вычисляющую функцию Смарандаша.
Технические условия. Программа Smarand читает с клавиатуры натуральное число k (1≤ k ≤109). Программа выводит на экран значение функции Смарандаша для этого числа.
Пример
Ввод
9
Вывод
6
Задача Palindrom2
Дано натуральное число n. Найдите минимальное число-палиндром, большее n. Палиндром – это число, которое читается слева направо так же, как справа налево.
Технические условия. Программа читает с клавиатуры натуральное число n (1<=n<1018). Программа выводит на экран искомый палиндром.
Пример
Ввод
131
Вывод
141
Задача Word2
Во время урока информатики два ученика, не слушая пояснений учителя, играют в такую игру. Каждый из них в своей тетради записывает два выбранных ими вместеслова и пытается за определенное количество ходов из первого слова получить второе. Выигрывает тот, кто сделает минимальное количество ходов.
Ход – это одна из таких операций:
1.заменить какой-то символ из первого слова каким-то символом второго слова;
2. вычеркнуть какой-либо символ из первого слова;
3. Вставить какой-нибудь символ из второго слова после либо перед каким-нибудь символом первого слова. Например, для преобразования слова “limuzin” в слово “buzina” необходимо выполнить такие действия:
|
Преобразование
|
Номер операции
|
|
limuzin
imuzin
ibuzin
ibuzina
|
Þ
Þ
Þ
Þ
|
imuzin
ibuzin
ibuzina
buzina
|
2
1
3
2
|
Попробуйте написать программу, которая находит минимальное количество ходов для преобразования одного заданного слова в другое.
Технические условия. Программа читает с клавиатуры две строчки длиной не более 104 символов каждая и выводит на экран единственное число – минимальное количество ходов.
|
Пример
|
Ввод
|
Вывод
|
|
|
limuzin
buzina
|
4
|
Задание подготовили А.Коротков, Г.Непомнящий, И. Порубльов, Ю.Пасихов
|
