Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|

Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |

Language: The Traveling Salesman
Description For thousands of years, salesmen have faced the problem of touring sites for potential customers, visiting each site exactly once, and minimizing the total cost of this tour. In the old days, these sites were towns spread out throughout the country, and the salesman had to travel the rickety, crooked roads that connected the towns. But now, in 2030, cities and have modernized and grown, so a salesman typically stays within the same city. Furthermore, modern cities are laid out in a grid-like pattern of tall skyscrapers, with sky bridges joining some pairs of adjacent skyscrapers on all floors. The salesman has determined which floor of each skyscraper contains the most potential customers and will only visit the best floor of each skyscraper. Now the salesman must plan his course. Starting on the ground floor (floor 0) of the skyscraper in the northwest corner of the grid, the salesman must visit the specified best floor of each skyscraper before returning to the ground floor of either of the skyscrapers at the southwest, southeast, or northeast corners. In order to travel between floor 10 of one skyscraper and floor 6 of an adjacent skyscraper, the salesman first takes the sky bridge across to floor 10 of the adjacent skyscraper and then takes an elevator down 4 floors. Of course, because the salesman’s time is precious, he wants to minimize the total number of floors he must travel by elevator. For example, if his tour involves traveling from floor 3 to 8 to 5 to 10, the number of floors traveled by elevator is (8 − 3) + (8 − 5) + (10 − 5) = 13. To make the salesman’s life (and yours) more difficult, some sky bridges do not exist between two adjacent skyscrapers, and in that case, obviously the salesman cannot fly across the gap. Because modern cities are much larger than the small towns that salesmen dealt with generations ago, our salesman needs a plan so that he does not lose his bearings and visit a skyscraper more than once (in which case he will get beaten by the people for pestering them so much) or less than once (in which case he might have lost profit). To that end, the salesman has decided to only consider tours similar to the one in the figure. The salesman starts at the northwest corner, and either goes south or east for any distance (as long as all sky bridges exist along that path). Then, he turns towards away from the edge of the city and travels to the adjacent skyscraper, and turns again, heading back opposite the initial direction. After any amount of zig-zagging, the salesman can choose to switch over to zig-zagging in the other orientation. Given the floors of each skyscraper in the city that the salesman wishes to visit and which sky bridges do not exist, compute the minimum number of floors that the salesman must travel on a tour that meets the above criteria. Also, print out the number of possible tours achieving that minimum. Input The first line contains two numbers Output If there is no tour, print Sample Input 2 4 0 y 10 20 30 5 8 25 28 Sample Output 1 tours, traveling a minimum of 60 total floors Source |

[Submit] [Go Back] [Status] [Discuss]

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di

Any problem, Please Contact Administrator