3390 - Game of Stones II 3390 - Jugando con Piedras II 3390 - Game of Stones II

Statistics Sub: 164 | AC: 35 | AC%: 21,34 | Score: 2,90
Created by Torneo Argentino de Programación ACM-ICPC 2015 - Pablo Blanc
Added by fidels (2015-10-12)
Limits
Total Time: 20000 MS | Test Time: 1000 MS |Memory: 256 MB | Output: 64 MB | Size: 16 KB
Enabled languages
Available in

Description

Jaimito didn't waste any time since he was offered his stones in 2013. He no longer spends his time playing with his mother Jimena to games in which his victory is guaranteed, for he explored many stone game variants, as every child should. He even became very good at some of these games, and took part in various championships obtaining excellent results.

For a few months now, he has been particularly interested in a game of stones called TArros con Piedras (TAP). In this game there are N jars with stones inside, and two players take turns to play. In his turn, each player should take one stone from one jar, two stones from another jar, and three stones from a third one, and so on until taking N stones from some jar, so that the player takes stones from every jar in a single turn. The game continues in this way until one of the players cannot take stones from the jars in a valid way in his turn. Said player loses the match, the other player being the winner.

For example, consider a match with N = 3 jars with one of them initially having P[1] = 3 stones, another one having P[2] = 4 stones and the third one having P[3] = 10 stones. In this match the player who starts playing has a winning strategy, as he can take one stone from the jar originally having ten stones, two stones from the jar which had three stones, and finally three stones from the jar that initially had four stones. He would then leave the jars with P[1] = 1, P[2] = 1 and P[3] = 9 stones, so that the second player cannot take stones from the jars in a valid way.

Jaimito is taking part in a TAP championship, and he has reached the finals, where he will face Jacinta. Both of them are expert players, so they make no mistakes when they play. Jaimito has told his mother everything about the match, i.e. the number N of jars and how many stones each of them will start with. Jimena knows Jacinta will start playing, and she would like to know if her son will win the championship, but she can't figure it out because she is too nervous to think properly. Can you help her?
Jaimito no ha perdido el tiempo desde que le regalaron las piedras en el 2013. Ya no se dedica a jugar con su madre, Jimena, a juegos en los que tiene asegurada la victoria, sino que en estos dos años ha explorado muchísimas variantes de juegos con piedras, como cualquier niño debería. Se ha vuelto muy bueno en algunos de ellos e incluso participó de diversos torneos obteniendo excelentes resultados.

Desde hace unos meses está interesado particularmente por un juego con piedras que se llama TArros con Piedras (TAP). En este juego hay N tarros con piedras adentro y participan dos jugadores que juegan alternadamente. En su turno un jugador debe sacar una piedra de un tarro, dos de otro, tres de otro y así siguiendo hasta sacar N piedras de algún tarro. De esta manera, cada jugador saca en su turno piedras de todos los tarros. El juego continúa hasta que uno de los jugadores no puede sacar las piedras de una manera válida en su turno. Dicho jugador pierde la partida, siendo el otro jugador el ganador.

Por ejemplo, una partida con N = 3 tarros puede comenzar teniendo uno de ellos P1 = 3 piedras, otro P2 = 4 piedras y el tercero P3 = 10 piedras. En tal partida el jugador que comienza dispone de una estrategia ganadora, ya que puede retirar una piedra del tarro que originalmente tenía diez, dos piedras del que tenía tres y, finalmente, tres piedras del que tenía cuatro. Deja de este modo a los tarros con P1 = 1, P2 = 1 y P3 = 9 piedras, por lo que el segundo jugador no puede sacar piedras de una manera válida.

Jaimito está participando de un torneo de TAP y ha llegado a la final, en la que va a enfrentar a Jacinta. Ambos son jugadores expertos y no cometen errores al jugar. Jaimito le contó a su madre cómo va a ser la partida, es decir la cantidad N de tarros que va a haber y cuántas piedras tendrán cada uno. Jimena sabe que Jacinta comenzará la partida y quiere saber si su hijo ganará el torneo, pero no logra determinarlo porque los nervios no le permiten pensar correctamente, está razonando fuera del recipiente. ¿Pueden ayudarla?
Jaimito didn't waste any time since he was offered his stones in 2013. He no longer spends his time playing with his mother Jimena to games in which his victory is guaranteed, for he explored many stone game variants, as every child should. He even became very good at some of these games, and took part in various championships obtaining excellent results.

For a few months now, he has been particularly interested in a game of stones called TArros con Piedras (TAP). In this game there are N jars with stones inside, and two players take turns to play. In his turn, each player should take one stone from one jar, two stones from another jar, and three stones from a third one, and so on until taking N stones from some jar, so that the player takes stones from every jar in a single turn. The game continues in this way until one of the players cannot take stones from the jars in a valid way in his turn. Said player loses the match, the other player being the winner.

For example, consider a match with N = 3 jars with one of them initially having P[1] = 3 stones, another one having P[2] = 4 stones and the third one having P[3] = 10 stones. In this match the player who starts playing has a winning strategy, as he can take one stone from the jar originally having ten stones, two stones from the jar which had three stones, and finally three stones from the jar that initially had four stones. He would then leave the jars with P[1] = 1, P[2] = 1 and P[3] = 9 stones, so that the second player cannot take stones from the jars in a valid way.

Jaimito is taking part in a TAP championship, and he has reached the finals, where he will face Jacinta. Both of them are expert players, so they make no mistakes when they play. Jaimito has told his mother everything about the match, i.e. the number N of jars and how many stones each of them will start with. Jimena knows Jacinta will start playing, and she would like to know if her son will win the championship, but she can't figure it out because she is too nervous to think properly. Can you help her?

Input specification

The first line contains an integer N representing the number of jars in the match (1 <= N <= 10^5). The second line contains N integers P[i] representing the number of stones in each jar before starting the match (1 <= P[i] <= 10^9 for i = 1, 2, ..., N).
La primera línea contiene un entero N que representa la cantidad de tarros en el juego (1 <= N <= 10^5). La segunda línea contiene N enteros Pi que representan la cantidad de piedras en cada tarro antes de comenzar la partida (1 <= Pi <= 10^9 para i = 1, 2, ..., N).
The first line contains an integer N representing the number of jars in the match (1 <= N <= 10^5). The second line contains N integers P[i] representing the number of stones in each jar before starting the match (1 <= P[i] <= 10^9 for i = 1, 2, ..., N).

Output specification

Print a line containing a charactner indicating if Jaimito will win the finals or not. The printed character should be an 'S' if Jaimito is to win, otherwise it should be an 'N'.
Imprimir en la salida una línea conteniendo un caracter que indica si Jaimito va a ganar la final o no. El caracter debe ser una 'S' si Jaimito va a ganar, y una 'N' caso contrario.
The first line contains an integer N representing the number of jars in the match (1 <= N <= 10^5). The second line contains N integers P[i] representing the number of stones in each jar before starting the match (1 <= P[i] <= 10^9 for i = 1, 2, ..., N).

Sample input

3
3 4 10

Sample output

N

Hint(s)

Sample input #2
2
10 3

Sample output #2
S
Sample input #2
2
10 3

Sample output #2
S
Sample input #2
2
10 3

Sample output #2
S

Recommendation

We have carefully selected several similar problems: 2441 | 1106 | 1399 | 1400 | 1646 | 1664