Версия для печати
Убрать все задачи
Имеются три пробирки, вместимостью 100 миллилитров каждая. Первые две
пробирки имеют риски, одинаковые на обеих пробирках. Возле каждой риски
надписано целое число миллилитров, которое вмещается в часть пробирки от
дна до этой риски (см. рисунок).
Изначально первая пробирка содержит 100 миллилитров пива, а остальные
две пусты. Требуется написать программу, которая выясняет, можно ли
отделить в третьей пробирке один миллилитр пива, и если да, то находит
минимально необходимое для этого число переливаний. Пиво можно
переливать из одной пробирки в другую до тех пор, пока либо первая из них не
станет пустой, либо одна из пробирок не окажется заполненной до какой-либо
риски.
Входные данные
В первой строке входного файла содержится число рисок N (1 ≤ N ≤ 20),
имеющихся на каждой из первых двух пробирок. Затем в порядке возрастания
следуют N целых чисел V1
, ..., VN (1 ≤ Vi ≤ 100), приписанных рискам. Последняя
риска считается сделанной на верхнем крае пробирок
(VN
= 100).
Выходные данные
В первой строке выходного файла должна содержаться строка «YES», если в
третьей пробирке возможно отделить один миллилитр пива, и «NO» – в
противном случае. В случае ответа «YES» во вторую строку необходимо
вывести искомое количество переливаний.
Пример входного файла
4
13 37 71 100
Пример выходного файла
YES
8
Решение
Найдите наибольшее значение выражения
x
+
y
.
Решение
Пусть P = (p
1, ... , P
n
) является перестановкой чисел 1, 2, ..., n. Таблицей инверсии
перестановки P называют последовательность T = (t
1, ...,
t
n), в которой t
i равно числу элементов перестановки Р,
стоящих (в Р) левее числа i и больших i. Например, для перестановки Р = ( 5,
9,1, 8, 2, 6, 4, 7, 3 ) чисел 1, ... , 2, ... , 9 таблица инверсий Т = ( 2, 3,
6, 4, 0, 2, 2, 1, 0 ). Написать программу, которая по заданной таблице инверсии
восстанавливает перестановку.
Решение
Фильтр
