ACM_ICPC/Prepare Asia Regional Contest

Difference between r1.1 and the current

@@ -1,8 +1,10 @@

[[TableOfContents]]
== 관련 페이지 ==

* [ACM_ICPC]

* [ACM_ICPC/2011년스터디]
* [ACM_ICPC/2012년스터디]
* [ACM_ICPC/2013년스터디]

* [AlgorithmStudy/2015 | ACM_ICPC/2015년스터디]

== Past Problems ==

=== at On-line Preliminary Contest(Oct. 2, 2004) ===

1. 관련 페이지

2. Past Problems

2.1. at On-line Preliminary Contest(Oct. 2, 2004)

2.1.1. Solution of Problem C. Mine Sweeper
2.1.2. Solution of Problem F. Coin Game
2.1.3. Solution of Problem G. Safe

1. 관련 페이지 ¶

2. Past Problems ¶

2.1. at On-line Preliminary Contest(Oct. 2, 2004) ¶

2.1.1. Solution of Problem C. Mine Sweeper ¶

~cpp
#include <iostream>
#include <fstream>
using namespace std; 

int main() 
{ 
	ifstream fin;
	fin.open("C.in");
	
	int nTest;
	fin >> nTest;

	int nMine;
	for ( int t = 0 ; t < nTest ; t++ ){
		fin >> nMine;

		const int MAX = 1001;
		static int workspace[MAX][MAX];

		for ( int i = 0 ; i < MAX ; i++ )
			for ( int j = 0 ; j < MAX ; j++ )
				workspace[i][j] = 0;

		int x, y;

		for ( int m = 0 ; m < nMine ; m++ ){
			fin >> x >> y;
			workspace[x][y] = 1;
		}

		int max = 0;

		const int SQUARE_SIZE = 11;
		int count;
		for ( x = 0 ; x < MAX-SQUARE_SIZE ; x++ ){
			for ( y = 0 ; y < MAX-SQUARE_SIZE ; y++ ){
				count = 0;
				for ( int sx = 0 ; sx < SQUARE_SIZE ; sx++ )
					for ( int sy = 0 ; sy < SQUARE_SIZE ; sy++ )
						if ( workspace[x+sx][y+sy] == 1 )
							count++;
				if ( count > max )
					max = count;
			}
		}
		cout << " " << max << endl;
	}
	fin.close();
    return 0; 
}

2.1.2. Solution of Problem F. Coin Game ¶

Original Problem Text

~cpp
class Coin
{
private:
	char face;
public:
	void flip(){face = ( face == 'H' ) ? 'T' : 'H';}
	bool equals(const Coin & coin){ return this->face == coin.face; }
	void set(const char face ){ this->face = face; }
};
////////////////////////////////////////////////////////////////////////////////
const int MAX = 4;
const int SIZE = 3;
const int INT_MAX = 20000000;
////////////////////////////////////////////////////////////////////////////////
class Gamer
{
private:
	Coin coins[SIZE][SIZE];
public:
	void constructCoins( const char input[SIZE][SIZE] );
	void flipRow(int rowNum);
	void flipCol(int colNum);
	void flipAsc();
	void flipDsc();
	void flipLine(int direction);
	bool isEnd();
};
////////////////////////////////////////////////////////////////////////////////

class GameEngine
{
private:
	int minimum;
public:
	GameEngine(){ minimum = INT_MAX; }
	void storeCounts(Gamer & gamer, int count);
	int report();
};
////////////////////////////////////////////////////////////////////////////////
void GameEngine::storeCounts(Gamer & gamer, int count )
{
	for ( int i = 0 ; i < 8 ; i++ )
	{
		gamer.flipLine(i);
		count++;
		if ( gamer.isEnd() )
			minimum = ( minimum > count ) ? count : minimum;
		else if ( count < MAX )
		    storeCounts( gamer, count );
		gamer.flipLine(i);
		count--;
	}
}

int GameEngine::report()
{
	if ( minimum == INT_MAX )
	    return -1;
	else
	    return minimum;
}

////////////////////////////////////////////////////////////////////////////////
void Gamer::constructCoins( const char input[SIZE][SIZE] )
{
	for ( int row = 0 ; row < SIZE ; row++ )
	    for ( int col = 0 ; col < SIZE ; col++ )
			coins[row][col].set(input[row][col]);
}

void Gamer::flipRow(int rowNum)
{
	for ( int col = 0 ; col < SIZE ; col++ )
	    coins[rowNum][col].flip();
}

void Gamer::flipCol(int colNum)
{
	for ( int row = 0 ; row < SIZE ; row++ )
	    coins[row][colNum].flip();

}

void Gamer::flipAsc()
{
	coins[2][0].flip();
	coins[1][1].flip();
	coins[0][2].flip();
}

void Gamer::flipDsc()
{
    coins[0][0].flip();
    coins[1][1].flip();
    coins[2][2].flip();
}

void Gamer::flipLine(int direction)
{
	if ( direction < 3 )
		flipRow( direction % 3 );
	else if ( direction < 6 )
		flipCol( direction % 3 );
	else if ( direction == 6 )
	    flipAsc();
	else if ( direction == 7 )
	    flipDsc();
}

bool Gamer::isEnd()
{
	for ( int row = 0 ; row < SIZE ; row++ )
	    for ( int col = 0 ; col < SIZE ; col++ )
			if ( !coins[row][col].equals( coins[0][0] ) )
			    return false;
	return true;
}

#include <iostream>
using namespace std;

int main()
{
	Gamer gamer;
	GameEngine engine;
	char input[SIZE][SIZE];
	for ( int row = 0 ; row < SIZE ; row++ )
	    for ( int col = 0 ; col < SIZE ; col++ )
			cin >> input[row][col];

	gamer.constructCoins( input );
	engine.storeCounts(gamer, 0);
	cout << engine.report() << endl;
	system("pause");
	return 0;
}

2.1.3. Solution of Problem G. Safe ¶

Original Problem Text

~cpp
#include <iostream>
using namespace std;

int round(double n);
int fall(int N, int K);
int main()
{
	int nTest;
	cin >> nTest;
	int N,K;
	for ( int t = 0 ; t < nTest ; t++ ){
		cin >> N >> K;	
		cout << fall(N,K) << endl;
	}
	return 0;
}

int round(double n)
{
	return n+0.5;
}

int fall(int N, int K)
{
	if(K == 1 || N <= 1)
		return N;
	else
		return fall(round(N/2),K-1)+1;
}