A - AtCoder Jumper¶

题意¶

本サイトのこの部分にお気づきでしょうか。

これらの番号は、どのページからどのページへも少ないクリック数で到達できるように、なおかつ各ページのリンク数が多くなりすぎないように配慮して選ばれています。この問題では、似たようなことを $1$ ページあたりリンク $2$ つで実現していただきましょう。

すぬけ君は、 $1$ から $N$ までの番号が振られた $N$ ページからなるサイトを作りました。あなたには、各 $i$ ( $1\le i\le N$ ) について 2 つの整数 $a_i,b_i$ ( $1\le a_i,b_i\le N$ ) を選び、ページ $i$ にページ $a_i$ へのリンクとページ $b_i$ へのリンクを貼ることで、以下の制約を満たしていただきます。

どのページから他のどのページへも、リンクを $10$ 回以下クリックすることで到達可能でなければならない。

この問題の制約の下で、これが常に可能であることは証明可能です。

解析¶

将 $0$ 和 $N$ 视作同一个点，令 $a_i=(2i+1)\bmod N+1,b_i=2i\bmod N$ 。则经过 $10$ 回后， $i$ 能够到达的位置的集合为 $(1024i,1024i+1,1024i+2,\ldots,1024i+N-1)\bmod N$ ，构成 $N$ 的一个完全剩余系。

实现¶

#include <bits/stdc++.h>

int n;

int main(){
    std::scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        std::printf("%d %d\n", i * 2 % n + 1, (i * 2 - 1) % n + 1);
}

来源¶

AtCoder Grand Contest 050 A - AtCoder Jumper

A - AtCoder Jumper¶

题意¶

解析¶

实现¶

来源¶

评论