Internet Problem Solving Contest

IPSC 1999

Problem C – Coins

Mary, a friend of little John, is going to have a birthday party. John would like to give her a present, so he opened his money-box and found there some coins. In Tralaland they have coins of values 1, 2, 5, 10, 20, 50, 100, 200, 500 and 1000 TD (Tralaland dollar). He decided to buy a very nice doll in a nearby shop. He wants to pay the exact price (without change) and he wants to use the smallest possible number of his coins.

John has a pocket computer and he found there a program solving his problem. The program reads 10 integers C1, C2, ..., C10 corresponding to the numbers of John's coins of values 1, 2, ..., 1000 TD followed by an integer V representing the price of the doll. Then the program performs some computation and outputs the number of coins necessary to pay the exact price V or the number -1 if it is impossible.

After some playing with the program John realized that it probably does not work correctly. Could you help him and find a counterexample?

Input file description

The input file contains a program from John's pocket computer. The program is given in both Pascal and C++ languages (you may assume that the programs are equivalent). The program reads input data from the standard input and writes output data to the standard output. You may assume that the algorithm used in the program is incorrect. However, the program itself does not contain syntax errors and it is a correct implementation of this (incorrect) algorithm.

Output file description

You should find integers C1, C2, ..., C10 and V such that the program given in the input file produces a wrong answer for these data. Your counterexample should satisfy following restrictions: for every i (1<=i<=10) 0<=Ci<=100 and 1<=V<=2000.

Write numbers C1, C2, ..., C10 and V to the output file delimited by whitespace.


Input file
program wrong;

#include <stdio.h>
void main(void)
Output file
1 0 0 0 0 0 0 0 0 0 1