Play with Roses
All submissions for this problem are available.
Chef is in love. But he is not sure whether his partner is Happy or not. So like a typical Bollywood movie Chef goes to garden which contains many roses. Chef picks in his hand one or several roses and tears of petals one by one. After each petal he pronounces alternatively "Happy" and "Sad".
Chef wants to pick up rose(s) with maximum possible total number of petals so that result would still be "Happy". Help Chef to find maximum number of petals possible.
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains a single integer N denoting the number of roses.
- The second line contains a string "Happy" or "Sad" denoting from which word Chef starts pronouncing.
- Next line contains N space-separated integers A1, A2, ..., AN denoting number of petals in each rose.
- For each test case, output a single line containing maximum number of petals on which the result would be "Happy". If there is no such possibilities, output "Sad".
- 1 ≤ T ≤ 50
- 1 ≤ N ≤ 105
- 1 ≤ Ai ≤ 106
- Sum of N over all test cases doesn't exceed 106
Subtask #1 : (20 points)
- 1 ≤ T ≤ 5
- 1 ≤ N ≤ 15
- Original Constraints.
Subtask #2: (80 points)
Input: 2 2 Sad 2 3 2 Happy 2 3 Output: 2 5
Example case 1. Chef can pick first rose such that result would still be Happy starting from Sad. Hence maximum number of petals possible is 2.
|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, CLOJ, FS|
Fetching successful submissions