ACM/ICPC Indonesia National Contest 2008

Problem G. Hotel

Problem Author: Bong Wince

Diberikan daftar prereferensi tiap peserta dan daftar tipe kamar hotel yang tersedia, anda diminta untuk menentukan hotel mana yang paling murah bagi tiap peserta. 17 tim berhasil menyelesaikan soal ini ketika kontes berlangsung.

Solusi dari soal ini cukup straight-forward: lakukan iterasi pada semua hotel untuk setiap peserta. Jumlah hotel dan jumlah peserta cukup kecil (50), sehingga metode bruteforce masih bisa dilakukan, O(N.M).

Solusi C/C++
oleh Suhendry Effendy

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

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

  for ( int tcase = 1; tcase <= T; tcase++ ) {
    int n, m;
    scanf( "%d %d", &n, &m );
    
    char hotel[100][30];
    char type[100];
    int bed[100];
    int room[100];
    int cost[100];
    int allow[100];

    for ( int i = 0; i < n; i++ ) {
      scanf( "%d %d %d %d %s", &bed[i], &allow[i], &room[i], &cost[i], hotel[i] );
      if ( bed[i] >= 20 && bed[i] <= 35 ) type[i] = 'A';
      if ( bed[i] >= 36 && bed[i] <= 48 ) type[i] = 'B';
      if ( bed[i] >= 49 && bed[i] <= 62 ) type[i] = 'C';
    }
    
    printf( "Case #%d:\n", tcase );
    while ( m-- ) {
      char a[10]; int b; int c;
      scanf( "%s %d %d", a, &b, &c );
      int idx = -1;
      int ans = 0;
      for ( int i = 0; i < n; i++ ) {
        if ( a[0] != type[i] ) continue;
        if ( min(allow[i],c) * room[i] < b ) continue;
        int lo = min(allow[i],c);
        int use = (b + lo - 1) / lo;
        if ( idx == -1 || use * cost[i] < ans || (use * cost[i] == ans && bed[i] > bed[idx]) )
          idx = i, ans = use * cost[i];
      }
      if ( idx != -1 ) printf( "%d %s\n", ans, hotel[idx] );
      else puts( "no-hotel" );
    }
  }
  
  return 0;
}

Solusi JAVA
oleh Suhendry Effendy

import java.util.*;

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

    int T = scan.nextInt();
    for ( int tcase = 1; tcase <= T; tcase++ ) {
      int n = scan.nextInt();
      int m = scan.nextInt();

      String[] hotel = new String[100];
      char[] type = new char[100];
      int[] bed = new int[100];
      int[] room = new int[100];
      int[] cost = new int[100];
      int[] allow = new int[100];

      for ( int i = 0; i < n; i++ ) {
        bed[i] = scan.nextInt();
        allow[i] = scan.nextInt();
        room[i] = scan.nextInt();
        cost[i] = scan.nextInt();
        hotel[i] = scan.next();
        if ( bed[i] >= 20 && bed[i] <= 35 ) type[i] = 'A';
        if ( bed[i] >= 36 && bed[i] <= 48 ) type[i] = 'B';
        if ( bed[i] >= 49 && bed[i] <= 62 ) type[i] = 'C';
      }

      System.out.printf( "Case #%d:\n", tcase );
      while ( m-- > 0 ) {
        String a = scan.next();
        int b = scan.nextInt();
        int c = scan.nextInt();
        int idx = -1;
        int ans = 0;
        for ( int i = 0; i < n; i++ ) {
          if ( a.charAt(0) != type[i] ) continue;
          if ( Math.min(allow[i],c) * room[i] < b ) continue;
          int lo = Math.min(allow[i],c);
          int use = (b + lo - 1) / lo;
          if ( idx == -1 || use * cost[i] < ans || (use * cost[i] == ans && bed[i] > bed[idx]) ) {
            idx = i;
            ans = use * cost[i];
          }
        }
        if ( idx != -1 ) System.out.printf( "%d %s\n", ans, hotel[idx] );
        else System.out.println( "no-hotel" );
      }
    }
  }

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