読者です 読者をやめる 読者になる 読者になる

土下座しながら探索中

主に競技プログラミング

UVa 12627 : Erratic Expansion

問題リンク : http://uva.onlinejudge.org/external/126/12627.html

問題概要 :
赤い風船を1つだけ持っている
次の日になると赤い風船が3つ、青い風船が1つになった
次の日になると赤い風船は前日と同様に分裂し、青い風船は4つの青い風船になった
詳しくは問題にある図を見ること
そんな感じの規則で1日毎に風船が変化していく
K日後の列Aから列Bまでにある赤い風船の数を数えよ

解法 :
再帰で領域を均等に4分割していくと良い

1 | 2
______
3 | 4

こんな感じで
4は全て青になる

rec(左上のx,左上のy,右下のx,右下のy) := この範囲にある赤い風船の数 とする
今みている領域がAからBの間にない場合、再帰を終了する ( 0を返す )
今みている領域がAからBの間に完全に入っている場合、4分割した領域のうち全て青になる領域でない領域は全て結果が等しくなるのでそのうちの1つだけ再帰しその結果を3倍して返す
今みている領域が2*2なら、1,2,3のうち対応する数を返す
それ以外の場合、1と2のみを計算し(1の結果)*2+(2の結果)を返す
1と3は全く同じ結果になりますからね


よくある再帰のアレ
コード :

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
int A,B,K,N;
 
inline bool isValid(int x) { return A <= x && x <= B; }
 
ll rec(int tx,int ty,int bx,int by){
  if( B < tx || bx < A ) return 0;
  int len_x = abs(tx-bx)+1;
  int len_y = abs(ty-by)+1;
  assert( len_x == len_y );
  if( len_x <= 2 ) {
    if( isValid(tx) && isValid(bx)  )  {
      return 3LL;
    } else {
      if( isValid(tx) && !isValid(bx) ) return 2LL;
      else if( isValid(bx) && !isValid(tx) ) return 1LL;
      return 0;
    }
  }
 
  bool all = false;
  if( isValid(tx) && isValid(bx) ) {
    all = true;
  }
  ll ret = 0;
  int h = len_x / 2;
  int nx[2],ny[2];
  //1
  nx[0] = tx, ny[0] = ty;
  nx[1] = tx+h-1, ny[1] = ty+h-1;
  ret += rec(nx[0],ny[0],nx[1],ny[1]) * 2LL;
  if( all ) return ret / 2LL * 3LL;
  //2
  nx[0] = tx+h, ny[0] = ty;
  nx[1] = bx, ny[1] = ty+h-1;
  ret += rec(nx[0],ny[0],nx[1],ny[1]);
  return ret;
}
 
int main(){
  int T,CNT=1;
  cin >> T;
  while( T-- ){
    cin >> K >> A >> B;
    N = (1<<K);
    if( K == 0 ) {
      printf("Case %d: 1\n",CNT++);
    } else {
      printf("Case %d: %lld\n",CNT++,rec(1,1,(1<<K),(1<<K)));
    }
  }
  return 0;
}