The Seventh Seal
All submissions for this problem are available.
The Seventh Seal tells you the journey of a medieval knight, “Max von Sydow” and a game of chess he plays with the personification of Death, “Bengt Ekerot” who has come to take his life.The game being played differs from the usual chess on the following basis:
(i) The game is played on an infinite chess board & there can be multiple pieces of the same type.
(ii) A single turn of a particular player could comprise of one or more moves.
(iii) More than two colours can be assigned to the pieces, not just black and white.
(iv) Both the players could have pieces(same or different type) of the same colour.
(v) A piece could capture another piece only if they are of the same colour & of the same type.
(vi) The knight is more powerful than the king.
Initially there are ‘N’ knights in the board. It is assumed that, there exists at least one knight such that it could reach the positions of all other knights in the board.This special knight could either belong to Sydow or Bengt.Sydow gets defeated, if he or Bengt loses at least one knight. He doesn’t want this to happen.
To safeguard him from losing, Sydow is given a chance to assign a colour to all the pieces in the board. He is given with ‘K’ colour boxes to paint the pieces,before the start of the game. Your task is to find the number of possible ways of assigning the colours to the pieces in the board such that Sydow wins with such arrangement.Print the answer modulo (10^9 + 7).
The first line consists of an integer ‘T’, the number of test cases.’T’ test cases follow:
Each of the test cases consists of a single line containing three integers N,K and C.
C is 0 if Sydow starts the game and 1 if Bengt starts the game.
For each test case, print the number of ways in a single line.Print "0" if Sydow could not win the game with any arrangement.(Quotes for clarity)
2 2 1
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, 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, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.