Gap

[問題] ACM/ICPC Asia Regional 2003 Aizu: Problem F

[解説]

幅優先探索。
詳細は後日。

[サンプルプログラム]

001 #include<iostream>
002 #include<stdio.h>
003 #include<queue>
004 #include<map>
005 using namespace std;
006 
007 class Gap{
008     public:
009     short buffer[4][8];
010     short pos[50];
011     short space[4];
012     
013     Gap(){}
014     
015     bool solved(){
016         for ( int i = 0; i < 4; i++ ){
017             for ( int j = 1; j < 7; j++ ){
018                 if ( buffer[i][j] != (i+1)*10 + (j+1) ) return false;
019             }
020         }
021         return true;
022     }
023     
024     bool operator < ( const Gap &g ) const{
025         for ( int i = 0; i < 4; i++ ){
026             for ( int j = 0; j < 8; j++ ){
027                 if ( buffer[i][j] == g.buffer[i][j] ) continue;
028                 return buffer[i][j] < g.buffer[i][j];
029             }
030         }
031         return false;
032     }
033 };
034 
035 Gap initial;
036 
037 int bfs(){
038     queue<Gap> Q;
039     map<Gap, bool> visited;
040     map<Gap, int> cost;
041     
042     Q.push(initial);
043     cost[initial] = 0;
044     visited[initial] = true;
045     
046     Gap u, v;
047     
048     while( !Q.empty() ){
049         u = Q.front(); Q.pop();
050         if ( u.solved() ) return cost[u];
051         
052         int si, sj, target;
053         for ( int s = 0; s < 4; s++ ){
054             si = u.space[s]/8; sj = u.space[s]%8;
055             if ( u.buffer[si][sj-1] == 0 ||
056             u.buffer[si][sj-1]%10 == 7 ) continue;
057             
058             target = u.buffer[si][sj-1] + 1;
059             v = u;
060             v.buffer[si][sj] = target;
061             v.buffer[v.pos[target]/8][v.pos[target]%8] = 0;
062             v.space[s] = v.pos[target];
063             v.pos[target] = si*8 + sj;
064             
065             if ( !visited[v] ){
066                 visited[v] = true;
067                 cost[v] = cost[u] + 1;
068                 Q.push(v);
069             }
070         }
071     }
072     
073     return -1;
074 }
075 
076 void compute(){
077     for ( int i = 0; i < 4; i++ ){
078         int v = 10*(i+1) + 1;
079         initial.buffer[i][0] = v;
080         initial.space[i] = initial.pos[v];
081         initial.buffer[initial.pos[v]/8][initial.pos[v]%8] = 0;
082         initial.pos[v] = i*8;
083     }
084     cout << bfs() << endl;
085 }
086 
087 void input(){
088     int x;
089     for ( int i = 0; i < 4; i++ ){
090         for ( int j = 1; j < 8; j++ ){
091             cin >> x;
092             initial.buffer[i][j] = x;
093             initial.pos[x] = i*8 + j;
094         }
095     }
096 }
097 
098 main(){
099     int tcase; cin >> tcase;
100     for ( int i = 0; i < tcase; i++ ){
101         input();
102         compute();
103     }
104 }

Molecular Formula

[問題] ACM/ICPC Asia Regional 2003 Aizu: Problem E

[解説]

構文解析。
詳細は後日。

[サンプルプログラム]

001 #include<iostream>
002 #include<string>
003 #include<map>
004 #include<cassert>
005 using namespace std;
006 
007 map<string, int> T;
008 bool isUnknown;
009 int cursor;
010 string line;
011 
012 bool isDigit( char ch ){
013     return ( '0' <= ch && ch <= '9' );
014 }
015 
016 bool isLower( char ch ){
017     return ( 'a' <= ch && ch <= 'z' );
018 }
019 
020 int getDigit(){
021     string digit = "";
022     while( isDigit(line[cursor]) ){
023         digit += line[cursor++];
024     }
025     if ( digit == "" ) digit = "1";
026     return atoi( digit.c_str());
027 }
028 
029 int molecular(){
030     assert( line[cursor] == '(') ;
031     cursor++;
032     string str ="";
033     int total = 0;
034     
035     while(1){
036         if ( line[cursor] == ')' ) break;
037         str = "";
038         if ( line[cursor] == '(' ) {
039             total += molecular()*getDigit();
040         } else {
041             str += line[cursor++];
042             if ( isLower(line[cursor]) ) str += line[cursor++];
043             if ( T.find( str ) == T.end() ) isUnknown = true;
044             total += T[str]*getDigit();
045         }
046     }
047     cursor++;
048     return total*getDigit();
049 }
050 
051 void makeTable(){
052     string name;
053     int x;
054     while(1){
055         cin >> name;
056         if ( name == "END_OF_FIRST_PART" ) break;
057         cin >> x;
058         T[name] = x;
059     }
060 }
061 
062 main(){
063     makeTable();
064     while(1){
065         cin >> line;
066         if ( line == "0" ) break;
067         line = "(" + line + ")1";
068         isUnknown = false;
069         cursor = 0;
070         int w = molecular();
071         if ( isUnknown ) cout << "UNKNOWN" << endl;
072         else cout << w << endl;
073     }
074 }
075 

Weather Forecast

[問題] ACM/ICPC Asia Regional 2003 Aizu: Problem D

[解説]

深さ優先探索。探索空間をいかに小さくするかがポイント。
詳細は後日。

[サンプルプログラム]

001 #include<iostream>
002 #include<cassert>
003 using namespace std;
004 #define DMAX 370
005 #define SMAX 4096
006 #define SIZE 16
007 
008 static const int nextP[9+2][5] = {{0, 1, 2, 4, 8},
009                                  {0, 1, 2, 5, 9},
010                                  {0, 1, 2, 6, 10},
011                                  {-1, -1, -1, -1 -1},
012                                  {0, 4, 5, 6, 8},
013                                  {1, 4, 5, 6, 9},
014                                  {2, 4, 5, 6, 10},
015                                  {-1, -1, -1, -1 -1},
016                                  {0, 4, 8, 9, 10},
017                                  {1, 5, 8, 9, 10},
018                                  {2, 6, 8, 9, 10}};
019 
020 int nday;
021 int schedule[DMAX][SIZE];
022 int no_rainy[SIZE];
023 bool visited[DMAX][11][SMAX];
024 
025 bool checkFestival(int pos, int day ){
026     if ( schedule[day][pos + 0] == 1 ||
027         schedule[day][pos + 1] == 1 ||
028         schedule[day][pos + 4] == 1 ||
029         schedule[day][pos + 5] == 1 ) return true;
030     return false;
031 }
032 
033 bool check7NoRainy(){
034     for ( int i = 0; i < SIZE; i++ ){
035         if ( no_rainy[i] >= 7 ) return true;
036     }
037     return false;
038 }
039 
040 int getState(){
041     return no_rainy[0] + no_rainy[3]*8 + no_rainy[12]*64 + no_rainy[15]*512;
042 }
043 
044 bool recursive( int pos, int day ){
045     if ( day == nday ) return true;
046     visited[day][pos][getState()] = true;
047 
048     int tmp[SIZE];
049     for ( int i = 0; i < SIZE; i++ ) tmp[i] = no_rainy[i];
050 
051     for ( int n = 0; n < 5; n++ ){
052         if ( checkFestival( nextP[pos][n], day+1 ) ) continue;
053     
054         for ( int i = 0; i < SIZE; i++ ) no_rainy[i] = tmp[i];
055     
056         for ( int i = 0; i < SIZE; i++ ){
057             if ( i == pos || i == pos + 1 || i == pos + 4 || i == pos + 5 ) {
058                 no_rainy[i] = 0;
059             } else no_rainy[i]++;
060         }
061     
062         if ( check7NoRainy() ) continue;
063         if ( visited[day+1][nextP[pos][n]][getState()] ) continue;
064     
065         if ( recursive( nextP[pos][n], day+1 ) ) return true;
066     }
067 
068     return false;
069 }
070 
071 void compute(){
072     for ( int i = 0; i < SIZE; i++ ) no_rainy[i] = 0;
073     for ( int i = 0; i < DMAX; i++ ){
074         for (int  j = 0; j < 11; j++ ){
075             for ( int k = 0; k < SMAX; k++ ) visited[i][j][k] = false;
076         }
077     }
078 
079     if ( !checkFestival( 5, 0 ) && recursive( 5, 0 ) ) cout << 1 << endl;
080     else cout << 0 << endl;
081 }
082 
083 bool input(){
084     cin >> nday;
085     if ( nday == 0 ) return false;
086     for ( int i = 0; i < nday; i++ ){
087         for ( int j = 0; j < SIZE; j++ ) cin >> schedule[i][j];
088     }
089     for ( int j = 0; j < SIZE; j++ ) schedule[nday][j] = 0;
090 
091     return true;
092 }
093 
094 main(){
095     while ( input() ) compute();
096 }
097 

Area of Polygons

[問題] ACM/ICPC Asia Regional 2003 Aizu: Problem C

[解説]

プログラム・プロムナードを参考。
詳細は後日。

[サンプルプログラム]

001 #include<iostream>
002 #include<algorithm>
003 #include<vector>
004 #include<cassert>
005 #include<cmath>
006 using namespace std;
007 
008 #define MAX 100
009 #define SHIFT 2000
010 #define EPS 0.00000001
011 
012 class Point{
013     public:
014     double x, y;
015     Point(){}
016     Point(int x, int y):x(x), y(y){}
017 };
018 
019 class Segment{
020     public:
021     int left, right;
022     Segment(){}
023     Segment( int left, int right ): left(left), right(right){}
024     
025     bool operator < ( const Segment &s ) const{
026         if ( left == s.left ) return right < s.right;
027         else return left < s.left;
028     }
029 };
030 
031 int n;
032 Point P[MAX+1];
033 int minY, maxY;
034 
035 double getX( Point p1, Point p2, int y ){
036     assert( p1.y != p2.y );
037     return 1.0*(p2.x - p1.x)*(y - p1.y)/(p2.y - p1.y) + p1.x;
038 }
039 
040 void compute(){
041     int total = 0;
042     
043     for ( int y = minY; y <= maxY - 1; y++ ){
044         vector<Segment> targets;
045         for ( int i = 0; i < n; i++ ){
046             if ( P[i].y <= y && P[i+1].y <= y ||
047             P[i].y >= y+1 && P[i+1].y >= y+1 ) continue;
048             double x1, x2;
049             int left, right;
050             x1 = getX(P[i], P[i+1], y);
051             x2 = getX(P[i], P[i+1], y+1);
052             left = (int)(min( x1, x2 ));
053             right = (int)(max( x1, x2 ) + 1 - EPS);
054             targets.push_back( Segment( left, right ) );
055         }
056         
057         assert( targets.size() % 2 == 0 );
058         sort ( targets.begin(), targets.end() );
059         
060         int prev = 0;
061         for ( int i = 0; i < targets.size(); i += 2 ){
062             total += targets[i+1].right - max( targets[i].left, prev );
063             prev = targets[i+1].right;
064         }
065     }
066     
067     cout << total << endl;
068 }
069 
070 bool input(){
071     cin >> n;
072     if ( n == 0 ) return false;
073     int x, y;
074     minY = 2001;
075     maxY = -2001;
076     
077     for ( int i = 0; i < n; i++ ){
078         cin >> x >> y;
079         x += SHIFT; y += SHIFT;
080         minY = min( minY, y );
081         maxY = max( maxY, y );
082         P[i] = Point(x, y);
083     }
084     P[n] = P[0];
085     
086     return true;
087 }
088 
089 main(){
090     while( input() ) compute();
091 }

Lagrange's Four-Square Theorem

[問題] ACM/ICPC Asia Regional 2003 Aizu: Problem B

[解説]

総当り、または動的計画法。
詳細は後日。

[サンプルプログラム]

001 #include<iostream>
002 using namespace std;
003 #define MAX 32768
004 
005 int T[MAX+1];
006 
007 main(){
008     for ( int i = 1; i <= MAX; i++ ) T[i] = 0;
009     for ( int i = 0; i*i <= MAX; i++ ) {
010         for ( int j = i; i*i + j*j <= MAX; j++ ) {
011             for ( int k = j; i*i+j*j+k*k <= MAX; k++ ){
012                 for ( int l = k; i*i+j*j+k*k+l*l <= MAX; l++ ){
013                     T[i*i + j*j + k*k + l*l]++;
014                 }
015             }
016         }
017     }
018     
019     int n;
020     
021     while (1){
022         cin >> n;
023         if ( n == 0 ) break;
024         cout << T[n] << endl;
025     }
026 }

Unreliable Message

[問題] ACM/ICPC Asia Regional 2003 Aizu: Problem A

[解説]

文字列操作。

[サンプルプログラム]

001 #include<iostream>
002 #include<string>
003 #include<algorithm>
004 
005 using namespace std;
006 
007 void shiftRight( string &line ){
008     line = line[line.size()-1] + line.substr(0, line.size()-1);
009 }
010 
011 void shiftLeft( string &line ){
012     line = line.substr(1, line.size()-1 ) + line[0];
013 }
014 
015 void swapHalf( string &line ){
016     int mid = line.size()/2;
017     if ( line.size() % 2 == 0 )
018     line = line.substr(mid, line.size()-mid) + line.substr(0, mid);
019     else
020     line = line.substr(mid + 1, mid) + line[mid] + line.substr(0, mid);
021 }
022 
023 void reverse( string &line){
024     reverse( line.begin(), line.end() );
025 }
026 
027 void decrement( string &line ){
028     for ( int i = 0; i < line.size(); i++ ){
029         if ( isalpha(line[i]) ) continue;
030         if ( line[i] == '0' ) line[i] = '9';
031         else line[i]--;
032     }
033 }
034 
035 void increment( string &line ){
036     for ( int i = 0; i < line.size(); i++ ){
037         if ( isalpha(line[i]) ) continue;
038         if ( line[i] == '9' ) line[i] = '0';
039         else line[i]++;
040     }
041 }
042 
043 
044 main(){
045     int tcase; cin >> tcase;
046     string command, line;
047     
048     for ( int i = 0; i < tcase; i++ ){
049         cin >> command >> line;
050         
051         for ( int c = command.size()-1; c >= 0; c-- ){
052             if ( command[c] == 'J' ) shiftRight( line );
053             else if ( command[c] == 'C' ) shiftLeft( line );
054             else if ( command[c] == 'E' ) swapHalf( line );
055             else if ( command[c] == 'A' ) reverse( line );
056             else if ( command[c] == 'P' ) decrement( line );
057             else if ( command[c] == 'M' ) increment( line );
058         }
059         
060         cout << line << endl;
061     }
062 }

ACM/ICPC 2003 Aizu

ID	問題	難易度	考察
A	Unreliable Message	★	-
B	Lagrange:s Four-Square Theorem	★☆	-
C	Area of Polygons	★★★☆	-
D	Weather Forecast	★★★	-
E	Molecular Formula	★★☆	-
F	Gap	★★★☆	-
G	Concert Hall Scheduling	★★★★	-
H	Monster Trap	★★★★★	grave