28
th
Annual ACM/ICPC Asia Regional Contest
Guangzhou
Sponsored by IBM
Hosted by Zhongshan (Sun Yat-sen) University
and
Yat-sen Cup Collegiate Programming Contest
Problem Set
2003-11-23
This problem set should contain eight (8) problems on nineteen (19) numbered pages.
Please inform a runner immediately if something is missing from your problem set.
PDF created with pdfFactory Pro trial version www.pdffactory.com
2003 ACM/ICPC Asia Regional Contest / Guangzhou
Zhongshan (Sun Yat-sen) University
Problem A: Special Experiment
- 1 -
Problem A
Special Experiment
Input File: atom.in
As we know, an atom can be in different energy states (or “energy levels”). Usually, when it
transits from a higher energy state to a lower one, it will emit a photon, whose energy is equal to
the difference in energy of these two states. Absorption of photons is the reverse process. If a
photon, whose energy equal to the difference in energy of two states of an atom, passes by, it may
be absorbed and its energy will put the atom into a higher energy level. For most elements, the
atom can transit between any two states directly, by emitting or absorbing only one photon.
Scientists are puzzled by a new element that they discovered recently. For two certain energy
states, the atom of this element can transit between them directly (emitting or absorbing one and
only one photon), but for some other pairs of energy states, the atom cannot.
Generally speaking, when an atom transits among energy states one after another, a trail of events
(emitting or absorbing a photon) occurs. For example, when transiting from energy state
1
i
E to
t
i
E , the atom follows this sequence:
tk
iiiii
EEEEE ,,,,,,
321
k
i
E (1 ≤ k ≤ t) represents a certain energy state. During the of process of transiting from
k
i
E to
1+k
i
E , one and only one photon is emitted or absorbed.
The atom can be in any energy state and transit to some other one. But as we mentioned above, for
some pairs of energy states, this special atom cannot transit between them directly. What’s more,
when its energy state changes from one to another, for example, from
1
j
E to
w
j
E , it can only
follow a unique sequence
w
jjjj
EEEE ,,,,
321
. And the most interesting thing is that it can only
follow another unique sequence
123
,,,,
jjjj
EEEE
w
, when it transits back from
w
j
E to
1
j
E .
You can find that it is the reversion of the former one! Right! Isn’t it special?
Now, the scientists need your help today. In an experiment, some atoms of this new element will
be put into a container. Any two atoms would be regarded as “dangerous atoms” if they satisfy one
of the following conditions:
l They are in the same energy state.
l They are in different energy states. But if one of them emits or absorbs a photon, they will be
PDF created with pdfFactory Pro trial version www.pdffactory.com
2003 ACM/ICPC Asia Regional Contest / Guangzhou
Zhongshan (Sun Yat-sen) University
Problem A: Special Experiment
- 2 -
in the same states too.
You must make sure that there are no dangerous atoms in this container. And the higher the total
energy of the atoms in the container is, the more easily will the experiment succeed.
Now, the scientists have told you all photons that the atoms of this element can emit or absorb, as
well as the energy of all atom states. They ask you calculate the highest total energy that the atoms
in the container can reach.
Input
There are several testcases in the input. Each begins with a line containing two integers N, M (0 <
N, M ≤ 200), representing the number of the energy levels and the number of the different photons
that this kind of atom can emit or absorb respectively. The two numbers are followed by exactly N
+ M lines, which contain one positive integer each. These N+M positive integers are not greater
than 1,000,000. The first N distinguishing integers are the energy of the atom in the N different
energy states in ascending order. The next M integers correspond to the energy of the M different
photons, which can be emitted or absorbed by atoms of this element. If the difference in energy of
any two states equals to the energy of one of the M photons, the atom can transit between these
two states directly.
There is no blank line between two data sets. The last testcase is followed by a line containing two
zeros.
Output
For each testcase, output one line containing an integer, which indicates the highest total energy
that the atoms in the container can reach. There should be no blank line between any two cases.
Sample Input
Output for the Sample Input
3 1
2
4
6
2
0 0
8
PDF created with pdfFactory Pro trial version www.pdffactory.com
2003 ACM/ICPC Asia Regional Contest / Guangzhou
Zhongshan (Sun Yat-sen) University
Problem B: Elevator Stopping Plan
- 3 -
Problem B
Elevator Stopping Plan
Input File: elevator.in
ZSoft Corp. is a software company in GaoKe Hall. And the workers in the hall are very
hard-working. But the elevator in that hall always drives them crazy. Why? Because there is only
one elevator in GaoKe Hall, while there are hundreds of companies in it. Every morning, people
must waste a lot of time waiting for the elevator.
Hal, a smart guy in ZSoft, wants to change this situation. He wants to find a way to make the
elevator work more effectively. But it’s not an easy job.
There are 31 floors in GaoKe Hall. It takes 4 seconds for the elevator to raise one floor. It means:
It costs 1204)131(
=
×
−
seconds if the elevator goes from the 1
st
floor to the 31
st
floor
without stop. And the elevator stops 10 second once. So, if the elevator stops at each floor, it will
cost 4101029430
=
×
+
×
seconds (It is not necessary to calculate the stopping time at 31
st
floor). In another way, it takes 20 seconds for the workers to go up or down one floor. It takes
6002030
=
×
seconds for them to walk from the 1
st
floor to the 31
st
floor. Obviously, it is not a
good idea. So some people choose to use the elevator to get a floor which is the nearest to their
office.
After thinking over for a long time, Hal finally found a way to improve this situation. He told the
elevator man his idea: First, the elevator man asks the people which floors they want to go. He
will then design a stopping plan which minimize the time the last person need to arrive the floor
where his office locates. For example, if the elevator is required to stop at the 4
th
, 5
th
and 10
th
floor,
the stopping plan would be: the elevator stops at 4
th
and 10
th
floor. Because the elevator will arrive
4
th
floor at 1243
=
×
second, then it will stop 10 seconds, then it will arrive 10
th
floor at
46461043
=
×
+
+
×
second. People who want to go 4
th
floor will reach their office at 12
second, people who want to go to 5
th
floor will reach at 322012
=
+
second and people who
want to go to 10
th
floor will reach at 46 second. Therefore it takes 46 seconds for the last person to
reach his office. It is a good deal for all people.
Now, you are supposed to write a program to help the elevator man to design the stopping plan,
which minimize the time the last person needs to arrive at his floor.
Input
The input consists of several testcases. Each testcase is in a single line as the following:
n f
1
f
2
… f
n
It means, there are totally n floors at which the elevator need to stop, and n = 0 means no testcases
PDF created with pdfFactory Pro trial version www.pdffactory.com
2003 ACM/ICPC Asia Regional Contest / Guangzhou
Zhongshan (Sun Yat-sen) University
Problem B: Elevator Stopping Plan
- 4 -
any more. f
1
f
2
… f
n
are the floors at which the elevator is to be stopped (n ≤ 30, 2 ≤ f
1
< f
2
… f
n
≤
31). Every number is separated by a single space.
Output
For each testcase, output the time the last reading person needs in the first line and the stopping
floors in the second line. Please note that there is a summary of the floors at the head of the second
line. There may be several solutions, any appropriate one is accepted. No extra spaces are allowed.
Sample Input
Output for the Sample Input
3 4 5 10
1 2
0
46
2 4 10
4
1 2
PDF created with pdfFactory Pro trial version www.pdffactory.com
