『ACM/ICPC国内予選突破の手引き』をやってみる（１）

解説がしっかりあって、難易度別、ジャンル別に体系付けられているACM/ICPC国内予選突破の手引きの問題を解いてみようと思います。

まずは”Step by step”から。

Problem 1129 : Hanafuda Shuffle

• 難易度 : ☆
• 種類 : シミュレーション

ベクターでカードの番号を管理して、並べ替えてみるだけ。

#include <iostream>
#include <vector>

using namespace std;


vector<int> cut( vector<int> src, int p, int c )
{
	vector<int> work = src;

	for( int i=0; i<p-1; i++ )
		work[i+c] = src[i];
	for( int i=0; i<c; i++ )
		work[i] = src[i+p-1];

	return work;
}

int main(void)
{
	int n, r, p, c, i;
	vector<int> cards;

	while( cin >> n >> r, n!=0 && r!=0 ){
		cards.clear();
		for( i=0; i<n; i++ )
			cards.push_back(n-i);

		for( i=0; i<r; i++ ){
			cin >> p >> c;
			cards = cut( cards, p, c );
		}

		cout << cards[0] << endl;
	}	

	return 0;
}

Problem 1135 : Ohgas' Fortune

• 難易度 : ☆
• 種類 : 文章読解

利子の計算、手数料の徴収は毎回変わらないのでそのまんま。
利子の加算について、単利だったら利子を毎回加算しない。けど初期化もしないで、最後に利子累計を加算する。複利だったら毎回加算して、利子を初期化しておく（次の年に残さない）。

#include <iostream>

using namespace std;


int main(void)
{
	int m, n, money, a, b, y, type, fee, max;
	int i, j, k;
	double rate;

	cin >> m;
	for( i=0; i<m; i++ ){
		cin >> money;
		cin >> y;
		cin >> n;

		max = 0;
		for( j=0; j<n; j++ ){
			cin >> type >> rate >> fee;
			a = money; b = 0;

			for( k=0; k<y; k++ ){
				b += a*rate;
				a -= fee;
				if( type ){
					a += b;
					b = 0;
				}
			}

			a += b;
			if( max < a )
				max = a;
		}

		cout << max << endl;
	}
	
	return 0;
}

Problem 2006 : Keitai Message

• 難易度 : ☆
• 種類 : シミュレーション

文字のテーブルを2次元配列で作る。文字が連続している数を数えて、テーブルをもとに出力するだけ。

#include <iostream>

using namespace std;


int main(void)
{
	int n, cnt;
	char ch1, ch2;
	char table[10][6] = {
		{ 0, 0, 0, 0, 0, 0 },
		{ 5, '.', ',', '!', '?', ' ' },
		{ 3, 'a', 'b', 'c', NULL, NULL },
		{ 3, 'd', 'e', 'f', NULL, NULL },
		{ 3, 'g', 'h', 'i', NULL, NULL },
		{ 3, 'j', 'k', 'l', NULL, NULL },
		{ 3, 'm', 'n', 'o', NULL , NULL },
		{ 4, 'p', 'q', 'r', 's', NULL },
		{ 3, 't', 'u', 'v', NULL, NULL },
		{ 4, 'w', 'x', 'y', 'z', NULL }
	};

	cin >> n; cin.get(ch1);
	while( n-- > 0 ){
		while( cin.get(ch1), ch1 != '\n' ){
			cnt = 0;

			while( cin.get(ch2), ch2 == ch1 )
				cnt++;

			if( ch2 == '0' )
				cout << table[ch1-'0'][cnt%table[ch1-'0'][0]+1];
			else
				cin.putback(ch2);
		}

		cout << endl;
	}

	return 0;
}