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

kengo92iの日記

プログラミングとかやったことの記録を書いていきます。

AOJ-2589 : North North West

North North West | Aizu Online Judge

概要

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

解法

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

既約分数への変換は,最大公約数を求めることで計算できます.最大公約数を求めるのには__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;
}