ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Open Ural SU Championship 2009

About     Problems     Submit solution     Judge status     Standings
Contest is over

D. Theft of the Century

Time limit: 1.0 second
Memory limit: 64 MB
An evil-doer got into a depository where gold and platinum bars were stored and took out n sacks with bars. In each sack there were k bars and all the bars in each sack were made of the same metal. To arouse less suspicions, the criminal painted all the bars black, which made gold bars and platinum bars look the same.
Soon he found a buyer for the platinum bars. However, it turned out that the thief didn't know which bars were in which sack. Still, he kept his head and decided to find that out using a balance that could show exact weights. The thief knew that the mass of a gold bar was x kilograms and the mass of a platinum bar was y kilograms. Help the thief determine in one weighing in which sacks there are gold bars and in which sacks there are platinum bars. Tell him how many bars from each sack he should put on the balance in order to determine which sacks contain platinum bars.


The only input line contains space-separated integers n, k, x, and y (3 ≤ n ≤ 20; 1 ≤ k ≤ 106; 1 ≤ x < y ≤ 10).


If it is possible to determine in which sacks there are platinum bars in one weighing, output “YES” in the first line and output n space-separated integers in the second line. These numbers must describe how many bars from each sack should be put on the balance. If there are several solutions, output any of them. If there is no solution, output “NO” in the only line.


4 8 9 10
4 5 6 8
Problem Author: Alexander Ipatov (idea by Artyom Skrobov)
Problem Source: XIV Open USU Championship
To submit the solution for this problem go to the Problem set: 1735. Theft of the Century