kmjp's blog

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

Codeforces #306 Div2 C. Divisibility by Eight

Eでしょうもないミスをして結構順位を落とした。
今回A-Cが同程度の難易度だけど、まぁCDEだけ書いていきます。
http://codeforces.com/contest/550/problem/C

問題

最大100桁の整数が与えられる。
ここから何桁か消して8で割れるかを答えよ。

解法

1000は8の倍数であることから、整数が8の倍数かどうかは下3桁で決まる。

よって100桁のうち1~3桁を総当たりで抜き出し、8で割れるものを探せばよい。
他にも色々解法があって、入力値の頭に00を加えたうえで008,016,...,992含むか判定するなどでも良い。

nt L;
string S;

void solve() {
	int i,j,k,l,r,x,y,z; string s;
	
	cin>>S;
	
	FOR(x,S.size()) {
		if((S[x]-'0')%8==0) return _P("YES\n%c\n",S[x]);
	}
	FOR(y,S.size()) FOR(x,y) {
		i = (S[x]-'0')*10+(S[y]-'0');
		if(i%8==0) return _P("YES\n%d\n",i);
	}
	FOR(z,S.size()) FOR(y,z) FOR(x,y) {
		i = (S[x]-'0')*100+(S[y]-'0')*10+(S[z]-'0');
		if(i%8==0) return _P("YES\n%d\n",i);
	}
	_P("NO\n");
}

まとめ

Div2 Cにしては簡単と思ったけど、Dynamic Scoreのスコア見てもそんな感じだね。

広告を非表示にする