ACPC11C - Circleland
You are visiting circleland, and you have long waited to visit their famous art exhibition. The exhibition has N rooms arranged in a cycle. In every room, there are some artistic pieces. The rooms are named R1, R2, ... RN. There are also N corridors, named C1, C2, ... CN, of lengths L1, L2, ... LN, respectively. Each corridor Ci connects the two rooms Ri and Ri+1, except CN which connects RN and R1. Thus, the whole exhibition forms a cycle. You can walk in both directions in every corridor.
There is a single entrance to the exhibition in room R1, but there are exits in every room. As there is nothing interesting to see in the corridors, you would like to spend the least effort walking through corridors in the exhibition. Compute the minimum total distance you need to walk in corridors such that you enter from the entrance, exit from any exit and visit all rooms.
Input
Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 100). Next T lines contain the test cases, each on a single line.
Each case starts with an integer N, the number of rooms in the exhibition (2 ≤ N ≤ 100,000), followed by N numbers, the lengths of the corridors, L1, L2, ... LN, in this order (1 ≤ Li ≤ 1,000,000).
The sum of the lengths of all corridors will not exceed 1,000,000,000.
Output
For each test case, output, on a single line, a single number representing the minimum total distance you have to walk in corridors such that you visit all rooms.
Example
Input: 2 5 1 1 1 1 1 7 100 15 20 42 33 15 24 Output: 4 149
hide comments
Akb:
2013-05-21 07:33:10
got AC in 0.09...second fastest solution as of now...!! :) |
|
divya gupta:
2013-05-21 07:33:10
@admin...please check my solution id 9104065
|
|
Devil D:
2013-05-21 07:33:10
Correct answer for
|
|
I_AM:
2013-05-21 07:33:10
@laplace: answer should be 16...
|
|
! include(L.ppt):
2013-05-21 07:33:10
@laplace : answer for ur test case is 16 acc. to me........ Last edit: 2012-01-31 13:17:39 |
|
Laplace:
2013-05-21 07:33:10
wah AC :)
|
|
Smit Mehta:
2013-05-21 07:33:10
can he visit the same room twice? |
|
Devil D:
2013-05-21 07:33:10
@mitch - thanks for the hint .
|
|
neerajcrespo:
2013-05-21 07:33:10
altogether, there can be only four possible cases. is there any tricky case? WA :(
|
|
Aniket Divekar:
2013-05-21 07:33:10
plz give some more test cases(tricky if possible)
|
Added by: | mohamedwahba |
Date: | 2011-12-15 |
Time limit: | 2.441s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Arab Collegiate Programming Contest 2011 |