Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- You are a traveling salesman, delivering clever ACM code to houses. There are N houses you
- need to visit, and your boss has assigned these houses so that you only need to travel up
- and down Main Street to visit all of them. House number i is x_i metres east of Town Hall
- on Main Street.
- Your task is to visit each house once. However you get paid $1 for each metre you travel,
- so you also want to make as much money as possible! Your boss knows this however, so he's
- given you a self-driving car than drives directly between two points. However, being the
- clever ACM coder you are, you have hacked the software and can change the order in which
- the car will visit houses, to some p_1, p_2, ..., p_n. Then the car will start at House p_1
- then drive to House p_2 then to House p_3 and so on. The car also has a "tour mode" where
- after visiting p_n, it will return to p_1.
- What is the maximum amount of money you can make, under certain requirements? How many orders
- p_i will make you that sum of money.
- Input:
- The first line will contain an integer T, the number of test cases.
- Each test case will contain two lines. The first line will contain the integer N (1<=N<=100,000.
- The second line will contain N space separated integers, x_1 to x_n (0<=x_1<=x_2<=...<=x_n<=10^9)
- Output:
- Output all integers modulo 1e9+7.
- For each test case, output two lines:
- The first line should contain two space separated integers: the maximum amount of money you can make
- not in tour mode, and the amount of different orders that will make you that sum.
- The second line should contain two space separated integers, with the same information given that
- you are in tour mode.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement