AOJ-2589 : North North West

North North West | Aizu Online Judge

概要

northとwestが複数繋がった文字列が与えられるので，その文字列が示す角度を分数で出力する問題．northが0°を意味し，westが90°を意味している．n個目からは，northは は意味し，west は (aは現在の角度)として計算します．答えは既約分数で出力すること．計算は右側から展開していきます．

解法

始めに，northとwestに関する情報を読み取ります．後ろから計算していくので，逆順に変更します．角度を計算する時は，分子は．現在の分子を2倍してから，±90します．分母は最後に で求めます．

既約分数への変換は，最大公約数を求めることで計算できます．最大公約数を求めるのには__gcd(a, b)という関数があるのでこれを使います．

ソースコード

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2589

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;

const int MAX = 20;
const int NORTH = 0;
const int WEST = 1;

struct fraction {
	int n; //分子
	int d; //分母
};

int main() {
	string s;
	while(cin >> s) {
		if(s == "#") break;
		
		vector<int> dir;
		rep(i, s.size()) {
			if(s[i] == 'n') {
				dir.push_back(NORTH);
				i += 4;
			}
			else if(s[i] == 'w') {
				dir.push_back(WEST);
				i += 3;
			}
		}

		reverse(ALL(dir));
		fraction f = {0, 1};

		int n=dir.size();
		rep(i, n) {
			if(dir[i] == NORTH) {
				f.n = (2 * f.n) - 90;
				if(f.n < 0) f = {0, 1};
			}
			else {
				f.n = (2 * f.n) + 90;
			}
		}

		f.d = 1 << (n-1);

		int g = __gcd(f.n, f.d);
		if(f.d / g == 1) {
			cout << f.n / g << endl;
		} else {
			cout << f.n / g << "/" << f.d / g << endl;     
		}
	}
	return 0;
}