Помощничек
Главная | Обратная связь


Археология
Архитектура
Астрономия
Аудит
Биология
Ботаника
Бухгалтерский учёт
Войное дело
Генетика
География
Геология
Дизайн
Искусство
История
Кино
Кулинария
Культура
Литература
Математика
Медицина
Металлургия
Мифология
Музыка
Психология
Религия
Спорт
Строительство
Техника
Транспорт
Туризм
Усадьба
Физика
Фотография
Химия
Экология
Электричество
Электроника
Энергетика

Ограничение времени 1 секунда



Входной файл input.txt

Выходной файл output.txt

Ограничение по времени 1 секунда на тест

Ограничение по памяти 16 мегабайт

 

За наименьшее число ходов провести шахматного коня из заданного начального пункта в заданный конечный пункт.

Вход

В первой строке текстового файла INPUT.TXT записан начальный пункт в шахматной нотации, во второй строке - конечный пункт в шахматной нотации.

Выход

В текстовый файл OUTPUT.TXT записать наименьшее число ходов, за которое конь может переместиться из начального пункта в конечный пункт.

Примеры входа и выхода

INPUT.TXT OUTPUT.TXT
a1 h3 5
d6 d5 3
c1 c8 5
a8 h1 6
d3 d3 0

 


Задача 2. "Три сосуда"(Областная олимпиада школьников 1997. Задача B)

Входной файл input.txt

Выходной файл output.txt

Ограничение по времени 1 секунда на тест

Ограничение по памяти 16 мегабайт

 

В трех сосудах, ёмкости которых известны, находится некоторое количество жидкости. Требуется за наименьшее количество переливаний отмерить заданное количество жидкости (в любом из трех сосудов). Правило переливания: из сосуда А в сосуд Б переливаем до тех пор, пока не опустеет сосуд А или не заполнится сосуд Б.

Вход

В файле INPUT.TXT содержится 7 целых положительных чисел: емкость 1-го сосуда, емкость 2-го сосуда, емкость 3-го сосуда, количество жидкости в 1-м сосуде, количество жидкости во 2-м сосуде, количество жидкости в 3-м сосуде и заданное количество жидкости, которое необходимо отмерить, разделенные пробелами и, может быть, символами конца строки. Все числа не превосходят 100.

Выход

В файл OUTPUT.TXT необходимо записать минимальное количество переливаний. Если решения не найдено, записать в файл фразу "no solution".

Примеры входа и выхода

INPUT.TXT OUTPUT.TXT
7 5 3 4 4 1 4 0
7 5 3 4 4 1 5 1
17 46 93 11 35 20 40 2
73 61 59 47 38 44 17 no solution
73 61 59 47 38 44 55 9

 

Задача 3. "Изношенный механизм"(BSU Programming Contest 2004, 2004)

Входной файл REMOTE.IN

Выходной файл REMOTE.OUT

Ограничение по времени 1 секунда на тест

Ограничение по памяти 16 мегабайт

Пульт управления телевизором имеет N кнопок (3 ≤ N ≤ 20) для включения одного из N принимаемых каналов. Когда пульт был новым, нажатие любой из этих кнопок автоматически приводило к отжатию остальных, так что в каждый момент времени только одна из кнопок переключения каналов была включена. К сожалению, с течением времени механизм пульта износился, и некоторые кнопки не отключаются при нажатии других кнопок. Таким образом, одновременно могут быть включены несколько каналов. Выбор нужной программы становится непростой задачей! С другой стороны, финансовые проблемы не позволяют Вам купить новый телевизор или хотя бы отремонтировать пульт... После долгих манипуляций с пультом Вы определили, какие кнопки отжимаются при нажатии кнопки с номером k (1 ≤ kN) и приноровились включать нужный канал нажатием последовательности из нескольких кнопок. Вам требуется определить минимальное количество нажатий кнопок переключения каналов, необходимых для включения канала с номером k (т.е. для перевода пульта в такое состояние, при котором кнопка k нажата, а все остальные - отжаты). Следует помнить, что повторное нажатие уже нажатой кнопки не вызывает никакого эффекта.

Входные данные находятся в текстовом файле REMOTE.IN, и содержат N+2 строки. Первая строка этого файла содержит значения N и k. Во второй строке записано текущее состояние пульта в виде последовательности из N нулей и единиц, где 1 соответствует нажатой кнопке, а 0 - отжатой. Наконец, каждая из последующих N строк содержит количество кнопок, отжимающихся при нажатии кнопки с номером k (1 ≤ kN), и их номера (нумерация кнопок начинается с единицы). Числа в строках входного файла разделяются одним или несколькими пробелами. Тесты подобраны таким образом, что задача всегда имеет хотя бы одно решение.

Выходные данные помещаются в текстовый файл REMOTE.OUT. Единственная строка этого файла содержит искомое число нажатий кнопок.

Примеры входа и выхода

REMOTE.IN REMOTE.OUT
5 3 1 1 0 0 1 4 2 3 4 5 4 1 3 4 5 2 2 4 4 1 2 3 4

Задача 4. “Фишки“(VIP-турнир 2008. А)

Вход: marbles.in

Выход: marbles.out

Ограничение памяти 64M

Ограничение времени 1 секунда

 

Игра ведётся на квадратной доске размером 3 на 3 клетки. Первоначально все клетки пусты. Есть фишки четырёх видов: синие, красные, зелёные и жёлтые. Фишки оцениваются, соответственно, в wb, wr, wg и wy очков, причём wbwrwgwy. На каждом ходе вы можете поставить фишку в одну из клеток. Если на этой клетке уже стоит фишка, её предварительно убирают, снятие фишки не считается отдельным ходом. Вы можете ставить фишки на доску сколько угодно раз (запас фишек каждого цвета неограничен), но при этом должны соблюдаться следующие правила:

1) Синюю фишку можно ставить всегда.

2) Красную фишку можно ставить, если на соседней клетке есть синяя фишка.

3) Зелёную фишку можно ставить, если на соседних клетках есть синяя и красная фишки.

4) Жёлтую фишку можно ставить, если на соседних клетках есть синяя, красная и зелёная фишки.

Соседними считаются клетки, имеющие общую сторону.

Напишите программу, вычисляющую минимальное количество ходов, после которых можно набрать не менее w очков. Количество очков равно сумме очков за все фишки, стоящие на доске.

Формат входа

Во входном файле записаны пять целых неотрицательных чисел wb, wr, wg, wy, w (1 ≤ wbwrwgwy ≤ 100, 0 ≤ w ≤ 1000).

Формат выхода

Запишите в выходной файл минимальное количество ходов. Если задача не имеет решения, запишите число -1.

 

 




Поиск по сайту:

©2015-2020 studopedya.ru Все права принадлежат авторам размещенных материалов.