C. Perfect Harmony

2011-05-22

01:19 |

他の人が鳴らす音の周波数が分かっている。
自分が鳴らす音を L～H の範囲で決めて、全員とハーモニーするようにしたい。
２人がハーモニーしてるとは、２人が出す周波数が「どっちかがどっちかで割り切れる」ことである。

8pt だし早速何人か解いてて正解率も高かったので問題を見てみると、Small だけなら総当りでいけそうなのでさくっと書いて点を取りに行く作戦。
Large は gcd と lcm を求めて L～H に入っているかどうか調べれば行けるかと思ったら全然そうではなくて、どっちかがどっちかで割り切れればよいので gcd～lcm の間にも解が有りうることに途中で気づいた。でお手上げ。

int main()
{
	int T;
	cin>>T;
	//cout<<T<<endl;
	REP(t, T)
	{
		int N,L,H;
		cin>>N>>L>>H;
		int v[N];
		REP(i, N) cin>>v[i];
		
		int ok=0;
		int ans=0;
		FOR(f, L, H+1)
		{
			int lok=1;
			REP(i, N)
			{
				if(f<v[i])
				{
					if(v[i]%f!=0) {lok=0; break;}
				}
				else if(f%v[i]!=0) {lok=0; break;}
			}
			if(lok) {ok=1; ans=f; break;}
		}
		
		if(ok)
			cout<<"Case #"<<t+1<<": "<<ans<<endl;
		else
			cout<<"Case #"<<t+1<<": NO"<<endl;
	}
	return 0;
}