ACM/ICPC Indonesia National Contest 2008

Problem A. Who Got the Medals?

Deskripsi Soal A
Problem Author: Bong Win Ce

Di soal ini kita bisa menyimpulkan bahwa jumlah medali yang diberikan (gold, silver, bronze dan excellence) adalah sama dengan jumlah peserta yang berhasil mendapatkan minimal 500 poin. Dengan demikian, dari sekian banyak data input yang diberikan kita cukup mengolah data peserta yang minimal 500 poin saja. Jumlah medali excellence bisa dihitung dengan mengurangkan jumlah medali yang harus diberikan dengan jumlah peraih medali gold, silver dan bronze. Urutkan data-data yang diberikan secara menurun (descending) dan kemudian lakukan simulasi pemberian medali kepada setiap peserta (maju satu per satu).

Gold	Silver	Bronze
1	1	1 + (2-poin dari bronze medalist pertama)
1	< 1	0 + (2-poin dari silver medalist terakhir)
2	0	1 + (2-poin dari bronze medalist pertama)
< 2	0	0 + (2-poin dari gold medalist terakhir)

Sebagian besar peserta gagal di soal ini hanya karena memang kurang teliti di dalam mengimplementasikan proses simulasinya.

Solusi C/C++
oleh Suhendry Effendy

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

int A[1005];

int comp(const void *a, const void *b) {
  return *(int*)b - *(int*)a;
}

int main()
{
  int T;
  scanf( "%d", &T );

  while ( T-- > 0 ) {
    int N, medal = 0;
    scanf( "%d", &N );

    for ( int i = 0; i < N ; i++ ) {
      scanf( "%d", &A[i] );
      if ( A[i] >= 500 ) medal++;
    }

    qsort(A,N,sizeof(int),comp);

    int gold = 0, pgold;
    int silv = 0, psilv;
    int bron = 0, pbron;
    int p = 0;

    pgold = 0;
    while ( p < medal && A[pgold] - A[p] <= 2 ) gold++, p++;

    if ( gold == 1 ) {
      psilv = p;
      while ( p < medal && A[psilv] - A[p] <= 2 ) silv++, p++;

      pbron = (silv == 1) ? p : p - 1;
      while ( p < medal && A[pbron] - A[p] <= 2 ) bron++, p++;
    }
    else {
      pbron = (gold == 2) ? p : p - 1;
      while ( p < medal && A[pbron] - A[p] <= 2 ) bron++, p++;
    }

    printf( "%d %d %d %d\n", gold, silv, bron, medal - p );
  }

  return 0;
}

Solusi JAVA
oleh Felix Halim

import java.util.*;

public class medals {
  void solve(){
    Scanner scan = new Scanner(System.in);

    int nTC = scan.nextInt();
    while (nTC-- > 0){
      int n = scan.nextInt();
      int[] sc = new int[601];
      for (int i=0; i<n; i++)
        sc[scan.nextInt()]++;

      int G=0,S=0,B=0,E=0, g=0,s=0,b=0,e=0;

      for (G=600; sc[G]==0 && G>=500; G--);
      if (G>=500 && sc[G]>0) g += sc[G];
      if (G-1>=500 && sc[G-1]>0) g += sc[G-1];
      if (G-2>=500 && sc[G-2]>0) g += sc[G-2];

      if (g==1){
        for (S=G-3; sc[S]==0 && S>=500; S--);
        if (S>=500 && sc[S]>0) s += sc[S];
        if (S-1>=500 && sc[S-1]>0) s += sc[S-1];
        if (S-2>=500 && sc[S-2]>0) s += sc[S-2];

        if (s==1){
          for (B=S-3; sc[B]==0 && B>=500; B--);
          if (B>=500 && sc[B]>0) b += sc[B];
          if (B-1>=500 && sc[B-1]>0) b += sc[B-1];
          if (B-2>=500 && sc[B-2]>0) b += sc[B-2];

          for (E=B-3; E>=500; E--) e += sc[E];
        } else if (s > 1){
          for (int i=2; i>=0; i--) if (sc[S-i]>0){ B = S-i; break; }
          if (B-1>=500 && sc[B-1]>0) b += sc[B-1];
          if (B-2>=500 && sc[B-2]>0) b += sc[B-2];

          for (E=B-3; E>=500; E--) e += sc[E];
        }
      } else if (g == 2){
        for (B=G-3; sc[B]==0 && B>=500; B--);
        if (B>=500 && sc[B]>0) b += sc[B];
        if (B-1>=500 && sc[B-1]>0) b += sc[B-1];
        if (B-2>=500 && sc[B-2]>0) b += sc[B-2];

        for (E=B-3; E>=500; E--) e += sc[E];
      } else if (g > 2){
        for (int i=2; i>=0; i--) if (sc[G-i]>0){ B = G-i; break; }
        if (B-1>=500 && sc[B-1]>0) b += sc[B-1];
        if (B-2>=500 && sc[B-2]>0) b += sc[B-2];

        for (E=B-3; E>=500; E--) e += sc[E];
      }

      System.out.printf("%d %d %d %d\n",g,s,b,e);
    }
  }

  public static void main(String[] args){
    new medals().solve();
  }
}