Chef and Chefu
All submissions for this problem are available.Chef and his friend Chefu are playing a game. They have a sequence of integers $A$ of size $N$. In each move a player chooses a subsequence such that the size of the subsequence is maximum and every element in the subsequence is similar to its adjacent elements. Total points scored by a player in each move is equal to sum of all the integers in the subsequence chosen by him. After a subsequence is chosen by any player it is removed from the remaining sequence of integers. Both the players take alternate turns and plays optimally. Chef being younger than Chefu starts first. Find the winner of the game and determine the number of points scored by him. In case of a draw output $“Draw”$ (without quotes) and display the score of any player. ###Input - First line contains a single integer $N$. - Second line contains $N$ integers represented by $A_i$. ###Output In the first line print $“Chef”$ or $“Chefu”$ or $“Draw”$ (without quotes). In the second line print the number of points scored by the winner or by anyone in case of a draw. ###Constraints - $1 \leq N \leq 2*10^5$ - $1 \leq A_i \leq10^6$ ###Subtasks - 20 points : $N , A_i \leq 1000$ - 80 points : $original$ $constraints$ ###Sample input 1: 5 1 5 4 4 5 ###Sample output 1: Chef 11 ###Sample input 2: 5 22 4 4 10 4 ###Sample output 2: Draw 22 ###Explaination In sample input $1$,first Chef choses subsequence $(5,5)$ then Chefu choses subsequence $(4,4)$ and finally Chef chooses $(1)$. So total score of Chef is $11$ and Chefu is $8$ and Chef wins. In sample input $2$,first Chef choses the subsequence $(4,4,4)$ then Chefu choses subsequence $(22)$ and finally Chef chooses $(10)$. So total score of Chef is $22$ and Chefu is also $22$ and it’s a draw.
|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, rust, SCALA, swift, 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, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.