忍者ブログ
23 December

[PR]

×

[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。

19 January

SRM604 div2 500

問題文

http://community.topcoder.com/stat?c=problem_statement&pm=12952

ゴールである(x,y)座標が与えられる。
kターン目には上か右に3^k分進まなければならないとすると、(kは0から)
ゴールには辿り着けるか返せ。

感想

本番の時は2^kならXOR?とかで解けるのにとか思っていましたが、
3^kでも同じようなものだとChallengeの時に気づきました。


#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class PowerOfThreeEasy {

	public: string ableToGet(int x, int y) {
		while(1){
			if((x%3==0&&y%3==1)||(x%3==1&&y%3==0)){
				x/=3;
				y/=3;
			}
			else{
				if(x==0&&y==0)return "Possible";
				return "Impossible";
			}
		}
	}

};


PR