kmjp's blog

競技プログラミング参加記です

Codeforces #411 Div1 A. Find Amir

グダったところもあったけど、幸いSubmit分は全部通ってHighest更新。
http://codeforces.com/contest/804/problem/A

問題

1~NのN個の頂点がある。
頂点i→jに移動すると、(i+j)%(N+1)のコストがかかる。
任意の頂点から始め、全頂点を1回以上訪問するのにかかる最小コストを求めよ。

解法

言い換えるとiと(N+1-i)の間はノーコストで移動できると言える。
1→N→2→(N-1)→…→x→(N+1-x)→x+1→…
と移動すると、訪問先番号が小さくなるタイミング、(N-1)/2回だけコスト1かかる。

ll N;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	cout<<(N-1)/2<<endl;
}

まとめ

考察系。あまり難しくないけど。

広告を非表示にする