SHINCARD - Shinchan and Magic Card
An alien group has attacked Kasukabe so whole city is in big trouble! All people (count is N) in Kasukabe try to run away so is Shinchan! They came across a bridge over a river, and that bridge has been cursed by aliens. Bridge will collapse when someone passes over it.
Shinchan as a legend calls an ultra legend Buri Buri Zaemon by his magic card. Buri Buri appears and suggests Shinchan that whenever a person having magic card in his hand passes over the bridge then it will not collapse but since bridge is fragile only maximum 2 persons at a time can pass over it (and one of them should have magic card in his hand). All citizens of Kasukabe have to go to other side of the river using bridge as quickly as possible. When two persons A and B pass over bridge, it takes MAX(time(A), time(B)) to get them on the other side of river (where time(i) is the time taken by ith person to pass over the bridge). Shinchan has an array of all time[] values of all citizens.
Find the minimum time in which they escape the bridge. (There is only one magic card)
Input
First line contains N, 1 <= N <= 100000.
Next line contains N integers, 1 <= time[i] <= 1000000000 for each 1 <= i <= N.
Output
Output the minimum time to get all persons over the other side of the river.
Example
Input: 4 1 2 5 10 Output: 17
Explanation
- 1 and 2 cross,
- 1 comes back,
- 5 and 10 cross,
- 2 comes back,
- 1 and 2 cross.
Total = 2 + 1 + 10 + 2 + 2 = 17.
hide comments
berted:
2019-12-23 10:15:46
Testcases not strong enough, doesn't consider cases in which the second person is slow
|
|
redblade098:
2019-12-23 07:42:24
my 50th with such special one
|
|
pandey101299:
2019-03-25 10:12:07
thanks@pranjulpal18 |
|
pranjulpal18:
2019-01-02 18:34:52
See for n=4 to 8 on pen and paper and you will get the formula. |
|
pranjulpal18:
2019-01-02 18:32:01
My 101th :)
|
|
:D:
2018-09-21 23:43:45
Fun problem. |
|
julkas:
2018-09-12 09:56:37
@shubham_001 Can you explain example test case, please?
|
Added by: | MichaelJ |
Date: | 2018-09-11 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | own |