Waterloo 2023 Fall D - Reptilian Communism

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 256M

Problem types

There are three types of chameleons inhabiting New Waterloo Island - red, green, and blue. When two chameleons of different colors meet, they both change their color to the third color and breed k new chameleons of that color. For example, when red and blue chameleons meet, they both become green as a result of this encounter and k new green chameleons appear. When two chameleons of the same color meet, nothing happens. When every single chameleon on the island becomes red, the communist revolution will happen on the island. Your task is to determine whether there exists a sequence of chameleon encounters that would lead to the communist revolution, and if such a sequence exists, give an example of one.

Input Specification

The first line of input contains three integers r, g, b - the number of red, green, and blue chameleons. The second line of input contains a single integer k. 2 \le r, g, b \le 10^4, 1 \le k \le 10^4.

Output Specification

Output YES if the communist revolution can happen, and NO otherwise. If you've outputted YES, in the next line print t - the number of encounters. In the t lines that follow, print two characters separated by a space, each of those characters being one of R, G, B. The symbols R, G, B correspond to red, green, and blue chameleons, and a string R B would mean a meeting between red and blue chameleons. If there are several ways to set up these encounters, print any one of them. However, the largest allowed t is 10^5 - beyond that, communist chameleons are going to give up their cause.

Sample Input 1

3 2 2

Sample Output 1


Explanation for Sample 1

In the first test, we're setting up two encounters between green and blue chameleons. The quantities of chameleons are going to change as follows: 3,2,2 \to 7,1,1 \to 11,0,0. The revolution will happen!

Sample Input 2

17 7 4

Sample Output 2



There are no comments at the moment.