Find Amir | Codeforces #411

2番目の入力例n=10を考えてみよう。

とりあえず、(i+j) mod (n+1) = 0

となるような辺(i, j)はコスト0なので全部張ろう。

1-10

2-9

3-8

4-7

5-6

あとはコスト1以上の辺を貼るしかない。

実はすべてコスト1の辺で繋げられる。

10+2≡1

9+3≡1

8+4≡1

7+5≡1

よってコストは4。

奇数の場合も同様に考えることができる。したがって解は

floor((n-1)/2)

クラスカル法っぽくやる