The 35th ACM-ICPC Asia Regional Contest 甘氨胆酸(Hangzhou)
isaoContest Section
October 24, 2010
Sponsored by IBM & Alibaba
Zhejiang Sci-Tech University
This problem set should contain 10 problems on numbered 24 pages. Please inform a runner immediately if something is missing from your problem set.
Problem A. Naughty fairies
Description
you商城
Once upon a time, there lived a kind of fairy in the world. Those fairies could hear the voice of fruit trees, and helped people with a harvest. But people didn’t know that fruits are also those fairies’ favorite food. After the fairies ate people’s fruits, they always did something to cover it up.
One day a little fairy named Lily flew into an orchard and found a large peach tree. Hungry as Lily was, she started eating without thinking until her stomach was full. In the fairy world, when a fairy ate the fruits in a fruit tree, sometimes the fruit tree would feel honored and bore more fruits immediately. That’s why sometimes the number of fruits in
a tree got increased after a fairy ate fruits of that tree.
But the fairies didn’t want people to find out weird things such as fruits become more or less suddenly. Lily decided to use a magic spell so that the orchard owner couldn’t find the change of the number of peaches.
Suppose there were N peaches on a tree originally and there were M peaches left after Lily was full. M may be greater than, less than or equal to N. All M peaches were visible at first, and Lily wanted to make an illusion so that exactly N peaches are visible.
Lily can do 3 kinds of spell to change the total visible number of peaches:
1) “PAPADOLA”：This spell would increase the number of visible peaches by one.
2) “EXPETO POTRONUM”：This spell would double the number of visible peaches.
3) “SAVIDA LOHA”:This spell would decrease the number of visible peaches by one.
Each spell would take one minute and Lily wanted to finish as fast as possible. Now pleas
e tell Lily the least time she needs to change the number of visible peaches to N.
Input
There are several test cases, ended by “0 0”.
For each test case, there are only one line containing two numbers separated by a blank, N and M, the original numbers of peaches and the numbers of peaches left(0<N,M<10500).There is no leading zero.
cpldOutput
For each test case, you should output just a number K indicating the minimum time (in minutes) Lily needed to finish her illusion magic.
Sample Input
5 2
1 99
86 32
0 0
桁架桥
Sample Output
2丙烯酸乳液
98
12
Problem B. Prison Break
Description
Rompire is a robot kingdom and a lot of robots live there peacefully. But one day, the king of Rompire was captured by human beings. His thinking circuit was changed by human and thus became a tyrant. All those who are against him were put into jail, including our cl
ever Micheal#1. Now it’s time to escape, but Micheal#1 needs an optimal plan and he contacts you, one of his human friends, for help.
The jail area is a rectangle contains n×m little grids, each grid might be one of the following:
1) Empty area, represented by a capital letter ‘S’.
2) The starting position of Micheal#1, represented by a capital letter ‘F’.
3) Energy pool, represented by a capital letter ‘G’. When entering an energy pool, Micheal#1 can use it to charge his battery ONLY ONCE. After the charging, Micheal#1’s battery will become FULL and the energy pool will become an empty area. Of course, passing an energy pool without using it is allowed.
4) Laser sensor, represented by a capital letter ‘D’. Since it is extremely sensitive, Micheal#1 cannot step into a grid with a laser sensor.
5) Power switch, represented by a capital letter ‘Y’. Once Micheal#1 steps into a grid with a Power switch, he will certainly turn it off.
In order to escape from the jail, Micheal#1 need to turn off all the power switches to stop the electric web on the roof—then he can just fly away. Moving to an adjacent grid (directly up, down, left or right) will cost 1 unit of energy and only moving operation costs energy. Of course, Micheal#1 cannot move when his battery contains no energy.
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议