АВТ ВоГУ - Задача 1553. Электрическая цепь

Идеальная девушка — девушка, сопротивлением которой при данных условиях можно пренебречь

физический фольклор

У Васи есть N резисторов и неограниченное количество проводов. Он хочет собрать электрическую цепь с сопротивлением, как можно более близким к R. Вася умеет соединять две цепи параллельно или последовательно. Сопротивлением проводов можно пренебречь.

Электрические цепи и их сопротивления определяются следующим образом:

Один резистор является электрической цепью; сопротивление такой цепи равно сопротивлению этого резистора.
Если A и B — две электрические цепи, а R_A и R_B — их сопротивления, то, соединив A и B последовательно, мы получим новую электрическую цепь C, а её сопротивление будет равно R_C=R_A+R_B.
Если A и B — две электрические цепи, а R_A и R_B — их сопротивления, то, соединив A и B параллельно, мы получим новую электрическую цепь C, а её сопротивление будет удовлетворять соотношению $\text{[math]}$ .

Например, если у Васи есть два резистора, 1 Oм и 2 Oма, то он может собрать цепи с сопротивлениями $\text{[math]}$ , 1, 2 и 3 Oма соответственно:

$\text{[math]}$

Отметим, что в цепи должен быть хотя бы один резистор.

Входные данные

В первой строке входного файла заданы через пробел три числа N, a и b (1<=N<=5, $\text{[math]}$ , 1<=b<=100, 0<=R<=R₁+R₂+...+R_N, a и b взаимно просты). Вторая строка содержит N целых положительных чисел R_i — сопротивления резисторов (1<=R_i<=100).

Выходные данные

Выведите |R-R_opt| — дробь в сокращённом виде (числитель и знаменатель дроби — взаимно простые неотрицательные целые числа). Здесь R — заданное во входном файле сопротивление, а R_opt — сопротивление цепи, которую может собрать Вася. Гарантируется, что числитель и знаменатель дроби не превосходят 2⁶³-1.

Примеры

Входные данные

2 2 3
1 2

Выходные данные

2/3

Входные данные

2 3 2
1 2

Выходные данные

1/1

Дистанционный практикум по программированию

1553. Электрическая цепь