ACM/ICPC Indonesia National Contest 2008

Problem E. Lemonade One

Deskripsi Soal E
Problem Author: Danny Gunawan

Jack ingin berjualan tapi dia hanya bisa memilih dua dari lima hari yang ada. Ini adalah soal termudah yang ada di babak penyisihan dan 45 tim berhasil mendapatkan Accepted. Untuk menyelesaikan soal ini kita cukup melakukan bruteforce dengan memilih dua kombinasi hari ke-i dan hari ke-j dengan i < j. Untuk setiap kombinasi, hitung berapa gelas lemonade yang bisa dijual dengan melakukan iterasi pada jumlah gelas lemonade yang bisa dijual di hari-i (hari pertama dari pilihan) dan mengkalkulasi gelas lemonade terjual pada hari-j (hari kedua dari pilihan).

greedy works!
Dengan pengamatan (atau mungkin intuisi) lebih lanjut, kita bisa menunjukkan bahwa penjualan lemonade di hari-i bisa di-greedy, sehingga kita hanya perlu mempertimbangkan apakah akan menjual sebanyak yang kita bisa atau tidak menjual sama sekali di hari-i. Bagi yang teliti di soal ini mungkin sempat berpikir "bagaimana jika menjual di hari-i lebih sedikit dari kemampuan (meskipun mampu menjual lebih banyak) agar penjualan di hari-j bisa lebih banyak sehingga total penjualannya lebih tinggi" terutama pada kondisi di mana harga di hari-i mahal dan akan menyebabkan kerugian (loss) untuk setiap gelas terjual. Tim yang cermat dan ingin mengambil jalan aman akan menggunakan solusi bruteforce seperti pada penjelasan di atas. Namun tim yang memiliki daya pengamatan dan intuisi yang bagus (atau mungkin juga hanya beruntung) banyak yang menggunakan solusi greedy dengan menjual sebanyak yang dia sanggup di hari-i.

Di sini akan dijelaskan bahwa solusi greedy berlaku untuk soal ini.

A: harga beli bahan di hari-i
B: harga beli bahan di hari-j
a: gelas lemonade terjual di hari-i
b: gelas lemonade terjual di hari-j
N: uang di awal hari-i
M: uang di awal hari-j

Pernyataan soal yang ditulis dalam bentuk matematik:

Anda diminta untuk memaksimalkan nilai ans pada persamaan di atas. Jika persamaan-persamaan di atas kita lanjutkan, maka:

N, A dan B adalah konstanta pada persamaan di atas. Dengan demikian, perubahan nilai ans hanya tergantung pada a. Dari persamaan itu juga dapat disimpulkan bahwa ans dan a berbanding lurus jika (20 - A + B) > 0, dan berbanding terbalik jika (20 - A + B) < 0. Kita tidak bisa menciptakan kondisi di mana ans' > ans sedangkan a' < a pada (20 - A + B) > 0, demikian juga dengan yang sebaliknya.

Meskipun merupakan soal termudah, namun beberapa tim sempat mengalami kesulitan di soal ini karena salah memahami maksud dari soal (kurang teliti). Selain hal tersebut, sebagian besar peserta lain gagal di soal ini karena kesalahan logika pada program yang dibuat. Kesalahan yang umum dijumpai antara lain:

Keuntungan penjualan di hari-j digunakan untuk membeli bahan di hari-i (mundur hari)
atau dengan kata lain hari kedua penjualan terjadi sebelum hari pertama. Di soal sudah disebutkan bahwa profit penjualan hanya bisa digunakan untuk pembelian di hari berikutnya ("Every buck that he earns each day can be used to buy more ingredients for any following days").

Test case ke-6 pada test data milik juri menangkap program yang salah di sini,
```
100
5 4 3 2 1
5 4 3 2 1
5 4 3 2 1
```
Tidak menjual jika akan menyebabkan kerugian (harga beli lebih dari 20 bucks)
Keputusan tidak menjual jika harga lebih dari 20 bucks adalah tidak tepat, karena yang ingin kita maksimalkan di soal ini adalah jumlah gelas terjual, bukan keuntungannya.

Test case ke-22 pada test data milik juri menangkap program yang salah di sini,
```
100
10 10 10 10 10
10 10 10 10 10
10 10 10 10 10
```
Memilih hari penjualan pertama pada hari yang biaya pembeliannya paling rendah
Keputusan ini juga tidak tepat. Jika biaya pembelian terendah ada di hari terakhir (hari kelima) program tersebut hanya akan menjual satu hari di hari terakhir. Padahal bisa saja di hari-hari sebelumnya meskipun harga pembeliannya lebih tinggi tapi masih bisa mendatangkan keuntungan, sehingga uang yang ada ketika berada di hari terakhir lebih banyak, yang artinya lebih banyak gelas yang bisa dijual.

Test case ke-6 (sama seperti di atas) pada test data milik juri menangkap program yang salah di sini,
```
100
5 4 3 2 1
5 4 3 2 1
5 4 3 2 1
```

Solusi C/C++
oleh Suhendry Effendy

#include <stdio.h>

const int nday = 5;

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

  while ( T-- > 0 ) {
    int P, L[nday], S[nday], C[nday], R[nday];
    scanf( "%d", &P );
    for ( int i = 0; i < nday; i++ ) scanf( "%d", &L[i] );
    for ( int i = 0; i < nday; i++ ) scanf( "%d", &S[i] );
    for ( int i = 0; i < nday; i++ ) scanf( "%d", &C[i] );
    for ( int i = 0; i < nday; i++ ) R[i] = 3 * L[i] + S[i] + 2 * C[i];

    int ans = 0;

    for ( int i = 0; i < nday; i++ ) {
      int one = P / R[i];
      if ( ans < one ) ans = one;

      int profit = one * (20 - R[i]);

      for ( int j = i + 1; j < nday; j++ ) {
        int two = (P + profit) / R[j];
        if ( ans < one + two ) ans = one + two;
      }
    }

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

  return 0;
}

Solusi JAVA
oleh Felix Halim

import java.util.*;

public class lemon {
  int[] L = new int[5];
  int[] S = new int[5];
  int[] C = new int[5];
  int[][][] dp = new int[5][1000][3];

  int rec(int i, int P, int W){
    if (i>=5 || P==0 || W==0) return 0;
    if (dp[i][P][W]!=-1) return dp[i][P][W];

    int ret = rec(i+1, P, W);
    for (int g=1; ; g++){
      int nP = P - g*(3*L[i] + S[i] + 2*C[i]);
      if (nP < 0) break; else nP += g*20;
      ret = Math.max(ret, g + rec(i+1, nP, W-1));
    }
    return dp[i][P][W] = ret;
  }

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

    int nTC = scan.nextInt();
    while (nTC-- > 0){
      int P = scan.nextInt();
      for (int i=0; i<5; i++) L[i] = scan.nextInt();
      for (int i=0; i<5; i++) S[i] = scan.nextInt();
      for (int i=0; i<5; i++) C[i] = scan.nextInt();
      for (int[][] d1 : dp) for (int[] d2 : d1) Arrays.fill(d2,-1);
      System.out.println(rec(0,P,2));
    }
  }

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