2nd Central European Olympiad in Informatics

Day 2 - Problem C Measuring Glasses

Breadth First Search Problem

We are given three glasses. The volume of each glass is 100 unit(cm³). The first two glasses have marks, same on both glasses, each mark indicating the volume measured from the bottom up to the mark. That volume is written beside the mark. Initially the first glass contains 100 unit volume of fluid, and the others are empty. Write a program that decides whether one unit volume of fluid can be separated in the third glass, and if so, computes the minimal number of steps needed to do it. In each step, after the operation at least one of the used glass must contain fluid up to a mark or empty. During the procedure we can keep track of the actual contents of each three glasses.

Input Data

The first line of the input text file contains N, the number of the marks on the first two glasses (1<=N<=20). The rest of the file contains N integers in increasing order; that is the volumes corresponding to the marks on the glasses. For each volume mark V the inequalities (1<=V<=100) hold and the largest value is 100.

Output Data

Write the string "YES" into the first line of the output textfile if one unit can be separated in the third glass and write "NO" otherwise. If the answer is yes for the first question then write the minimal number of steps in the second line.

Example input:

4
13 37 71 100

Example output:

YES
8

Solution (Yogy Namara) :

A state is defined as two integers v1 and v3. v1 is the volume of liquid in the 1st glass. v3 is the volume of liquid in the 3rd glass. We can calculate the volume of liquid in the 2nd glass with the equation :

   v1+v2+v3=100  =>  v2=100-v1-v3

The program will run a little faster if we use a queue. Fortunately, it's fast enough without one.

yogy-n@sby.mega.net.id