Hello. Could somebody tell me a right DP approach to this problem. I couldn't figure out the solution better than O(|S|*M). |S| - length of the string.

   Hi everybody,
   After a lot of testing I have wa21 ... Is there anything spacial about this test case ? Thanks in advance.

Edited by author 18.07.2009 22:28

int n,i=0; -- AC
int n,i; -- - WA №1

import java.util.Scanner;

public class ex2031 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
     Scanner sc=new Scanner(System.in);
     int n=sc.nextInt();
     if(n==1){
         System.out.println("11");
     }else{
         if(n==2){
             System.out.println("11"+" "+"01");
         }else{
             if(n==3){
                 System.out.println("001"+" "+"66"+" "+"86");
             }else{
                 if(n==4){
                     System.out.println("16"+" "+"06"+" "+"68"+" "+"88");
                 }else{
                     System.out.println("Glupenky Pierre");
                 }
             }
         }
     }
    }

}

One of them was found on the forum, too.

4
0 0
0 1
1 1
1 0
YES

5
0,654508 0,0244717
0,0954915 0,206107
0,0954915 0,793893
0,654508 0,975528
1 0,5
YES

5
1 0,5
0,654508 0,975528
0,0954915 0,793893
0,0954915 0,206107
0,654508 0,0244717
YES

12
-0,1 0,3
0,1 0,3
0,1 0,1
0,3 0,1
0,3 -0,1
0,1 -0,1
0,1 -0,3
-0,1 -0,3
-0,1 -0,1
-0,3 -0,1
-0,3 0,1
-0,1 0,1
NO

8
0 0
0 -1
1 -1
1 0
0 0
0 1
1 1
1 0
NO

Note*: if you have WA1 just skip all #10 and #13 symbols from input data!

((*Answer is YES*))
(((*Answer is YES*)))
(**) YES
 (* NO
(*) NO
(*(*) YES
(11(*)) NO
(*(**)*) NO
((**)*)(**)*)  NO!
((**)*)  YES

()()
(())
((())) YES

(1+1
)  YES

Just sort() numbers...
It will take approximately 1e5 * log(1e5) ≈ 1e6 operations, which is not that long to compute.

Edited by author 02.12.2017 00:54

var
  n:Integer;
  r:cardinal;
begin
  read(n);
  asm
    xor eax,eax
    mov ebx,eax
    inc eax
    mov esi,eax
    mov edi,eax
    mov ecx,1 shl 5
    @@3:
     or ecx,ecx
     je @@1
      mov eax,ebx
      mul eax
      mov ebx,eax
      mov eax,esi
      mul eax
      add eax,ebx
      mov esi,eax
      mov eax,edi
      mul eax
      add eax,ebx
      mov edi,eax
      sub eax,esi
      mov ebx,eax
      test n,ecx
      je @@2
        add edi,ebx
        add ebx,esi
        mov esi,edi
        sub esi,ebx
      @@2:
      shr ecx,1
      jmp @@3
    @@1:
    mov eax,ebx
    shl eax,1
    mov r,eax
  end;
  write(r);
end.

I can not find the error. Share the tests, please

#include <stdio.h>

int main(){
int i,n,x,y,z,x1=0,y1=0,z1=0;
scanf("%d",&n);
int* A=new int[n];
for(i=0;i<n;i++)
scanf("%d",&A[i]);
x=A[0];
i=1;
y=-100;
while(1){
if(A[i]==x)
x=A[i];
else if(A[i]!=y)
y=A[i];
else
{
z=A[i];
break;
}
i++;}
for(i=0;i<n;i++)
{
if(A[i]==x)
x1++;
else if(A[i]==y)
y1++;
else if(A[i]==z)
z1++;
}
if(x1>y1 && x1>z1)
printf("%d",x);
else if (y1>z1 && y1>x1)
printf("%d",y);
else if (z1>x1 && z1>y1)
printf ("%d",z);
return 0;
}

20
19 17 15 13 11 9 7 5 3 1 2 4 6 8 10 12 14 16 18 20

ans:
5
17 13 9 5 1 2 6 8 10 12 14 16 18 20 4 3 7 11 15 19
1 2 8 12 16 20 7 11 15 19 3 4 18 14 10 6 5 9 13 17
1 2 12 20 11 19 3 4 18 10 9 17 13 5 6 14 15 7 16 8
1 2 20 19 3 4 18 17 5 6 7 8 16 15 14 13 9 10 11 12
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

I don't have test only use handle binary search get the test, and find answer with eyes...
my programme output 6,so it must be smaller than 6...

var
a,b,c:integer;
begin
read(a,b);
writeln(a+b);
end.

program SumAB;
var
  a,b:integer;
begin
  Assign(input,'input.txt');
  Reset(input);
  Assign(output,'output.txt');
  Rewrite(output);
  Readln(a,b);
  Writeln(a+b);
  Close(input);
  Close(output);
end.
При таком коде возникала ошибка.
Написал
program SumAB;
var
  a,b:integer;
begin
  Readln(a,b);
  Writeln(a+b);
end.
Система приняла. Т.е что получается, не нужно писать имена входного/выходного файлов?
А в других задачах тот же принцип?

RT

this is my checker of this problem, it can't be wrong ,but WA on test 8

    if(i>=n||a[i]!=k)
    {
        while(!(n==5&&k==5))
           puts("orz");
       puts("-1");
        }
    else
    {
        printf("%d\n",cnt_ans);
        while(cnt_ans>3*n)
           puts("orz");
        for(i=0;i<cnt_ans;i++)
           printf("%d %d\n",ax[i],ay[i]);
        for(i=0;i<n;i++)
            a[i]=1;
        for(i=0;i<cnt_ans;i++)
        {
            int id1=ax[i]-1,id2=ay[i]-1;
            while(id1>=n||id1<0||id2>=n||id2<0||id1==id2)
               puts("orz");
            a[id1]-=a[id2];
            a[id2]*=2;
            while(a[id1]<0)
               puts("orz");
        }
        for(i=0;i<n;i++)
        {
            if(a[i]==k)
               break;
        }
        while(i!=0)
           puts("orz");
    }

I think it is a NP hard problem ,how could it be solved with range 1000??

1 495
1
5 99
Answer: Too small

1 494
1
5 99
Answer: Too small

1 397
1
5 99
Answer: Too small

1 396
1
5 99
Answer: Block the hole

var k,n,i,q,w:integer;
begin
read(k,n);
for i:=1 to n do begin
  read(q);
  w:=w+q;
  end;
if k*n>=w then writeln(0) else writeln(w-k*n);
end.

I used stable sort from STL and got AC