ROUND 1A
Problem A. Seven-segment Display
Tom is a boy whose dream is to become a scientist, he invented a lot in his spare time. He came up with a great idea several days ago: to make a stopwatch by himself! So he bought a seven-segment display
immediately.
The seven elements of the display are all light-emitting diodes (LEDs) and can be lit in different combinations to represent the arabic numerals like:
However, just when he finished the programs and tried to test the stopwatch, some of the LEDs turned out to be broken! Some of the segments can never be lit while others worked fine. So the display kept
on producing some ambiguous states all the time...
Tom has recorded a continuous sequence of states which were produced by the display and is curious about whether it is possible to understand what this display was doing. He thinks the first step is to
determine the state which the display will show next, could you help him?
Please note that the display works well despite those broken segments, which means that the display will keep on counting down cyclically starting from a certain number (can be any one
of 0-9 since we don't know where this record starts from). 'Cyclically' here means that each time when the display reaches 0, it will keep on counting down starting from 9 again.
For convenience, we refer the seven segments of the display by the letters A to G as the picture below:
For example, if the record of states is like:
It's not that hard to figure out that ONLY segment B is broken and the sequence of states the display is trying to produce is simply "9 -> 8 -> 7 -> 6 -> 5". Then the next number should be 4, but considering
of the brokenness of segment B, the next state should be:
Input
The first line of the input gives the number of test cases, T. Each test case is a line containing an integer N which is the number of states Tom recorded and a list of
the Nstates separated by spaces. Each state is encoded into a 7-character string represent the display of segment A-G, from the left to the right. Characters in the string can either be '1' or '0', denoting the corresponding segment is on
or off, respectively.
Output
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1). If the input unambiguously determines the next state of the display, y should be that next
state (in the same format as the input). Otherwise, y should be "ERROR!".
Limits
1 ≤ T ≤ 2000.
Small dataset
1 ≤ N ≤ 5.
Large dataset
1 ≤ N ≤ 100.
Sample
妹的，
这个题想到了
- 给出一个mask（在当前n个数字中亮过的segments），则127-mask为没有亮过的segments。没有亮过的segment有可能坏了，也有可能n个数没有用到该segment。
- 接下来枚举第一个数字（从0到9），判断后续数字是否满足和mask进行与操作之后刚好等于给出的串。如果存在不等，则该方案不成立。
- 如果都相等，则要判断已经出现的数字用到的所有segments（设为t），那么t中的segment要么坏了，要么亮过；而剩余的（127-t）的segments不能判断是否坏了。
- 如果下一个数字和127-t进行与，不为0，那这里又存在多种情况。根据题意，只能存在一种情况，所以这里就是error了。
- 如果存在多种枚举方案，那也返回error
但是奇葩的没有过大数据@@
#include <iostream>
#include <string.h>
#include <queue>
#include <assert.h>
#include <map>
using namespace std;
int a[10]={// each bit stands for segment [A,B,C,D,E,F,G] should be lighted or not
//0, 1, 2, 3... 9
0B1111110, 0B0110000, 0B1101101, 0B1111001, 0B0110011,
0B1011011, 0B1011111, 0B1110000, 0B1111111, 0B1111011
};
int main(){
int t; cin>>t;
int num[100];
int ss=127;
for(int casei=1; casei<=t; casei++){
int mask=0;
int n; cin>>n;
for(int i=0; i<n; i++){
char a[8]; cin>>a;
int t=0;
for(int j=0; j<7; j++){
if(a[j]=='1')
t+=(1<<(6-j));
}
num[i]=t;
mask=mask|t;
}
int i, j;
int idx=-1, cnt=0;
//int t=0; //@error: t should be set to 0 inside loop-i
for(i=0; i<10; i++){
int t=0;
for(j=0; j<n; j++){
int m=(100+i-j)%10;
t=t|a[m];
if(num[j]!=(a[m]&mask)) break;//find a number not match
}
t=127-t;// segments which are not sure to be good or bad
if(j==n) {// find answer
int m=(100+i-n)%10; //test the last number, to see if it uses segments that are not surely good or bad
if(a[m]&t) {cnt+=2; break;}//it uses these unsure segments, so the answer is not unique!!
cnt++;
if(cnt>1) break;//find multi i, so the answer is not unique!!
idx=i;
}
}
cout<<"Case #"<<casei<<": ";
if(cnt==1){
int m=(100+idx-n)%10; //the last number
int t=a[m]&mask; //which only uses segments that are surely good or bad
char ans[8]; ans[7]=0;
for(int k=0; k<7; k++){
if(t&(1<<(6-k))) ans[k]='1';
else ans[k]='0';
}
cout<<ans<<endl;
}
else{
cout<<"ERROR!"<<endl;
}
}
return 0;
}
Problem B. Super 2048
Guide to get started.
|
Small input 6 points |
|
|
Large input 13 points |
|
Problem
2048 is a famous single-player game in which the objective is to slide tiles on a grid to combine them and create a tile with the number 2048.
2048 is played on a simple 4 x 4 grid with tiles that slide smoothly when a player moves them. For each movement, the player can choose to move all tiles in 4 directions, left, right, up, and down, as far as possible at the same time. If two tiles of the
same number collide while moving, they will merge into a tile with the total value of the two tiles that collided. In one movement, one newly created tile can not be merged again and always is merged with the tile next to it along the moving direction
first. E.g. if the three "2" are in a row "2 2 2" and the player choose to move left, it will become "4 2 0", the most left 2 "2" are merged.
The above figure shows how 4 x 4 grid varies when player moves all tiles 'right'.
Alice and Bob accidentally find this game and love the feel when two tiles are merged. After a few round, they start to be bored about the size of the board and decide to extend the size of board to N x N, which they called
the game "Super 2048".
The big board then makes them dazzled (no zuo no die -_-| ). They ask you to write a program to help them figure out what the board will be looked like after all tiles move to one specific direction on a given board.
Input
The first line of the input gives the number of test cases, T. T test cases follow. The first line of each test case gives the side length of the board, N, and the direction the tiles will move to, DIR. N and DIR are
separated by a single space. DIR will be one of four strings: "left", "right", "up", or "down".
The next N lines each contain N space-separated integers describing the original state of the board. Each line represents a row of the board (from top to bottom); each integer represents the value of a tile (or 0 if there
is no number at that position).
Output
For each test case, output one line containing "Case #x:", where x is the test case number (starting from 1). Then output N more lines, each containing N space-separated integers which describe the board after the move in
the same format as the input.
Limits
Each number in the grid is either 0 or a power of two between 2 and 1024, inclusive.
Small dataset
1 ≤ T ≤ 20
1 ≤ N ≤ 4
Large dataset
1 ≤ T ≤ 100
1 ≤ N ≤ 20
Sample
Problem C. Addition
Guide to get started.
|
Small input 11 points |
|
|
Large input 19 points |
|
Problem
Six years ago, a robot, Bob, with infant's intelligence has been invented by an evil scientist, Alice.
Now the robot is six years old and studies in primary school. Addition is the first operation he learned in math. Due to his strong reasoning ability, he could now conclude a+b=12 from a=2 and b=10.
Alice wanted to test Bob's addition skills. Some equations were given to Bob in form of a=2, b=10, c=4, and Bob has to find out the answers of questions like a+b, a+c, etc.
Alice checked Bob's answers one by one in the test papers, and no mistake has been found so far, but Alice lost the given equations after a cup of coffee poured on them. However she has some of Bob's correct answers, e.g. a+b=12, a+c=6, c+d=5. She wants
to continue with the checkable equations, e.g. b+d=11 could be concluded by a+b=12, a+c=6, c+d=5, and thus the question b+d is checkable.
To prevent the artificial intelligence technology from being under the control of Alice, you disguised yourself as her assistant. Now Alice wants you to figure out which of the rest of questions are checkable and their answers.
Input
The first line of the input gives the number of test cases, T. T test cases follow.
The first line of each test case contains a single integer N: the number of correctly answered questions. Each of the next N lines contain one correctly answered question in the form "x+y=z",
where x and y are names of variables and z is a decimal integer.
The next line contains a single integer Q: the number of remaining questions. Each of the next Q lines contain one question in the form "x+y", where x and y are
names of variables.
Output
For each test case, the first line of output contains "Case #x:", where x is the test case number (starting from 1). For each question in the input that was checkable, output a single line with the answer in the form "x+y=z",
where x and y are names of variables andz is a decimal integer. Questions should be listed in the same order as they were given in the input. Please do NOT ignore duplicated questions, since
Alice would fire you if you pointed any mistake of hers.
Limits
Names of variables are strings of lowercase English letters. Each name contains at most 10 characters.
-200000 ≤ z ≤ 200000
There is no contradiction in the answered questions and if the answer is checkable, the result is an integer.
Small dataset
T ≤ 10
N ≤ 10
Q ≤ 10
Large dataset
T ≤ 3
N ≤ 5000
Q ≤ 5000
Sample
仔细观察发现，想要得到 xi + xj， 必须遵循的步骤是： （xi + xj1)-(xj1+xj2)+(xj2+xj3)-(xj3-xj4).....+(xjk+xj)
也容易发现，这个过程中用到的所有向量 <xjn, xj(n+1) > 的系数都是非1即-1， 而且系数为1的次数比为-1的多1。（而且用到的向量总个数为奇数）
于是这个题目等价于 找图中一条路经，他从点xi 出发， 到达 xj，并且途中经过了奇数条边，即距离为奇数。
怎么寻找这样一条奇数长路径呢？想到一种方法是floyd的变形。
方法一：
dist[j][k][0/1] , 0 表示j到k有偶数长路， 1表示有奇数长路,
for i = 1 to N :
for j = 1 to N:
for k=1 to N:
dist[j][k][0]!=1? dist[j][i][0]==1 && dist[i][k][0]==1 || dist[j][i][1]==1 && dist[i][k][1]==1 //奇数*2 偶数*2 = 偶数
dist[j][k][1]!=1? dist[j][i][0]==1 && dist[i][k][1]==1 || dist[j][i][1]==1 && dist[i][k][0]==1 // 偶数+奇数=奇数
但是有一点问题，如果dist[j][j]存在怎么办？ 那就是有环了！
不怕，floyd可以处理环！（只要经过n个点的哪怕是带环的路径，都能够被floyd这货检测出来！而且每个环都能被这货考虑到！）
不需要两次floyd（错误：第一次就把所有环考虑进来，放进了dist[j][j]中，第二次floyd的时候，这些环就被完全用上了。）
假设一个dist[j][k]经过路径 j ... jn .... jn ... jm...jm...k， 且其中经过了s个环。
按道理来说，最多1个环就够了，而且有用的环是奇数长度的。 因为环在这里的唯一用处是将偶数路径变成奇数，或奇数路径变成偶数。
所以说， 本质上是找到一个奇数环（jiquan）就可以了。然后qiquan这货还是传递的，连同分支一个节点有jiquan，那么其他点都在jiquan里。
方法二：
由于floyd太慢，而利用上面的qiquan的性质，其实更简单的寻找奇圈的方法是dfs两遍。
- 第一遍类似于有向图找强连通分支：
- 凡是到达已访问过的点的边，都够成了quan（可以忽略到达父节点的边，反正这里环长为2，一定不是jiquan所以用不上）。如果还是jiquan，那么标记该点。
- 第二遍dfs：如果一个点在qiquan里，那么该联通分支上所有点都在jiquan里。都应该被标记。
方法一实现：
#include <iostream>
#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <map>
using namespace std;
#define MAXN 5000
int dist[MAXN][MAXN][2];
int ss[MAXN][MAXN][2];
void dfs(bool visit[], int u, int n){
visit[u]=true;
for(int i=0; i<n; i++){
if(dist[u][i][1]>0&&!visit[i]){
dist[i][i][1]=1, ss[i][i][1]=2*ss[u][i][1]-ss[u][u][1];
dfs(visit, i, n);
}
}
}
void floyd(int n){
//dfs to find all jiquan(connected tree contains qiquan-vertexs)
bool visit[MAXN]; memset(visit, 0, sizeof(visit));
for(int i=0; i<n; i++){
if(dist[i][i][1]>0){
dfs(visit, i, n);
}
}
//floyd
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
for(int k=0; k<n; k++){
if(dist[j][k][1]<=0){
if(dist[j][i][1]>0&&dist[i][k][0]>0) dist[j][k][1]=1, ss[j][k][1]=ss[j][i][1]-ss[i][k][0];
else if(dist[j][i][0]>0&&dist[i][k][1]>0) dist[j][k][1]=1, ss[j][k][1]=ss[j][i][0]+ss[i][k][1];
}
if(dist[j][k][0]<=0){
if(dist[j][i][1]>0&&dist[i][k][1]>0) dist[j][k][0]=1, ss[j][k][0]=ss[j][i][1]-ss[i][k][1];
else if(dist[j][i][0]>0&&dist[i][k][0]>0) dist[j][k][0]=1, ss[j][k][0]=ss[j][i][0]+ss[i][k][0];
}
}
}
}
}
int read(char *buf, char *a, char *b){
int j=0;
while(buf[j]!='+') j++;
strncpy(a, buf, j); a[j]=0;
j++;
int k=j;while(buf[k]!='=') k++;
strncpy(b, buf+j, k-j); b[k-j]=0;
k++;
return k;
}
int main(){
int N; scanf("%d", &N);
char a[100], b[100], buf[100], *tmp; int t;
for(int casei=1; casei<=N; casei++){
int n; scanf("%d", &n);
map<string, int> names;
int idx=0;
memset(dist, -1, sizeof(dist));
for(int i=0; i<n; i++){
scanf("%s", buf);
int k=read(buf, a, b);
sscanf(buf+k, "%d\n", &t);
if(!names.count(a))
names[a]=idx++;
if(!names.count(b))
names[b]=idx++;
int l=names[a], r=names[b];
dist[l][r][1]=dist[r][l][1]=1;
ss[l][r][1]=ss[r][l][1]=t;
//cout<<l<<","<<r<<":"<<t<<endl;
}
floyd(idx);
//floyd1(idx);
//for debug
for(int i=0; i<idx; i++){
if(dist[i][i][0]) assert(ss[i][i][0]==0);
}
int m; scanf("%d", &m);
printf("Case #%d:\n", casei);
for(int i=0; i<m; i++){
scanf("%s", buf);
int k=read(buf, a, b);
if(!names.count(a) || !names.count(b)) continue;
int l=names[a], r=names[b];
if(dist[l][r][1]>0) {//@error: if(dist[l][r][1]) (-x will return true)
printf("%s+%s=%d\n", a, b, ss[l][r][1]);
}else if(dist[l][l][1]>0&&dist[r][r][1]){
printf("%s+%s=%d\n", a, b, (ss[l][l][1]+ss[r][r][1])/2);
}
}
}
return 0;
}
写了一个程序，但终究还是渣了。。。
对得起这个通过率：
事情还没有完，后来我发现我傻逼的把倒数第7行写成了
else if(dist[l][l][1]>0&&dist[r][r][1]){
我一直把if(负数）等价于if(false)了，看我是有多傻逼！
于是改良之后的版本在这里，顺利ac。
戳下面。
Problem D. Cut
Tiles
Guide to get started.
|
Small input 13 points |
|
|
Large input 16 points |
|
Problem
Enzo is doing renovation for his new house. The most difficult part is to buy exactly the right number of tiles. He wants N tiles of different sizes. Of course they have to be cut from the tiles he bought. All the required tiles are square.
The lengths of side of the tiles are 2S1, 2S2, ..., 2SN. He can only buy a lot of tiles sized M*M, and he
decides to only cut tiles parallel to their sides for convenience. How many tiles does he need to buy?
Input
The first line of the input gives the number of test cases: T. T lines follow. Each line start with the number N and M, indicating the number of required tiles and the size of the big tiles
Enzo can buy. N numbers follow: S1, S2, ... SN, showing the sizes of the required tiles.
Output
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the number of the big tiles Enzo need to buy.
Limits
1 ≤ 2Sk ≤ M ≤ 2^31-1.
Small dataset
1 ≤ T ≤ 100.
1 ≤ N ≤ 20.
Large dataset
1 ≤ T ≤ 1000.
1 ≤ N ≤ 500.
Sample
Round 1B
Problem A. Password
Attacker
Guide to get started.
|
Small input 8 points |
|
|
Large input 13 points |
|
Problem
Passwords are widely used in our lives: for ATMs, online forum logins, mobile device unlock and door access. Everyone cares about password security. However, attackers always find ways to steal our passwords. Here is one possible situation:
Assume that Eve, the attacker, wants to steal a password from the victim Alice. Eve cleans up the keyboard beforehand. After Alice types the password and leaves, Eve collects the fingerprints on the keyboard. Now she knows which keys are used in the password.
However, Eve won't know how many times each key has been pressed or the order of the keystroke sequence.
To simplify the problem, let's assume that Eve finds Alice's fingerprints only occurs on Mkeys. And she knows, by another method, that Alice's password contains N characters. Furthermore, every keystroke on the keyboard
only generates a single, unique character. Also, Alice won't press other irrelevant keys like 'left', 'home', 'backspace' and etc.
Here's an example. Assume that Eve finds Alice's fingerprints on M=3 key '3', '7' and '5', and she knows that Alice's password is N=4-digit in length. So all the following passwords are possible: 3577, 3557, 7353 and 5735.
(And, in fact, there are 32 more possible passwords.)
However, these passwords are not possible:
1357 // There is no fingerprint on key '1'
3355 // There is fingerprint on key '7',
so '7' must occur at least once.
357 // Eve knows the password must be a 4-digit number.
With the information, please count that how many possible passwords satisfy the statements above. Since the result could be large, please output the answer modulo 1000000007(109+7).
Input
The first line of the input gives the number of test cases, T.
For the next T lines, each contains two space-separated numbers M and N, indicating a test case.
Output
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the total number of possible passwords modulo 1000000007(109+7).
Limits
Small dataset
T = 15.
1 ≤ M ≤ N ≤ 7.
Large dataset
T = 100.
1 ≤ M ≤ N ≤ 100.
Sample
这道题用 抽屉原理 或 DP 即可
DP公式 cnt[i][j] = j*cnt[i-1][j] + (n-(j-1))*cnt[i-1][j-1]
注意随时大数%MOD防溢出就行 l = (a+b)%MOD, l= (a*b%MOD) * (c*d%MOD) %MOD ..
Problem B. New Years Eve
Guide to get started.
|
Small input 11 points |
|
|
Large input 12 points |
|
Problem
At new years party there is a pyramidal arrangement of glasses for wine. For example, at the top level, there would just be one glass, at the second level there would be three, then 6 and then 10 and so on and so forth like the following image
.
The glasses are numbered using 2 numbers, L and N. L represents the level of the glass and N represents the number in that level. Numbers in a given level are as follows:
Level 1:
1
Level 2:
1
2 3
Level 3:
1
2 3
4 5 6
Level 4:
1
2 3
4 5 6
7 8 9 10
Each glass can hold 250ml of wine. The bartender comes and starts pouring wine in the top glass(The glass numbered L = 1 and N = 1) from bottles each of capacity 750ml.
As wine is poured in the glasses, once a glass gets full, it overflows equally into the 3 glasses on the next level below it and touching it, without any wine being spilled outside. It doesn't overflow to the glasses on the same level beside it. It also doesn't
overflow to the any level below next level (directly).
For example: When the glass of L = 2 and N = 2 overflows, the water will overflow to glasses of L = 3 and N = 2, 4, 5.
Once that the bartender is done pouring B bottles, figure out how much quantity in ml of wine is present in the glass on level L with glass number N.
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case consists of three integers, B, L, N, B is the number
of bottles the bartender pours and L is the glass level in the pyramid and N is the number of the glass in that level.
Output
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the quantity of wine in ml in that glass.
We recommend outputting y to 7 decimal places, but it is not required. y will be considered correct if it is close enough to the correct number: within an absolute or relative error of 10-6. See the FAQ for
an explanation of what that means, and what formats of real numbers we accept.
Limits
1 ≤ T ≤ 150.
Small dataset
1 ≤ B ≤ 1000.
1 ≤ L ≤ 100.
1 ≤ N ≤ Number of glasses on the corresponding level.
Large dataset
1 ≤ B ≤ 50000.
1 ≤ L ≤ 400.
1 ≤ N ≤ Number of glasses on the corresponding level.
Sample
Problem C. Card
Game
Guide to get started.
|
Small input 9 points |
|
|
Large input 17 points |
|
Problem
Bob is fond of playing cards. On his birthday party, his best friend Alice gave him a set of cards.
There are N cards and each card contains an integer number. He put the cards from left to right on a desk and wants to discard some of them. Before he discards any cards, he will choose a number K. At each time, he always
chooses 3 adjacent cards to discard, and we assume that the numbers on each card from left to right are a, b and c. Bob guarantees that
c - b = b - a = K
Bob want to know what is the smallest number of cards he can be left with at the end. If he ever has a choice of which cards to discard, he chooses the cards and will leave the fewest cards at the end.
Input
The first line of the input gives the number of test cases, T. T test cases follow.
Each test cases contains two lines. The first line of each test case contains two integers: the number of cards N and the number K Bob chooses. The second line contains Nintegers a1, a2,
..., aN the numbers on the cards from left to right.
Output
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the smallest number of cards Bob can be left with after he has discarded everything he can.
Limits
1 ≤ T ≤ 100.
1 ≤ ai ≤ 106(1 ≤ i ≤ N).
1 ≤ N ≤ 100.
Small dataset
K = 0.
Large dataset
1 ≤ K ≤ 106.
Sample
这题还是DP，首先观察到类似于给一个式子加括号使得最后最大。
假设最终方案中给某个区间[l, r] 加了括号，那么这个区间（括号内部的东西）最终可能完全被消除， 也可能留下几个数字。
所以先枚举每个区间能否被 完全消除，存于bool [n][n], 这个递推公式一定要强大到包含所有递推情况：
- 第零种（初始化边界）： [l, l+2] = true if num[l],... 三个数刚好等差
- 第一种： [l, r] = [l, mid] + [mid+1, r], 作为两个区间分别被消除。
- bool[l][r] = ...
- 第二种：[l, r]被作为一个区间消除，也就是左边界和右边界最后碰面，然后消除（中间还有一个值）。这个区间相当于被切分了两个子区间加三个单独的数。
- bool[l][r] = num[l] , bool[l+1][r1], num[r1+1], bool[r1+2][r-1], num[r] ，其中r1>=(l+1)-1, r-1>=(r1+2)-1 .当r1==l+1-1时，[l+1, r1]子区间是空的， 后面同理
Problem D. Parentheses
Order
Guide to get started.
|
Small input 10 points |
|
|
Large input 20 points |
|
Problem
An n parentheses sequence consists of n "("s and n ")"s.
A valid parentheses sequence is defined as the following:
You can find a way to repeat erasing adjacent pair of parentheses "()" until it becomes empty.
For example, "(())" is a valid parentheses, you can erase the pair on the 2nd and 3rd position and it becomes "()", then you can make it empty.
")()(" is not a valid parentheses, after you erase the pair on the 2nd and 3rd position, it becomes ")(" and you cannot erase any more.
Now, we have all valid n parentheses sequences. Find the k-th smallest sequence in lexicographical order.
For example, here are all valid 3 parentheses sequences in lexicographical order:
((())) (()()) (())() ()(()) ()()()
Input
The first line of the input gives the number of test cases, T. T lines follow. Each line represents a test case consisting of 2 integers, n and k.
Output
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the k-th smallest parentheses sequence in all valid nparentheses sequences. Output "Doesn't Exist!"
when there are less than k different nparentheses sequences.
Limits
1 ≤ T ≤ 100.
Small dataset
1 ≤ n ≤ 10.
1 ≤ k ≤ 100000.
Large dataset
1 ≤ n ≤ 100.
1 ≤ k ≤ 1018.
Sample
这道题是卡特兰数类似的计数问题，给定 左括号 右括号 相对数量 t， 剩余长度n，求满足条件的括号序列（卡特兰序列）个数:
dp(t, n):
a[0][t]=1,
for i=1 to n:
for j=0 to (n - i):
a[i][j] = a[i-1][j-1] ( if j>=1 ) + a[i-1][j+1]
return a[n][0]
再然后从左到右枚举每一位是 ( 时的方案数量 m=dp(xx, yy). 如果rank>m, 那就 说明要取 ) , rank - = m.
如果到最后一位还是rank>0,那么无解。
Round 1c
Problem
A. Minesweeper
Guide to get started.
|
Small input 8 points |
|
|
Large input 14 points |
|
Problem
Minesweeper is a computer game that became popular in the 1980s, and is still included in some versions of the Microsoft Windows operating system. This problem has a similar idea, but it does not assume you have played Minesweeper.
In this problem, you are playing a game on a grid of identical cells. The content of each cell is initially hidden. There are M mines hidden in M different cells of the grid. No other cells contain mines. You may click on any cell to reveal it. If the revealed
cell contains a mine, then the game is over, and you lose. Otherwise, the revealed cell will contain a digit between 0 and 8, inclusive, which corresponds to the number of neighboring cells that contain mines. Two cells are neighbors if they share a corner
or an edge. Additionally, if the revealed cell contains a 0, then all of the neighbors of the revealed cell are automatically revealed as well, recursively. When all the cells that don't contain mines have been revealed, the game ends, and you win.
For example, an initial configuration of the board may look like this ('*' denotes a mine, and 'c' is the first clicked cell):
*..*...**. ....*..... ..c..*.... ........*. ..........
There are no mines adjacent to the clicked cell, so when it is revealed, it becomes a 0, and its 8 adjacent cells are revealed as well. This process continues, resulting in the following board:
*..*...**. 1112*..... 00012*.... 00001111*. 00000001..
At this point, there are still un-revealed cells that do not contain mines (denoted by '.' characters), so the player has to click again in order to continue the game.
You want to win the game as quickly as possible. You want to find the minimum number of clicks to win the game. Given the size of the board (N x N), output such minimum number of clicks.
Input
The first line of the input gives the number of test cases, T. Ttest cases follow. First line of each test case contains one integer N. N lines strings with length N follows containing '*' and '.', denotes the Minesweeper
initial board.
Output
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the minimum number of clicks to win.
Limits
1 ≤ T ≤ 100.
Small dataset
1 ≤ N ≤ 50.
Large dataset
1 ≤ N ≤ 300.
Sample
Problem B. Taking Metro
Guide to get started.
|
Small input 9 points |
|
|
Large input 15 points |
|
Problem
Tom is taking metros in the city to go from station to station.
The metro system in the city works like this:
- There are N metro lines in the city: line 1, line 2, ..., line N.
- For each metro i, there are SNi stations. Let's assume they are Si,1,Si,2, ... ,Si,SNi.
These stations are ordered from one end point to the other end point. The metro is running in both directions. In other words, the metro is going from Si,1 ->Si,2 -> ... -> Si,SNi,
and Si,SNi -> Si,SNi-1 -> ... -> Si,1. You can take the metro from any station and get off at any station. It takes a certain time to travel from one
station to the next station. It takes Timei,1 minutes to travel from Si,1 to Si,2,Timei,2 minutes to travel from Si,2 to Si,3,
etc. It takes the same time in the other direction. - There are M transfer tunnels. Each transfer tunnel connects two stations of different metro lines. It takes a certain amount of time to travel through a tunnel in either direction. You can get off the metro
at one end of the tunnel and walk through the tunnel to the station at the another end. - When you arrive at a metro station of line i, you need to wait Wi minutes for the next metro.
Now, you are going to travel from one station to another. Find out the shortest time you need.
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, the number of metro lines. N metros descriptions follow. Each metro description starts with two integers SNi and Wi, the number
of stations and the expected waiting time in minutes. The next line consists of SNi-1 integers,Timei,1, Timei,2, ..., Timei,SNi-1, describing
the travel time between stations.
After the metro descriptions, there is an integer M, the number of tunnels. M lines follow to describe the tunnels. Each tunnel description consists of 5 integers, m1i, s1i, m2i, s2i,ti which
means the tunnel is connecting stations Sm1i,s1i and station Sm2i,s2i. The walking time of the tunnel is ti.
The next line contains an integer Q, the number of queries. Each of the next Q lines consists of 4 integers, x1, y1, x2, y2, which mean you are going to travel
from stationSx1,y1 to station Sx2,y2.
Output
For each test case, output one line containing "Case #x:", where x is the test case number (starting from 1), then followed by Q lines, each line containing an integer y which is the shortest time you need for that query. If it's impossible,
output -1 for that query instead.
Limits
1 ≤ T ≤ 100.
1 ≤ Wi ≤ 100.
1 ≤ Timei,j ≤ 100.
1 ≤ m1i ≤ N.
1 ≤ s1i ≤ SNm1i.
1 ≤ m2i ≤ N.
1 ≤ s2i ≤ SNm2i.
m1i and m2i will be different.
1 ≤ ti ≤ 100.
1 ≤ Q ≤ 10.
1 ≤ x1 ≤ N.
1 ≤ y1 ≤ SNx1.
1 ≤ x2 ≤ N.
1 ≤ y2 ≤ SNy2.
Station Sx1,y1 and station Sx2,y2 will be different.
Small dataset
1 ≤ N ≤ 10.
0 ≤ M ≤ 10.
2 ≤ SNi ≤ 100.
The total number of stations in each case is at most 100.
Large dataset
1 ≤ N ≤ 100.
0 ≤ M ≤ 100.
2 ≤ SNi ≤ 1000.
The total number of stations in each case is at most 1000.
Sample
In the first case, you are going to travel from station 1 of metro line 1 to station 4 of metro line 2. The best way is:
- wait 3 minutes for line 1 and get on it.
- take it for 3 minutes and get off at station 2.
- take the tunnel and walk for 1 minute to station 2 of line 2.
- wait 2 minutes for line 2 and get on it.
- take it for 2 minutes and get off at station 4.
The total time is: 3+3+1+2+2=11.
Problem C. Broken
Calculator
Guide to get started.
|
Small input 10 points |
|
|
Large input 16 points |
|
Problem
Alice is a smart student who is very good at math. She is attending a math class. In this class, the teacher is teaching the students how to use a calculator. The teacher will tell an integer to all of the students, and the students must type that exact
number into their calculators. If someone fails to type the number, he or she will be punished for failing such an easy task!
Unfortunately, at the beginning of the class, Alice finds that her calculator is broken! She finds that some of the number buttons are totally broken, and only the "multiply" and "equals" operator buttons are available to use. So she can only use these buttons
to get the number quickly.
For instance, the teacher may say the number "60", while Alice's calculator can only type "1", "2" and "5". She could push the following buttons:
- Button "15" (2 clicks)
- Button "multiply" (1 click)
- Button "2" (1 click)
- Button "multiply" (1 click)
- Button "2" (1 click)
- Button "equals" (1 click)
This method requires 7 button clicks. However, if Alice uses "12*5=", only 5 clicks are needed. Of course Alice wants to get the integer as fast as possbile, so she wants to minimize the number of button clicks. Your task is to help her find a way to get the
required number quickly.
Input
The first line of the input gives a number T, the number of integers the teacher says. Ttest cases follow.
Each case contains two lines. The first line contains ten numbers each of which is only 0 or 1. the ith number (starting from 0) is "1" if the number i can be clicked, or "0" if it is broken. The second line contains only
one number X, the integer the teacher tells everyone.
Output
For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the minimum number of button clicks needed, or "Impossible" if it is not possible to produce the number.
Limits
1 ≤ T ≤ 100.
Small dataset
1 ≤ X ≤ 100.
Large dataset
1 ≤ X ≤ 106.
Sample
The first sample case is explained in problem statement.
In the second case, all digits are available, so Alice can just press "1", "2", "8" and then "equals" to get the result. Please note that she still needs to press "equals" in the last step, even though there are no calculations.
For the last case, it's impossible since Alice cannot input any even numbers.
Problem D. Tetris
Guide to get started.
|
Small input 11 points |
|
|
Large input 17 points |
|
Problem
Tetris is a famous video game that almost everyone has played it. In this problem, you need to simulate a simplified version of it.
In our version, the game is played in a W by H field with gravity. At the beginning, the field is empty. Then the tetrominos start to fall from above top of the field to bottom of the field, one by one. Each tetromino will
stop as soon as it touches some other tetrominos or bottom of the field.
One interesting feature of the game is called "line clearing". A line will be cleared as soon as it is filled by tetrominos. More than one line may be cleared at a time. For example:
|..............| |..............| |..............|
|.............o| |..............| |..............|
|.............o| |..............| |..............|
|.............o| |..............| |..............|
|.............o| |..............| |..............|
|..xx..........| --> |..xx..........| --> |..............|
|xxxxxxxxxxxxx.| |xxxxxxxxxxxxxo| |..............|
|xxxxxxxxxxxxx.| |xxxxxxxxxxxxxo| |..xx..........|
|xx..xxxxxxxxx.| |xx..xxxxxxxxxo| |xx..xxxxxxxxxo|
|xxxxxxxxxxx...| |xxxxxxxxxxx..o| |xxxxxxxxxxx..o|
---------------- ---------------- ----------------
Falling Stopped Cleared 2 lines
Note that in this simplified version, the "floating" tetromino blocks won't continue to fall after lines are cleared. This is why the top-most two squares will keep in such position. Consequently, cascade clearing won't happen, even though it would happen
in the original version of Tetris.
The game ends when all the given tetrominos are placed, or the current tetromino cannot be placed due to the height limit of the field is reached.
In this problem, each tetromino will has its type, rotation and falling position told by the input. They will start to fall from the above of the field. Your goal is to simulate and get the final result of each play.
Input
We have 7 types of tetromino:
1 2 3 4 5 6 7
x x x x xx x x
xx xx x x xx x xxx
x x xx xx x
x
Rotation of a tetromino is represented by a number r. r can be 0, 1, 2 or 3. Rotation is counterclockwise. For example:
r=0 r=1 r=2 r=3
x x xxx x
xxx xx x xx
x x
x xx x xx
xx xx xx xx
x x
The horizontal falling position is represented by a number x. It is the coordinate of the lower left square of a tetromino's bounding box. Here x starts from 0.
The first line of the input gives the number of test cases, T. For each test case, the first line of input has 3 integers, W, H, N. W is the width, H is the height and N is
the number of blocks that are going to fall.
Then N lines below, each line has 3 integers, ti, ri, xi. ti tells the tetromino type. ri is the rotation of this tetromino. xi is
the horizontal falling position of this tetromino. It is guaranteed that xi will make the tetromino inside the field, horizontally.
Output
For each test case, first output one line containing "Case #i:", where i is the test case number (starting from 1). And then, if the game ends before the N blocks, output "Game Over!"(without quotes). Otherwise, output the
game field's final state, which should haveH lines, each has W characters. Each character can be '.' or 'x'.
Limits
1 <= T <= 100
1 <= ti <= 7
0 <= ri < 4
Small dataset
4 <= W <= 20
1 <= H <= 20
0 <= N <= 100
Large dataset
4 <= W <= 100
1 <= H <= 100
0 <= N <= 5000
Sample