The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
Problem A. Shell Pyramid
Description
In the 17th century, with thunderous noise, dense smoke and blazing fire, battles on the sea were
just the same as those in the modern times. But at that time, the cannon were extremely simple. It
was just like an iron cylinder, with its rearward end sealed and forward end open. There was a
small hole at the rearward end of it, which was used to install the fuse. The cannons on the
warships were put on small vehicles which had four wheels and the shells were iron spheres with
gunpowder in them.
At that time, it was said that there was an intelligent captain, who was also a mathematician
amateur. He liked to connect everything him met to mathematics. Before every battle, he often
ordered the soldiers to put the shells on the deck and make those shells to form shell pyramids.
Now lets suppose that a shell pyramid has four layers, and there will be a sequence of ordinal
numbers in every layer. They are as the following figure:
In the figure, they are the first layer, the second layer, the third layer and the fourth layer
respectively from the left to the right.
In the first layer, there is just 1 shell, and its ordinal number is 1. In the second layer, there are 3
shells, and their ordinal numbers are 1, 2, and 3. In the third layer, there are 6 shells, and their
ordinal numbers are 1, 2, 3, 4, 5, and 6. In the fourth layer, there are 10 shells, and their ordinal
numbers are shown in the figure above.
There are also serial numbers for the whole shell pyramid. For example, the serial number for the
third shell in the second layer is 4, the serial number for the fifth shell in the third layer is 9, and
the serial number for the ninth shell in the fourth layer is 19.
There is also a interrelated problem: If given one serial number s, then we can work out the s th
shell is in what layer, what row and what column. Assume that the layer number is i, the row
number is j and the column number is k, therefore, if s=9, then i=4, j=4 and k=3.
1/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
Now let us continue to tell about the story about the captain.
A battle was going to begin. The captain allotted the same amount of shells to every cannon. The
shells were piled on the deck which formed the same shell pyramids by the cannon. While the
enemy warships were near, the captain ordered to fire simultaneously. Thunderous sound then was
heard. The captain listened carefully, then he knew that how many shells were used and how many
were left.
At the end of the battle, the captain won. During the break, he asked his subordinate a question:
For a shell pyramid, if given the serial number s, how do you calculate the layer number i, the row
number j and column number k?
Input
For a shell pyramid which is big enough, a integer is given, and this integer is the serial number s
s<2^63. There are several test cases. Input is terminated by the end of file.
Output
For each case, output the corresponding layer number i, row number j and column number k.
Sample Input
19
75822050528572544
Output for the Sample Input
443
769099 111570 11179
2/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
Problem B. K-dimension number
Description
What a nice day! The sky is blue, and the sea is calm. It is a day that is suitable for marine
navigation training. A training ship of a Naval Training School sails out from the naval port and
arrives at a sea area. The navigation instructor is not only an expert in navigation but also an
amateur mathematician. The instructor gives the practice assignment as soon as the first student
stands at the position of the navigator: First, navigates 1 nautical mile to the east, and then 2
nautical miles to the south, finally 4 nautical miles to the west, and stops at a certain place. The
first student accomplishes the task successfully. Then the second student takes the place, and the
instructor gives him a new practice assignment: Firstly, navigates 1 nautical mile to the east, then
2 nautical miles to the south, and then 3 nautical miles to the west, finally 3 nautical miles to the
north, and stops at a fixed place. Just like this, the students drive the training ship to accomplish
the assignment one by one. There is a student who is interested in numbers and taking records. He
writes down the first sequence 1, 2, and 4 as soon as the first student accepts the assignment. Later,
he writes down the second sequence1, 2, 3, and 6 when the second student accepts the assignment.
As a mathematic lover, the student always connects the numbers to some mathematic problems.
When he writes down the first sequence, 1, 2, and 4, he figures out that every number in the
sequence is the divisors of 4, and 4 is also the last number in the sequence. When he writes down
the second sequence1, 2, 3 and 6, he also figures out that every number in the sequence is the
divisors of 6, and 6 is also the last number in the sequence. After all the students have finished the
assignment, the student looks at the record and comes to the conclusion followed: There is one
thing in common for the assignments that the instructor has given to the students, that is, take the
direction turning point as the gap, and the sailing distance in all directions form a sequence, every
number in the sequence is the divisor of the last one.
The marine navigation training finishes. On the way back, the students have a good time, singing,
talking, laughing, and appreciating the sea scenery. The student shows the instructor the records
and tells him his findings. The instructor laughs and says to the student, Well done! You like
taking records and thinking, and then finding out something from it. It is a good habit, and also a
scientific habit. The instructor then continues, Just like science does not have limit, the scientific
questions do not have limit, either. The question we have just discussed will not end, and we can
also pose new questions.
The following is the new question the instructor raises:
First, we give a new definition: For a positive integer, if it has K different divisors, then it is called
a K- dimension number.
For instance, the positive integer 4 has three divisors, 1, 2and 4, so 4 is a 3- dimension number.
The positive integer 6 has four divisors, 1, 2, 3and 6, so 6 is a 4- dimension number.
Now a question is posed: how to work out the nth K-dimension number? (n<10000
3/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
Kmax<=100,here Kmax is the greatest prime divisor of K).And you can assume if K is a
k-dimension number, it doesn't exceed 3-dimension.
For example, if it is required to work out the second 3-dimension number, that is to say when n=2,
K=3, then the answer is 9. Because 4 is the first 3-dimension number, and 9 has three common
divisors 1, 3 and 9. Therefore, 9 is the second 3-dimension number.
The student thinks: if n and K are small enough, we can work out easily. Otherwise, we have to
turn to the computer for n and K are too big to deal with.
He begins to think it over on the ship.
Input
There are several test cases. Each case takes up a line, contains two positive integers; they are n
and K respectively. Input is terminated by the end of the file.
Output
Output the nth K-dimension number, each result takes up one line.
Sample Input
13
14
Output for the Sample Input
4
6
4/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
Problem C. Mining Station on the Sea
Description
The ocean is a treasure house of resources and the development of human society comes to depend
more and more on it. In order to develop and utilize marine resources, it is necessary to build
mining stations on the sea. However, due to seabed mineral resources, the radio signal in the sea is
often so weak that not all the mining stations can carry out direct communication. However
communication is indispensable, every two mining stations must be able to communicate with
each other (either directly or through other one or more mining stations). To meet the need of
transporting the exploited resources up to the land to get put into use, there build n ports
correspondently along the coast and every port can communicate with one or more mining stations
directly.
Due to the fact that some mining stations can not communicate with each other directly, for the
safety of the navigation for ships, ships are only allowed to sail between mining stations which
can communicate with each other directly.
The mining is arduous and people do this job need proper rest (that is, to allow the ship to return
to the port). But what a coincidence! This time, n vessels for mining take their turns to take a rest
at the same time. They are scattered in different stations and now they have to go back to the port,
in addition, a port can only accommodate one vessel. Now all the vessels will start to return, how
to choose their navigation routes to make the total sum of their sailing routes minimal.
Notice that once the ship entered the port, it will not come out!
Input
There are several test cases. Every test case begins with four integers in one line, n (1 = <n <=
100), m (n <= m <= 200), k and p. n indicates n vessels and n ports, m indicates m mining stations,
k indicates k edges, each edge corresponding to the link between a mining station and another one,
p indicates p edges, each edge indicating the link between a port and a mining station. The
following line is n integers, each one indicating one station that one vessel belongs to. Then
there follows k lines, each line including 3 integers a, b and c, indicating the fact that there exists
direct communication between mining stations a and b and the distance between them is c. Finally,
there follows another p lines, each line including 3 integers d, e and f, indicating the fact that there
exists direct communication between port d and mining station e and the distance between them is
f. In addition, mining stations are represented by numbers from 1 to m, and ports 1 to n. Input is
terminated by end of file.
Output
5/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
Each test case outputs the minimal total sum of their sailing routes.
Sample Input
3556
124
133
144
155
253
243
115
153
253
246
314
322
Output for the Sample Input
13
6/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
Problem D. Gauss Elimination
Description
Li Zhixiang have already been in Friendship ocean-going freighter for three months. The
excitement has gradually disappeared. He stands on the board, holding the railing and watching
the dazzling ocean in the sun silently. Day after day, the same scenery is monotonous and tasteless,
even the merry seagulls following the freighter cannot arouse his interest. Hearing the footsteps
behind, he turns back to see the old captain is coming towards him. The captain has understood his
idea, however, he starts a new topic with the young man.
Do you know how far our voyage is? The captain asks. Li Zhixiang feels ashamed because he
can not answer. Then the captain says with a smile, 5050 miles. Do you still remember the story
of 5050? This time the young man really blushes. The old captain continues saying: You
definitely know the story of 5050. When the German mathematician, the prince of
mathematicians, Gauss was 10 years old Young man remembers this story and goes on to tell,
When Gauss was 10 years old, he could add a list of integers from 1 to 100 in a few seconds,
which shocked the teachers. The old captain adds, Gauss has many other stories like this. When
he entered the university at the age of 17, he was able to construct heptadecagon by compass and
straightedge. His university teachers were also impressed by his ability. Not only could college
graduate students fail to do it, but also they felt hard to understand Gausss constructing process.
At this time, vice-captain greets the old captain. The old captain says to Li Zhixiang: Come over
to my office tonight, lets continue the conversation. It is still calm and tranquil in the evening.
The freighter travels smoothly on the sea in the silver moonlight. The captain tells the young man
the following words.
Among the mathematicians through the ages, there are three greatest mathematicians: Archimedes,
Newton and Gauss. Most of Gausss mathematical achievements are difficult to understand.
Nevertheless, there are some comparatively easy. For instance, when it comes to solving
multivariate system of linear equations, there is a solution called Gauss Elimination. In the
navigation business, many problems can be solved by Gauss elimination. If you are interested in
it, I will show you a simple question. Try it.
Input
There are several test cases. In the first line of each case, a number n indicates that there are n
equations. The following n lines, each line has n+1 numbers, ai1,ai2,ai3..ain, bi(1<= i <=n),
these numbers indicate the coefficients of systems of the equations. ai1*x1+ai2*x2+......ain*xn=bi.
Input is terminated by the end of file.
7/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
Output
For each given systems of equations, if there are solutions, output n solutions in the order of
appearance in the equationsn<=100, each solution number is in one line. If solution is not
integer, show it in fraction. If no solution, output No solution. Leave a blank line after each
case.
Sample Input
2
1000000000000000000000000 1000000000000000000000000 1000000000000000000000000
-1000000000000000000000000 1000000000000000000000000 0
1
04
Output for the Sample Input
1/2
1/2
No solution.
8/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
Problem E. Searching Treasure in Deep Sea
Description
A deep-sea salvage company found out that there was a sunken ship in some deep-sea area of the
Pacific with a case of priceless treasure in it. The senior leaders concluded as followed:
There may be some sea monsters, they may cause some distraction. The company had some most
advanced intelligent underwater robots. They were equipped with enough weapons to kill the
monster.
After they research a map, they got information as follow (according to the Sample Input): S
indicated the starting place. E indicated the place of the treasure case. D indicated the doors of the
rooms in the ship. K indicated the keys which were needed while opening the doors. H indicated
the stairs went up. L indicated the stairs went down. "#" indicated the walls which separated the
rooms. Every lowercase in the map indicated a monster.
The enclosed space formed by the doors and the walls was called a separated room. Entering a
room needed a key K to open a door D. After that, the key could not be used any more, the door
would be open for ever, and there would be no need to use the key. The total number of rooms in
the ship was not exceeding 30, the total number of the monsters in the ship was not exceeding 26,
and the number of the monsters in each room would not exceed 3. There was no monster in the
rooms where S and E, H and L were in.
The advanced intelligent underwater robot carried a machine gun whose cartridge clip capacity
was 100 bullets and enough spare ammunition. It could re-load the bullets if given a chance. The
surface of its body was equipped with 100 components. If all the components were destroyed
while fighting with the monster, the robot could not function any more and would sink into the sea
for ever. If only a part of the components was destroyed, the robot could recover if given a
[Link] robot could attack the monsters in two ways; one is feign attack, and the other fierce
attack. The feign attack would cause 1 reduction of the monsters' life value, and the fierce attack
would cause a certain amount of deduction of the monsters' life value according to the degree of
the fierce attack. The robot had 10 kinds of fierce attack tactics at most. Every attack tactics
differed in bullet consumption and the certain reduction of the monsters' life value. For example, a
certain kind of attack tactics would consume 30 bullets, and reduce 35 life value of the monster.
The life of the monster was so limited that when the injuries accumulated to a certain amount it
would be killed. Suppose its life value was 100, and every attack would reduce a certain amount
of life value.
When robot enters the treasure vessel, it searches the rooms one by one. As soon as it encounters
the monsters, it will attack the monsters immediately. By consuming a certain amount of
9/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
ammunition, a certain amount of the life value of the monsters is reduced. And then, the monsters
attack the robot and destroy a certain number of robot's parts. Then they attack each other
alternately like this. However, each time the robot launches attack firstly. If there are two or more
monsters, the robot must kill the first one before another attack, and the monsters won't help each
other in the battle. The choice of the order of attack is decisive when a number of monsters are in
a room, because it closely relates with the final result of this battle.
The robot itself and machine guns it takes possess the capacity of restoration. The robot will
re-load 2 bullets when it launches an attack. In the same room, the robot will repair 10 damaged
parts of the body surface and re-filled cartridges after it kills a monster. The robot can't leave the
room until all monsters are eradicated. At the time he leaves the room, 100 damaged parts are
repaired and 100 cartridges are refilled again. It should be noted that, under no circumstances will
the robot's parts and bullets of cartridges be more than 100.
Now intelligent underwater robot has been put into the sea, gradually approaching the location of
the treasure vessel. Whether it can eradicate deep-sea monsters, and return the treasure box is the
problem that you are supposed to resolve.
Input
There are several test cases. The first line of each case has 3 positive integers k, n and m (1 <= k
<= 3, 1 <n, m <= 100), indicating that the deep-sea shipwreck is of k floors, each floor is a maze
composed by n rows and m columns. (The Sample Input map is seen as below). That is, the maze
is composed by characters of n lines, and each line has m characters. The following line has an
integer p (0 <= p <= 10), indicating that there are p kinds of fierce attack tactics for the robot.
Then there are a lines and each line has two positive integers, indicating the consumption of the
number of bullets and reduction of the life value of the monsters as a result of injury by the robot's
tactics. Then there is an integer q (0 <= q <= 26) taking up one line to indicate that there are q
monsters in the treasure vessel. The following are q lines, and each line has one positive integer,
indicating the number of damaged parts of the robot by those q monsters for one attack. Monsters
are expressed in lowercase letters which are formed as a sequential increase from latter "a" to the
letter "z". For example, when q = 10, then the names of the monsters are a, b, c, d, e, f, g, h, i, j,
then the 10 lines of positive integers are the number of destroyed parts of robot as the result of the
attack of those 10 monsters. Finally, there are k * n lines, every n lines indicates a floor of the ship,
each line has m characters. The K floors are given from high to low. Input is terminated by the end
of the file.
Output
For Each test case, if it can arrive "E" place, then output "Yes", or output "No". Each output takes
up one line.
10/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
Sample Input
1 5 10
0
0
3 5 10
1
1 10
3
1
2
3
Output for Sample Input
No
Yes
11/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
Problem F. Simple Addition Expression
Description
A luxury yacht with 100 passengers on board is sailing on the sea in the twilight. The yacht is
ablaze with lights and there comes out laughers and singing from the hall where an evening party
is in full swing. People are singing, dancing and enjoying themselves.
The yacht is equipped with the most advanced navigation and driving system which can all be
manipulated by a computer. When the captain notices that there is only gentle breeze and the sea
waves are not high, he starts the autopilot. The yacht sails forward smoothly, ploughs the waves.
When its completely dark, the passengers start to feel a little funny for sudden forward rushes or
sudden decelerations or slight swings. The captain immediately walks to the driving platform and
switches the autopilot to human manipulation. The yacht returns back to normal and the party
restarts. Laughers come back, too.
The captain summons the engineer on board to do a thorough check of the navigation system. It
turns out that only the computer is out of order, but the exact failure is still unclear. There is a
computer scientist among the passengers who is also invited to the cab to give a hand. He first
inputs several groups of data to test the computer. When he inputs 1+2+3, the computer outputs 6,
which is exactly right. But when he inputs 4+5+6, the computer outputs 5, which is wrong. Then
he inputs 12+13+14, and gets 39, another right answer, while he inputs 14+15+16, and gets 35,
another wrong answer. After the test, the computer scientist says smilingly: the failure is clear
now. The computer's adder can not carry." After excluding the failure, the captain restarts the
autopilot and the yacht returns back to normal, sailing smoothly on the sea.
The captain and the engineer invite the computer scientist to sit down and have a talk. The
computer scientist tells a story as following:
A former mathematician defined a kind of simple addition expression.
If there is an expression (i) + (i+1) + (i+2), i>=0, when carried out additive operations, no position
has a carry, it is called simple addition expression.
For instance, when i equals 0, 0+1+2 is a simple addition expression, meanwhile when i equals 11,
11+12+13 is a simple addition expression, too. Because of that no position has a carry.
However, when i equals 3, 3+4+5 is not a simple addition expression, that is because 3+4+5
equals 12, there is a carried number from unit digit to tens digit. In the same way, when i equals 13,
13+14+15 is not a simple addition expression, either. However, when i equals 112, 112+113+114
is a simple addition expression. Because 112+113+114 equals 339, there is no carry in the process
of adding.
12/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
when the students have got the definition of simple addition expression, the mathematician puts
forward a new question: for a positive integer n, how many simple addition expressions exist
when i<n. In addition, i is the first number of a simple addition expression.
when the value of n is large enough, the problem needs to be solved by means of computer.
Input
There are several test cases, each case takes up a line, there is an integer n (n<10^10).
Output
Output the number of all simple addition expressions when i<n.
Sample Input
1
2
3
4
10
11
Output for the Sample Input
1
2
3
3
3
4
13/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
Problem G. Navy maneuvers
Description
In times of peace, various countries have held regular maneuvers to maintain militarys vigilance.
There is a navy fleet in a certain country which also starts a new round imaginary naval battle.
At the maneuver stage, the admiral intends to assess the combat effectiveness of two warships,
Victory and Glory, so he lets two warships carry out countering exercises. Both of the warship
commanders are young and promising, who graduated from naval academy as outstanding
students. Not only have they had rich navigation direction experiences, but also have profound
scientific knowledge, especially in mathematics.
The admiral appoints one marine area dotted with many islets. Suppose all these islets are
occupied by the enemy, and there are positive integers of enemy firebases. The hypothetical
exercise situations given by the admiral and the rule of the competition are as follows:
(1) All the occupied islets are connected. There are some routes among these islets, but the route
from one islet to another islet is unidirectional. In other words, if we take an islet as a node
and an islet route as an edge, then we will get a directed non-cyclic connected graph.
(2) There is a unique 1st islet in the graph. If we start from this islet, we can reach any other islet.
maybe the 1st islet is not the islet which is numbered 1
(3) At the beginning of the maneuver, two warships simultaneously sail to the 1st islets and
eliminate all enemy firebases together.
(4) The two warships, Victory and Glory take turns to navigate and exchange as soon as they
arrive at an islet, then they move forward together. But each time they can only go along the
unidirectional route, sail to the islet directly connected to the current, and eliminates all the
enemy firebases on the islet. By the way, when start from 1st islet, Victory first navigates.
(5) Because each route is unidirectional, and graph is non-cycle, therefore the maneuver
terminates when the two warships fail to go on navigating.
(6)When the maneuver ends, sum the numbers of eliminated enemy firebases on the routing path.
If the number is greater than or equal to certain number f assigned by the admiral, then
Victory wins. Otherwise, Glory wins.
The warship commanders are both mathematicians. After being assigned to such task, they see it is
a Graph Theory problem. On the first simple directed non-cyclic connected graph, each node has a
certain positive integer,it indicates the enemy firebases. The assignment is that two captains take
turn to move forward along the directed edge until they are unable to do so. Then sum the total
positive integers of the nodes on the routing path. Compare the number with the certain number f,
and decides the final winning or losses.
Therefore, when it is the time for their own navigation, they are supposed to choose the route to
14/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
win the final success.
Input
There are several test cases, in each case there are three positive integers n, m and f in first line. n
indicates there are n (1< n <10000 ) nodes in the graph. The node serial number is arranged from 1
to n. m indicates that there are m edges in the graph. The following line has n positive integers,
which indicate in sequence the positive integers in the nodes. Finally, there are m lines, and each
line has two positive integers a, b (1< = a, b< =n), indicating there is a directed edge from the a
node to the b node. Input is terminated by the end of file.
Output
To each group of the test case, if Victory wins, then output Victory. Otherwise, output Glory.
The output each case takes up one line.
Sample Input
4
2
4
2
4
3
4
1
1
1
1
2
4
4
2
2
1
3
1
5
2
2
3
4
3
3
7
2 2
6
3 4
Output for Sample Input
Glory
Victory
15/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
Problem H. Carrying Out A Task
Description
During the process of the military exercise, there is a ship on the sea level .The ship will go to
certain place to carry out a task. For every action, the ship has two ways to sail. They are normal
sailing and accelerated sailing. The normal speed of the ship is certain, when the ship sails
normally, it can only move 1 step to the adjacent normal sea level. The ship can also accelerate.
There are 2 kinds of accelerated sailings, one is moving forward d steps (d <= 5) in a straight line,
and it must move forward d steps exactly every time it accelerates, The d steps must be on the
normal sea level, otherwise, it can not accelerate. The other is accelerating while getting through
the undercurrent. There are a lot of undercurrents on the sea, and entering the undercurrent area
needs to accelerate when the ship is 1 step to the undercurrent. However, the ship itself will be
damaged more or less by the undercurrent, After entering the undercurrent, the speed of the ship
will become normal immediately. Every time it accelerates, the ship has to consume a certain B
energy, and when it starts up ,it carries certain B energy.
While the ship is sailing on the sea, it needs to consume a certain A energy. One unit of distance
will consume one unit of A energy, and when the ship starts up, it carries enough A energy.
There are many reefs on the sea, and the ship can not get through.
Now the ship is required to sail to the certain place, of course, to minimize the damage to the ship
itself is a priority because the cost of ships is very expensive. The damage is, of course, the
smaller, the better. At the same time, an attempt should be made to control the consumption of A
energy to the smallest amount during the whole process because the cost of A energy is much
more expensive than that of B energy, and you can use B energy which the ship carried when it
started up as you wish.
Now the question is to work out the minimal times of action from the departure point to the
destination under the condition that to minimize the damage to the ship is a priority and then the
consumption of A energy to the smallest degree.
16/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
Input
The input file contains several test cases, the first line contains an integer T, indicates the number
of test cases. In each case the first line includes two integers n, m (5 <= n, m <= 20), which
indicate the size of the sea level for military exercises, and n rows and m columns are the current
state of the sea level ('S' indicates the ship's initial position, 'E' indicates the destination place, '#'
indicates the reefs, '*' indicates the undercurrent , ' ' the normal sea level), followed a line with a
number d in it, it indicates the distance of the first kind of acceleration, then another line includes
two integers, indicate that the initial value of the B energy and the value of the B energy needed
while accelerating every time.
Output
Output an integer to indicate the smallest times of action, and if can not reach the task place, then
output "can not reach!"
Sample Input
2
5 10
##########
#E
#*###### #
#S
##########
5
10 2
6 10
17/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
##########
#E
#*######*#
#*######*#
#S
#
##########
5
32
Output for the Sample Input
8
can not reach!
18/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
Problem I. Degree Sequence of Graph G
Description
Wang Haiyang is a strong and optimistic Chinese youngster. Although born and brought up in the
northern inland city Harbin, he has deep love and yearns for the boundless oceans. After
graduation, he came to a coastal city and got a job in a marine transportation company. There, he
held a position as a navigator in a freighter and began his new life.
The cargo vessel, Wang Haiyang worked on, sails among 6 ports between which exist 9 routes. At
the first sight of his navigation chart, the 6 ports and 9 routes on it reminded him of Graph Theory
that he studied in class at university. In the way that Leonhard Euler solved The Seven Bridges of
Knigsberg, Wang Haiyang regarded the navigation chart as a graph of Graph Theory. He
considered the 6 ports as 6 nodes and 9 routes as 9 edges of the graph. The graph is illustrated as
below.
According to Graph Theory, the number of edges related to a node is defined as Degree number of
this node.
Wang Haiyang looked at the graph and thought, If arranged, the Degree numbers of all nodes of
graph G can form such a sequence: 4, 4, 3,3,2,2, which is called the degree sequence of the graph.
Of course, the degree sequence of any simple graph (according to Graph Theory, a graph without
any parallel edge or ring is a simple graph) is a non-negative integer sequence
Wang Haiyang is a thoughtful person and tends to think deeply over any scientific problem that
grabs his interest. So as usual, he also gave this problem further thought, as we know, any a
simple graph always corresponds with a non-negative integer sequence. But whether a
non-negative integer sequence always corresponds with the degree sequence of a simple graph?
That is, if given a non-negative integer sequence, are we sure that we can draw a simple graph
according to it.
Lets put forward such a definition: provided that a non-negative integer sequence is the degree
sequence of a graph without any parallel edge or ring, that is, a simple graph, the sequence is
draw-possible, otherwise, non-draw-possible. Now the problem faced with Wang Haiyang is
how to test whether a non-negative integer sequence is draw-possible or not. Since Wang Haiyang
hasnt studied Algorithm Design course, it is difficult for him to solve such a problem. Can you
19/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
help him?
Input
The first line of input contains an integer T, indicates the number of test cases. In each case, there
are n+1 numbers; first is an integer n (n<1000), which indicates there are n integers in the
sequence; then follow n integers, which indicate the numbers of the degree sequence.
Output
For each case, the answer should be yes or no, indicating this case is draw-possible or
non-draw-possible.
Sample Input
2
6443322
42111
Output for the Sample Input
yes
no
20/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
Problem J. Dividing Sea Area to Navigation-Triangle
Description
When a vessel sails on the vast and boundless sea, the captain must know his position in any time.
There is a technique called triangle-navigation can solves this problem.
Suppose there are three islands in some sea area. They form a large triangle. There is a radio
navigation station respectively on each island. The navigation station sends out radio signals
continuously. After the vessel receives the signals, its position can be known by calculating those
three different signals.
There is a raised n-multilateral sea area which is formed by n islands. Each island has a radio
navigation station. The n islands form a raised n-multilateral graph. Every three islands form a
triangle division area. Vessels sailing in this triangle area should determine the position by the
signals from those three radio navigation stations in the three islands.
Of course, all navigation triangles divided from the raised n-multilateral graph can not overlap one
another. Consequently, this raised n-multilateral graph is divided into n-2 triangles areas.
By the way, there are some smaller islets in the raised n-multilateral sea area and there is no
navigation station in any islet. These small islets are related with our problem, we will explain it
later.
An experienced captain had navigated in this sea area for several years. However, he found it is
improper to divide the sea area to n-2 navigation triangles as the current scheme. After deep
thinking, he put forward a new method.
21/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
Of course, he still divided raised n-multilateral graph sea area into n-2 navigation triangles which
are not overlapped one another. The three vertexes of the triangles are three islands with
navigation station. According to the scheme which is put forward by the old captain, a weight
value is necessary for each triangle sea division area. Calculating formula of the weight value is as
follows:
V= S+2*a +b
In that formula, the letter V expresses the weight value of the triangle sea area, the letter S
expresses the area of that triangle sea, The letter a expresses the number of smaller islets inside
the triangle. The letter b expresses the number of those small islets on the common edge
between the two triangle sea areas. After calculating according to the formula above, each triangle
sea area division has a weight value. The old captain thought, for the n-2 triangle areas, there will
be n-2 weight values. Among these weight values, when the difference of the maximum weight
value and the minimum weight value reaches a minimum, this scheme of division is optimum.
That scheme will benefit sailing most.
As none people can solve that problem on the vessel. Now the captain is visiting you, he hopes
you can help him.
Input
Two positive integers n (3<=n <=100) and m (0 <=m<=20) are provided firstly in each test case.
They take up one line respectively, then n lines of data follow, there are 2 floating numbers in each
line expressing coordinates of radio navigation station, then following m lines, there are 2 floating
numbers in every line expressing coordinates of smaller islets which are not equipped with radio
navigation station. Input is terminated by end of file.
Output
For each case, when the difference of weight value between the maximum weight value and
minimum weight value is minimum, output this difference, the result should be a
floating-point-number, having 2 digits after radix point.
Sample Input
42
00
10
11
01
0.2 0.2
0.5 0.9
22/23
The 33rd ACM International Collegiate Programming Contest Asia Harbin Regional Contest
4 10
00
10
11
01
0.5 0.1
0.5 0.2
0.5 0.3
0.5 0.4
0.5 0.5
0.5 0.6
0.5 0.7
0.5 0.8
0.5 0.9
0.2 0.1
Output for the Sample Input
0.00
2.00
23/23