LCC/Moose '19 Contest 3 S5 - Konnect

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 256M

Problem type

One of Ashley and Oleg's presents was a board game called Konnect, which is a game where two players take turns dropping pieces of their color into a 2D grid and the first person to get K pieces of their color in a row horizontally, vertically, or diagonally wins.

Ashley and Oleg recorded the sequence of moves that were played during one of their games, but they have since forgotten the result of the game. Could you help figure out who won?

Input Specification

The input begins with two integers N, K (1 \le N, K \le 300\ 000), the number of moves that were played and the value K. The next line contains N integers C_i (1 \le C_i \le 10^6), which say that the i-th move was played in column C_i. The two players alternate making moves, with Ashley going first.

For 30% of cases, N \le 100, C_i \le 1,000.
For 50% of cases, K \le 10.

Output Specification

Output the winner of the game (Ashley or Oleg) as well as the turn on which the game ended (it is possible the game ends before the last move). It is guaranteed that the game ends with a winner.

Sample Input 1

8 4
1 2 1 2 1 2 1 2

Sample Output 1

Ashley 7

Sample Input 2

4 2
1 1 1 2

Sample Output 2

Oleg 4


There are no comments at the moment.