thx

Извините за то, что пишу не на английском. Это лучше, чем использование электронного переводчика, да и администрация, по всей видимости, состоит только из русскоговорящих :)

Пишу решение к зачаче 1856. Прилагаю две программы, первая - исходная, вторая - незначительно изменённая (добавлен новый формальный параметр к функции, который никак не используется и на ход программы не влияет). Первая прошла 2 теста, вторая - только 1 с вердиктом Wrong Answer на втором.


КОД 1
вердикт: Time Limit Exceeded #3
_____________________________________
type
  situation = array [1..1000] of boolean;
  memory = array of situation;



var
  a: array [1..1000] of record
       a, b: integer;
     end;
  mem: memory;
  n, i: integer;



Function Process (ml: integer; mem: memory): boolean;

var
  z1, z2: boolean;
  s: situation;

function Sravn (a, b: situation): boolean;
var i: integer;
begin
  for i := 1 to n do
    if a[i] <> b[i] then
    begin
      sravn := false;
      exit;
    end;
  sravn := true;
end;

function War: boolean;
var
  i: integer;
  z: boolean;
begin
  z := false;
  for i := 1 to n do
    if mem[ml][i] then
      if z
        then begin
          war := false;
          exit;
        end
        else z := true;
  war := true;
end;

function Peace: boolean;
var i: integer;
begin
  for i := 0 to ml-1 do
    if sravn(mem[ml], mem[i]) then
    begin
      peace := true;
      exit;
    end;
  peace := false;
end;

function zA: situation;
var
  i, j: integer;
  s: situation;
begin
  for i := 1 to n do
    for j := 1 to n do
      if mem[ml-1][j] and (a[j].a = i) then
      begin
        s[i] := true;
        break;
      end;
  zA := s;
end;

function zB: situation;
var
  i, j: integer;
  s: situation;
begin
  for i := 1 to n do
    for j := 1 to n do
      if mem[ml-1][j] and (a[j].b = i) then
      begin
        s[i] := true;
        break;
      end;
  zB := s;
end;

begin
  inc(ml);
  if ml = length(mem) then setlength(mem, length(mem)+50);
  s := za;
  mem[ml] := s;
  if war
    then if ml mod 2 = 1
      then process := true
      else begin
        mem[ml] := zb;
        if war
          then process := true
          else if peace
            then process := false
            else process := process(ml, mem);
      end
    else if peace
      then if ml mod 2 = 0
        then process := false
        else begin
          mem[ml] := zb;
          if war
            then process := true
            else if peace
              then process := false
              else process := process(ml, mem);
        end
      else begin
        mem[ml] := zb;
        if war
          then if ml mod 2 = 1
            then process := true
            else begin
              mem[ml] := s;
              process := process(ml, mem);
            end
          else if peace
            then if ml mod 2 = 0
              then process := false
              else begin
                mem[ml] := s;
                process := process(ml, mem);
              end
            else begin
              z2 := process(ml, mem);
              mem[ml] := s;
              z1 := process(ml, mem);
              if ml mod 2 = 1
                then process := z1 or z2
                else process := not(z1) or not(z2);
            end;
      end;
end;



BEGIN
  {$IFNDEF ONLINE_JUDGE}
   assign(input, 'input.txt');
   reset(input);
   assign(output, 'output.txt');
   rewrite(output);
  {$ENDIF}
  {$M 67108864}

  readln(n);
  setlength(mem, 50);
  for i := 1 to n do
  begin
    readln(a[i].a, a[i].b);
    mem[0][i] := true;
  end;
  if process(0, mem)
    then write('War')
    else write('Peace');

  {$IFNDEF ONLINE_JUDGE}
   close(input);
   close(output);
  {$ENDIF}
END.
_____________________________________



КОД 2, звёздочками выделены изменения
вердикт: Wrong Answer #2
_____________________________________
type
  situation = array [1..1000] of boolean;
  memory = array of situation;



var
  a: array [1..1000] of record
       a, b: integer;
     end;
  mem: memory;
  n, i: integer;



Function Process (ml: integer; mem: memory; v: boolean): boolean;  //***************

var
  z1, z2: boolean;
  s: situation;

function Sravn (a, b: situation): boolean;
var i: integer;
begin
  for i := 1 to n do
    if a[i] <> b[i] then
    begin
      sravn := false;
      exit;
    end;
  sravn := true;
end;

function War: boolean;
var
  i: integer;
  z: boolean;
begin
  z := false;
  for i := 1 to n do
    if mem[ml][i] then
      if z
        then begin
          war := false;
          exit;
        end
        else z := true;
  war := true;
end;

function Peace: boolean;
var i: integer;
begin
  for i := 0 to ml-1 do
    if sravn(mem[ml], mem[i]) then
    begin
      peace := true;
      exit;
    end;
  peace := false;
end;

function zA: situation;
var
  i, j: integer;
  s: situation;
begin
  for i := 1 to n do
    for j := 1 to n do
      if mem[ml-1][j] and (a[j].a = i) then
      begin
        s[i] := true;
        break;
      end;
  zA := s;
end;

function zB: situation;
var
  i, j: integer;
  s: situation;
begin
  for i := 1 to n do
    for j := 1 to n do
      if mem[ml-1][j] and (a[j].b = i) then
      begin
        s[i] := true;
        break;
      end;
  zB := s;
end;

begin
  inc(ml);
  if ml = length(mem) then setlength(mem, length(mem)+50);
  s := za;
  mem[ml] := s;
  if war
    then if ml mod 2 = 1
      then process := true
      else begin
        mem[ml] := zb;
        if war
          then process := true
          else if peace
            then process := false
            else process := process(ml, mem, false);  //***************
      end
    else if peace
      then if ml mod 2 = 0
        then process := false
        else begin
          mem[ml] := zb;
          if war
            then process := true
            else if peace
              then process := false
              else process := process(ml, mem, false);  //***************
        end
      else begin
        mem[ml] := zb;
        if war
          then if ml mod 2 = 1
            then process := true
            else begin
              mem[ml] := s;
              process := process(ml, mem, false);  //***************
            end
          else if peace
            then if ml mod 2 = 0
              then process := false
              else begin
                mem[ml] := s;
                process := process(ml, mem, false);  //***************
              end
            else begin
              z2 := process(ml, mem, false);  //***************
              mem[ml] := s;
              z1 := process(ml, mem, false);  //***************
              if ml mod 2 = 1
                then process := z1 or z2
                else process := not(z1) or not(z2);
            end;
      end;
end;



BEGIN
  {$IFNDEF ONLINE_JUDGE}
   assign(input, 'input.txt');
   reset(input);
   assign(output, 'output.txt');
   rewrite(output);
  {$ENDIF}
  {$M 67108864}

  readln(n);
  setlength(mem, 50);
  for i := 1 to n do
  begin
    readln(a[i].a, a[i].b);
    mem[0][i] := true;
  end;
  if process(0, mem, false)  //***************
    then write('War')
    else write('Peace');

  {$IFNDEF ONLINE_JUDGE}
   close(input);
   close(output);
  {$ENDIF}
END.
_____________________________________


Код 1 второй тест проходил, код 2 по неведомым мне причинам выдал неверный ответ.
Как это изменение могло повлиять на результат?

Заранее благодарю за помощь.

why my program give wrong answer?

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include <sstream>
using namespace std;
struct RPair
{
    int x;
    int y;
};
int main()
{
    int N;
    while(cin>>N)
    {
       int p1,p2;
       RPair P;
       vector<int> x_hold;
       vector<int> y_hold;
       vector<RPair> P_hold;
          string  stringx_hold;
           string stringy_hold;
       vector<int> level;
       level.resize(N);
       ostringstream convert;
       string result;
        for(int i=0;i<N;i++)
        {
            cin>>p1>>p2;
              x_hold.push_back(p1);
              y_hold.push_back(p2);
              P.x=p1;P.y=p2;
              P_hold.push_back(P);
              convert<<p1;
              result=convert.str();
              stringx_hold+=result[result.size()-1];
             convert<<p2;
              result=convert.str();
              stringy_hold+=result[result.size()-1];
        }
    sort(x_hold.begin(),x_hold.end());
    sort(y_hold.begin(),y_hold.end());
    sort(stringx_hold.begin(),stringx_hold.end());
    sort(stringy_hold.begin(),stringy_hold.end());
    for(int i=0;i<P_hold.size();i++)
    {
        RPair temp;
        for(int j=0;j<P_hold.size();j++)
        {
            if(P_hold[i].x<P_hold[j].x)
            {
               temp=P_hold[i];
               P_hold[i]=P_hold[j];
               P_hold[j]=temp;
            }
            if(P_hold[i].x==P_hold[j].x&&P_hold[i].y<P_hold[j].y)
            {
               temp=P_hold[i];
               P_hold[i]=P_hold[j];
               P_hold[j]=temp;
            }
        }
    }
    size_t found;
    int t=0;
    for(int i=0;i<x_hold.size();i++)
    {
        t=i;
        if(i!=x_hold.size()-1)
        {
            while(P_hold[t].x==P_hold[t+1].x&&P_hold[t].y==P_hold[t+1].y)
            {
                t++;
              if(t==x_hold.size()-1)
                  break;
            }
        }
        if(i==t)
        {
        convert<<P_hold[t].y;
        result=convert.str();
        found=stringy_hold.find(result[result.size()-1]);
        level[min((int)found,t)]++;
        //stringy_hold.insert((int)found,"n");
        stringy_hold.replace((int)found,1,"n");
        }
        else
        {
     int hold=  level[t]++;
        //stringy_hold.insert((int)found,"n");
        stringy_hold.replace(t,1,"n");
        for(int j=i;j<t;j++)
        {
            level[t]++;
             stringy_hold.replace(j,1,"n");
        }
        }
        i=t;
    }
     for(int i=0;i<level.size();i++)
         cout<<level[i]<<"\n";
     }
}

I cannot pass test10 and i cannot find any mistakes.
Is my algo wrong?
my code:
program p1490;
var
  r,n:int64;
  i:longint;
  x:real;
begin
  readln(r);
  for i:=r-1 downto 0 do
    begin
      x:=sqrt(sqr(r)-sqr(i));
      if x-trunc(x)<1e-10
        then inc(n,r-trunc(x))
        else inc(n,r-trunc(x)-1);
    end;
  writeln(4*(r*r-n));
end.

uses std::nth_element

I have WA#3ю Please give me test

#pragma comment(linker,"/STACK:1000000000,1000000000")

I think, this problem requires that; right?

Any method description or link to article is really appreciable
Thanks in advance.

the distance between any pair of computer must greater than one, not between two pair which connect whit cable.

sorry for my poor english.
GOOD LUCK!!!

Edited by author 06.12.2010 20:26

Edited by author 06.12.2010 20:26

6
1 999999998 b
1 2 b
2 3 w
4 5 b
5 6 w
6 7 b

ans:
999999998 1000000000


Do you understand?

if both players get stuck and after shooting their rockets still stuck?

or is infinite game scenario like 'stalemate' is possible? like

2
......
.*..2.
......
......
.1....
......

Here, if 1 makes turn 2 wins by killing; same goes for 2. now, would they infinitely 'pass moves' to lead it to a 'Draw' / stalemate? or the ans is 'Lose'?

Please, help me understand the problem?
Thanks in Advance.

Hi! My program got output for test1 (011010011):
5
back 0
double
double
double
front 1

---------------------------------------
''-> 0 -> 01 -> 0110 -> 01101001 -> 011010011

It's right?

Upd: I found bug in my program, and fixed it, AC!

Edited by author 28.07.2012 17:59

#include<iostream>
#include<stdio.h>
using namespace std;
int main()
{char c[200000],d;
int i=0,j,k;
while(cin>>c[i]&&i<200000)
{char d=c[i];
if(i!=0&&c[i-1]==d){c[i]=c[i-1]=NULL;i=i-1;}
else if(int(d)==32){c[i]=NULL;}
else i++;
}

cout<<c<<endl;
return 0;
}


Edited by author 20.07.2012 19:31

Hi guys I can't recognize what I've done wrong:

#include <cstdlib>
#include <iostream>
#include <string>
#include <sstream>

using namespace std;

int main(int argc, char *argv[])
{
    int b,c,d,k,n,a[99],TrafficJam=0;
    string line1, line2, line1p, line2p, sk, sn, sa[99];
    size_t pos,pos1[99];
    do
    {
           cout<<"Give first line"<<endl;
           getline (cin,line1);
           pos=line1.find(" ");
           sk=line1.substr(0,pos);
           line1p=line1.substr(pos+1);
           pos=line1p.find(" ");
           sn=line1p.substr(0,pos);
           if ( !(istringstream(sk) >> k) ) k=0;
           if ( !(istringstream(sn) >> n) ) n=0;
    }
    while ( ( sk.size() + sn.size() + 1 ) != line1.size() || k < 1 || k > 100 || n < 1 || n > 100);
    do
    {
          b=0;
          d=-1;
          cout<<"Give second line"<<endl;
          getline (cin, line2);
          line2p=line2;
          for (int i=0;i<n;i++)
          {
              pos1[i]=line2.find(" ");
              sa[i]=line2.substr(0,pos1[i]);
              line2=line2.substr(pos1[i]+1);
              istringstream(sa[i]) >> a[i];
              d+=sa[i].size()+1;
              if (a[i]<0 || a[i] > 100) b++;
          }
    }
    while (b!=0 || d!=line2p.size() );
    for (int i=0;i<n;i++)
    {
        TrafficJam=TrafficJam+a[i]-k;
        if(TrafficJam<0)
        TrafficJam=0;
    }
    cout<<TrafficJam<<endl;
    system("PAUSE");
    return EXIT_SUCCESS;
}

Everything works, but still wrong answer test #1. Can you help? I've tried to find sth for many times, without success.

Edited by author 27.07.2012 16:01

Edited by author 27.07.2012 16:01

Finally, I found the way to solve it in O(n) (needs about 4 full string-checks). In journey to this solution i tried to imagine that i'm cutting brackets like '()'. And watching what I can get by cutting all this pieces. Looking on new sequence I understood what I need to shift to get right bracket-sequence.

Here are some tests that helped me:

)))(()((
ans: 1

(()(()))
ans: 1

())(
ans: 1

))(())())((()(
ans: 1

Edited by author 27.07.2012 14:19

what is the test #7? I have tried my own tests, my program outputs right answers, i don't know what to do