ACM_ICPC/PrepareAsiaRegionalContest (rev. 1.4)
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 ¶
~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 ¶
~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;
}
