Volume 1 / 0166->0168

パソコン甲子園2007本選　解答

Problem 0166 : Area of Polygon（未）

"Wrong Answer"
円に内接する多角形の面積比較。
多角形は三角形の集合だから、(三角形の面積)=0.5*r*r*sin(v)を足しこめば多角形の面積が出るはず…。

#include <iostream>
#include <cmath>

#define PI 3.14

using namespace std;


int main(void)
{
	int m, n, v, vsum, i;
	double rad;
	double s1, s2;

	while(true){
		cin >> m;
		if( m == 0 ) break;
		s1 = 0; s2 = 0;
		vsum = 0;
		for( i=0; i<m-1; i++ ){
			cin >> v;
			vsum += v;
			s1 += sin(v*PI/180);
		}
		s1 += sin((360-vsum)*PI/180);

		cin >> n;
		vsum = 0;
		for( i=0; i<n-1; i++ ){
			cin >> v;
			vsum += v;
			s2 += sin(v*PI/180);
		}
		s2 += sin((360-vsum)*PI/180);

		if( s1 > s2 )
			cout << 1 << endl;
		else if( s1 < s2 )
			cout << 2 << endl;
		else
			cout << 0 << endl;
	}

	return 0;
}

Problem 0167 : Bubble Sort

バブルソートの交換回数を調べる。

#include <iostream>
#include <vector>

using namespace std;


int bubbleSort( int n, vector<int> vec )
{
	int cnt, tmp;

	cnt = 0;
	for( int i=0; i<n; i++ ){
		for( int j=0; j<n-i-1; j++ ){
			if( vec[j] > vec[j+1] ){
				tmp = vec[j];
				vec[j] = vec[j+1];
				vec[j+1] = tmp;
				cnt++;
			}
		}
	}

	return cnt;
}

int main(void)
{
	int n, i, input;
	vector<int> data;

	while( cin >> n, n != 0 ){
		data.clear();
		for( i=0; i<n; i++ ){
			cin >> input;
			data.push_back(input);
		}

		cout << bubbleSort( n, data ) << endl;
	}

	return 0;
}

Problem 0168 : Kannondou

【ヒント】
n段目にいたる一歩手前はn-1段目か、n-2段目か、n-3段目のいずれかで、それより下では一足ではn段
目には到達できません。n段目での上り方をanとすると、an は、an-1、an-2、an-3の式で表されますね。

(パソコン甲子園公式サイト　２００７年本選問題より)

つまり、（n段目）＝（n-1段目）＋（n-2段目）＋（n-3段目）

#include <iostream>

using namespace std;


int main(void)
{
	int n, cnt, y;
	int c[31];

	c[0] = 1;
	c[1] = 1;
	c[2] = 2;
	for( int i=3; i<=30; i++ )
		c[i] = c[i-1] + c[i-2] + c[i-3];

	while( cin >> n, n != 0 ){
		y = c[n]/(365*10);
		y += !( c[n]%(365*10) == 0 );
		cout << y << endl;
	}

	return 0;
}