Supercon2011 Report

I took part in Supercon2011 with my juniors. However, I'm not high school student, I join only qualification round. We can solve problems in three weeks, but we too busy to solve all of them. So, we solve Problem-A & Problem-B.

The problem is here(Japanese).

In short,it was the shortest road problem. If we use Dijkstra method, the problems can be solved. So I feel not difficult. If we have more time, I'll think Problem-C and better algorithms. It's regrettable.

A:This problem is same to calculation of Pascal's triangle.

#include <assert.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <time.h>

int main(int argc, char** argv) {

  int answer = -1; 

  int m, n;

  int D[200+1][200+1][4];

  char* problem_file;

  clock_t start, end;

  FILE* fp;

  int i, x, y;

  char buf[0xffff];

  char* p;

  if (argc <= 1) {

    fprintf(stderr, "Enter the input file.¥n");

    exit(EXIT_FAILURE);

  }

  problem_file = argv[1];

  fp = fopen(problem_file, "r");

  if (fp == NULL) {

    fprintf(stderr, "Cannot open %s.¥n", problem_file);

    exit(EXIT_FAILURE);

  }

  p = fgets(buf, 0xffff, fp);

  assert(p != 0);

  m = atoi(strtok(buf, ", ¥n"));

  n = atoi(strtok(NULL, ", ¥n"));

  assert(m > 0 && m <= 200);

  assert(n > 0 && n <= 200);

  for (y = 0; y <= n; y++) {

    p = fgets(buf, 0xffff, fp);

    assert(p != 0);

    p = strtok(buf, ", ¥n");

    for (i = 0; i < m; i++) {

      int length = atoi(p);

      assert(length >= 0 && length <= 1);

      D[i][y][1] = length;

      D[i+1][y][3] = length;

      p = strtok(NULL, ", ¥n");

    }

    D[0][y][3] = 0;

    D[m][y][1] = 0;

  }

  for (x = 0; x <= m; x++) {

    p = fgets(buf, 0xffff, fp);

    assert(p != 0);

    p = strtok(buf, ", ¥n");

    for (i = 0; i < n; i++) {

      int length = atoi(p);

      assert(length >= 0 && length <= 1);

      D[x][i][0] = length;

      D[x][i+1][2] = length;

      p = strtok(NULL, ", ¥n");

    }

    D[x][0][2] = 0;

    D[x][n][0] = 0;

  }

  fclose(fp);

   unsigned int data[51][51];

  int j;

  memset(data,0,sizeof(data));

  for(i=0;i<=m;i++){

    for(j=0;j<=n;j++){

      if(i==0 && j==0){

data[i][j]=1;

continue;

      }

      if(i!=0) data[i][j]+=D[i][j][3]*data[i-1][j];

      if(j!=0) data[i][j]+=D[i][j][2]*data[i][j-1];

    }

  }

  answer=data[m][n];

  

  printf("%s, %d¥n", problem_file, answer);

  return 0;

}

B:It's shortest road problem.

#include <assert.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <time.h>

int main(int argc, char** argv) {

  int answer_length = -1;

  int answer_number = -1;

  int m, n;

  int D[200+1][200+1][4];

  char* problem_file;

  clock_t start, end;

  FILE* fp;

  int i, x, y;

  char buf[0xffff];

  char* p;

  if (argc <= 1) {

    fprintf(stderr, "Enter the input file.¥n");

    exit(EXIT_FAILURE);

  }

  problem_file = argv[1];

  fp = fopen(problem_file, "r");

  if (fp == NULL) {

    fprintf(stderr, "Cannot open %s.¥n", problem_file);

    exit(EXIT_FAILURE);

  }

  p = fgets(buf, 0xffff, fp);

  assert(p != 0);

  m = atoi(strtok(buf, ", ¥n"));

  n = atoi(strtok(NULL, ", ¥n"));

  assert(m > 0 && m <= 200);

  assert(n > 0 && n <= 200);

  for (y = 0; y <= n; y++) {

    p = fgets(buf, 0xffff, fp);

    assert(p != 0);

    p = strtok(buf, ", ¥n");

    for (i = 0; i < m; i++) {

      int length = atoi(p);

      assert(length >= 0 && length <= 20);

      D[i][y][1] = length;

      D[i+1][y][3] = length;

      p = strtok(NULL, ", ¥n");

    }

    D[0][y][3] = 0;

    D[m][y][1] = 0;

  }

  for (x = 0; x <= m; x++) {

    p = fgets(buf, 0xffff, fp);

    assert(p != 0);

    p = strtok(buf, ", ¥n");

    for (i = 0; i < n; i++) {

      int length = atoi(p);

      assert(length >= 0 && length <= 20);

      D[x][i][0] = length;

      D[x][i+1][2] = length;

      p = strtok(NULL, ", ¥n");

    }

    D[x][0][2] = 0;

    D[x][n][0] = 0;

  }

  fclose(fp);

 struct{

    unsigned int dis;

    unsigned int num;

  } data[201][201];

  int j,k,l,flg;

  unsigned int mind,mink,minm,minn;

  

  memset(data,0,sizeof(data));

  data[0][0].dis=0;

  data[0][0].num=1;

  for(i=0;data[m][n].dis!=0 || i<=(m+1)*(n+1);i++){

    mind=2000000000;

    flg=0;

    for(j=0;j<=m;j++){

      for(k=0;k<=n;k++){

if(data[j][k].dis==0 && j+k!=0) continue;

for(l=0;l<=3;l++){

 if(D[j][k][l]==0) continue;

 if(data[j-(l-2)*(l%2)][k-(l-1)*((l+1)%2)].num!=0) continue;

 if(mind>D[j][k][l]+data[j][k].dis){

   mind=D[j][k][l]+data[j][k].dis;

   mink=data[j][k].num;

   minm=j-(l-2)*(l%2);

   minn=k-(l-1)*((l+1)%2);

   flg=1;

 }else if(mind==D[j][k][l]+data[j][k].dis){

   if(minm==j-(l-2)*(l%2) && minn==k-(l-1)*((l+1)%2)) mink+=data[j][k].num;

 }

}

      }

    }

    if(flg==0) break;

    data[minm][minn].dis=mind;

    data[minm][minn].num=mink;

  }

  

  answer_length=data[m][n].dis;

  answer_number=data[m][n].num;

  printf("%s, %d, %d¥n", problem_file, answer_length, answer_number);

  return 0;

}