Volume 1 / 0169->0170

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

Problem 0169 : Blackjack

ブラックジャックの点数計算。
1の枚数を数えといて、1にするか11にするかはあとで計算。

#include <iostream>

using namespace std;


int main(void)
{
	int point, card, one_flag, i;
	char ch;

	while( cin.get(ch), ch != '0' ){
		cin.putback(ch);
		point = 0; one_flag = 0;

		while( cin.get(ch), ch != '\n' ){
			cin.putback(ch);
			cin >> card;
			if( card == 1 )
				one_flag++;
			if( card >= 10 )
				card = 10;
			point += card;
		}

		for( i=0; i<one_flag && point<=11; i++ )
			point += 10;

		if( point > 21 )
			point = 0;

		cout << point << endl;
	}

	return 0;
}

Problem 0170 : Lunch

(一番上〜i番目の食べ物の重さの合計[above])<=(i番目の許容重量[s])となるように上から順に積んでいく。

#include <iostream>
#include <string>
#include <limits.h>

using namespace std;


int n, minG, f[10], ans[10];
bool isUsed[10];
struct food_tag {
	string name;
	int w, s;
} foods[10];

int getG(){
	int g = 0;
	for( int i=0; i<n; i++ )
		g += foods[f[i]].w*(n-i+1);

	return g;
}

void calc( int above, int depth )
{
	if( depth == n ){
		int g = getG();
		if( g < minG ){
			minG = g;
			for( int i=0; i<n; i++ )
				ans[i] = f[i];
		}
		return;
	}

	for( int i=0; i<n; i++ ){
		if( !isUsed[i] && above <= foods[i].s ){
			f[depth] = i;
			isUsed[i] = true;
			calc( above+foods[i].w, depth+1 );
			isUsed[i] = false;
		}
	}
	return;
}

int main(void)
{
	int i;

	while( cin >> n ){
		if( n == 0 ) break;
		for( i=0; i<n; i++ ){	
			cin >> foods[i].name >> foods[i].w >> foods[i].s;
			isUsed[i] = false;
		}

		minG = INT_MAX;
		calc( 0, 0 );
		for( i=n-1; i>=0; i-- )
			cout << foods[ans[i]].name << endl;
	}
	return 0;
}