Ha-ha...

6 5
1 0 1
3 2 1
5 4 1
2 1 0
4 1 0

answer:


Possible
0
1
1
2
1
2

I assume Test 9 looks like this:

input:
1000000000

output:
26263 25600

Or just DFS.

#include<iostream>
#include<cmath>
using namespace std;



int main(){
int n,a[20],delta=1000000000;
cin>>n;
for(int i=0;i<n;i++)
cin>>a[i];
int  s1=0,s2=0;
int t = 1<<n;
for(int i=0;i<t;i++){
    s1=0;
    s2=0;
    for(int j=0;j<n;j++){
        if( ( (1<<j) & (i) ) == 0 ) s1+=a[j];
        else s2+=a[j];
    }
    if(abs(s1-s2) < delta)
    delta = abs(s1-s2);

}
cout<<delta<<endl;
return 0;
}

I've got AC! Here is the reason of WA14:
The length of the first line may be >250!

I hope it will help someone.

My program gives 1368.894 on your first test, but I have AC. Maybe you was wrong in your realization?

Try this tests WITH other tests from forum:
intput
1 12 10
13 15 10
57 180 10
0 0
output
0.08(3)
0.8(6)
0.31(6)

large tests:
1 9991 10
1 9992 10
1 9997 10
1 958 10
0 0
0.(000100090081072965669102191972775497948153338004203783405064558102292062856570913822440196176558903012711440296266639975978380542488239415473926533880492443198878991091982784506055449904914422980682614352917625863276949254328896006405765188669802822540286257631868681813632269042137924131718546692022820538484636172555299769792813532178961064958462616354719247322590331298168351516364728255429886898208387548793914523070763687318586728055249724752277049344409968972074867380642578320488439595636072465218696827144429986988289460514463016715043539185266740066059453508157341607446702031828645781203082774497047342608347512761485336803122810529476528875988389550595535982384145731158042238014212791512361125012511260134120708637773996596937243519167250525472925633069762786507857071364227805024522069862876588930037033329996997297567811029926934240816735061555399859873886497848063256931238114302872585326794114703232909618656791112000800720648583725352817535782203983585226704033630267240516464818336502852567310579521569412471224101691522370133119807827044339905915323791412271043939545591031928735862276048443599239315383845460914823341006906215594034631168051246121509358422580322290061054949454509058152337103393053748373536182564307877089380442398158342508257431688519667700930837753978580722650385346812130917826043439095185667100390351316184566109498548693824441997798018216394755279751776598939045140626563907516765088579721749574617155439895906315684115704133720348313482133920528475628065258732859573616254629166249624662195976378740866780102091882694424982484235812231007907116404764287859073165849264337904113702332098889)
0.000(1000800640512409927942353883106485188150520416333066453162530024019215372297838270616493194555644515612489991993594875900720576461168935148118494795836669335468374699759807846277021617293835068054443554843875)
0.(000100030009002700810243072921876562968890667200160048014404321296388916675002500750225067520256076823046914074222266680004001200360108032409722916875062518755626688006401920576172851855556667)
0.0(01043841336116910229645093945720250521920668058455114822546972860125260960334029227557411273486430062630480167014613778705636743215031315240083507306889352818371607515657620041753653444676409185803757828810020876826722338204592901878914405)

1st student makes 1st move, the second one makes 2nd move, then first strudent makes third move and so on.

 if (k>n/2)k=n-k+1;

1. 2 2 1 1 - YES
This is such a sequence:
(1;2) and (1;0)
2. 2 2 2 2 - NO
This is impossible because number 2 is written only on one card (2;1)
so it couldn't appear twice.

Good luck!

Edited by author 07.06.2010 13:52

Right answer is:

0