Devu and most energetic minion
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
After celebrating his birthday, Devu decided to have some adventure and set himself on a secret mission by joining the AVL (Anti-Villain League) to fight against bad people. For their new secret mission, Devu wants to recruit the most energetic minion. You know how minions get energy? By eating bananas. The minions travel in a grid B that has bananas in each of its N x N cells. B[x][y] is the energy stored in a banana in row x and column y.
The journey starts from top-left cell (1, 1) and ends at bottom-right cell (N, N) by going only either right or down each step (i.e. from a cell (x, y) to either (x, y + 1) or (x + 1, y) only). Initial energy of minion is zero. When a minion with energy e enters a cell (x, y), it eats a banana and its energy becomes e ^ B[x][y], where ^ is the standard bitwise-XOR operator. There are many different ways of completing the journey. Please help the minion to find out a journey with maximum energy so that it can be recruited by Devu. Please output the maximum energy a minion can achieve in some journey(Bitwise xor operator is denoted by a caret (^) in several programming languages like C, C++, C#, Java, Perl, Ruby and Python. More about it: http://en.wikipedia.org/wiki/Exclusive_or)
- There is a single test case.
- First line contains an integer N denoting the number of rows or columns of the grid B.
- Next N lines represent the grid B, where each of these N lines contain N space separated integers. i-th line contains N space separated integers denoting i-th row of the grid B.
Print a single integer denoting maximum energy a minion can achieve at the end of a right-down path from (1, 1) to (N, N).
- 2 ≤ N ≤ 18
- 0 ≤ B[i][j] ≤ 109
Input: 3 1 3 2 3 4 3 5 3 7 Output: 4
There are 6 different possible journeys of the minion, and energy at the end of them are -- One journey -- 1 ^ 3 ^ 2 ^ 3 ^ 7 = 4 Four journeys -- 1 ^ 3 ^ 4 ^ 3 ^ 7 = 2 One journeys -- 1 ^ 3 ^ 5 ^ 3 ^ 7 = 3 So the maximum energy achieved by a minion is 4.
|Tags||cook58, flying_ant, medium-hard, tries|
|Time Limit:||2 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.