/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
あなたは「AtCoderじゃんけん」という一対一のゲームの大会を主催することになりました。 大会の参加者は N 人で、それぞれには 1 から N の相異なる番号が割り振られています。 アリーナには二人が入ることのできる対戦場が M 個用意されており、あなたはそれぞれの対戦場に二つの相異なる 1 以上 N 以下の整数を割り当てなければいけません。 複数の対戦場に同じ整数を割り当てることはできません。 大会は N ラウンドによって構成され、それぞれのラウンドは以下のようにして取り行われます。
- それぞれの参加者は、自分の番号が割り当てられた対戦場が存在するならそこに行き、そこに来たもう一方の相手と対戦する。
- その後、それぞれの参加者が、自分の番号に 1 を足す。もし 1 を足した後の番号が N+1 であるなら、その値を 1 に変更する。
N 回のラウンドを通じて、二回以上同じ参加者と対戦するような参加者が存在しないようにしたいです。 このような条件を満たす対戦場への整数の割り当てをひとつ出力してください。 ただし、与えられる制約のもとでそのような割り当てが必ず存在することが示せます。
制約
- 1 \leq M
- M \times 2 +1 \leq N \leq 200000
入力
入力は以下の形式で標準入力から与えられる。
N M
出力
以下の形式で M 行に出力せよ。 i 行目には i 個目の対戦場に割り当てる二つの整数を出力せよ。
a_1 b_1 a_2 b_2 : a_M b_M
入力例 1
4 1
出力例 1
2 3
参加者 4 人を A,B,C,D とし、はじめ A には 1、Bには 2、Cには 3、Dには 4 が割り振られているとします。
-
1 回目のラウンドでは 2 の割り振られた B と 3 の割り振られた C が対戦し、A の番号が 2 、B の番号が 3、Cの番号が 4、D の番号が 1となります。
-
2 回目のラウンドでは 2 の割り振られた A と 3 の割り振られた B が対戦し、A の番号が 3 、B の番号が 4、C の番号が 1、D の番号が 2 となります。
-
3 回目のラウンドでは 2 の割り振られた D と 3 の割り振られた A が対戦し、A の番号が 4 、B の番号が 1、C の番号が 2、D の番号が 3 となります。
-
4 回目のラウンドでは 2 の割り振られた C と 3 の割り振られた D が対戦し、A の番号が 1 、B の番号が 2、C の番号が 3、D の番号が 4 となります。
4 回のラウンドを通じて二回以上同じ参加者と対戦するような参加者が存在しないため、この出力は正解となります。
入力例 2
7 3
出力例 2
1 6 2 5 3 4
Score : 500 points
Problem Statement
You are going to hold a competition of one-to-one game called AtCoder Janken. (Janken is the Japanese name for Rock-paper-scissors.) N players will participate in this competition, and they are given distinct integers from 1 through N. The arena has M playing fields for two players. You need to assign each playing field two distinct integers between 1 and N (inclusive). You cannot assign the same integer to multiple playing fields. The competition consists of N rounds, each of which proceeds as follows:
- For each player, if there is a playing field that is assigned the player's integer, the player goes to that field and fight the other player who comes there.
- Then, each player adds 1 to its integer. If it becomes N+1, change it to 1.
You want to ensure that no player fights the same opponent more than once during the N rounds. Print an assignment of integers to the playing fields satisfying this condition. It can be proved that such an assignment always exists under the constraints given.
Constraints
- 1 \leq M
- M \times 2 +1 \leq N \leq 200000
Input
Input is given from Standard Input in the following format:
N M
Output
Print M lines in the format below. The i-th line should contain the two integers a_i and b_i assigned to the i-th playing field.
a_1 b_1 a_2 b_2 : a_M b_M
Sample Input 1
4 1
Sample Output 1
2 3
Let us call the four players A, B, C, and D, and assume that they are initially given the integers 1, 2, 3, and 4, respectively.
-
The 1-st round is fought by B and C, who has the integers 2 and 3, respectively. After this round, A, B, C, and D have the integers 2, 3, 4, and 1, respectively.
-
The 2-nd round is fought by A and B, who has the integers 2 and 3, respectively. After this round, A, B, C, and D have the integers 3, 4, 1, and 2, respectively.
-
The 3-rd round is fought by D and A, who has the integers 2 and 3, respectively. After this round, A, B, C, and D have the integers 4, 1, 2, and 3, respectively.
-
The 4-th round is fought by C and D, who has the integers 2 and 3, respectively. After this round, A, B, C, and D have the integers 1, 2, 3, and 4, respectively.
No player fights the same opponent more than once during the four rounds, so this solution will be accepted.
Sample Input 2
7 3
Sample Output 2
1 6 2 5 3 4