ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Common Board

1016 : please give me some test data that make my program fail
Posted by Sam Green 1 Apr 2002 20:04
#include <stdio.h>
class heap {
 private:
  int *v;
  int *d;
  int *p;
  int size;
 private:
  int parent(int index);
  int left(int index);
  int right(int index);
  int cmp(int a, int b);
  void swap(int a, int b);
  void up(int index);
  void down(int index);
 public:
  ~heap();
  heap(int v[], int size);
  int extract();
  void update(int index, int value);
};

 int heap :: cmp(int a, int b) {
  return (v[d[b]]==-1 || v[d[a]]<v[d[b]])&&v[d[a]]!=-1;
 }

 void heap :: swap(int a, int b) {
  d[a]^=d[b]^=d[a]^=d[b];
  p[d[a]]=a;
  p[d[b]]=b;
 }

 int heap :: parent(int index) {
  return (index-1)>>1;
 }

 int heap :: left(int index) {
  return (index<<1)+1;
 }

 int heap :: right(int index) {
  return (index<<1)+2;
 }

 void heap :: up(int index) {
  while (index>0 && cmp(index,parent(index))) {
   swap(index,parent(index));
   index=parent(index);
  }
 }

 void heap :: down(int index) {
 int con;
  do {
   con=0;
   if (right(index)<size) {
    if (cmp(left(index), right(index))) {
     if (cmp(left(index), index)) {
      swap(left(index), index);
      index=left(index);
      con=1;
     }
    }
    else if (cmp(right(index), index)) {
     swap(right(index), index);
     index=right(index);
     con=1;
    }
   }
   else if (left(index)<size) {
    if (cmp(left(index), index)) {
     swap(left(index), index);
     index=left(index);
     con=1;
    }
   }
  } while (con);
 }

 heap ::  heap(int v[], int size) {
  this->size=size;
  this->v=v;
  d=new int[size];
  p=new int[size];
  for (int i=0; i<size; i++) {
   v[i]=-1;
   d[i]=i;
   p[i]=i;
  }
 }

 heap :: ~heap() {
  if (d!=NULL)
   delete d;
  if (p!=NULL)
   delete p;
 }

 void heap :: update(int index, int value) {
   v[index]=value;
   up(p[index]);
   down(p[index]);
 }

 int heap :: extract() {
 int toreturn;
  if (size==0||v[d[0]]==-1) {
   return -1;
  }
  else {
   toreturn=d[0];
   swap(0,size-1);
   size--;
   down(0);
   return toreturn;
  }
 }

int main() {
#ifndef ONLINE_JUDGE
FILE *fi=fopen("1016.in","r");
FILE* fo=fopen("1016.out","w");
#else
FILE *fi=stdin;
FILE *fo=stdout;
#endif
const int width=8;
const int side[6][4]={{2,3,4,5},{2,5,4,3},{1,3,0,5},{1,4,0,2},{0,3,1,5},
{2,0,4,1}};
const int opposite[6]={1,0,4,5,2,3};
const int directions=4;
const int dx[directions]={0,0,-1,1};
const int dy[directions]={-1,1,0,0};
const int of[directions]={-1,-2,0,0}; // -1 bottom , -2 top , 0 same
const int ob[directions]={2,0,3,1}; // offset , counter clock wise
int pos[6][6];
int dist[width*width*24];
int from[width*width*24];
int path[width*width*24];
int pathsize;
int startpos, endpos, curpos;
int num[6];
int i,j,k;
int cx,cy,ck,cb,cf;
int nb,nf;
char c,d;
heap h(dist,width*width*24);
 for (i=0; i<6; i++)
  for (j=0; j<4; j++) {
   pos[i][side[i][j]]=j;
  }
 fscanf(fi," %c %c",&c,&d);
 startpos=((c-'a')*width+(d-'1'))*24+(4*4+pos[4][1]);
 fscanf(fi," %c %c",&c,&d);
 endpos=((c-'a')*width+(d-'1'))*24+0;
 for (i=0; i<6; i++)
  fscanf(fi,"%d",num+i);
 h.update(startpos,num[4]);
 while ((curpos=h.extract())!=-1) {
  ck=curpos%24;
  cb=ck/4;
  cf=ck%4;
  cy=(curpos/24)%width;
  cx=curpos/(24*width);
  /*
    printf("\n%c%c:%d%d %d",cx+'a',cy+'1',cb,side[cb][cf],dist
[curpos]);
    getchar();
  */
  for (i=0; i<directions; i++)
   if (cx+dx[i]>=0 && cx+dx[i]<width && cy+dy[i]>=0 && cy+dy[i]
<width) {
    nb=side[cb][(cf+ob[i])%4];
    if (of[i]==-1) {
     nf=pos[nb][cb];
    }
    else if