UnKoder#04は本番参加していないので後日の練習のみです。
https://www.hackerrank.com/contests/unkoder-04/challenges/islands-in-circle
問題
N個の島が円形に並んでいる。
ある島から初めて、隣の島に移動するという処理をK回繰り返した場合、最終的にいる可能性のある島は何個あるか。
解法
今の番号を0~(N-1)とし、初期位置を0とする。
Kが奇数なら、-K, -K+2, -K+4, .., -1, 1, .. K (mod N)で止まる。
Kが偶数なら、-K, -K+2, -K+4, .., -2, 0, 2, .. K (mod N)で止まる。
このことを踏まえ、以下N,Kの偶奇で場合分けできる。
- Nが奇数の場合
- Kが奇数なら、-K~Kの計2*floor((K+1)/2)箇所に止まれる。
- Kが偶数なら、-K~Kの計1+2*floor(K/2)箇所に止まれる。
- ただし、上記値がNを超えても上限はN。
- Nが偶数の場合
- 基本的な考え方は奇数の場合と同じ。
- ただ、最終的に止まれる場所の偶奇はKの偶奇と一致するので、上限がN/2。
ll N,K; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; if(N%2==1) { cout<<min(N,(K%2==0)+2*((K+1)/2))<<endl; } else { cout<<min(N/2,(K%2==0)+2*((K+1)/2))<<endl; } }
まとめ
偶奇で混乱するけど、落ち着けば簡単に書ける。