Volume 1 / 0158->0165

AIZU Online Judge C/C++

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

Problem 0158 : Collatz's Problem

#include <iostream>

using namespace std;


int collatz( int num )
{
	if( num == 1 ) return 0;
	if( num%2 == 0 ) return 1+collatz(num/2);
	else return 1+collatz(num*3+1);
}

int main(void)
{
	int n;
	while( cin >> n ){
		if( n == 0 ) break;
		cout << collatz(n) << endl;
	}
	return 0;
}

Problem 0159 : The Best Body

#include <iostream>
#include <cmath>

using namespace std;


int main(void)
{
	int n, i, min_i;
	double  h, w, work, min;

	while( cin >> n ){
		if( n == 0 ) break;

		min = 10000.0;
		while( n-- > 0 ){
			cin >> i >> h >> w;
			h /= 100;
			work = abs(22.0-w/(h*h));
			if( work < min ){
				min = work;
				min_i = i;
			}
		}

		cout << min_i << endl;
	}

	return 0;
}

Problem 0160 : Delivery Fee

#include <iostream>

using namespace std;


int main(void)
{
	int n, x, y, h, w, xyh, money;
	while( cin >> n ){
		if( n == 0 ) break;
		money = 0;
		while( n-- > 0 ){
			cin >> x >> y >> h >> w;
			xyh = x + y + h;
			if( xyh <= 60 && w <= 2 )
				money += 600;
			else if( xyh <= 80 && w <= 5 )
				money += 800;
			else if( xyh <= 100 && w <= 10 )
				money += 1000;
			else if( xyh <= 120 && w <= 15 )
				money += 1200;
			else if( xyh <= 140 && w <= 20 )
				money += 1400;
			else if( xyh <= 160 && w <= 25 )
				money += 1600;
		}
		cout << money << endl;
	}
	return 0;
}

Problem 0161 : Sport Meet

#include <iostream>
#include <vector>

using namespace std;


vector<int> id;
vector<int> times;

void vecsort()
{
	int tmp;

	for( int i=0; i<times.size(); i++ ){
		for( int j=i+1; j<times.size(); j++ ){
			if( times[i] > times[j] ){
				tmp = times[i];
				times[i] = times[j];
				times[j] = tmp;
				tmp = id[i];
				id[i] = id[j];
				id[j] = tmp;
			}
		}
	}

	return;
}

int main(void)
{
	int n, c, m1, s1, m2, s2, m3, s3, m4, s4, i;

	int ms;
	while( cin >> n ){
		if( n == 0 ) break;

		times.clear(); id.clear();
		for( i=0; i<n; i++ ){
			cin >> c >> m1 >> s1 >> m2 >> s2 >> m3 >> s3 >> m4 >> s4;
			id.push_back(c);
			times.push_back((m1+m2+m3+m4)*60+(s1+s2+s3+s4));
		}

		vecsort();
		cout << id[0] << endl;
		cout << id[1] << endl;
		cout << id[times.size()-2] << endl;
	}

	return 0;
}

Problem 0162 : Hamming Numbers

#include <iostream>

using namespace std;


int table[3] = { 2, 3, 5 };
int m, n;

int calc( int num, int prev )
{
	int cnt;
	cnt = ( num >= m ) ? 1 : 0;
	for( int i=prev; i<3; i++ ){
		if( num*table[i] <= n ){
			cnt += calc( num*table[i], i );
		}
	}
	return cnt;
}

int main(void)
{
	int i, cnt;
	cnt = 0;
	while( cin >> m >> n ){
		cnt = 0;
		if( m == 1 ) cnt++;
		for( i=0; i<3; i++ )
			if( table[i] <= n )
				cnt += calc( table[i], i );

		cout << cnt << endl;
	}
	return 0;
}

Problem 0163 : Highway Toll

#include <iostream>

using namespace std;


int main(void)
{
	bool flag;
	int ic1, ic2, h1, m1, h2, m2, money;
	int d[7][7] = 
	{	{ -1, 6, 13, 18, 23, 43, 58 },
		{ 6, -1, 7, 12, 17, 37, 52 },
		{ 13, 7, -1, 5, 10, 30, 45 },
		{ 18, 12, 5, -1, 5, 25, 40 },
		{ 23, 17, 10, 5, -1, 20, 35 },
		{ 43, 37, 30, 25, 20, -1, 15 },
		{ 58, 52, 45, 40, 35, 15, -1 } };
	int v[7][7] = 
	{	{ -1, 300, 500, 600, 700, 1350, 1650 },
		{ 300, -1, 350, 450, 600, 1150, 1500 },
		{ 500, 350, -1, 250, 400, 1000, 1350 },
		{ 600, 450, 250, -1, 250, 850, 1300 },
		{ 700, 600, 400, 250, -1, 600, 1150 },
		{ 1350, 1150, 1000, 850, 600, -1, 500 },
		{ 1650, 1500, 1350, 1300, 1150, 500, -1 } };

	while( cin >> ic1 ){
		flag = false;
		if( ic1 == 0 ) break;
		cin >> h1 >> m1;
		if( 17*60+30 <= h1*60+m1 && h1*60+m1 <= 19*60+30 )
			flag = true;
		cin >> ic2;
		cin >> h2 >> m2;
		if( 17*60+30 <= h2*60+m2 && h2*60+m2 <= 19*60+30 )
			flag = true;

		if( d[ic1-1][ic2-1] > 40 ) flag = false;

		money = v[ic1-1][ic2-1];
		if( flag ){
			money /= 2;
			if( money%50 != 0 ){
				money -= money%50;
				money += 50;
			}
		}

		cout << money << endl;
	}
	return 0;
}

Problem 0164 : Ohajiki Game

#include <iostream>
#include <vector>

using namespace std;


int main(void)
{
	vector<int> a;
	int i, n, input;
	while( cin >> i ){
		if( i == 0 ) break;
		a.clear();
		while( i-- ){
			cin >> input;
			a.push_back(input);
		}
		n = 32;
		for( i=0; n>0; i++ ){
			n -= (n-1)%5;
			if( n < 0 ) n = 0;
			cout << n << endl;
			if( n != 0 ){
				n -= a[i%a.size()];
				if( n < 0 ) n = 0;
				cout << n << endl;
			}
		}
	}

	return 0;
}

Problem 0165 : Lottery

素数のみ入れたベクターを用意してそっちを調べるようにしないと、時間切れになる（Time Limit Exceeded）。

#include <iostream>
#include <vector>

using namespace std;


int main(void)
{
	vector<int> a;
	int i, n, input;
	while( cin >> i ){
		if( i == 0 ) break;
		a.clear();
		while( i-- ){
			cin >> input;
			a.push_back(input);
		}
		n = 32;
		for( i=0; n>0; i++ ){
			n -= (n-1)%5;
			if( n < 0 ) n = 0;
			cout << n << endl;
			if( n != 0 ){
				n -= a[i%a.size()];
				if( n < 0 ) n = 0;
				cout << n << endl;
			}
		}
	}

	return 0;
}