Problemas Recomendados en Acm Icpc News

Bejing Normal University
2014 ACM-ICPC Beijing

Invitational Programming Contest
May 18th, 2014
Problem A: A Matrix
Problem B: Beautiful Garden
Problem C: Champions League
Problem D: Dices in Yahtzee
Problem E: Elegant String
Problem F: Football on Table
Problem G: Great Escape
Problem H: Happy Reversal
Problem I: In A Maze
Problem J: Justice String
2014 ACM-ICPC Beijing Invitational Programming Contest
Problem A. A Matrix
Chaos King loves permutation and matrix, now he is trying to nd out some relations between
them.
Now Chaos King has a permutation. He wants to transform the permutation to a matrix by the
program beneath.
int f[][];
int p[];
int n;
void insert(int r, int x)
{
for (int i=1; 1; i++)
if (f[r][i]==0)
{
f[r][i]=x;
return ;
}
else if (f[r][i]>x)
{
int tmp=f[r][i];
f[r][i]=x;
insert(r+1, tmp);
return ;
}
}
void Permutation2Matrix()
{
for (int i=1; i<=n; i++)
insert(1, p[i]);
}
initially, all elements in f are 0.
Now Chaos King has got a matrix from the program above, then he sends this matrix to you and
asks you what is the initial permutation. Can you do it?
Input
First line of the input is an integer T indicating the number of cases,
For each test case,
First line contains 2 integers N (1 N 10
5
), M (1 M N) indicating length of the
permutation and number of rows which do not contains 0 in the matrix.
Then M lines, the i
th
line represent the ith row in the matrix.
The rst integer in each line is P
i
, indicating the number of non-zero elements in this
row. Then P
i
integers, indicating those elements.
Page 1 of 21
It is guaranteed that
P
i
= N and every element in the matrix is an integer in [1, N]. There are
no 2 elements have the same value.
Output
For each case, rst output the case number as Case #x: , and x is the case number. Then
output a permutation of N, indicating the answer of this test case.
If there are multiple answers, output the permutation with the largest alphabet order after reversal.
(e.g. there are 2 answers: 1 2 3 and 1 3 2. You should output 1 2 3, because 1 3 2 is larger than
1 2 3)
If there is no answer, output No solution.
Sample input and output
Sample Input Sample Output
2
3 2
2 1 2
1 3
2 1
2 2 1
Case #1: 1 3 2
Case #2: No solution
Page 2 of 21
Problem B. Beautiful Garden
There are n trees planted in lxhgwws garden. You can assume that these trees are planted along
the X-axis, and the coordinate of i
th
tree is x
i
.
But in recent days, lxhgww wants to move some of the trees to make them look more beautiful.
lxhgww will recognize the trees as beautiful if and only if the distance between any adjacent trees
is the same.
Now, lxhgww wants to know what is the minimum number of trees he need to move.
Just to be clear, after moving, there should still be n trees in the X-axis.
Input
The rst line of the input contains a single integer T, which is the number of test cases.
For each case,
The rst line contains an integers number n (1 n 40), representing the number of trees
lxhgww planted;
The second line contains n integers numbers, the i
th
number represents x
i
.
(1000000000 x
i
1000000000)
Output
output a single number, representing the minimum number of trees lxhgww needs to move.
1
4
1 3 6 7
Case #1: 1
Page 3 of 21
This page is intentionally left (almost) blank.
Page 4 of 21
Problem C. Champions League
UEFA Champions League is a famous soccer event in Europe. Lots of soccer teams in Europe
come and ght for the champion of this event every year.
This year, there are 4 N team take part in this event. At the beginning, they are divided into
N groups.
lxhgww is the manager of Captain Chen Television (CCTV). He is so powerful that he can re-
arrange the schedule of any match for all the teams.
However there are some limits even for such a powerful man:
For any 2 teams from the same group, for example A and B, there will be 2 matches between
them. In one match, A is home team, B is away team. In another match, A is away team,
B is home team.
In one day, one team should have and can only have 1 match with one team.
In one day, each group should have 2 matches.
At the 4
th
day, all matches should be the same with those at the 1
st
day. For example, if A
and B have a match on the 1
st
day, and A is home team, B is away team, A and B should
have a match on the 4
th
day, and A is away team, B is home team. And the same restriction
applies for 5
th
day and 2
nd
day, 6
th
day and 3
rd
day.
So after 6 days, all teams will nish their matches.
After the arrangement, lxhgww should choose some matches to livecast on TV.
But unfortunately, in one day, all matches in this day are held at the same time. So lxhgww can
only broadcast 1 match per day.
Now lxhgww sets a wonderful point for each match, if he broadcast some match, and its wonderful
point is X, which means he will get X dollars.
So can you tell him how many dollars can he get at most, if he arrange matches properly?
Input
The rst line of the input is an integer T (T 200), indicating the number of cases.
For each test case:
The rst line is an integer N (1 N 10000), indicating the number of groups.
Then N matrix of 4 4, the i
th
matrix indicating the wonderful point for the matches in
the i
th
group. It is guaranteed that for each matrix a, a
ii
= 1, and all a
ij
(i = j) are
non-negative integer. Furthermore, a
ij
represents the wonderful point when the i
th
team is
the home team and the j
th
team is the away team.
Output
output an integer, indicating the answer of this case.
Page 5 of 21
1
6
-1 2 3 4
2 -1 3 4
2 3 -1 4
2 3 4 -1
-1 2 3 5
8 -1 1 3
2 3 -1 5
8 1 3 -1
-1 2 4 6
8 -1 2 4
6 8 -1 2
4 6 8 -1
-1 5 10 2
1 -1 3 7
3 1 -1 2
2 2 2 -1
-1 3 5 3
1 -1 1 9
5 1 -1 1
3 5 7 -1
-1 2 2 3
2 -1 3 4
2 3 -1 2
2 3 0 -1
Case #1: 51
Page 6 of 21
Problem D. Dices in Yahtzee
Yahtzee is a famous game with dices, and its scorecard contains 14 boxes. The game contains
14 turns. On each turn, the player rolls ve dices. After each rolling, the player must choose an
unused box to put dices and get his score according to the rule of this box. Each players total
score is calculated by summing all 14 score boxes.
The Yahtzee scorecard can be divided into two sections: the upper section and the lower section.
In the upper section, there are six boxes, and the i
th
box is scored by summing all the dices whose
face is i, i.e, the number of dices whose face is i mutiplies i.
The lower section contains a number of poker-themed combinations with specic point values:
1. Two-Pairs: If there are two pairs (for example, 2 2 3 3 4 and 2 2 3 3 3 are
valid, but 3 3 3 3 4 and 3 3 3 3 3 are not valid), the score is the sum of all
dices, otherwise the score is zero.
2. Three-Of-A-Kind: If there are at least three dices showing the same face, the score is the
sum of all dices, otherwise the score is zero.
3. Four-Of-A-Kind: If there are at least four dices showing the same face, the score is the sum
of all dices, otherwise the score is zero.
4. Full House: If there is a three-of-a-kind and a pair (for example, 2 2 3 3 3 is valid,
but 3 3 3 3 3 is not valid), the score is 25, otherwise the score is zero.
5. Small Straight: If there is a four sequential dice (for example, 1 2 3 4, 2 3 4 5,
or 3 4 5 6), the score is 30, otherwise the score is zero.
6. Large Straight: If there is a ve sequential dice (for example, 12345 or 23456),
the score is 40, otherwise the score is zero.
7. Yahtzee: If all ve dices show the same face, the score is 50, otherwise the score is zero.
8. Chance: The score is the sum of all dice.
Now, Elfnesss dices are non-uniform, but he know the probability of the dice showing one to six.
Can you tell him the expectation of a players total score if he uses the best strategy to choose
the boxes during the game?
Input
One integer T on the rst line indicates the number of cases.
Then followed by T cases, each case contains only one line. Each line contains six numbers, the
i
th
number is the probability when the dice shows the face of i. They are given with 4 digits after
the decimal point. We assume the sum of the probability equals to 1.
Output
output the expect score that a player will get, rounded to 6 digits after the decimal point.
Page 7 of 21
2
0.1600 0.1600 0.1700 0.1700 0.1700
0.1700
0.1000 0.1000 0.2000 0.2000 0.2000
0.2000
Case #1: 149.372281
Case #2: 162.624651
Page 8 of 21
Problem E. Elegant String
We dene a kind of strings as elegant string: among all the substrings of an elegant string, none
of them is a permutation of 0, 1, . . . , k.
Let function(n, k) be the number of elegant strings of length n which only contains digits from 0
to k (inclusive). Please calculate function(n, k).
Input
Input starts with an integer T (T 400), denoting the number of test cases.
Each case contains two integers, n and k. n (1 n 10
18
) represents the length of the strings,
and k (1 k 9) represents the biggest digit in the string.
Output
output function(n, k) mod 20140518 in this case.
2
1 1
7 6
Case #1: 2
Case #2: 818503
Page 9 of 21
Page 10 of 21
Problem F. Football on Table
Bored? Lets play table football!
The table football is played on a rectangular table, usually contains m rows of players which are
plastic, metal, wooden, or sometimes carbon-bre gures mounted on vertical metal bars. After
playing table football for hours, we decide to take a rest. And the state of the table remains
random, that means each bar is placed at any legal position with equal possibilities (players cant
be outside the table and a bar is xed at a row).
Now Im wondering if the goal-keeper shoot a ball, whats the possibility of this shoot turning to
a goal? (If the ball did not touch any player, then I made a goal).
Lets assume there is a
i
players on the i
th
row (counted from left to right). And we know the
width of each player and the distance between two players. (To simplify the problem, we ignore
the thickness of the players, in other words, we consider the players as vertical segments. Then
we treat the football as a point, moving along a straight line and will not touch the boundary of
the table).
Input
The rst line contains an integer T, which denotes the number of test cases.
For each test case:
The rst line contains two numbers L, W (1 L, W 10
8
), denoting the length and the
width of the table. (the lower left corner of the table is (0, 0) , and the top right corner of
the table is (L, W)).
The second line contains four number X, Y , d
x
, d
y
. (X, Y ) denotes the initial position of
the ball and (d
x
, d
y
) denotes the shooting direction. (X will always be zero, 0 Y W,
d
x
> 0).
The third line contains an integer m (1 m 10), the number of rows of the players.
Following m blocks, for the i
th
block,
The rst line contains a number x
i
and an integer a
i
,(0 < x
i
< L, 1 a
i
100)
denoteing the x-coordinate of the i
th
row and the number of players at the i
th
row.
Page 11 of 21
The second line contains a
i
numbers, the j
th
number w
j
denotes the width of the j
th
(from bottom to top) player at the i
th
row.
The third line contains a
i
1 numbers, the j
th
number d
j
denotes the distance between
the j
th
player and the (j + 1)
th
player. If a
i
equals 1, this line will be a blank line.
We guarantee that
w
j
+
d
j
+ 1 < W
Output
output the result rounded to 5 digits after the decimal point, representing the possibility of this
shoot turning to a goal, in other words, that the ball does not touch any player.
2
8.0 10.0
0.0 5.0 2.0 -0.1
1
3.0 2
2.0 2.0
1.0
8.0 10.0
0.0 5.0 2.0 0.0
2
3.0 2
2.0 2.0
1.0
4.0 3
2.0 1.0 2.0
1.0 1.0
Case #1: 0.23000
Case #2: 0.13333
Page 12 of 21
Note
For test 1:
The black solid lines denote the table.
The dashed line denotes the bar.
The gray lines denote the players.
The dot-dashed line denote the trajectory of the ball.
Page 13 of 21
Page 14 of 21
Problem G. Great Escape
Beijing Invitational Programming Contest is now approaching, but the problems-set for the contest
is not ready yet. Every day, the DEVIL lxhgww pushed Mochavic to set a question, then set a
question again, then set a question again once more... Finally, Mochavic could not stand him
anymore so he decided to escape to a safer place immediately.
The area where Mochavic lives in can be seen as N +1 identical buildings along a horizontal axis
(X-axis), the buildings are numbered 0, 1, 2, . . . , N from left to right. The distance between the
i
th
and (i + 1)
th
building is d
i
unit length. Each building has L + 1 oors, which are numbered
0, 1, 2, . . . , L from bottom to top. The height of each oor is 1 unit length so that the j
th
oor
of each building can be viewed as a point (x, j), where x is the location of the building on the
X-axis. Mochavic can move up and down in one building at a vertical speed of W, he can also
y between adjacent buildings using the Liserious-Glider. Mochavic has an excellent gliding
skill that he can y along any path he likes, but he has to fall at one of the oors after nishing
one glide. The gliding speed is determined by the air motion which he has measured carefully in
advance: the gliding speed between the i
th
and (i + 1)
th
building is a constant v
i
.
The DEVIL lxhgww is so horrible that Mochavic has to run faster and faster. So we can assume
that it costs no time for Mochavic to move through one oor inside one building. Moreover,
Mochavic dont want waste any opportunity to show his gliding skill, so he will still take a glide
between buildings even he is at the 0
th
oor.
Mochavic (can be simply viewed as a point) is now at the L
th
oor of the 0
th
building, please
calculate the least time he has to spend if he wants to escape to the 0
th
oor of the N
th
building.
Input
The rst line of the input gives the number of test cases, T(T 200). Then T test cases follow.
For each test case:
Page 15 of 21
The rst line contains three integers N, L, W(1 N 10
3
, 1 L 10
9
, 1 W 10
6
).
The second line contains N integers, the i
th
number represents d
i
(1 d
i
10
6
) as described.
The third line contains N integers, the i
th
number represents v
i
(1 v
i
10
6
) as described.
Output
For each case, rst output one line as Case #x:, and x is the case number. Then followed by
the least time. Result within a relative error of 10
6
will be accepted.
2
3 10 3
5 2 3
5 2 7
1 10000 211
911
207
Case #1: 3.231651964072
Case #2: 48.246236647122
Page 16 of 21
Problem H. Happy Reversal
Elfness is studying in an operation NOT.
For a binary number A, if we do operation NOT A, after that, all digits of A will be reversed.
(e.g. A =1001101, after operation NOT K, A will be 0110010).
Now Elfness has N binary numbers of length K, now he can do operations NOT for some of his
numbers.
Lets assume after his operations, the maximum number is M, the minimum number is P. He
wants to know whats the maximum M P he can get. Can you help him?
Input
The rst line of input is an integer T (T 60), indicating the number of cases.
For each case, the rst line contains 2 integers N (1 N 10000) and K (1 K 60), the next
N lines contains N binary numbers, one number per line, indicating the numbers that Elfness
has. The length of each binary number is K.
Output
you should output an integer, indicating the maximum result that Elfness can get.
2
5 6
100100
001100
010001
010001
111111
5 7
0001101
0001011
0010011
0111000
1001011
Case #1: 51
Case #2: 103
Page 17 of 21
Page 18 of 21
Problem I. In A Maze
You are in a maze! Again!!
Fortunately, there is a mystery man with a mystery voice willing to help you out. But, everything
comes with a price. You must help him solve his problems in return. He gave you a map for his
problem.
The map is consists of many untouched polygons (strictly inside or separated). Obviously, the
map was split into multiple connected regions. Now he will give you lots of queries, asking about
the area of the connected region a point is in. Specically, if a point is located at the side of a
polygon, we think its located just inside that polygon.
Input
The rst line of the input contains a single integer K, which is the number of test cases.
For each case,
The rst line contains an integer M (0 < M 50000), represents the number of polygons.
In the following M lines, each line describes a polygon. The rst integer represents the
number of points T
i
(T
i
30), then T
i
pairs of points in either clockwise or counter-clockwise
order.
The next line contains a number N (N 2 10
5
), indicating the number of queries.
In the next N lines, each line contains a point, representing a query.
Every point has integer coordinates, and the absolute value is less than 10
6
.
We guarantee the number of all points will be less than 250000.
Output
For each case, rst output one line as Case #x:, and x is the case number.
Then output N lines, the i
th
line represents the area for the i
th
query, rounded to two digits after
decimal point. If a query is in the outside area (not belong to any closed connected region), just
output 0.00 instead.
Page 19 of 21
1
3
4 0 0 0 10 10 10 10 0
4 2 2 8 2 8 8 2 8
4 3 5 5 7 7 5 5 3
4
1 9
3 7
5 5
100 100
Case 1:
64.00
28.00
8.00
0.00
Note
The picture of the sample:
Page 20 of 21
Problem J. Justice string
Given two strings A and B, your task is to nd a substring of A called justice string, which has
the same length as B, and only has at most two characters dierent from B.
Input
The rst line of the input contains a single integer T, which is the number of test cases.
For each test case, the rst line is string A, and the second is string B.
Both string A and B contain lowercase English letters from a to z only. And the length of these
two strings is between 1 and 100000, inclusive.
Output
output a number indicating the start position of substring C in A, position is counted from 0. If
there is no such substring C, output 1.
And if there are multiple solutions, output the smallest one.
3
aaabcd
abee
aaaaaa
aaaaa
aaaaaa
aabbb
Case #1: 2
Case #2: 0
Case #3: -1
Page 21 of 21

Problemas Recomendados en Acm Icpc News

Uploaded by

Copyright:

Available Formats

Problemas Recomendados en Acm Icpc News

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Problemas Recomendados en Acm Icpc News

Uploaded by

Copyright:

Available Formats

Bejing Normal University

2014 ACM-ICPC Beijing

You might also like