Bina Nusantara Programming Contest for High School Students 2008

Problem : A | B | C | D | E | F | G | H

E - Makan Sepuasnya

Inti permasalahan pada soal ini adalah sama dengan Activity Selection Problem, di mana waktu mulai setiap activity adalah t + d sedangkan waktu selesainya adalah t + d + e. Soal ini bisa diselesaikan secara greedy dengan memilih activity yang selesai lebih dulu.

Statistik Problem E
YES = 3
NO - Wrong Answer = 10
NO - Time Limit Exceeded = 6
NO - Run-time Error = 1
NO - Compile Error = 0

Solusi C/C++ (oleh Suhendry Effendy)

#include <cstdio>
#include <algorithm>
using namespace std;

struct food { int start; int finish; };
bool operator < (const food &a, const food &b) {
  return a.finish < b.finish;
}

food arr[100005];

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

  while ( T-- ) {
    int  n, t, d, e;
    scanf( "%d", &n );
    
    for ( int i = 0; i < n; i++ ) {
      scanf( "%d %d %d", &t, &d, &e );
      arr[i] = (food){t+d,t+d+e};
    }
    
    sort(arr,arr+n);
    
    int ans = 0, last = -1;
    for ( int i = 0; i < n; i++ ) {
      if ( arr[i].start >= last ) {
        ans++;
        last = arr[i].finish;
      }
    }

    printf( "%d\n", ans );
  }
  
  return 0;
}

Solusi Pascal (oleh Eko Wibowo)

type
  food = record
  start, finish : longint;
  end;
  tlist = array[1..100000] of food;

var
  t,d,e,n,i,tcase,ans,last : longint;
  arr : tlist;

// diambil dari contoh pada free-pascal
procedure sort(var a:tlist;l,r: longint);
var
  i, j : longint;
  x, y : food;
begin
  i := l;
  j := r;
  x := a[(l + r) div 2];
  repeat
     while a[i].finish < x.finish do i := i + 1;
     while x.finish < a[j].finish do j := j - 1;
     if i <= j then
     begin
       y := a[i];
       a[i] := a[j];
       a[j] := y;
       i := i + 1;
       j := j - 1;
     end;
   until i > j;
   if l < j then sort(a,l,j);
   if i < r then sort(a,i,r);
end;

begin
  read(tcase);
  while (tcase>0) do
  begin
    tcase := tcase - 1;
    read(n);
    for i := 1 to n do
    begin
      read(t,d,e);
      arr[i].start  := t + d;
      arr[i].finish := t + d + e;
    end;
    sort(arr,1,n);
    ans  := 0;
    last := -1;
    for i := 1 to n do
      if (arr[i].start >= last) then
      begin
        ans  := ans + 1;
        last := arr[i].finish;
      end;
    wrans);
  end;
end.