UVa10705

uva10705
i番目が(2^i)もしくは-(2^i)の重みを持つ様なビット列を考える。
各ビットが正なのか負なのかと整数nが入力として与えられる。
整数nがビット列で表現できるかどうか、表現できる場合はそのビット列を出力する。
aoj0233と似ている。似たアプローチでやってみた。

// uva 10705

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long int lli;

int main(void)
{
  int tc;
  cin >> tc;
  while( tc-- ){
    lli size, n, bit = 1;
    string s, r;
    cin >> size >> s >> n;
    for(int i=size-1; 0<=i; --i){      
      if( n & bit ){
        r += '1';
        n -= ( s[i] == 'p' ) ? bit : -bit;
      }
      else{
        r += '0'; 
      }
      bit <<= 1;
    }
    reverse( r.begin(), r.end() );
    cout << ( n ? "Impossible" : r ) << endl;
  }
  return 0;
}

筆算をやる様に、不足の場合は上位のビットから借りてくる。