OSPROB1 - Operating System Problems (Task Scheduling)

no tags 

As you all know, Operating System (OS) is a software that controls the execution of computer programs and may provide various services. Although modern operating systems are very easy to use and give us lots of services, their designing is not so easy. It needs lots of work and time to design a good OS. But no OS is perfect. Either they are not so usable or they are not so secure (got tons of viruses). Lingates, as an excellent programmer, wants perfection in all things. So he decided to not use this OSs and write his own OS. But he found out this work is not so easy to do alone even for a programmer like him. So he needs your help.

As a programmer with honor he won’t let you do equal or more work in a turn then him (Means Lingates has to do more work then you on each turn). Each turn you both divide the works between yourself. But the works are related so it’s better to take works which are adjacent. Like if there are 5 works 5, 2, 7, 1, 3 then Lingates would take 1st work and give you the 2nd work. But you can't take 2nd and 3rd work because that sum to 7+2 = 9 which is more than his work (5). Again you can't take 2nd and 4th work because they are not adjacent. After you both finish your work you both will again distribute your works. There is no limit how much work you both can take on a turn. Like Lingates can take 1st and 2nd work on first turn and give you no work on that turn or he can take 1st, 2nd and 3rd turn (total 5 + 2 + 7 = 14) and give you only 4th (1) or both works (1 + 3 = 4). As you are helping him he let you to divide the works but it has to be that Lingates has to do more work on each turn. As you are also a programmer with honor you also like to take the turns and divide the work on each turn such that it maximizes your total works.

Write a program which will take the list of work and give the total amount of work done by Lingates and you if you make the list optimally. Again Lingates will do any amount of work you will give him in any turn as long as your work on that turn is less than his.

Input

The first line will be number of test cases (T <= 500) and each case will start with an integer n (0 <= n <= 100). In the following line n numbers will given as the amount of works (all will be non negative integer < 1000)

Output

A single line for each test case first the total work of Lingates and second the work of your.

Example

Input:
4
3
1 2 3
5
5 2 7 1 3
5
6 6 6 6 6
7
4 9 5 7 6 5 1

Output:
6 0
12 6
18 12
20 17

Explanation

In 1st case you have to give Lingates all 3 works because 1 < (2 + 3) and (1 + 2) = 3, so you can't take any work.

In 2nd case you can give Lingates 1st work (5) and you can take 2nd (2). Then you can give Lingates the 3rd (7) and you can take the rest (1 + 3).

In 3rd case you can give Lingates 1st to 3rd work (6 + 6 + 6 = 18). You can take the left two works (6 + 6 = 12).

In 4th case you can give Lingates 4 and 9 and you will take 5 and 7. Then in next turn you can give him 6 and you own take 5. Then you can give him 1. So totalling (4 + 9 + 6 + 1) = 20 and (5 + 7 + 5) = 17.


hide comments
Stanislav Zholnin: 2016-04-28 23:53:35

I've been reading it for half an hour and still don't understand why, e.g. in case 2 Lingate can't take 5+2+7 giving you 1+3 with total work of 14+4, which is definitely more total works then 5+2 mentioned in official solution.

Ah, understood - limitations of English language. "Your" is meant here to be singular, not plural, so "Your work" means only work of person solving the problem. Another valid way to understand "Your" is your work as a team, so both Lingates and me. But this is incorrect understanding.

Last edit: 2016-04-29 22:08:39
Vidit Gupta: 2012-12-13 14:08:34

In case 1, cant I take the first work (i.e. 1) and let Lingates take 2nd and 3rd (i.e. 2 and 3 respectively)?

:-P: 2011-11-05 20:17:02

what's wrong with this problem ?
there's submit button and last submissions frame !
and even my Ac solution gets wrong answer !

Last edit: 2011-11-05 20:17:33
Husnun Nashir: 2010-12-07 05:54:03

I get confused with the 4th case. Why the last work(1) must be given to Lingate ? If the last work given to me, the output should be = 19 18, that more maximal and not contradict with the rules. Please correct me if I am wrong, thanks..

Reply : If the last work 1 will given to you int the second turn then total amount of your work will be 6 which is equal to Lingates work. So you can't take that. Also if in 3rd turn you take the work then your total work in that turn is 1 and total work of Lingates is 0. So it also not possible.

Last edit: 2011-01-24 13:38:54
Billy Pramboro: 2010-12-01 05:02:01

Sorry but that you was told that "Again you can't take 2nd and 4th work because they are not adjacent". It's make me confused. Cause it's contrast with the 2nd case. Thanks

Reply: You can't take 2nd and 4th work on a single turn. Because they are not adjacent. In a new turn you can take anything if that not contradict with rules.

Last edit: 2010-12-03 16:15:59
Manukranth: 2010-11-23 11:28:22

EDIT:
Output for n=0:
0 0

Reply: If n=0 then also in any turn Lingates don't get smaller or equal work then you because their is no round. So I think it could be a valid case.

Last edit: 2010-11-23 21:49:42
Oleg: 2010-11-22 12:36:09

Also wrong exaplanation about 5 2 7 1 3 -> 12 6

Seems Lingates get 1 + 3 and not 1 + 2 + 3.

Edit: Sorry and thanks :) . Actually the explanations are of 3rd and 4th case but was written as 2nd and 3rd. Updated and Fixed.

Last edit: 2010-11-22 08:33:09
Muhammad Ridowan: 2010-11-22 12:36:09

Please tell if you find any fault or ambiguous is the problem description. Its my first created problem so any suggestion is welcomed.


Added by:Muhammad Ridowan
Date:2010-11-21
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 CLOJURE FORTRAN ICON ICK PRLG-swi ST
Resource:Own, thanks for helping Zobayer,Tulip and Shiplu