DMOPC '21 Contest 3 P3 - Hopping Frogs

View as PDF

Submit solution


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

Author:
Problem type

Two friendly frog families are standing on a line of N+M+1 stones numbered 0 to N+M from left to right. The first family consists of N frogs standing on the stones numbered from 0 to N-1, each of the frogs facing to the right. The second family consists of M frogs standing on the stones numbered from N+1 to N+M, each of the frogs facing to the left.

The frog families are now going on a family trip! The first family wants to stand on the stones numbered from M+1 to N+M, whereas the second family wants to stand on the stones numbered from 0 to M-1. To reach these stones, any frog can perform any number of the following hops:

  1. If there is at least one stone in the direction that the frog faces and the stone directly in front of the frog does not have a frog on it, hop to that stone.
  2. If there are at least two stones in the direction that the frog faces, the stone directly in front of the frog is occupied by a frog from the other family, and the stone behind the other frog does not have a frog on it, hop to that stone.

Given these conditions, is it possible for all the frogs to reach their desired stones? If it is, please find the shortest sequence of hops that achieves it.

Constraints

1 \le N, M \le 2 \times 10^3

Subtask 1 [10%]

N = 1

Subtask 2 [40%]

N = M

Subtask 3 [50%]

No additional constraints.

Input Specification

The first and only line contains 2 integers N and M.

Output Specification

If it is impossible for all the frogs to reach their desired stones, output -1.

Otherwise, the first line of your output should contain an integer K, the minimum number of jumps required for all the frogs to reach their desired stones.

Then, the i-th of the next K lines should contain an integer p_i (0 \le p_i \le N + M), representing that the frog on stone p_i should perform one of the possible hops as the i-th hop in your solution.

Scoring

For each test case, your output should satisfy the following requirement:

  1. The integer on the first line of output must be correct.

If the integer on the first line is not -1, then your output should satisfy the following additional requirements:

  1. For each p_i, there must be a frog on stone p_i and it should be able to perform exactly one of the two hops.
  2. After performing the hops given, the first family of frogs should be on stones M+1 to N+M and the second family of frogs should be on stones 0 to M-1.

If your output satisfies all of the necessary requirements, you will receive Accepted for that test case. Otherwise, you will receive Wrong Answer.

Sample Input

2 2

Sample Output

8
1
3
4
2
0
1
3
2

Comments

There are no comments at the moment.