Codeforces Round 171 (Div. 2) |
---|
Закончено |
Вам задана последовательность положительных целых чисел a1, a2, ..., an. Все числа в последовательности различны. Зафиксируем набор переменных b1, b2, ..., bm. Изначально в каждой переменной bi (1 ≤ i ≤ m) хранится значение нуль. Рассмотрим следующую последовательность, состоящую из n операций.
Первая операция состоит в том, чтобы присвоить какой-то переменной bx (1 ≤ x ≤ m) значение, равное a1. Каждая из следующих n - 1 операций состоит в том, чтобы присвоить какой-то переменной by значение, равное сумме значений, хранящихся в переменных bi и bj (1 ≤ i, j, y ≤ m). При этом значение, которое присваивается на t-ой операции, должно быть равно at. Для каждой операции числа y, i, j выбираются заново.
Вам требуется найти минимальное количество переменных m такое, что с помощью этих переменных можно произвести описанную последовательность операций.
В первой строке записано целое число n (1 ≤ n ≤ 23). Во второй строке через пробел записаны n целых чисел a1, a2, ..., an (1 ≤ ak ≤ 109).
Гарантируется, что все числа в последовательности различны.
В единственной строке выведите целое число — минимальное количество переменных m такое, что с помощью этих переменных можно произвести описанную последовательность операций.
Если ни при каком значении m выполнить последовательность операций нельзя, выведите -1.
5
1 2 3 6 8
2
3
3 6 5
-1
6
2 4 8 6 10 18
3
В первом примере можно при помощи двух переменных b1 и b2 произвести следующую последовательность операций.
Название |
---|