MWC '15 #5 P2: WildCard

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 3.0s
Memory limit: 256M

Author:
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

aurpine and kushanzaveri are playing a game called WildCard. In this game, N cards are placed face up, adjacent to one another. Each card has a special integer representing its wild factor W_{i}. On each player's turn, they must find a pair of any two cards which have a combined wild factor of exactly K. Once a pair is found, the two cards are removed from the game, and the next player's turn starts. The player who cannot make a valid pair of two cards on their turn loses the game.

As both aurpine and kushanzaveri are amateurs and take a long time to complete a single game, you want to write a program that can calculate the result of their game.

Input Specification

On one line, three space separated integers N (1 \leq N \leq 10^6), K (1 \leq K \leq 10^9) and T (0 \leq T \leq 1), with T representing the player who goes first (0 being aurpine and 1 being kushanzaveri).

On the second line, N space separated integers representing W_{i} (1 \leq W_{i} \leq 10^8), the wild factor of the i^{th} card.

Output Specification

On one line output the name of the player who wins the game as well as the number of pairs that he can make, separated by a space.

Sample Input

6 10 1
1 5 2 8 3 9

Sample Output

aurpine 1

Explanation of Sample Input

If kushanzaveri goes first, he can choose to make one of two pairs: (2, 8) or (1, 9). Either way, after both players each play one turn (each player making one of the valid pairs), there will be no more valid pairs to make and aurpine will win having made one pair.


Comments


  • -1
    vincentdmacri  commented on April 28, 2016, 11:05 p.m.

    If K=10^9, there will be no pairs, since card can't be higher than 10^8. Since someone solved this already, I guess it's a typo. Which value has a mistake?


    • 2
      atarw  commented on April 29, 2016, 9:24 a.m. edit 5

      The player who cannot make a valid pair of two cards on their turn loses the game.

      No mistake was made.


  • 1
    Daniel123  commented on April 23, 2016, 4:12 p.m.

    Do the cards have distinct wild factors?


    • 4
      atarw  commented on April 23, 2016, 4:26 p.m. edited

      Don't assume anything not explicitly stated :D (they don't have to be unique)


  • 0
    Daniel123  commented on April 23, 2016, 11:48 a.m.

    kushanzaveri wins


    • 1
      atarw  commented on April 23, 2016, 12:13 p.m. edited

      The sample output was correct but the explanation was wrong. It has been fixed. (good catch!)


  • 4
    kushanzaveri  commented on April 23, 2016, 10:59 a.m.

    Thanks atarw.