ICPC2007

japan_a.c

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

int main()
{
  int number;
  int i;
  int max, min;
  int score;
  int count;
  int sum;

  while (1) {
    scanf("%d", &number);
    if (number == 0) {
      exit(0);
    }
    max = -1;
    min = 10000;
    sum = 0;
    for (i = 0; i < number; i ++) {
      scanf("%d", &score);
      if (score < min) {
        min = score;
      }
      if (score > max) {
        max = score;
      }
      sum += score;
    }
    printf("%d\n", (sum - min - max)/(number - 2));
  }
}

japan_a_input.txt

3
1000
342
0
5
2
2
9
11
932
5
300
1000
0
200
400
8
353
242
402
274
283
132
402
523
0

japan_b.c

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

struct history {
  int start;
  int end;
  struct history *next;
};

struct history *history[10001];
int using[1001];

void insert_history(int, int, int);
void query(int, int, int);
int min(int, int);
int max(int, int);

int main()
{
  int N, M, r, q;
  int t, n, m, s;
  int i;
  int ts, te;

  while (1) {
    scanf("%d %d", &N, &M);
    if (N == 0 && M == 0) {
      exit(0);
    }
    /* initialize history */
    for (i = 1; i <= M; i ++) {
      history[i] = NULL;
    }
    /* initialize using */
    for (i = 1; i <= N; i ++) {
      using[i] = 0;
    }
    /* read r */
    scanf("%d", &r);
    /* read history */
    for (i = 0; i < r; i ++) {
      scanf("%d %d %d %d", &t, &n, &m, &s);
      if (s == 1) { /* login */
        using[n] = t;
      } else if (s == 0) { /* logout */
        insert_history(m, using[n], t);
        using[n] = 0;
      }
    }

    /* read query */
    scanf("%d", &q);
    for (i = 0; i < q; i ++) {
      scanf("%d %d %d", &ts, &te, &m);
      query(ts, te, m);
    }
  }
}

void insert_history(int m, int start, int end)
{
  struct history *h = (struct history *)malloc(sizeof(struct history));
  if (h == NULL) {
    exit(1);
  }
  h -> start = start;
  h -> end = end;
  h -> next = history[m];
  history[m] = h;
}

void query(int ts, int te, int m)
{
  struct history *ptr = history[m];
  int sum = 0;
  int start, end;

  if (ptr != NULL) {
    start = ptr -> start;
    end = ptr -> end;
  }

  while (ptr != NULL) {
    // printf("%d %d\n", ptr -> start, ptr -> end);
    if (start < ptr -> end) {
      start = min(start, ptr -> start);
    } else {
      // printf("%d %d %d %d\n", start, end, ts, te);
      if (ts < end && start < te) {
        sum += min(end, te) - max(start, ts);
      }
      start = ptr -> start;
      end = ptr -> end;
    }
    ptr = ptr -> next;
  }
  // printf("%d %d %d %d\n", start, end, ts, te);
  if (ts < end && start < te) {
    sum += min(end, te) - max(start, ts);
  }
  printf("%d\n", sum);
}

int max(int i, int j)
{
  if (i < j) {
    return j;
  } else {
    return i;
  }
}

int min(int i, int j)
{
  if (i < j) {
    return i;
  } else {
    return j;
  }
}

japan_b_input.txt

4 2
10
775 1 1 1
780 4 2 1
790 2 1 1
800 2 1 0
810 3 1 1
820 1 1 0
825 3 1 0
860 1 1 1
870 4 2 0
880 1 1 0
1
780 870 1
13 15
12
540 12 13 1
600 12 13 0
650 13 15 1
660 12 15 1
665 11 13 1
670 13 15 0
675 11 13 0
680 12 15 0
1000 11 14 1
1060 12 14 1
1060 11 14 0
1080 12 14 0
3
540 700 13
600 1000 15
1000 1200 11
1 1
2
600 1 1 1
700 1 1 0
5
540 600 1
550 650 1
610 620 1
650 750 1
700 800 1
0 0

japan_c.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;
}

japan_c_input.txt

3 5 6
1 18
2 19
1 2
3 4 1
1 1
2 1
3 1
0 2 5
0 0 0