問題はこちら
No.281 門松と魔法(1) - yukicoder
3本の竹をa,b,cとする
門松列にするにはbを最大か最小にしなければならない
#define max(p,q)(p>q?p:q) int main(){ int a,b,c,ta,tb,tc,d,s,t; scanf("%d%d%d%d",&d,&ta,&tb,&tc); ta>tc?ta^=tc^=ta^=tc:0; //常にta≦tcとしてよい if(d==0){ //魔法が使えないなら if(ta!=tc&&(ta<tb&&tc<tb||ta>tb&&tc>tb))s=0; //元から門松なら0 else s=-1; //さもなくば-1 }else{ //魔法が使えるなら //bを最大にする場合 t=0;a=ta;b=tb;c=tc; if(a>=b){t+=(a-b)/d+1;a=max(0,a-((a-b)/d+1)*d);} if(c>=b){t+=(c-b)/d+1;c=max(0,c-((c-b)/d+1)*d);} //a,cがどちらもbより短くなるまで魔法を使って if(a==c){a=max(0,a-d);t++;} //その結果a,cが一致してればダメ押しのもう1回 if(c>0)s=t; else s=-1; //bを最小にする場合 t=0;a=ta;b=tb;c=tc; if(a==c){a=max(0,a-d);t++;} //aとcが一致していればaを縮める if(b>=a){t+=(b-a)/d+1;b=max(0,b-((b-a)/d+1)*d);} //a<cなのでb<aとなればbが最小 if(a>0&&(s==-1||s>t))s=t; } printf("%d",s); return 0; }
場合分けがたくさんあるのでどの順番で整理していくかがかなり難しい
いろいろ試行錯誤した結果だが、これより短いのがあるかもしれない
・まずif(a==c)の処理が2箇所ともに出てくるのでこれは最初に行う
a>c?a^=c^=a^=c:a==c?s++,a-=a<d?a:d:0; //sは魔法の使用回数
・次にこの時点で門松になっているかどうかをチェックする
これにより以降様々なパターンを排除することができるので、この時点で行っておくのが多分得策
この時点で門松になっていないなら「a≦b≦cかつ(a==c==0かa<c)」or「d==0かつa==c」
・魔法使用フェイズ
d==0なら魔法を使えないので-1
c==0ならa==0なので-1
・bを最大にするパターン
cに魔法を使いc<bかつa≠cとなるようにすれば良い
このときの回数は、まずc<bになるまで (c-b)/d+1 回。これをtとおくと
t*d≧cならc==0となるのでa==0ならこのパターンはダメ、そうでなければOK
そうでないならcは非0なので、必要なら(aとcが一致していれば)もう1回魔法を使うことで門松列にできる
・bを最小にするパターン
b<aになれば良いので魔法を (b-a)/d+1 回使う。
このときt*d≧bならb==0となるのでa==0ならダメ、そうでないならOK
ということでこれをまとめる
a,b,c,d,s; main(t){ scanf("%d%d%d%d",&d,&a,&b,&c); a>c?a^=c^=a^=c:a==c?s++,a-=a<d?a:d:0; if(a<b&c<b|a>b&c>b&&a-c){putchar(48+s);return 0;} if(d==0||c==0){puts("-1");return 0;} //bを最大にするパターン t=(c-b)/d+1; if(t*d>=c&&a==0)t=-1; //↑このような事態が起こるのはb≦dのときのみであることに注意! else t=t+s+(c-t*d==a); //bを最小にするパターン //cの値は要らなくなったので、一時保存変数として使い回す c=(b-a)/d+1; if(c*d<b||a!=0)if(c<t)t=c+s; //1つ目のifはこのパターンがOKか、2つ目は最小値を更新したか //もしtが-1ならb≦dなのでc*d≧d≧bかつa==0なのでこのパターンはもともとダメ //つまり「このパターンはOKだけどtが-1だから最小値が更新できない」ということはない printf("%d",t); return 0; }
縮めて
a,b,c,d,s; main(t){ scanf("%d%d%d%d",&d,&a,&b,&c); a>c?a^=c^=a^=c:a==c?s++,a-=a<d?a:d:0; a<b&c<b|a>b&c>b&&a-c?putchar(48+s) :d&&c?t=(c-b)/d+1, t+=t*d<c|a?s+(c-t*d==a):~t, c=(b-a)/d+1, printf("%d",c*d<b|a&&c<t?c+s:t) :puts("-1"); return 0; }
returnも頑張ればまとめられる
a,b,c,d,s; main(t){ scanf("%d%d%d%d",&d,&a,&b,&c); a>c?a^=c^=a^=c:a==c?s++,a-=a<d?a:d:0; a=a<b&c<b|a>b&c>b&&a-c?!putchar(48+s) :d&&c?t=(c-b)/d+1, t+=t*d<c|a?s+(c-t*d==a):~t, c=(b-a)/d+1, !printf("%d",c*d<b|a&&c<t?c+s:t) :!puts("-1"); }
225B
いやー難しい