問題はこちら
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