AIOC Banner

Problem: Travelling Salesperson

Want to try solving this problem? You can submit your code online if you log in or register.

Travelling Salesperson

Input File: salesin.txt
Output File: salesout.txt
Time Limit: 1 second

Even in uncertain economic times, no home can be without electrical appliances. Realising that there is still a sales opportunity, you have recently taken up a part-time job selling electrical appliances the old fashioned way--travelling door to door. However, your hometown of Perth is full of electrical salespeople who have cornered the market, and so you must travel across Australia to find customers.

You will start in your hometown, Perth, drive across Australia to Sydney, and then back again to Perth. There are three routes between Perth and Sydney. In your market research, you have counted the number of customers living along each route. You wish to plan your trip to Sydney and back so that you visit the greatest number of customers possible. You must take a different route on the return journey, otherwise you would simply end up visiting the same satisfied customers twice.

Your task is to write a program which, given the number of customers along each of the three routes between Perth and Sydney, determines the greatest number of customers you can visit by travelling from Perth to Sydney and back.


The input file will consist of three lines, each containing a single integer (whole number), representing the number of customers on the northern, central and southern routes respectively. Each route will contain between 0 and 1000000 customers, inclusive.


The output file should consist of a single integer: the greatest number of customers you can visit by driving from Perth to Sydney and back again.

Sample Input


Sample Output



The sample input is demonstrated in the diagram below.


To ensure you visit the greatest number of customers in this case, you should travel the southern route to visit 700 customers on the way to Sydney, then return via the northern route to visit 500 customers on the way back for a total of 1200 customers. Alternately, you could take the northern route first, and return via the southern route, however the maximum number of customers you can visit is 1200.


The score for each input scenario will be 100% if the correct answer is written to the output file, and 0% otherwise.


Privacy statement
© Australian Mathematics Trust 2001-2023

Page generated:  3 June 2023,  2:33pm AEST