問題はこちら
No.682 Average - yukicoder
(A+B+i)/3が整数⇔A+B+iが3の倍数 を使って全探索するだけ
main(){
int a,b;
scanf("%d%d",&a,&b);
int ans=0;
for(int i=a;i<=b;i++)if((a+b+i)%3==0)ans++;
printf("%d",ans);
}
「A≦i≦BのうちA+B+iが3の倍数になるようなiの個数」は「A+B+A以上A+B+B以下の3の倍数の個数」なので
(A+B+B)/3-(A+B+A-1)/3により求めることができる。
しかし実はさらに短い計算式が存在する。
答えがA%3,B%3,(B-A)/3のみに依存していることは容易に想像できるので、場合分けをしてみる。n=(B-A)/3とおく
| A%3 | B%3 | 答え |
|---|---|---|
| 0 | 0 | n+1 |
| 0 | 1 | n |
| 0 | 2 | n+1 |
| 1 | 0 | n+1 |
| 1 | 1 | n+1 |
| 1 | 2 | n |
| 2 | 0 | n |
| 2 | 1 | n+1 |
| 2 | 2 | n+1 |
表をぐっと睨むと、答えは
(B-A)%3が1のときn、それ以外のときn+1になっていることがわかる
ということで(B-A)/3+((B-A)%3!=1)で計算できる。
この式を睨んで次のように短縮する
main(a,b){
scanf("%d%d",&a,&b);
printf("%d",(b-=a)/3+1-b%3%2);
}
61B
