ACM International Collegiate Programming Contest, Japan Domestic, 2007, Problem C

gistfile1.c

#include <stdio.h>
#include <stdlib.h>

struct cake {
  int w;
  int d;
  struct cake *next;
  struct cake *prev;
};

struct area {
  int v;
  struct area *next;
  struct area *prev;
};

struct cake *split(struct cake *, int);
int min(int, int);

int main()
{
  int n, w, d;
  int p, s;
  int i, j;
  struct cake *l;
  struct area *ll;
  struct cake *ptr;
  struct cake *last;
  struct cake *temp;
  int area;
  struct area *lltemp, *lltemp2;

  while (1) {
    scanf("%d %d %d", &n, &w, &d);
    if (n == 0 && w == 0 && d == 0) {
      exit(0);
    }
    l = (struct cake *)malloc(sizeof(struct cake));
    if (l == NULL) {
      exit(1);
    }
    l -> w = w;
    l -> d = d;
    l -> next = l -> prev = NULL;
    last = l;
    
    /* read cut method */
    for (i = 0; i < n; i ++) {
      scanf("%d %d", &p, &s);
      for (j = 1, ptr = l; j < p; j ++) {
        ptr = ptr -> next;
      }

      last -> next = split(ptr, s);
      last -> next -> prev = last;
      last = last -> next -> next;

      // fprintf(stderr, "%d %d\n", ptr -> w);
      temp = ptr -> prev;
      ptr -> next -> prev = temp;
      if (temp != NULL) {
        temp -> next = ptr -> next;
      }
      if (l == ptr) {
        l = ptr -> next;
      }
      free(ptr);
    }
    // ptr = l;
    // while (ptr != NULL) {
    //   printf("%d %d ", ptr -> w, ptr -> d);
    //   ptr = ptr -> next;
    // }
    // printf("\n");

    ll = (struct area *)malloc(sizeof(struct area));
    ll -> next = ll -> prev = NULL;
    ptr = l;
    while (ptr != NULL) {
      area = ptr -> w * ptr -> d;
      // fprintf(stderr, "%d\n", area);
      lltemp = ll;
      while (lltemp -> next != NULL && lltemp -> next -> v < area) {
        lltemp = lltemp -> next;
      }
      lltemp2 = (struct area *)malloc(sizeof(struct area));
      lltemp2 -> v = area;
      lltemp2 -> next = lltemp -> next;
      if (lltemp -> next != NULL) {
        lltemp -> next -> prev = lltemp2;
      }
      lltemp2 -> prev = lltemp;
      lltemp -> next = lltemp2;
      ptr = ptr -> next;
    }
    lltemp = ll -> next;
    while (lltemp != NULL) {
      printf("%d ", lltemp -> v);
      lltemp = lltemp -> next;
    }
    printf("\n");
  }
}

struct cake *split(struct cake *orig, int s)
{
  int w = orig -> w, d = orig -> d;
  int w1 = w, w2 = w;
  int d1 = d, d2 = d;
  struct cake *cake1, *cake2;
  
  /* split */
  while (1) {
    if (s < w) {
      w1 = min(s, w - s); w2 = w - w1;
      break;
    } else if (s > w && s < w + d) {
      s -= w;
      d1 = min(s, d - s); d2 = d - d1;
      break;
    } else if (s > w + d && s < w * 2 + d) {
      s -= (w + d);
      w1 = min(s, w - s); w2 = w - w1;
      break;
    } else if (s > w * 2 + d && s < w * 2 + d * 2) {
      s -= (w * 2 + d);
      d1 = min(s, d - s); d2 = d - d1;
      break;
    } else {
      s -= (w * 2 + d * 2);
    }
  }
  // printf("%d: %d %d -> %d %d %d %d\n", s, w, d, w1, d1, w2, d2);

  cake1 = (struct cake *)malloc(sizeof(struct cake));
  cake1 -> w = w1; cake1 -> d = d1;
  cake2 = (struct cake *)malloc(sizeof(struct cake));
  cake2 -> w = w2; cake2 -> d = d2;
  cake1 -> next = cake2; cake2 -> next = NULL;
  cake2 -> prev = cake1; cake1 -> prev = NULL;

  return cake1;
}

int min(int i, int j)
{
  return (i < j) ? i : j;
}