ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Общий форум

1016 : please give me some test data that make my program fail
Послано Sam Green 1 апр 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