Volume 1 / 0139->0143

AIZU Online Judge C/C++

Problem 0139 : Snakes

頭→尻尾＆全身の長さ→中身の順で判定。

#include <iostream>
#include <string>

using namespace std;


void checkA( string str ){
	int length = str.size();
	if( str[length-1] != '~' || length == 4 ){
		cout << "NA" << endl;
		return;
	}

	int i, cnt = 0;
	bool flag = false;

	for( i=2; i<length-1; i++ ){
		if( str[i] == '#' ){
			flag = true;
			continue;
		}
		if( flag ){
			if( cnt > 0 && str[i] == '=' )
				cnt--;
			else
				break;
		} else {
			if( str[i] == '=' )
				cnt++;
			else
				break;
		}
	}

	if( cnt == 0 && i == length-1 )
		cout << "A" << endl;
	else
		cout << "NA" << endl;

	return;
}

void checkB( string str ){
	int length = str.size();
	if( str[length-1] != '~' || str[length-2] != '~' || length == 4 ){
		cout << "NA" << endl;
		return;
	}

	int i;
	for( i=2; i<length-2; i+=2 )
		if( str[i] != 'Q' || str[i+1] != '=' )
			break;

	if( i >= length-2 )
		cout << "B" << endl;
	else
		cout << "NA" << endl;

	return;
}

int main(void)
{
	int n;
	string snake;

	cin >> n;
	while( n-- > 0 ){
		snake.clear();
		cin >> snake;
		if( snake[0] == '>' && snake[1] == '\'' )
			checkA( snake );
		else if( snake[0] == '>' && snake[1] == '^' )
			checkB( snake );
		else
			cout << "NA" << endl;
	}

	return 0;
}

Problem 0140 : Bus Line

出発地から目的地まで、バスの道順を辿る。

#include <iostream>

using namespace std;


int bs[15] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 5, 4, 3, 2, 1 };

int main(void)
{
	int n, a, b, x, d_min, i, j;

	cin >> n;
	while( n-- > 0 ){
		cin >> a >> b;
		d_min = 16;
		for( i=0; i<15; i++ ){
			if( bs[i] == a ){
				for( j=0; j<15; j++ ){
					if( bs[(i+j)%15] == b ){
						if( d_min > j ){
							d_min = j;
							x = i;
						}
						break;
					}
				}
			}
		}

		cout << bs[x];
		for( i=1; i<=d_min; i++ )
			cout << " " << bs[(x+i)%15];
		cout << endl;
	}

	return 0;
}

Problem 0141 : Spiral Pattern

壁にぶつかったら方向変えて…という探索で解こうとしたけどギブアップ。
解法をALGORITHM NOTE ぐるぐる模様（ALGORITHM NOTE）で見た。

#include <iostream>
#include <vector>

using namespace std;


vector<vector<char> > vec;
int vx[4] = { -1, 0, 1, 0 };
int vy[4] = { 0, -1, 0, 1 };

int main(void)
{
	int d, n, x, y, i, j, v, tmp;

	cin >> d;
	while( d-- > 0 ){
		cin >> n;

		vec.clear();
		vec.resize(n+2);
		for( y=0; y<=n+1; y++ )
			vec[y].resize(n+2);
		for( y=0; y<=n+1; y++ ){
			for( x=0; x<=n+1; x++ ){
				if( y == 1 || x == 1 || ( n!=2 && x==n ) )
					vec[y][x] = '#';
				else
					vec[y][x] = ' ';
			}
		}

		tmp = 0; x = y = n; v = 0;
		for( i=0; i<n-3; i++ ){
			if( i%2 == 0 ) tmp += 2;
			for( j=1; j<n-tmp; j++ ){
				x += vx[v]; y += vy[v];
				vec[y][x] = '#';
			}
			v = (v+1)%4;
		}

		for( y=1; y<=n; y++ ){
			for( x=1; x<=n; x++ ){
				cout << vec[y][x];
			}
			cout << endl;
		}
		if( d != 0 ) cout << endl;
	}

	return 0;
}

Problem 0142 : Nature of Prime Numbers

for文を回す回数を減らしてAccepted

#include <iostream>
#include <vector>
#include <set>

using namespace std;


int main(void)
{
	int n, work, i;

	vector<int> m;
	set<int> r;
	set<int>::iterator it1, it2;

	while( cin >> n, n != 0 ){
		m.clear(); r.clear();
		m.resize((n-1)/2+1);

		for( i=1; i<n; i++ )
			r.insert(i*i%n);

		for( it1=r.begin(); it1!=r.end(); it1++ ){
			for( it2=it1; it2!=r.end(); it2++ ){	// it2 = it1+1みたいに書きたいんだけどなぁ。
				if( it2 == it1 ) continue;
				work = *it1 - *it2;
				if( work < 0 ) work += n;
				if( work > (n-1)/2 ) work = n - work;
				m[work]++;

				work = *it2 - *it1;
				if( work < 0 ) work += n;
				if( work > (n-1)/2 ) work = n - work;
				m[work]++;
			}
		}

		for( i=1; i<=(n-1)/2; i++ )
			cout << m[i] << endl;
	}

	return 0;
}

Problem 0143 : Altair and Vega（未）

Wrong Answer
うーん…。

#include <iostream>

using namespace std;

typedef struct POINT {
	int x, y;
} P; 

int checkIntersect( P p1, P p2, P p3, P p4 ){
	int flag1, flag2;
	flag1 = ((p3.x-p1.x)*(p2.y-p1.y)-(p3.y-p1.y)*(p2.x-p1.x))*((p4.x-p1.x)*(p2.y-p1.y)-(p4.y-p1.y)*(p2.x-p1.x));
	flag2 = ((p1.x-p3.x)*(p4.y-p3.y)-(p1.y-p3.y)*(p4.x-p3.x))*((p2.x-p3.x)*(p4.y-p3.y)-(p2.y-p3.y)*(p4.x-p3.x));

	if( flag1 < 0 && flag2 < 0 )
		return -1;
	if( flag1 == 0 )
		return 2;

	return 1;
}

int main(void)
{
	int n, result;
	P p1, p2, p3, k, s;

	cin >> n;
	while( n-- > 0 ){
		cin >> p1.x >> p1.y >> p2.x >> p2.y >> p3.x >> p3.y >> k.x >> k.y >> s.x >> s.y;

		if( ((p3.x-p1.x)*(p2.y-p1.y)-(p3.y-p1.y)*(p2.x-p1.x)) == 0 ){
			cout << "NG" << endl;
			continue;
		}

		result = 1;
		result *= checkIntersect( p1, p2, k, s );
		result *= checkIntersect( p2, p3, k, s );
		result *= checkIntersect( p3, p1, k, s );

		if( result == 1 || result == 2 || result == -4 )
			cout << "NG" << endl;
		else
			cout << "OK" << endl;
	}
	return 0;
}