メモ

yukicoderでゆるふわgolf

yukicoder No.531 エヌスクミ島の平和協定

問題はこち
No.531 エヌスクミ島の平和協定 - yukicoder

m≧nなら全員で船に乗れば1日で移動できる。そうでないとする。
1回目の移動で船に乗るグループと乗らないグループに分けると、これはどちらも非空集合なので、動物1が船に乗り、動物2が船に乗らないとして一般性を失わない。
このとき「捕食者⇒被捕食者」の対偶「被捕食者でない⇒捕食者でない」から、動物3は船に乗る。
以下帰納的に奇数番目の動物は船に乗り、偶数番目の動物は乗らないことになる。
nが奇数のとき動物nが捕食者でありながら被捕食者でないのでダメ。
nが偶数のときグループ分けはうまくいくが、m<n/2のときは該当する動物が船に乗ることができないのでダメ。
よって「nが偶数かつm≧n/2」が可能であるための必要条件であり、実際にこのときグループ分けに従って、1日目に奇数番、2日目に偶数番の動物が移動することで2日で移動ができる。
m<nなので移動が可能ならば2日が最短である。

n,m,ans;
main(){
	scanf("%d%d",&n,&m);
	if(m>=n)ans=1;
	else if(n%2==0 && m>=n/2)ans=2;
	else ans=-1;
	printf("%d",ans);
}

ぎゅ

main(n,m){scanf("%d%d",&n,&m);printf("%d",n>m?n%2|m<n/2?-1:2:1);}

65B