ЗАДАЧИ
problems.ru |
О проекте
|
Об авторах
|
Справочник
Каталог по темам | по источникам | |
|
Задача 102890
УсловиеИмеются три пробирки, вместимостью 100 миллилитров каждая. Первые две пробирки имеют риски, одинаковые на обеих пробирках. Возле каждой риски надписано целое число миллилитров, которое вмещается в часть пробирки от дна до этой риски (см. рисунок). Изначально первая пробирка содержит 100 миллилитров пива, а остальные две пусты. Требуется написать программу, которая выясняет, можно ли отделить в третьей пробирке один миллилитр пива, и если да, то находит минимально необходимое для этого число переливаний. Пиво можно переливать из одной пробирки в другую до тех пор, пока либо первая из них не станет пустой, либо одна из пробирок не окажется заполненной до какой-либо риски.
Решение
Скачать архив тестов и решений Построим граф, изображающий возможные состояния набора из трех пробирок и возможные переходы между ними. Состояние задается тройкой неотрицательных целых чисел (x1,x2,x3), где xi – количество пива в пробирке i и x1 + x2 + x3 = 100. Опишем теперь перечислитель вершин (x'1,x'2,x'3) графа, в которые можно перейти из вершины (x1,x2,x3) за одно переливание. Рассмотрим, для определенности, случай переливания из пробирки i в пробирку j (1 ≤ i, j ≤ 3). Пусть в результате было перелито Δ миллилитров пива, т.е. x'i = xi - Δ, x'j = xj - Δ, x'k = xk, где k = 6 - i - j. Наша задача сейчас – определить список возможных значений для Δ. Для этого обозначим через ri1, ..., ris те значения рисок пробирки i, которые меньше xi, а через rj1, ..., rjt – те значения рисок пробирки j, которые меньше xj. Ясно, что тогда Далее осталось найти кратчайший путь в построенном графе, взяв в качестве начальной вершину (x1,x2,x3 ), а в качестве конечных – вершины (x1,x2,x3 ) с x3 = 1. Источники и прецеденты использования |
© 2004-...
МЦНМО
(о копирайте)
|
Пишите нам
|
![]() |
Проект осуществляется при поддержке