I passed the test in the problem.
But why I couldn't pass the  first test?
Here are my program:
var
  s,s2:string;
  n,i,j,k,l:longint;
  s1,c:array[1..50000]of string;
  m:array[1..100,1..100]of integer;
  b:boolean;
function xun(len:longint):boolean;
  var
    j:longint;
  begin
    if j=1
    then begin
           xun:=true;
           exit;
         end;
    for j:=len-1 downto 1 do
      begin
        if m[j,len]>0
        then begin
               if xun(j)
               then begin
                      write(s1[m[j,len]],' ');
                    end;
             end;
      end;
  end;
begin
  //assign(input,'1002.in');reset(input);
  readln(s);
  repeat
  l:=length(s);
  readln(n);
  for i:=1 to n do
    begin
      b:=false;
      readln(s1[i]);
      for j:=1 to length(s1[i]) do
        case s1[i][j] of
          'i','j':c[i]:=c[i]+'1';
          'a','b','c':c[i]:=c[i]+'2';
          'd','e','f':c[i]:=c[i]+'3';
          'g','h':c[i]:=c[i]+'4';
          'k','l':c[i]:=c[i]+'5';
          'm','n':c[i]:=c[i]+'6';
          'p','r','s':c[i]:=c[i]+'7';
          't','u','v':c[i]:=c[i]+'8';
          'w','x','y':c[i]:=c[i]+'9';
          'o','q','z':c[i]:=c[i]+'0';
        end;
      for j:=1 to l-length(c[i])+1 do
        begin
          s2:=copy(s,j,length(c[i]));
          if s2=c[i]
          then m[j,j+length(c[i])-1]:=i;
        end;
    end;
    for j:=length(s)-1 downto 1 do
      begin
        if m[j,length(s)]>0
        then begin
               if xun(j-1)
               then begin
                      b:=true;
                      write(s1[m[j,length(s)]]);
                      break;
                    end;
             end;
      end;
    if b=false
    then write('No solution.');
    readln(s);
    writeln;
      fillchar(s1,sizeof(s1),0);
      fillchar(c,sizeof(c),0);
      fillchar(m,sizeof(m),0);
  until s='-1';
  //close(input);
end.

4
14 13 14 13

the answer is 2!

my algorithm is quite simple and i dont know how to make it fast. my hints would be appreciated.

1. i am using dfs to get the distance from vertex v to vertex u such that dist(v, u) = d given.

2. while computing the vertex u..i am saving the result of all previous vertices u1, u2, ....ud..such that distance between v and u1 is 1, v and u2 is 2 and so on. i am saving the result in hashmap.

3. i only use dfs if the hashmap doesnt contain the query.

I can email my code as well....

Thanks

Problem 1008 C++

#include <iostream>
using namespace std;
int main()
{
   int col,x,y,nowx[7],nowy[7],now=1;
   nowx[1]=11;nowy[1]=11;
   int p[11][11];
   int i,j;
   scanf("%d",&col);
   for(i=1;i<11;i++){
       for(j=1;j<11;j++){
           p[i][j]=0;
       }
   }
   for(i=1;i<col+1;i++){
         scanf("%d %d",&x,&y);
         p[x][y]=1;
   }
   for(i=1;i<11;i++){
       for(j=1;j<11;j++){
           if (p[i][j]==1){
              if(nowx[1]>i) nowx[1]=i;
           }
       }
   }
   for(j=1;j<11;j++){
            if (p[nowx[1]][j]==1){
              if(nowy[1]>j) nowy[1]=j;
            }
   }
   p[nowx[1]][nowy[1]]=0;
   printf("%d %d\n",nowx[1],nowy[1]);
   for(i=1;i<col+1;i++){
      if (p[nowx[i]-1][nowy[i]]==1) {
                                    now++;
                                 nowx[now]=nowx[i]-1;
                                 nowy[now]=nowy[i];
                                 p[nowx[i]-1][nowy[i]]=0;
                                 printf("L");
      }
      if (p[nowx[i]][nowy[i]-1]==1) {
                                    now++;
                                 nowx[now]=nowx[i];
                                 nowy[now]=nowy[i]-1;
                                 p[nowx[i]][nowy[i]-1]=0;
                                 printf("B");
      }
      if (p[nowx[i]+1][nowy[i]]==1){
                                    now++;
                                 nowx[now]=nowx[i]+1;
                                 nowy[now]=nowy[i];
                                 p[nowx[i]+1][nowy[i]]=0;
                                 printf("R");
      }
      if (p[nowx[i]][nowy[i]+1]==1){
         now++;
                                 nowx[now]=nowx[i];
                                 nowy[now]=nowy[i]+1;
                                 p[nowx[i]][nowy[i]+1]=0;
                                 printf("T");
      }
      if (col!=i) printf(",\n");
   }
   printf(".");
   return 0;
}

I checked my program, and I'm pretty sure that it gives the correct answers for the sample input/output, and for all the tests given on this forum. I also went to the page of NEERC 2002 and downloaded their test examples, and everything seems to be correct.

I tried ending output with or without a newline('\n'), and I still can't figure out why I could possibly be getting a wrong answer three times in a row.

Please give me some advice as to where my problem is. Maybe it is someting small? Maybe I misread something in the problem statement?

Anyway, here's my program(I'm sure the code is pretty bad, but keep in mind that I don't have much experience with these sorts of problems):

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

int main() {
    int A[10002];
    long int pos = 0;

    cin.unsetf(ios::skipws);

    do {
        char input[3];

        cin >> input[0];

        if(input[0] == '\n') break;

        cin >> input[1];

        input[2] = 0;

        A[pos] = (int) strtol(input, (char **) input + 2 * sizeof(char), 16);
        pos++;

    } while(1);

    int current;
    int key;

    char input[3];
    input[0] = 'C';
    input[1] = '9';
    input[2] = 0;

    cin >> input[0] >> input[1];
    key = (int) strtol(input, (char **) input + 2 * sizeof(char), 16);
    key ^= 32;

    for(int i = 0; i < pos; i++) {
            cout << hex << uppercase << setfill('0') << setw(2) << key;

            cin >> input[0] >> input[1];

            current = (int) strtol(input, (char **) input + 2 * sizeof(char), 16);

            key = ((key) ^ (A[i])) ^ (current);
    }

    cout << hex << uppercase << setfill('0') << setw(2) << key << "\n";

    return 0;
}

Please help! Any advice will be appreciated!

Finally I got accepted. I include several tests to help you debug:
input            output:
8                YES
1 70             1 70
4 65             4 65
64 66            61 64
61 64            65 64
66 62            66 64
80 50            66 62
80 60            80 60
65 64            80 50

input:           output:
3                YES
1 3              1 3
2 1              1 2
2 3              3 2

var
  n,i,j,l:integer;
  a:array[1..100,1..100] of integer;
begin
  read(n);
  for i:=1 to n do
    for j:=1 to n do
      read(a[i,j]);
  i:=1;
  j:=1;
  for l:=1 to n do
    begin
      i:=l;
      j:=1;
      while i<>0 do
        begin
          write(a[i,j],' ');
          dec(i);
          inc(j);
        end;
    end;
  for l:=n + 2 to n + n do
    begin
      i:=n;
      j:=l - n;
      while j <= n do
        begin
          write(a[i,j],' ');
          dec(i);
          inc(j);
        end;
    end;
  readln;
  readln;
end.

How can i reach acm.timus team? I tried to write an e-mail, but it returned to me with some errors in their mailing box.

I can`t find place where it can be crash.

If you solve this problem with a help of finding roots of the initial polynom, use long long or __int64 type in this function! This fact costed me about 5 submissions...
This is the part of my code:

long long PolynomValue (vector<int>PolynomCoeffs, int x0)
{
long long value;
...
return value;
}

int FindRoot (vector<int> PolynomCoeffs)
{
...
if (!PolynomValue(PolynomCoeffs,a)) return a;
...
}
If I changed long long to int I would not find a root in several cases.

To understand me more clearly try these tests:

-20000 19998 20000 -19999
(x-1)(x-1)(x+1)(x-19999)

-19998 -20000 20000 -19999
(x-19999)(x3+x2-x+1)

-19999 -19999 -19999 -20000
(x+1)(x-20000)(x2+1)

I guess 13th and 14th tests are something like these ones.
Good luck!

Edited by author 22.01.2010 21:07

Please, give me some difficult tests...

Send them please on snipious@mail.ru!!!

Can anybody tell me how to calucate bynomial coefficients with a help of the fastest method?

uses math;
var len,r:extended;
begin
 read(len,r);
 if(r<=len/2)then writeln((pi*r*r):0:3) else
 if(sqrt(2)*len/2<=r)then writeln((len*len):0:3) else
  writeln((pi*r*r-4*arccos(len/r/2)*r*r+2*len*sqrt(r*r-len*len/4)):0:3);
end.

that is what my AC prog gives on some tests:
n=7, res=1
n=7777, res=2340
n=77777, res=23412
n=99997, res=30101
n=99998, res=30102
n=52251, res=15728
n=55555, res=16723
n=100000, res=30102

var
  a : array[-1000..0] of integer;
  b : array[0..1000] of integer;
  n, i, j, k, l, m, u, x : integer;
  c : array[1..100] of integer;
begin
  read(n, x);
  k := 0;
  m := 0;
  l := 0;
  u := 0;
  j := 0;
  i := 0;
  for i := 1 to n do begin
    read(c[i]);
    if c[i] >= 0 then b[c[i]] := 1 else a[c[i]] := 1;
  end;
  if b[0] = 1 then u := 1;
  if x = 0 then begin
    k := 0;
    m := 0;
  end;
  if x < 0 then begin
    for i := x to -1 do begin
      if a[i] = 1 then begin
        u := 1;
        break;
      end;
    end;
    if i = 0 then begin
      for j := 0 downto x do begin
        inc(m);
      end;
      m := m - 1;
      repeat
        inc(k);
      until b[k] = 1;
      k := 2 * k + m;
      end;
  end;
  if x > 0 then begin
      for i := 0 to x do begin
        if(b[i]) = 1 then begin
          u := 1;
          break;
        end;
      end;
      if i = x + 1 then begin
        for j := 0 to x do begin
          inc(k);
        end;
        k := k - 1;
        repeat
          inc(m);
          dec(l);
        until a[l] = 1;
        m := 2 * m + k
      end;
    end;
    if u = 1 then writeln('Impossible') else
    writeln(k,' ', m);
    readln;
    readln;
end.
my code it is work for different numbers and tests (my tests( but WA 1) plese, who can help me?

I have had WA#3, but when I have tried following test, I pass Test#3, but have WA#13:

4 3 2
2.0 0.0
2.0 10.0

Right answer:
0.0000000

Now I have AC.

Edited by author 20.01.2010 13:32

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

#define forr(i,x,y) for(int i=(int)(x); i<=(int)(y); i++)

int p[24][6]={
{1,2,3,4,5,6},{1,2,6,5,3,4},{1,2,4,3,6,5},{1,2,5,6,4,3},{2,1,4,3,5,6},{2,1,6,5,4,3},{2,1,3,4,6,5},{2,1,5,6,3,4},
{3,4,2,1,5,6},{3,4,6,5,2,1},{3,4,1,2,6,5},{3,4,5,6,1,2},{4,3,6,5,1,2},{4,3,2,1,6,5},{4,3,5,6,2,1},{4,3,1,2,5,6},
{5,6,3,4,2,1},{5,6,1,2,3,4},{5,6,4,3,1,2},{5,6,2,1,4,3},{6,5,3,4,1,2},{6,5,2,1,3,4},{6,5,4,3,2,1},{6,5,1,2,4,3}};
int n,a[7],b[7],id[7][7][7][7][7][7],m=0,x=0;
vector< vector<int> > y(100100);

int main() {
 scanf("%d",&n);
 forr(i,1,n) {
  scanf("%d %d %d %d %d %d",&a[3],&a[4],&a[2],&a[5],&a[1],&a[6]);
  forr(q,0,23) if(x=id[a[p[q][0]]][a[p[q][1]]][a[p[q][2]]][a[p[q][3]]][a[p[q][4]]][a[p[q][5]]])break;
  if(!x) { y[++m].push_back(i); id[a[1]][a[2]][a[3]][a[4]][a[5]][a[6]]=m; } else y[x].push_back(i);
 }
 printf("%d\n",m);
 forr(i,1,m) { forr(j,0,y[i].size()-1) printf("%d ",y[i][j]); printf("\n"); }
}

There are three themes about mistake in check system!!! Add tests

http://acm.timus.ru/forum/thread.aspx?space=1&num=1005&id=23613
and
http://acm.timus.ru/forum/thread.aspx?space=1&num=1005&id=22373
and
http://acm.timus.ru/forum/thread.aspx?space=1&num=1005&id=21912