/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
正の整数 N,M が与えられます。
以下を満たす整数の組の列 ((X_1,Y_1),(X_2,Y_2),\dots,(X_K,Y_K)) を素晴らしい整数の組の列ということとします。
- 1 \le X_i \le N
- 1 \le Y_i \le M
- i \neq j ならば X_i+3Y_i \neq X_j+3Y_j かつ 3X_i+Y_i \neq 3X_j+Y_j
素晴らしい整数の組の列のうち、長さ K が最大であるものを 1 個構築してください。
制約
- 1 \le N,M \le 10^5
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられます。
N M
出力
以下の形式で出力してください。
K X_1 Y_1 X_2 Y_2 \vdots X_K Y_K
ここで、K は素晴らしい整数の組の列の長さの最大値とします。そして、((X_1,Y_1),(X_2,Y_2),\dots,(X_K,Y_K)) は素晴らしい整数の組の列である必要があります。 答えが複数存在する場合、どれを出力しても正解とみなされます。
入力例 1
3 4
出力例 1
10 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 3 4
N=3,M=4 の時、長さ 11 以上の素晴らしい整数の組の列は存在せず、かつ上記の出力は素晴らしい整数の組の列であるためこの出力は正当です。
Score : 700 points
Problem Statement
You are given positive integers N and M.
Let us call a sequence of pairs of integers ((X_1,Y_1),(X_2,Y_2),\dots,(X_K,Y_K)) wonderful when it satisfies the following.
- 1 \le X_i \le N
- 1 \le Y_i \le M
- X_i+3Y_i \neq X_j+3Y_j and 3X_i+Y_i \neq 3X_j+Y_j, if i \neq j.
Make a wonderful sequence of pairs of integers whose length, K, is the maximum possible.
Constraints
- 1 \le N,M \le 10^5
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M
Output
Print your answer in the following format:
K X_1 Y_1 X_2 Y_2 \vdots X_K Y_K
Here, K should be the maximum possible length of a wonderful sequence of pairs of integers, and ((X_1,Y_1),(X_2,Y_2),\dots,(X_K,Y_K)) should be a wonderful sequence of pairs of integers. If multiple solutions exist, printing any of them is accepted.
Sample Input 1
3 4
Sample Output 1
10 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 3 4
For N=3, M=4, there is no wonderful sequence of pairs of integers whose length is 11 or longer, and the above sequence of pairs of integers is wonderful, so this output is valid.