Pishty and birthday
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
A little boy Pishty lives in Khust - an ancient town in the best country of the world - Uzhlyandia (also Khust is a wonderful town with their own castle and smart bears, but this is not relevant for us). And he is celebrating his birthday today!
Citizens of Uzhlyandia love two things : cakes and goulash , but Pishty prefer cakes. So his friend Lotsy decided to buy N cakes, because a friend's birthday must be the best day of his life!
A cake can be thought of as a 4 × 4 square matrix, and in each cell of the matrix no more than 1 candle can be placed.
The two boys like to play a game, in which they extinguish candles.
They play in turns, with the birthday boy Pishty taking the first turn. In each turn, one of the boys picks a cake with burning candles on it, chooses a rectangle (ie. a submatrix ) which has burning candles in all its cells, and extinguishes all those candles. If a boy can't make a move, he loses. You should assume that they play optimally. No one likes to lose a game, even to their best friend!
Because Pishty and Lotsy are best friends, Lotsy wants to buy the best collection of cakes, and so he has M queries to make to the Chef. There are 2 types of queries :
- to find the winner in the game if it is played with only the cakes in the range [L; R]
- to change a matrix, denoting a cake at some position
The first line contains one integer T , denoting the number of test cases. Then T test case descriptions follow.
The first line of the each description contains two integers N and M, denoting the number of cakes and the number of queries respectively.
The following 5 × N lines contain information about the N cake-denoting matrices (four lines of strings of four chars (without spaces), followed by an empty line). An element of a matrix equals 1 if there is a burning candle and 0 if there isn't anything.
Then the queries follow in one of the following formats:
- 1 L R - to find the winner in the game where only the caked in the range [L; R] are used.
- 2 pos matrix - to change the cake-denoting matrix at position pos to matrix
Here, 2 pos will be on the first line and matrix will be described in the next four lines. each of which will be a string of four chars, without spaces in between. There will be no empty line after these four lines.
For each query of first type output a single line containing a string "Pishty", if Pishty will win, or "Lotsy" otherwise.
- 1 ≤ T ≤ 5
- 1 ≤ N, M ≤ 105
- 1 ≤ L ≤ R ≤ N
- 1 ≤ pos ≤ N
Subtask 1 : 20 points
- 1 ≤ N, M ≤ 10
Subtask 2: 30 points
- 1 ≤ N, M ≤ 1000
Subtask 3 : 50 points
- 1 ≤ N, M ≤ 105
Input: 1 3 6 0110 0000 0000 0001 0000 0000 0000 0000 1000 1000 0000 0000 1 1 1 1 2 2 1 3 3 1 1 3 2 2 0001 0010 0100 1000 1 1 3 Output: Pishty Lotsy Pishty Pishty Pishty
|Tags||fekete, game-theory, march17, medium, segment-tree, sprague-grundy|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.