Yet Another Contest 6 P4 - No More Nails!

View as PDF

Submit solution


Points: 12 (partial)
Time limit: 0.6s
Python 1.0s
Memory limit: 512M

Author:
Problem types

Mike is tired of working with nails and wood in the Canadian Carpentry Challenge (CCC). So, he decided to take a break and invited Nils to come play a game with him. To play this game, Mike has gathered N square pieces of wood. The i-th piece of wood has integer length and width of s_i units.

A piece of wood with length L and width W is divided into sections that consist of L rows with W columns each. Initially, there is a nail placed on the bottom right corner of each wood board.

Mike and Nils will take turns during the game. On each player's turn, they will choose exactly one of the wood boards, and then choose one of the following moves:

  • Make a horizontal cut across the entire wood board such that the length and width of both pieces are integral after the cut, and discard the piece that does not contain the nail.
  • Make a vertical cut across the entire wood board such that the length and width of both pieces are integral after the cut, and discard the piece that does not contain the nail.
  • Move the nail X units left such that X is a positive integer and the nail remains on the board.
  • Move the nail X units up such that X is a positive integer and the nail remains on the board.
  • Move the nail X units left and X units up such that X is a positive integer and the nail remains on the board.

When a player is unable to make a move, they lose, and the other player wins. Nils will go first.

Mike wants to win the game, and he will make sure he does by adding exactly one more square wood board of integral side length to the game. Like any other piece of wood, the added board will have a nail on the bottom right corner. Since Mike does not want to arouse suspicion, the additional square board's side length must not exceed M and be minimal among all possible lengths.

Can you tell Mike the smallest board to add so that he will win if both Nils and him play optimally, or report that it is impossible to do so?

Constraints

1 \le N \le 10^6

1 \le M, s_i \le 100

Subtask 1 [20%]

N = M = 1

1 \le s_i \le 30

Subtask 2 [20%]

M = 1

s_1 = s_2 = \dots = s_N

Subtask 3 [30%]

1 \le M, s_i \le 30

Subtask 4 [30%]

No additional constraints.

Input Specification

The first line contains two integers N and M.

The next line contains s_1, s_2, \dots, s_N.

Output Specification

On a single line, print the minimum square board size with side lengths less than or equal to M to be added such that Mike will win if both players play optimally. If no solution exists, output -1 on a single line instead.

Sample Input 1

2 4
6 2

Sample Output 1

3

Explanation for Sample Output 1

After adding a square wood board with side length 3, it can be shown that Mike will win the game if both player play optimally. A sample interaction where each player plays optimally is shown below.

At the end of the game, Nils is unable to make a valid move, so Mike wins. It can be shown that adding a square board of side length 3 is the minimal solution.

Sample Input 2

1 68
1

Sample Output 2

1

Explanation for Sample Output 2

Even though Mike will already win as Nils is unable to make any move at the start, he must add another wood board to the game. So, he can add a square board with side lengths of 1, which is the minimal possible board size.

Sample Input 3

4 10
9 7 3 8

Sample Output 3

-1

Explanation for Sample Output 3

It can be shown that no square board with side lengths up to 10 once added will allow Mike to win if both players play optimally.

Sample Input 4

6 29
4 1 4 20 6 9

Sample Output 4

21

Comments

There are no comments at the moment.