我也有够懒的，今天才跑来写总结，自觉面壁中…
上一篇是Practice Round，今天是Round A，五道题。
每次做完都想说，其实题不难。。但在做的过程中总是会各种卡，只有自己一行一行实现了，才算真正做过一道题，忌眼高手低啊~没做过的先自己做做吧。
Problem A. Read Phone Number
For example, In China, the phone numbers are 11 digits, like: 15012233444. Someone divides the numbers into 3-4-4 format, i.e. 150 1223 3444. While someone divides the numbers into 3-3-5 format, i.e. 150 122 33444. Different formats lead to different ways to read these numbers:
150 1223 3444 reads one five zero one double two three three triple four.
150 122 33444 reads one five zero one double two double three triple four.
Here comes the problem:
Given a list of phone numbers and the dividing formats, output the right ways to read these numbers.
Rules:
Single numbers just read them separately.
2 successive numbers use double.
3 successive numbers use triple.
4 successive numbers use quadruple.
5 successive numbers use quintuple.
6 successive numbers use sextuple.
7 successive numbers use septuple.
8 successive numbers use octuple.
9 successive numbers use nonuple.
10 successive numbers use decuple.
More than 10 successive numbers read them all separately.
Input
The first line of the input gives the number of test cases, T. T lines|test cases follow. Each line contains a phone number N and the dividing format F, one or more positive integers separated by dashes (-), without leading zeros and whose sum always equals the number of digits in the phone number.
Output
For each test case, output one line containing "Case #x: y", where x is the case number (starting from 1) and y is the reading sentence in English whose words are separated by a space.
Limits
1 ≤ T ≤ 100.
Small dataset
1 ≤ length of N ≤ 10.
Large dataset
1 ≤ length of N ≤ 100.
Sample
| Input |
|
3 |
|
|
|
|
| Output |
|
Case #1: one five zero one double two three three triple four |
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std; void ReadPhoneNumber()
{
string times[] = {"double", "triple", "quadruple", "quintuple", "sextuple", "septuple", "octuple", "nonuple", "decuple"};
string number[] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine"};
int T;
cin >> T;
for(int i = ; i <= T; ++i)
{
cout << "Case #" << i << ": ";
string N, F;
cin >> N >> F;
int FInd1 = ;
int FInd2 = ;
int NInd1 = ;
int NInd2 = ;
int index = ;
while(FInd2 < F.length())
{
int divNum = ;
while(FInd2 < F.length() && F[FInd2] != '-')
FInd2++;
while(FInd1 < FInd2)
{
divNum = * divNum + F[FInd1] - '';
FInd1++;
}
index += divNum;
FInd2++;
FInd1 = FInd2;
int repNum = ;
int j = ;
while(j < divNum)
{
while(NInd2 < index && N[NInd2] == N[NInd1])
{
repNum++;
NInd2++;
}
if(NInd2 == N.length())
{
if(repNum > && repNum < )
{
cout << times[repNum-] << ' ';
cout << number[N[NInd1]-''];
}
else
{
while(NInd1 < NInd2 - )
{
cout << number[N[NInd1]-''] << ' ';
NInd1++;
}
cout << number[N[NInd1]-''];
}
}
else{
if(repNum > && repNum < )
{
cout << times[repNum-] << ' ';
cout << number[N[NInd1]-''] << ' ';
}
else
{
while(NInd1 < NInd2)
{
cout << number[N[NInd1]-''] << ' ';
NInd1++;
}
}
}
j += repNum;
repNum = ;
NInd1 = NInd2;
NInd2++;
}
}
if(i < T)
cout << endl;
}
} int main()
{
freopen("A-large-practice.in", "r", stdin);
freopen("A-large-practice.out", "w", stdout);
ReadPhoneNumber();
return ;
}
Problem B. Rational Number Tree
1/1
______|______
| |
1/2 2/1
___|___ ___|___
| | | |
1/3 3/2 2/3 3/1
...
It is known that every positive rational number appears exactly once in this tree. A level-order traversal of the tree results in the following array:
1/1, 1/2, 2/1, 1/3, 3/2, 2/3, 3/1, ...
Please solve the following two questions:
- Find the n-th element of the array, where n starts from 1. For example, for the input 2, the correct output is 1/2.
- Given p/q, find its position in the array. As an example, the input 1/2 results in the output 2.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of one line. The line contains a problem id (1 or 2) and one or two additional integers:
- If the problem id is 1, then only one integer n is given, and you are expected to find the n-th element of the array.
- If the problem id is 2, then two integers p and q are given, and you are expected to find the position of p/q in the array.
Output
For each test case:
- If the problem id is 1, then output one line containing "
Case #x: p q", wherexis the case number (starting from 1), andp,qare numerator and denominator of the asked array element, respectively. - If the problem id is 2, then output one line containing "
Case #x: n", wherexis the case number (starting from 1), andnis the position of the given number.
Limits
1 ≤ T ≤ 100; p and q are relatively prime.
Small dataset
1 ≤ n, p, q ≤ 216-1; p/q is an element in a tree with level number ≤ 16.
Large dataset
1 ≤ n, p, q ≤ 264-1; p/q is an element in a tree with level number ≤ 64.
Sample
| Input |
Output |
4 |
Case #1: 1 2 |
#include <iostream>
#include <fstream>
using namespace std; void RationalNumberTreeId1(unsigned long long n, unsigned long long &p, unsigned long long &q)
{
if (n == )
{
p = ;
q = ;
return;
}
RationalNumberTreeId1(n/, p, q);
if((n & ) == )
{
p = p+q;
return;
}
else
{
q = p+q;
return;
}
} void RationalNumberTreeId2(unsigned long long p, unsigned long long q, unsigned long long &n)
{
if(p == && q == )
{
n = ;
return;
}
if(p > q)
{
RationalNumberTreeId2(p - q, q, n);
n = * n + ;
}
else
{
RationalNumberTreeId2(p, q - p, n);
n = * n;
}
} void RationalNumberTree()
{
int T;
cin >> T;
for(int i = ; i <= T; ++i)
{
cout << "Case #" << i << ": ";
int id;
cin >> id;
switch(id)
{
case():
unsigned long long n1;
cin >> n1;
unsigned long long p1,q1;
RationalNumberTreeId1(n1, p1, q1);
cout << p1 << " " << q1;
break;
case():
unsigned long long p2, q2;
cin >> p2 >> q2;
unsigned long long n2 = ;
RationalNumberTreeId2(p2, q2, n2);
cout << n2;
break;
}
if(i < T)
cout << endl;
}
} int main()
{
freopen("B-large-practice.in","r",stdin);
freopen("B-large-practice.out","w",stdout);
RationalNumberTree();
return ;
}
Problem C. Sorting
Unfortunately, Alex and Bob went outside and didn't know what their father did. When they were back, they came to realize the problem: they usually arranged their books in their own orders, but the books seem to be in a great mess on the bookshelf now. They have to sort them right now!!
Each book has its own worth, which is represented by an integer. Books with odd values of worth belong to Alex and the books with even values of worth belong to Bob. Alex has a habit of sorting his books from the left to the right in an increasing order of worths, while Bob prefers to sort his books from the left to the right in a decreasing order of worths.
At the same time, they do not want to change the positions of the labels, so that after they have finished sorting the books according their rules, each book's owner's name should match with the label in its position.
Here comes the problem. A sequence of N values s0, s1, ..., sN-1 is given, which indicates the worths of the books from the left to the right on the bookshelf currently. Please help the brothers to find out the sequence of worths after sorting such that it satisfies the above description.
Input
The first line of input contains a single integer T, the number of test cases. Each test case starts with a line containing an integer N, the number of books on the bookshelf. The next line contains N integers separated by spaces, representing s0, s1, ..., sN-1, which are the worths of the books.
Output
For each test case, output one line containing "Case #X: ", followed by t0, t1, ..., tN-1 in order, and separated by spaces. X is the test case number (starting from 1) and t0, t1, ...,tN-1 forms the resulting sequence of worths of the books from the left to the right.
Limits
1 ≤ T ≤ 30.
Small dataset
1 ≤ N ≤ 100
-100 ≤ si ≤ 100
Large dataset
1 ≤ N ≤ 1000
-1000 ≤ si ≤ 1000
Sample
| Input |
Output |
2 |
Case #1: 1 4 2 3 5 |
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std; bool myfunction (int i,int j)
{
return (i > j);
} void Sorting()
{
int T;
cin >> T;
for(int i = ; i <= T; ++i)
{
cout << "Case #" << i << ": ";
int pos1[], pos2[];
memset(pos1, -, );
memset(pos1, -, );
int ord1[], ord2[];
int num1 = ;
int num2 = ;
int book[];
int N;
cin >> N;
for(int j = ; j < N; ++j)
{
cin >> book[j];
if(book[j] & == )
{
pos1[num1] = j;
ord1[num1] = book[j];
num1++;
}
else
{
pos2[num2] = j;
ord2[num2] = book[j];
num2++;
}
}
vector<int> myvector1 (ord1, ord1 + num1);
sort (myvector1.begin(), myvector1.begin() + num1);
vector<int> myvector2 (ord2, ord2 + num2);
sort (myvector2.begin(), myvector2.begin() + num2, myfunction);
int index = ;
for (vector<int>::iterator it=myvector1.begin(); it!=myvector1.end(); ++it)
{
book[pos1[index++]] = *it;
}
index = ;
for (vector<int>::iterator it=myvector2.begin(); it!=myvector2.end(); ++it)
{
book[pos2[index++]] = *it;
}
for(int j = ; j < N-; ++j)
{
cout << book[j] << ' ';
}
cout << book[N-];
if(i < T)
cout << endl;
}
} int main()
{
freopen("C-large-practice.in", "r", stdin);
freopen("C-large-practice.out", "w", stdout);
Sorting();
return ;
}
Problem D. Cross the maze
Assume that Edison has found himself in a square-shaped maze of NxN square cells which is surrounded by walls from the outside. In the maze, some of the cells are also walls. Edison can only move between two empty cells in four directions, north, south, west and east. In order to get out of the maze, he drafts a plan. He uses his left hand to lean on the wall and goes by following the wall.
Here is the question, is Edison able to get out of the maze in at most 10,000 steps? If he can make it, output the path. By getting out of the maze, he only needs to be in the exit cell. If the starting cell is the same as the exit, Edison won't need to move and can directly get out of the maze.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with an integer N. N is the size of the maze. The following N lines, each line contains N characters which may be '.' or '#'. '.' is an empty cell, '#' is a wall. Followed by a line which contains four integers: sx, sy, ex, ey. (sx, sy) means that Edison is standing on row sx and column sy as his starting cell, (ex, ey) is the exit of the maze. (sx, sy) is guaranteed to be at one of the 4 corners of the maze, and Edison can only touch the wall on 4 adjacent cells(not 8) initially. (ex, ey) can be anywhere in the maze. Note that the top-left corner is at position (1,1).
Output
For each test case, output a line containing "Case #x: y", where x is the case number (starting from 1) and y is "Edison ran out of energy." (without the quotes) if Edison can't reach the exit of the maze in at most 10,000 steps, otherwise y should be the number of steps followed by another line which contains y characters to describe the path (each character should be E for east, S for south, W for west or N for north). There is no character to represent the turning around. We don't care about the turning around steps, please only output the path of how Edison will cross the maze.
Limits
1 ≤ T ≤ 30.
1 ≤ sx, sy, ex, ey ≤ N.
The starting cell and the exit of the maze will always be an empty cell. And the starting cell and the exit of the maze won't be the same.
Small dataset
2 ≤ N ≤ 10.
Large dataset
2 ≤ N ≤ 100.
Sample
| Input |
Output |
3 |
Case #1: Edison ran out of energy. |
Note:
In the 2nd test case after moving 1 cell down from his starting cell, Edison will still be able to lean on the wall at the cell (1,2) by his left hand.
In the third test case, due to Edison can't touch the wall at cell (2,2) initially, so he has to go east in his first step.
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std; bool Adjacent(int x1, int y1, int x2, int y2)
{
if(x1 - x2 > || x2 - x1 > || y1 - y2 > || y2 - y1 > )
return false;
return true;
} void CrossTheMaze()
{
int T;
cin >> T;
for(int i = ; i <= T; ++i)
{
cout << "Case #" << i << ": ";
int N;
cin >> N;
char **maze;
maze = new char*[N];
for(int j = ; j < N; ++j)
maze[j] = new char[N];
for(int j = ; j < N; ++j)
{
for(int k = ; k < N; ++k)
cin >> maze[j][k];
}
int sx, sy, ex, ey;
cin >> sx >> sy >> ex >> ey;
sx -= ;
sy -= ;
ex -= ;
ey -= ;
int cx = sx, cy = sy;
vector<char> path;
char flag;
int wx, wy;
if(sx == )
{
if(sy == )
{
wx = -;
wy = ;
flag = 'e';
}
else
{
wx = ;
wy = N;
flag = 's';
}
}
else
{
if(sy == )
{
wx = N-;
wy = -;
flag = 'n';
}
else
{
wx = N;
wy = N-;
flag = 'w';
}
}
int turn = ;
for(int j = ; j <= && (cx != ex || cy != ey);)
{
bool n = (cx > && maze[cx-][cy] == '.') && (((cy == || maze[cx][cy-] == '#') && Adjacent(cx,cy-,wx,wy)) || (cy > && maze[cx-][cy-] == '#' && flag == 'e'));
bool s = (cx < N- && maze[cx+][cy] == '.') && (((cy == N- || maze[cx][cy+] == '#') && Adjacent(cx,cy+,wx,wy)) || (cy < N- && maze[cx+][cy+] == '#' && flag == 'w'));
bool w = (cy > && maze[cx][cy-] == '.') && (((cx == N- || maze[cx+][cy] == '#') && Adjacent(cx+,cy,wx,wy)) || (cx < N- && maze[cx+][cy-] == '#' && flag == 'n'));
bool e = (cy < N- && maze[cx][cy+] == '.') && (((cx == || maze[cx-][cy] == '#') && Adjacent(cx-,cy,wx,wy)) || (cx > && maze[cx-][cy+] == '#' && flag == 's'));
if(n||s||w||e)
{
if(n && flag != 's')
{
turn = ;
++j;
cx -= ;
path.push_back('N');
flag = 'n';
if(cy == || maze[cx][cy-] == '#')
{
wx = cx;
wy = cy-;
}
else
{
wx = cx+;
wy = cy-;
}
}
else if(s && flag != 'n')
{
turn = ;
++j;
cx += ;
path.push_back('S');
flag = 's';
if(cy == N- || maze[cx][cy+] == '#')
{
wx = cx;
wy = cy+;
}
else
{
wx = cx-;
wy = cy+;
}
}
else if(w && flag != 'e')
{
turn = ;
++j;
cy -= ;
path.push_back('W');
flag = 'w';
if(cx == N- || maze[cx+][cy] == '#')
{
wx = cx+;
wy = cy;
}
else
{
wx = cx+;
wy = cy+;
}
}
else if(e && flag != 'w')
{
turn = ;
++j;
cy += ;
path.push_back('E');
flag = 'e';
if(cx == || maze[cx-][cy] == '#')
{
wx = cx-;
wy = cy;
}
else
{
wx = cx-;
wy = cy-;
}
}
}
else
{
if(flag == 'n' && Adjacent(cx-,cy,wx,wy))
{
flag = 'e';
wx = cx-;
wy = cy;
++turn;
}
else if(flag == 's' && Adjacent(cx+,cy,wx,wy))
{
flag = 'w';
wx = cx+;
wy = cy;
++turn;
}
else if(flag == 'w' && Adjacent(cx,cy-,wx,wy))
{
flag = 'n';
wx = cx;
wy = cy-;
++turn;
}
else if(flag == 'e' && Adjacent(cx,cy+,wx,wy))
{
flag = 's';
wx = cx;
wy = cy+;
++turn;
}
else
break;
if(turn == )
break;
}
}
if(cx == ex && cy == ey)
{
cout << path.size() << endl;
for(vector<char>::iterator it = path.begin(); it != path.end(); ++it)
cout << *it;
}
else
cout << "Edison ran out of energy.";
if(i < T)
cout << endl;
for(int j = ; j < N; ++j)
delete [] maze[j];
delete [] maze;
}
} int main()
{
freopen("D-large-practice.in","r",stdin);
freopen("D-large-practice.out","w",stdout);
CrossTheMaze();
return ;
}
Problem E. Spaceship Defence
Teleporters allow your soldiers to move instantly between rooms. Every room contains a teleporter, and rooms are color-coded: if a soldier is in a room with some color, she can use the teleporter in that room to immediately move to any other room with the same color.
Turbolifts allow your soldiers to move between rooms more slowly. A turbolift is like an elevator that moves in many directions. Each turbolift moves from one room to one other room, and it takes a certain amount of time to travel. Notes about turbolifts:
- Turbolifts are not two-way: if a turbolift moves soldiers from room
ato roomb, the same turbolift cannot move soldiers from roombto rooma, although there might be another turbolift that does that. - More than one soldier can use the same turbolift, and they do not interfere with each other in any way.
You will be given the locations and destinations of several soldiers. For each soldier, output the minimum amount of time it could take that soldier to travel from his location to his destination.
Input
The first line of the input gives the number of test cases, T. T test cases follow.
For every test case:
The first line of every test case contains an integer N, which is the number of rooms in your spaceship. The rooms are numbered from 1 to N. The following N lines each contain a string telling the color of the rooms, from room 1 to room N. The strings only contain characters a-z (the lower-case English letters) and 0-9 (the number 0 to 9), and the length of each string will be less than or equal to 2.
The next line in the test case is an integer M, which indicates the number of turbolifts in your spaceship. The following M lines each contain 3 space-separated integers ai, bi, ti, telling us that there is a turbolift that can transport soldiers from room ai to room bi in tiseconds.
The next line in the test case contains an integer S, which is the number of soldiers at your command. The following S lines each contain two integers: the location and destination of one soldier, pj and qj.
Output
For each test case, output one line containing only the string "Case #x:", where x is the number of the test case (starting from 1). On the next S lines, output a single integer: on line j, the smallest number of seconds it could take for a soldier to travel from pj to qj. If there is no path from pj to qj, the integer you output should be -1.
Limits
1 ≤ S ≤ 100.
1 ≤ ai, bi ≤ N.
0 ≤ ti ≤ 1000.
1 ≤ pj, qj ≤ N.
Small dataset
1 ≤ T ≤ 10.
1 ≤ N ≤ 1000.
0 ≤ M ≤ 3000.
Large dataset
T = 1.
1 ≤ N ≤ 80000.
0 ≤ M ≤ 3000.
Sample
| Input |
Output |
3 |
Case #1: |
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
using namespace std; int shortest[][]; void SpaceshipDefence()
{
int T;
cin >> T;
for(int i = ; i <= T; ++i)
{
cout << "Case #" << i << ":" << endl;
long N;
cin >> N;
int *roomColor;
roomColor = new int[N];
for(int j = ; j < ; ++j)
{
for(int k = ; k < ; ++k)
shortest[j][k] = 0x7FFF;
shortest[j][j] = ;
}
string color;
map<string, int> colorMap;
for(long j = ; j < N; ++j)
{
cin >> color;
if(!colorMap.count(color))
colorMap.insert(pair<string,int>(color, colorMap.size()));
roomColor[j] = colorMap[color];
}
int M;
cin >> M;
unsigned long a, b, t;
for(int j = ; j <= M; ++j)
{
cin >> a >> b >> t;
a -= ;
b -= ;
if(shortest[roomColor[a]][roomColor[b]] > t)
shortest[roomColor[a]][roomColor[b]] = t;
}
for(long u = ; u < colorMap.size(); ++u)
{
for(long v = ; v < colorMap.size(); ++v)
{
for(long w = ; w < colorMap.size(); ++w)
{
if(shortest[v][u] + shortest[u][w] < shortest[v][w])
shortest[v][w] = shortest[v][u] + shortest[u][w];
}
}
}
int S;
cin >> S;
long p, q;
for(int j = ; j <= S; ++j)
{
cin >> p >> q;
p -= ;
q -= ;
if(shortest[roomColor[p]][roomColor[q]] == 0x7FFF)
cout << - << endl;
else
cout << shortest[roomColor[p]][roomColor[q]] << endl;
}
delete [] roomColor;
}
} int main()
{
freopen("E-large-practice.in","r",stdin);
freopen("E-large-practice.out","w",stdout);
SpaceshipDefence();
return ;
}
这个里面一个刚开始没想到的问题是，既然同color间传送耗时为0，那么就不用计算所有room之间的最短距离，只需计算所有color间的最短距离即可，这样求最短路的矩阵大小就不用N×N了（不然large dataset，N=80000就hold不住了），而color最多是36*36种，也就一千多种。另外，这么大的矩阵貌似就不能在函数间传递或者在调用的函数中申请了，用全局变量就可以了。