To solve this problem, use brute force search.
Just generate all the subsets of the given set of stones. For each subset, calculate S=W1-W2, where  W1 is the total weight of the subset, W2 is the total weight of the remaining stones. Select the minimal I.

if program writes -0, your [censored] checker says WA#3
inspite of accuracy  in 2 digits. abs(-0-0) < 0.001 !

Edited by moderator 06.04.2007 22:54

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
int main(){
    long a;
    double b[100000];
    int i=0;
    cin>>a;
    while(a!=EOF){
    if (a>=0) {b[i]=sqrt((double)a);i++;}
    else  continue;
    cin>>a;
    }
    cout.setf(ios::fixed);
    cout.setf(ios::showpoint);
    for(int j=i-1;j>=0;j--) cout<<setprecision(4)<<b[i]<<endl;
return 0;
}

Can anybody help me? I have WA on the test number 9, but I don't know where I have errors in code. I think, my algorithm is true. It work on all my tests, but crash on jury test. Find errors in my code or give me that test, please. He is it:

program Sum_1497;

{$APPTYPE CONSOLE}
var
  a,b,c,d,e,f,g,h,i,j,n:integer;
  q:array[1..1000,1..1000]of integer;
  ch:char;
  x1,x2,y1,y2:integer;

function TestRect(x1,y1,x2,y2,f:integer):boolean;
var
  i,j:integer;
  a:boolean;
  x,y:integer;
begin
  a:=true;

  if f=1 then
    for j:=y1 to y2 do
    begin
      x:=n+1;
      y:=0;
      for i:=x1 to x2 do
      begin
        if q[j][i]=1 then
          if i<x then x:=i;
        if q[j][i]=0 then
          if i>y then y:=i;
      end;
      if x<y then
        a:=false;
  end;

  if f=2 then
    for j:=y1 to y2 do
    begin
      x:=0;
      y:=n+1;
      for i:=x1 to x2 do
      begin
        if q[j][i]=1 then
          if i>x then x:=i;
        if q[j][i]=0 then
          if i<y then y:=i;
      end;
      if x>y then
        a:=false;
  end;

  if f=3 then
    for j:=x1 to x2 do
    begin
      x:=n+1;
      y:=0;
      for i:=y1 to y2 do
      begin
        if q[i][j]=1 then
          if i<x then x:=i;
        if q[i][j]=0 then
          if i>y then y:=i;
      end;
      if x<y then
        a:=false;
  end;

  if f=4 then
    for j:=x1 to x2 do
    begin
      x:=0;
      y:=n+1;
      for i:=y1 to y2 do
      begin
        if q[i][j]=1 then
          if i>x then x:=i;
        if q[i][j]=0 then
          if i<y then y:=i;
      end;
      if x>y then
        a:=false;
  end;

  TestRect:=a;
end;

begin
  readln(n);
  for i:=1 to n do
  begin
    for j:=1 to n do
    begin
      read(ch);
      q[i][j]:=Ord(ch)-Ord('0');
    end;
    readln;
  end;
  x1:=n+1;
  y1:=n+1;
  x2:=0;
  y2:=0;

  for i:=1 to n do
    for j:=1 to n do
    begin
      if q[i][j]=0 then
      begin
        if i>x2 then x2:=i;
        if i<x1 then x1:=i;
        if j>y2 then y2:=j;
        if j<y1 then y1:=j;
      end;
    end;

  if x1=n+1 then
  begin
    writeln('Yes');
    halt;
  end;
  if (TestRect(1,y1,x2,y2,1))or(TestRect(x1,y1,n,y2,2))
  or(TestRect(x1,1,x2,y2,3))or(TestRect(x1,y1,x2,n,4)) then
    begin
      writeln('Yes');
//      readln(a);
      halt;
    end;

  writeln('No');
//  readln(a);
end.

Comments: I find rect, in which this figure is situated. Then I test all rects, that must bu filles by "0" to free the figure. For this i find the last symbol "0" and the first symbol "1" in each line. If x (position of "0") > y(position of "1") then we cann't free the figure by this direction. There are 4 different directions: up, down, left, and right. If in any of that direction I get "true", then the answer if "Yes". Else the answer is "No".

P.S. Sorry for poor English. ^_^

Please, tell me, why I get access violation??
It's my code:


{$apptype console}
var i,n,x,k,z:integer;
s:ansistring;
a:array[-10000..2000001]of boolean;
t:array[1..6]of string;

function correct(i,j:integer):boolean;
begin
result:=true;
for z:=1 to length(t[j]) do
if s[i+z]<>t[j,z] then begin result:=false; exit; end;
end;

procedure test;
var i,j:integer;
begin
fillchar(a,sizeof(a),false);
a[0]:=true;
for i:=1 to length(s) do
for j:=1 to 6 do
if a[i-length(t[j])] then
if correct(i-length(t[j]),j) then a[i]:=true;
end;

begin
readln(n);
t[1]:='one';
t[2]:='out';
t[3]:='output';
t[4]:='puton';
t[5]:='in';
t[6]:='input';
for i:=1 to n do begin
readln(s);
test;
if a[length(s)] then writeln('YES') else writeln('NO');
end;
end.




I can't understand. Maybe some hint?

Edited by author 06.04.2007 09:56

could anyone help me with test number 5 or give some tests for which my solution gives wrong answer? I have checked all the tests from the webboard.

I tried to solve this test nearly 2 hours and always got WA.The problem was that numbers of "!" can be more than 20 (in 15 test). So my program with next code got wa:
char s[20]
int n;
scanf("%d %s",&n,&s);
int k = strlen(s);

i changed char s[20] to char s[100] and got ac. Admins, plz correct it.

I'm using BFS, for my tests program works correctly.
Please, give me some tests or/and hints concerning my bug

Edited by author 04.04.2007 21:15

Dear admins. I think you must add max test like this
200000 sorted integers.
I think some people may lost AC.
Please check this.

#include <iostream.h>
#include <math.h>
int prost(int a)
{
    int kol=0;
    for(int i=2;i<=int (sqrt(a));i++)
    {
        if(a%i==0)
            kol++;
    }
    if(kol==0)
        return 1;
    else
        return 0;
}
int main()
{
    int T,n,kol=0,i=0,p=2;
    cin>>T;
    for(int j=0;j<T;j++)
    {
        cin>>n;
        while(i!=n)
        {
            if((prost(pow(2,p)-1))==1)
            {
                i++;
            }
            if(i==n)
            {
                cout<<p<<' ';
            }
            p++;
        }

    }
    return 0;

}

i do this in linux, but online judge told me wrong
i have run it by gcc...

I Qsorted it for I didn't see it was already fucking sorted,Oh damn!WASTE ME 1 HOUR!!!

I'm sure that my algorythm is correct. It's complexity is O
(n log n), because I use quicksort, and then 2 linear
procedures. Why do I get TimeLimitExceed? Is it possible
not to use sorting?

As I understand by random selecting I cannt solve this problem, so I have searching a bit in internet some info to find algo of it - AC. But how could ACM participants check this problem? What another approach? Random --> while (true) subbmiting or what? Please tell me...

http://acm.timus.ru/status.aspx?space=1&pos=1533345

regrettably I change my Motto ( it was "Your server is one big bug")
know i have to remember this words

Who have the test case?
MAIL ME: sunzheng.david@163.com

in Input format:

 В следующим M строках находит цвета), числа в строке разделены одним пробелом.

Some mistake there - no sense of sentence

Firstly I've got WA13 but when I check test [ 1 0 ] - it got AC. But description says that N >= 2 - I am not misstaken?

Thank!!! Programm terminated!

Edited by author 03.04.2007 14:19

Edited by author 03.04.2007 14:19