Younger Brother

Problem code: CHEFBRO

All submissions for this problem are available.

Chef's younger brother is in town. He's a big football fan and has a very important match to watch tonight. But the Chef wants to watch the season finale of MasterChef which will be aired at the same time. Now they don't want to fight over it like they used to when they were little kids. They want to decide it in a fair way. So they agree to play a game to make a decision. Their favourite childhood game!

The game consists of C boards. Each board i is a grid of dimension ni x mi.

Rules of the game:

  • A coin is placed at (1,1) on every board initially.
  • Each one takes a turn alternatively.
  • In one turn, a player can choose any one board and move a coin from a cell (i,j) to one of the following cells:

    (i+1,j) OR (i+2,j) OR (i,j+1) OR (i,j+2) OR (i+1,j+1) OR (i+2,j+2).

  • A coin cannot be moved out of the board at any point during the game.
  • A coin cannot be moved once it reaches the cell (n,m) where n and m are the dimensions of the board of that coin.
  • A player MUST make one valid move.
  • The player who makes the last move gets to watch TV.

    • Both of them are passionate about their interests and want to watch their respective shows. So they will obviously make optimal moves in every turn. The Chef, being the elder brother, takes the first turn.

    Your task is to predict which show they will be watching tonight.

    Input:

    The first line of input contains a single integer T, the number of test cases. T tests follow.Each test case starts with a single line containing C, the number of boards in the game. Then follow C lines: each containing 2 integers ni and mi, the dimensions of the ith board.

    Output:

    Given the number and dimensions of boards, for each test case, output in a single line: "MasterChef" if the Chef wins or "Football" if his brother wins.

    Constraints:

    1<=T<=10000
    1<=C<=20
    2<=ni,mi<=1000

    Example:

    Input:
    1
    1
    2 2

    Output:
    MasterChef

    Explanation:

    The Chef can move the coin on the board from (1,1)->(2,2). This coin cannot be moved any further. And so, the Chef wins. Notice that if the Chef moves it to any other valid position, i.e. either to (1,2) or (2,1) he will lose!

Author: vamsi_kavala
Date Added: 25-07-2011
Time Limit: 1 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC


Comments

what if c is even and both

amriteshanand @ 1 Sep 2011 03:13 PM
what if c is even and both wins the same no.of matches?

if any coin reached the

sharky @ 1 Sep 2011 03:34 PM
if any coin reached the (ni,mi) cell of board i, is it the end of the game?

"The player who makes the

sirbu_cristina @ 1 Sep 2011 03:35 PM
"The player who makes the last move gets to watch TV" so the last who make a move win.

what is a c board like??

decrypto @ 1 Sep 2011 07:33 PM
what is a c board like??

example given is too easy to

rachit001 @ 1 Sep 2011 10:17 PM
example given is too easy to test the program... example with bigger values (atleast c=2) must be given to help...

^ There are 'C' number of

kozicode @ 1 Sep 2011 10:17 PM
^ There are 'C' number of boards.

very very weak test case...

aayush123 @ 2 Sep 2011 01:31 AM
very very weak test case... :((

this two are not meaning full

goelrinku @ 2 Sep 2011 08:01 AM
this two are not meaning full explain (i+1,j) and (i+2,j)

Whats with 'C' boards in a

karunesh1821 @ 2 Sep 2011 09:34 AM
Whats with 'C' boards in a single game? Do they play at the first board first, then go to the next board (where the loser of the previous board plays first), and so on, or is it something different?

they choose any board to make

lg5293 @ 2 Sep 2011 10:52 AM
they choose any board to make one move. If they can't move on any board, they lose.

@amriteshanand The last

lg5293 @ 2 Sep 2011 11:49 AM
@amriteshanand The last person to move wins, so you can't "win" a single board (unless c=1) @decrypto There are c boards in the game, not a c board. (i.e. if c = 3, there could be a 2x3 board, a 10x9 board and a 25x80 board) @sharky the game only ends when all pieces have reached (ni, mi) on all of their respective boards @rachit001, I hope this test case helps: given two boards of identical size, the brother will always win since he can just copy what the Chef does on the other board. (I hope this doesn't give too much away). This is a pretty trivial case, but it'll help you get thinking. @goelrinku If you have a 3x3 grid and you are at the top left corner, you can go to any square on the top side, left side, or diagonal starting from the top left to bottom right (of course, you can't stay at your original square). If you don't get the indices, I suggest you get some graph paper and draw it out.

@lg5293: how to calculate the

paramanantham @ 2 Sep 2011 12:14 PM
@lg5293: how to calculate the number of moves???

thanx... for the direction..

rachit001 @ 2 Sep 2011 12:17 PM
thanx... for the direction.. :)

@paramanantham you don't need

lg5293 @ 2 Sep 2011 12:19 PM
@paramanantham you don't need to calculate the number of moves since it's not part of the answer.You just need to calculate who will move last if they both play optimally.

@lg5293 You got it right in

kozicode @ 2 Sep 2011 12:26 PM
@lg5293 You got it right in the first go ! Nice :)

give more testcases.

abhineet08 @ 2 Sep 2011 02:56 PM
give more testcases.

Is board of size 1x1 a valid

chamanchindi @ 2 Sep 2011 03:44 PM
Is board of size 1x1 a valid board?

Sorry, didn't saw the limits

chamanchindi @ 2 Sep 2011 03:56 PM
Sorry, didn't saw the limits first time.

@admin: players play

curiosity @ 2 Sep 2011 04:48 PM
@admin: players play optimally to win the current board or current test case?

I know my algorithm is

coolnirdh @ 2 Sep 2011 10:46 PM
I know my algorithm is correct, I also know that my code is bug free. On local machine, it gives expected output, but upon submitting, it gives "Wrong Answer". I wonder, under what conditions can one get "Wrong Answer". As on the FAQs page, I ensured that everything is according to the requirements. The format of output also matches with that given in test case.

*Example

coolnirdh @ 2 Sep 2011 10:47 PM
*Example

@curiosity They play

lg5293 @ 2 Sep 2011 11:31 PM
@curiosity They play optimally to win the current test case (over all boards) @coolnirdh You get wrong answer when the output of your program doesn't match the output of the judge. If the judge says your output is wrong, it is wrong. Don't be so prideful that you refuse to correct your own algorithm when the judge is telling you it's wrong. The only verified output that you have probably tested is the given test case, which is trivial, so you need to create more cases for yourself and do them by hand to see if your program matches.

@lg5293: Your response is

coolnirdh @ 2 Sep 2011 11:46 PM
@lg5293: Your response is appreciated, but well, it isn't about being proud, and I have already followed all the things you mentioned. Took one complete day to work out 24 test cases by hand. Now isn't that more than enough? Took lot of time to debug, lot of time to understand what I overlooked. So it appealed to me that I must check the reasons for getting Wrong Answer. And then see what am I missing out. Most of the times algorithms are never an issue to me. And neither is programming, it is just that the online judge too strict, anyways, it is supposed to be like that.

Can the size of different

bknarendra @ 2 Sep 2011 11:48 PM
Can the size of different boards in the same case be different. For eg. size of 1st borad is 2X3 size of 2nd board is 6X6 size of 3rd board is 10X8

@coolnirdh, ok sorry for

lg5293 @ 3 Sep 2011 04:51 AM
@coolnirdh, ok sorry for making assumptions, but you shouldn't just assume that your program is correct. I feel like most of the time, people making those comments are just saying they pass the sample cases, and their program should pass, but they didn't see every case. My suggestion to you is to write a brute-force program to see if your strategy really is correct. Are you sure you're extending your strategy correctly to more than one board? Again, the only reason for wrong answer is that your program isn't outputting the expected output. I can't give too many hints cause this is a contest, but best of luck to you. If you decide to give up, just remember you can read the editorial after to see if you were on the right track. @bknarendra. yes.

@lg5293: Thanks for the

coolnirdh @ 3 Sep 2011 11:45 AM
@lg5293: Thanks for the suggestions, I am planning to work on this once again from a scratch :)

Well I know its the wrong

bknarendra @ 3 Sep 2011 11:51 AM
Well I know its the wrong time to ask this question but i would like to know that how can i know for which test case my problem fails may be after the contest is over

accepted.. :)))

aayush123 @ 3 Sep 2011 03:07 PM
accepted.. :)))

anyone kindly post a correct

alexmj26 @ 3 Sep 2011 05:55 PM
anyone kindly post a correct output as in the required format with an input like 2 3 4 5 5 5 2 2 2 6 8 2 3

how we have to select the

deeee @ 3 Sep 2011 09:02 PM
how we have to select the board,can anyone suggest me

@alexmj26...is your answer

rajrocks1992 @ 3 Sep 2011 09:53 PM
@alexmj26...is your answer coming... MasterChef Football ???

Can any1 gv me sum sample

rajrocks1992 @ 3 Sep 2011 09:55 PM
Can any1 gv me sum sample input and output????my program is showing Wrong answer but i cant find any error!!

My problem ID is

rajrocks1992 @ 3 Sep 2011 09:56 PM
My problem ID is 645208....admin can u pls check my problem once...or can u please recommend sum sample inputs and outputs???

ignore my last questons..i

rajrocks1992 @ 3 Sep 2011 10:05 PM
ignore my last questons..i just found the error!!!!

what does optimal moves

rajrocks1992 @ 3 Sep 2011 10:15 PM
what does optimal moves mean???say a board has dimensions of (7,20)..so does optimal moves mean da moves will be (3,3),(5,5),(7,7),(7,9),(7,11),(7,13),(7,15),(7,17),(7,19),(7,20) ??????

@admin...this tym i am

rajrocks1992 @ 3 Sep 2011 10:33 PM
@admin...this tym i am certain my program is bug free yet da compiler is showing "Wrong Answer"...my problem id is 645234.....please check and also suggest some bigger test cases!!!thank u..

@deeee: The players make

vamsi_adm @ 4 Sep 2011 12:25 PM
@deeee: The players make optimal moves. So they select the board accordingly. @rajrocks1992: Optimal move means that a player will always try to win. He will always make the move that gives him the best chance to win. About getting a Wrong Answer, if your code is not getting Accepted, it means there is some mistake(however small it may be) in it. You can try you own test cases and compare your answers with a brute checker. That would help you finding out your mistake.

ok..Thanx...

rajrocks1992 @ 4 Sep 2011 12:55 PM
ok..Thanx...

i cant even figure out for

moody @ 4 Sep 2011 05:17 PM
i cant even figure out for which test case my code fails... admin cud u plz give a hint...

how is everyone making

h2010442 @ 4 Sep 2011 07:09 PM
how is everyone making boards???? are u using 2D arrays or creating board class???

Not sure why it is happening

nitin.nizhawan @ 4 Sep 2011 09:45 PM
Not sure why it is happening but I tested my solution with multiple approaches, with brute force checker, both in theory and by testing it seems correct. Also its agrees with whatever has been discussed so far in comments. I am still getting WA. Is there some small thing I need worry like capitalization of output, my programs output "MasterChef" / "Football" (without quotes) per line after reading one test case in sequence one by one My submission Id is 646783, any help will be appreciated

@moody, try to figure it out

lg5293 @ 5 Sep 2011 12:34 AM
@moody, try to figure it out yourself, remember this is a contest problem, you can ask these questions after the contest is over. @h2010442, this is a contest problem. Don't ask for implementation details until after the contest. @nitin.nizhawan, I suggest you relook at your strategy and check if your brute-force checker is really correct. The capitalization seems fine in your post, and you should output one per line.

OK, got accepted, I was wrong

nitin.nizhawan @ 5 Sep 2011 01:05 AM
OK, got accepted, I was wrong :)

i wonda whr m makin a

bodmas @ 5 Sep 2011 06:27 AM
i wonda whr m makin a mistake! i dont knw y m gettin a WA. av cross checkd my code.my submission id is 647189. thanks in advance.

I saw many people getting WA,

dumb_coder @ 5 Sep 2011 06:58 PM
I saw many people getting WA, like me, but they are confident on their approach. @admin I may be wrong here but I feel its because of the less number of test cases given, that many people are not understanding the fine details of the problem and missing some edge testcases. Can you please share some more test cases(specially with more number of boards) so that we can know where we are doing wrong. I understand that its a contest and you cant give more hints, but I think sharing some more test cases should be absolutely OK. Admin, please comment.

It is a request to all.

jayantjpr @ 5 Sep 2011 09:54 PM
It is a request to all. Please provide some more test cases - a little complicated ones - for testing the correctness of the code. thanks in advance!!

can someone tell me the o/p

siddharth_l @ 5 Sep 2011 10:07 PM
can someone tell me the o/p for 1 3 2 7 2 8 2 9?

@siddharth_i is the answer

amnsinghl @ 5 Sep 2011 10:48 PM
@siddharth_i is the answer MasterChef

@admin: can you please check

taneja_stud @ 5 Sep 2011 11:20 PM
@admin: can you please check my submission ID:648156, and give some hint.any help will be accepted

@siddarth_I - i m gettin

tranquility @ 6 Sep 2011 01:47 AM
@siddarth_I - i m gettin Football

@ Admin - Please have a look

tranquility @ 6 Sep 2011 03:29 AM
@ Admin - Please have a look http://www.codechef.com/viewsolution/648385 . Tested it against a aced soln.

Can any one tell me whether

Illusion03 @ 6 Sep 2011 12:54 PM
Can any one tell me whether the coins can be placed at any previous position? Moving from (1,1) and after placing the coin at various (ni,mi) , Can i put the coin back on (1,1) or some other cell which i have visited previously?

at lg5293: yeah i know... its

moody @ 6 Sep 2011 12:54 PM
at lg5293: yeah i know... its jst that i cnt seem to figure out the mistake... hey bt cud u plz tell me what do you mean by brute force checker...and how do you check ur code in that.. thanks.

hey what is the out put

karthikabinav @ 6 Sep 2011 10:28 PM
hey what is the out put format.. if the out put is Foootball , MasterChef,Football.. for 1st test case and MasterChef for second test case then the program should output as ? FootballMasterChefFootballMasterChef .. I am I right ?

sorry i meant for four test

karthikabinav @ 6 Sep 2011 10:29 PM
sorry i meant for four test cases...

@Everyone: The homepage of

vamsi_adm @ 6 Sep 2011 10:40 PM
@Everyone: The homepage of the contest says "Please do not discuss strategy, suggestions or tips in the comments during a live contest. Posting questions clarifying the problem statement is ok." The statement is quite clear. Please do NOT ask for hints or ask us to look into your solution. If the judge doesn't accept your code it means your code has some mistake(big or small). Now it is up to you to figure out the mistake. Also, once the contest is over, the editorials will be released. It might help you understanding the approach or finding out the mistake(if any) in your approach. As far as the test cases are concerned, if you understood the problem statement clearly, you can create your own small tests and manually work it out to get an answer. The given test case is only an example and it is enough for the sake of understanding the format of the tests. If you are still unsatisfied, refer to one of ig2539's comments. It contains a useful tip about a certain type of a test case. Hope it makes things clearer. Remember, this is a contest problem. So please do not expect us to give you any hints during the contest. And please do NOT post test cases and discuss the output.

@admin : In a scenario let

gaurav_saxena2000 @ 6 Sep 2011 11:24 PM
@admin : In a scenario let there are 4 boards , first player chooses a board and wins that board ie. makes last move on that board. Then the same first player will get chance to play on any other board ie. does the winner of last board gets chance to play on any next board or only first player will have first chance ?

@gaurav: Making a last move

vamsi_adm @ 6 Sep 2011 11:51 PM
@gaurav: Making a last move on a board doesn't mean that a player has won that board. Infact, there's nothing such as "winning a board". A player does *not* win a board. A player wins a GAME. A game has many boards in it. Making the last move in the game(i.e. no possible move after it on *any* of the boards) makes the player win the game. Hope it clears out the doubt. Go through the problem statement again now!

@karthikabinav: The output

vamsi_adm @ 6 Sep 2011 11:54 PM
@karthikabinav: The output for every test case should be separated by a newline.

I am new to CodeChef , i dont

milanpaliwal @ 7 Sep 2011 03:43 PM
I am new to CodeChef , i dont know why am getting runtime error i hv written a program in java i hv run and compiled the program its not showing any error and take input in the same way as it has given plz help

on each board chef move first

milanpaliwal @ 7 Sep 2011 06:36 PM
on each board chef move first is it like that (eg c=3 then chef move first on all the respective boards)

can any one post more test

talibzaheer @ 7 Sep 2011 10:02 PM
can any one post more test cases with their output.

Plz give 1 or 2 more test

phantom11 @ 8 Sep 2011 12:15 AM
Plz give 1 or 2 more test cases especially for the one in which we have higher value for c

can anyone explain winner in

rijin @ 8 Sep 2011 02:26 AM
can anyone explain winner in each level in 1 3 2 7 2 8 2 9?

@admin I submitted the source

phantom11 @ 9 Sep 2011 02:08 AM
@admin I submitted the source file in JAVA and got Time Limit Exceeded and then the same algorithm in a C++ source file and got correct answer. But this was a simple question so not much depth required about the language you are using.I dont have command in c++ language. So I request you to please see that no such partial judging is done so that the contest is fair and focuses on logic and algorithm rather than language used..Please look after my grievance .Possible options: i) You can increase the time limit for java or ii) decrease the time limit for c++ and c.

@ admin : Could you tell the

gaurav_saxena2000 @ 9 Sep 2011 12:29 PM
@ admin : Could you tell the output for the case 5 345 877 213 123 21 12 333 333 222 222 ? It is quite difficult to figure out the output in such large cases so one such answer would help a lot in figuring out the correctness of my program.

@admin: can i get any other

nagendracse @ 10 Sep 2011 05:10 PM
@admin: can i get any other test case. the test case given in problem is trivial one. You must give at least one different test case.

Admin, would you please

hacker007 @ 10 Sep 2011 05:34 PM
Admin, would you please release the test data when the contest is over? It would be rather helpful for finding bugs.

Hi Will u kindly tell me how

arvindpurohit @ 12 Sep 2011 05:02 PM
Hi Will u kindly tell me how do reached to decision (N+M-2)%2

@admin, plz check d solutn i

bodmas @ 15 Sep 2011 01:22 AM
@admin, plz check d solutn i submitted during d contest, d algorithm agrees with d one discussed in the editorials but i got a WA !!

@admin, plz check d solutn i

bodmas @ 15 Sep 2011 01:22 AM
@admin, plz check d solutn i submitted during d contest, d algorithm agrees with d one discussed in the editorials but i got a WA !!

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

CodeChef is a global programming communityCodeChef hosts online programming competitions