SPOJ.com - Problem COLORCAT

COLORCAT - Magical colorful cats (easy)

no tags

There is a circle with n cats, includes white cats, red cats and green cats. When two cats with different color talk with each other, they both change to third color. If they are same color, nothing will happen.

At each step, the 1^st cat talks with 2^nd cat, the 2^nd cat talks with the 3^rd cat,… and the n^th cat talks with 1^st cat.

Given the original color of n cats, your task is find the color of n cats after k steps.

Input :

- First line : n and k (1 ≤ n ≤ 20000, 1 ≤ k ≤ 30000)

- Second line : n characters, the i-th charater denotes color of the i-th cat at first state

Output :

- n characters denotes the color of n cats after k steps.

Sample :

Input :

3 1

GRR

Output :

RGR

Input :

5 4

WRWRW

Output :

GGGWG

Note : After solved this problem, you may want to try BLCATS

Submit solution!

hide comments



	monish007: 2015-08-02 12:05:14 ANY HINT PLEASE
	Kata: 2015-01-29 11:38:50 At the time I publish this problem, my brute force solution couldn't pass in 1s, but my optimized solution could pass (also in 0.3s), so I set time limit to 1s. But some day after, I found that only a little optimizations make it pass in 1s, so I changed it. It's my fault that I didn't notice it any more. I agree with Min_25. Time limit set back to 1s. Thanks your helps. Last edit: 2015-01-29 11:41:03
	Min_25: 2015-01-29 10:39:21 As far as I remember, the time limit of this problem has been changed twice; 1.00 -> 0.50 -> 0.30s. And there were 3 solvers for this problem. I think the time limit should be set back to 1.00s. Last edit: 2015-01-29 10:40:13
	Kata: 2015-01-29 05:40:31 I have changed the time limit after publish the problem some days and leave a comment, but it was deleted (?). Because it's a old problem, I didn't notice it. Sorry. p/s : The new time limit is decided based on the idea of original problem.
	Mitch Schwartz: 2015-01-29 05:09:44 Why was time limit changed so that Robert Gerbicz no longer gets AC? That doesn't seem fair. Edit: Thanks for that info. I can't say I'm entirely satisfied with all of that, but I would like to be constructive. Please consider: (1) Whether you accidentally set the time limit too tightly. (2) Creating tutorial version of the problem with relaxed time limit, which could help people test. (3) Take screenshots of important comments to your problems so you have a backup in case they get lost, and/or add a short note to the bottom of the problem description whenever an important change is made. (4) Be very reluctant to change problems after publication, out of respect for solvers. A better option in many cases would be to move the original problem to tutorial and create a new version for classical. And of course, try to publish very carefully to avoid issues in the first place. (5) Time limits are generally chosen according to problem setter's solution at time of publication. It's possible that after publication, there are some very fast submissions that used ideas the problem setter never thought of. That sort of situation is generally not good justification for lowering time limit, in my view. It can cause various issues, which may or may not be obvious, and I can go into that later if it seems useful / applicable. Thanks. Last edit: 2015-01-29 08:59:29
	Kata: 2015-01-29 03:08:06 No, but it need some special optimizations.
	Ivan Katanic: 2015-01-27 18:03:35 Time limit seems very tight..is O(nlog(n)log(k)) supposed to pass? Last edit: 2015-01-27 18:03:53

Submit solution!

Added by:	Kata
Date:	2014-03-13
Time limit:	1s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	VNOI