BNPCHS 2016

Tahun 2016 ini, BNPCHS mengalami penambahan jumlah peserta yang cukup signifikan dari tahun sebelumnya menjadi lebih dari 80 siswa-siswi SMA dari seluruh Indonesia. Hal ini mungkin merupakan pertanda bahwa semakin banyak siswa-siswi Indonesia yang mulai mengenal competitive programming. Harapan kami adalah semoga tahun-tahun berikutnya peserta BNPCHS akan semakin bertambah lebih banyak lagi. Pada Babak Kualifikasi yang diadakan pada tanggal 24 Juli 2016 lalu, tim Juri menyiapkan 6 buah soal dengan tingkat kesulitan yang beragam. Babak kualifikasi tersebut berlangsung selama 3 Jam 30 Menit dari Pukul 13.00 - 16.30. Tim Juri menggunakan sistem Jollybee Online Judge untuk melaksanakan Babak Kualifikasi.

Jumlah peserta yang berhasil menyelesaikan minimal satu soal pada tahun ini berkurang menjadi 3 orang, dengan 6 orang berhasil mensapu bersih semua soal yang kami siapkan. Selamat kepada siswa dengan username hs16sergiovieri yang berhasil menduduki peringkat pertama dalam Babak Kualifikasi lalu, walau bukan siswa pertama yang berhasil menyelesaikan semua soal. Sebagian besar peserta tahun ini sudah menggunakan C++ sebagai bahasa pemrogramannya. Padahal, beberapa tahun lalu Pascal masih mendominasi BNPCHS.

Setelah Babak Kualifikasi berakhir, tim Juri menyusun daftar siswa-siswi yang lolos ke Babak Final di Jakarta tanggal 7 Agustus 2016 nanti. Sebanyak 70 Siswa-Siswi berhasil memenuhi Kualifikasi untuk masuk ke Babak Final. Kami mengundang dan mengharapkan kehadiran teman-teman SMA semua pada tanggal tersebut di Kampus Anggrek Binus University. Pada Babak Final nanti akan ada banyak makanan dan hadiah untuk dimakan dan diraih oleh kalian semua. Tunggu apalagi? Jangan sampai tidak datang!

Cukup dengan basa-basinya, berikut adalah pembahasan untuk semua soal-soal Babak Penyisihan lalu. Semoga editorial ini bermanfaat bagi siswa-siswi yang membutuhkannya.

Problem A - Tiga Sekawan dan Bola Basket

Author: Suhendry Effendy

Ini adalah salah satu soal termudah di babak kualifikasi ini. Diberikan input berupa 3 buah bilangan bulat, A, B, dan C yang merupakan banyaknya bola basket yang berhasil dimasukkan oleh Jingga, Putra, dan Wijaya, tentukan siapa yang memenangkan pertandingan basket tersebut.

Solusi untuk soal ini adalah mengecek angka siapa yang paling besar diantara ketiga orang tersebut. Apabila A yang terbesar dari 2 angka lainnya, maka "JINGGA"-lah yang menang. Selain itu, apabila B yang terbesar dari 2 angka lainnya, maka "PUTRA"-lah yang menang. Selain 2 kasus tersebut, maka "WIJAYA"-lah yang menang.

Beberapa peserta tidak memperhatikan format output yang ditentukan soal. Contohnya, apabila input yang diberikan adalah 5 2 19 (outputnya WIJAYA), berikut adalah beberapa kesalahan ditemui pada program peserta:

Wijaya (salah, karena tidak ada keluaran 'Kasus #X: ', selain itu Wijaya harus ditulis 'WIJAYA')
KASUS #1: WIJAYA (salah, karena 'KASUS' seharusnya 'Kasus')
Kasus #1:WIJAYA (salah, karena setelah ':' harus diberikan tepat satu spasi)

Tahun ini tidak ada yang mengeluarkan output tambahan yang tidak diminta soal (ct: "Masukan Input: ", "Input: ", dan lainnya). Meskipun masih ada beberapa yang kurang teliti dalam menangani output.

Solusi C++
#include <cstdio> int main() { int T; scanf( "%d", &T ); for ( int tc = 1; tc <= T; tc++ ) { int A, B, C; scanf( "%d %d %d", &A, &B, &C ); printf( "Kasus #%d: ", tc ); if ( A > B && A > C ) printf( "JINGGA\n" ); if ( B > A && B > C ) printf( "PUTRA\n" ); if ( C > A && C > B ) printf( "WIJAYA\n" ); } return 0; } oleh Suhendry Effendy
Solusi Pascal
var T, tc : integer; A, B, C : integer; begin readln(T); for tc := 1 to T do begin readln(A, B, C); write('Kasus #', tc, ': '); if (A > B) and (A > C) then writeln('JINGGA'); if (B > A) and (B > C) then writeln('PUTRA'); if (C > A) and (C > B) then writeln('WIJAYA'); end; end. oleh Felix Jingga

Problem B - Haus

Author: Anton Wibowo

Pertama, cari terlebih dahulu lokasi Jingga pada peta yang diinput. Kemudian lakukan Breadth First Search untuk mencari posisi 'E' terdekat dari lokasi Jingga berada. Untuk setiap lokasi 'E' yang terdekat (bisa lebih dari 1 lokasi), lakukan flood fill dari titik itu untuk menghitung seberapa banyak ember yang ada pada wilayah tersebut. Jawabannya adalah output maksimum dari setiap flood fill yang kita jalankan.

Solusi C++

#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;

typedef struct {
  int r, c;
} Cell;

int N;
char maps[120][120];
int visited[120][120];

// delta variable to "move"
// ^ = move UP, < = move LEFT, > = move RIGHT, v = move DOWN
//                 ^   >   v   <
int deltaRow[] = {-1, +0, +1, +0}; // delta for Row
int deltaCol[] = {+0, +1, +0, -1}; // delta for Column



int floodfill(Cell currentCell) {
  int ret = 1;
  visited[currentCell.r][currentCell.c] = 2; // tandai bahwa dia sudah di proses
  for(int i=0; i<4; i++) {

    int newRow = currentCell.r + deltaRow[i];
    int newCol = currentCell.c + deltaCol[i];
    Cell newCell = (Cell){newRow, newCol};

    // cek apakah keluar dari Peta
    if (newRow < 0 || newRow >= N || newCol < 0 || newCol >= N) {
      continue;
    }

    // cek apakah sudah di proses
    if (visited[newRow][newCol] == 2) {
      continue;
    }

    // hanya proses apabila 'E'
    if (maps[newRow][newCol] == 'E') {
      ret += floodfill(newCell);
    }
  }
  return ret;

}

int solve(Cell initialCell) {
  memset(visited, 0, sizeof(visited));
  bool isDone = false;
  int ans = 0;

  // Breadth First Search!
  queue< Cell > q;
  q.push(initialCell);


  for(int moves=0; !isDone && q.size() > 0; moves++) {

    // hanya proses sebanyak jumlah cell di queue pada "moves" sekarang.
    for(int currentMoves = 0, currentCellInQueue = q.size(); currentMoves < currentCellInQueue; currentMoves++) {
      Cell currentCell = (Cell)q.front();
      q.pop();

      // Jangan proses lagi apabila sudah pernah selesai di proses
      if (visited[currentCell.r][currentCell.c] == 2) continue;


      // tandai bahwa dia sudah selesai di proses
      visited[currentCell.r][currentCell.c] = 2;

      // untuk setiap 'E' pada "moves" yang sama 
      // (berarti distancenya sama, dan ini adalah distance terminimum)
      if (maps[currentCell.r][currentCell.c] == 'E') {
        ans = max(ans, floodfill(currentCell));
        isDone = true;
      }

      for(int i=0; !isDone && i<4; i++) {
        int newRow = currentCell.r + deltaRow[i];
        int newCol = currentCell.c + deltaCol[i];
        Cell newCell = (Cell){newRow, newCol};

        // cek apakah keluar dari Peta
        if (newRow < 0 || newRow >= N || newCol < 0 || newCol >= N) {
          continue;
        }

        // cek apakah sudah di proses
        if (visited[newRow][newCol] > 0) {
          continue;
        }

        if (maps[newRow][newCol] == '.' || maps[newRow][newCol] == 'E') {
          visited[newRow][newCol] = 1; // tandai bahwa dia sedang di proses
          q.push(newCell);
        }
      }

    }

  }

  return ans;

}
 
int main() {
  int T;
  scanf("%d", &T);
  for ( int tc = 1; tc <= T; tc++ ) {
    scanf("%d", &N);

    int startRow, startColumn;
    for(int i=0; i<N; i++) {
      scanf("%s", maps[i]);
      for(int k=0; k<N; k++) {
        if (maps[i][k] == 'J') {
          startRow = i;
          startColumn = k;
        }
      }
    }

    Cell initialCell = (Cell){startRow, startColumn};

    printf("Kasus #%d: %d\n", tc, solve(initialCell));

  }
  return 0;
}

oleh Felix Jingga

Problem C - Andi dan Krisis Akhir Bulan

Author: Ricky Sentoso, Andi Halim

Kita dapat melakukan Breadth First Search untuk soal ini. Keadaan awal yang kita masukkan ke algoritma Breadth First Search adalah jumlah uang sekarang di dompet dan bank (JumlahUangDiBank, JumlahUangDiDompet). Lalu, Output yang diinginkan adalah berapa langkah agar algoritma Breadth First Search mencapai keadaan (0,JumlahUangDiBank + JumlahUangDiDompet). Apabila keadaan (0,JumlahUangDiBank + JumlahUangDiDompet) tidak dapat dicapai, kita harus mengeluarkan output "-1"

Solusi C++

#include <bits/stdc++.h>
using namespace std;

#define INF 2123123123

typedef struct {
  int bank, dompet;
} Uang;

int T, N, B, D, A[105];
int dist[205][205]; // saldo di bank, uang di dompet

int solve(){
  for(int i = 0; i < 205; i++)
    for(int j = 0; j < 205; j++) dist[i][j] = INF;


  // Breadth First Search
  dist[B][D] = 0;
  queue< Uang > q;
  q.push((Uang){B, D});


  while(!q.empty()){
    Uang uangSekarang = q.front();
    q.pop();


    // untuk setiap ATM
    for(int i = 0; i < N; i++){
      // coba Setor!
      Uang uangSetelahSetor = (Uang){uangSekarang.bank+A[i], uangSekarang.dompet-A[i]};
      if(uangSetelahSetor.dompet >= 0){
        if(dist[uangSetelahSetor.bank][uangSetelahSetor.dompet] == INF){
          dist[uangSetelahSetor.bank][uangSetelahSetor.dompet] = dist[uangSekarang.bank][uangSekarang.dompet]+1;
          q.push(uangSetelahSetor);
        }
      }
      // Coba Tarik dari ATM
      Uang uangSetelahTarik = (Uang){uangSekarang.bank-A[i], uangSekarang.dompet+A[i]};
      if(uangSetelahTarik.bank >= 0) { // kalo tarik sbyk A[i] dari ATM dan di ATM >= 0
        if(dist[uangSetelahTarik.bank][uangSetelahTarik.dompet] == INF) {
          dist[uangSetelahTarik.bank][uangSetelahTarik.dompet] = dist[uangSekarang.bank][uangSekarang.dompet]+1;
          q.push(uangSetelahTarik);
        }
      }
    }
  }
  int ret = -1;
  if (dist[0][B+D] != INF) ret = dist[0][B+D];
  return ret;
}

int main(){
  scanf("%d", &T);
  for(int tc=1; tc<=T; tc++) {
    scanf("%d %d %d", &N, &B, &D);
    for(int i = 0; i < N; i++) scanf("%d", &A[i]);
    printf("Kasus #%d: %d\n", tc, solve());
  }
  return 0;
}

oleh Ricky Sentoso

Problem D - Quiz Tebak Kode

Author: Hutomo Widjaja

Pada soal ini yang kita lakukan adalah mencoba semua kemungkinan angka dari 0000 ... 9999 (10000 kemungkinan). Untuk setiap kemungkinan angka tersebut, asumsikan bahwa angka itu adalah angka yang dipikirkan oleh Rangga. Kemudian, cek apakah semua tebakan Felix dan semua jawaban Rangga konsisten dengan angka asumsi tersebut.

Solusi C++

#include<cstdio>
#include<cstring>

char Guess[105][10], currentGuess[10];
int correct[105], inPlace[105];

int countCorrect(int idx) {
  int count[15];
  int ret = 0;
  memset(count, 0, sizeof(count));

  for(int i=0, len=strlen(currentGuess); i<len; i++) {
    count[currentGuess[i]-'0']++;
  }
  for(int i=0, len=strlen(Guess[idx]); i<len; i++) {
    if (count[Guess[idx][i]-'0'] > 0) {
      ret++;
      count[Guess[idx][i]-'0']--;
    }
  }
  return ret;
}

int countInPlace(int idx) {
  int ret = 0;
  for(int i=0, len=strlen(currentGuess); i<len; i++) {
    if (currentGuess[i] == Guess[idx][i]) ret++;
  }
  return ret;
}

int main() {
  int ntc;
  scanf("%d", &ntc);
  for(int TC=1; TC<=ntc; TC++) {
    int N;
    scanf("%d", &N);
    for(int i=0; i<N; i++) {
      scanf("%s %d %d", Guess[i], &correct[i], &inPlace[i]);
    }

    int ans = 0;
    for(int i=0; i<10000; i++) {
      sprintf(currentGuess, "%04d", i);

      bool isCandidate = true;
      for(int k=0; isCandidate && k<N; k++) {

        int correctDigit = countCorrect(k);
        int correctInPlace = countInPlace(k);
        int correctNotInPlace = correctDigit - correctInPlace;

        if (!(correctNotInPlace == correct[k] && correctInPlace == inPlace[k])) {
          isCandidate = false;
        }
      }
      if (isCandidate) ans++;
    }

    printf("Kasus #%d: %d\n", TC, ans);
  }
  return 0;
}

oleh Felix Jingga

Problem E - Lilin Kue Ulang Tahun

Author: Suhendry Effendy

Hitung banyaknya tiap karakter 'a' sampai 'z' dalam input string pertama yang diberikan. Kemudian untuk string kedua yang diberikan, cek apakah terdapat jumlah karakter yang cukup pada string pertama untuk membentuk string tersebut.

Solusi C++

#include <bits/stdc++.h>
using namespace std;

char L[105];
char K[105];

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

  for(int tc=1; tc <= T; tc++) {
    scanf( "%s", L );
    scanf( "%s", K );

    int num[256] = {0};

    bool ans = true;
    for(int i=0, _n=strlen(L); i<_n; i++) num[L[i]]++;
    for(int i=0, _n=strlen(K); i<_n; i++) {
      num[K[i]]--;
      if ( num[K[i]] < 0 ) ans = false; // Jika karakter yang tersedia tidak mencukupi
    }

    printf( "Kasus #%d: %s\n", tc, ans ? "YA" : "TIDAK" );
  } 
  
  return 0;
}

oleh Suhendry Effendy

Problem F - Warnet Jingga

Author: Rafael Herman Yosef

Soal ini meminta kita untuk menghitung berapa banyak orang yang diperlukan agar tidak ada komputer yang dapat dipakai lagi.

Setiap orang dapat mencakup paling banyak sebanyak 2*K+1 komputer, dan paling sedikit sebanyak K+1 komputer.

Berikut adalah contoh K=2 (X = area cakupan, O = orangnya)
Paling maksimum untuk kasus ini, cara mencakupnya adalah seperti berikut

XXOXX XXOXX

Paling minimum untuk kasus ini, untuk mencakupnya adalah seperti berikut

OXX OXX

Sehingga, agar banyaknya orang yang dibutuhkan minimum, maka cakupan komputer yang harus dicakup setiap orang harus maksimum(XXOXX XXOXX). Sehingga banyaknya orang minimum dapat dihitung dengan rumus N/(2*K+1). Namun apabila N tidak habis dibagi oleh 2*K+1, maka diperlukan 1 orang tambahan untuk mencakup sisa komputer yang tidak dapat dicakup.

Agar banyaknya orang yang dibutuhkan maksimum, maka cakupan komputer yang harus dicakup setiap orang harus minimum(OXX OXX). Sehingga banyaknya orang maksimum dapat dihitung dengan rumus N/(K+1). Namun apabila N tidak habis dibagi oleh K+1, maka diperlukan 1 orang tambahan untuk mencakup sisa komputer yang tidak dapat dicakup.

Hal yang harus diperhatikan adalah batasan N dan K yang dapat mencapai 10¹⁵. Untuk soal ini memerlukan tipe data 64 bit. Kesalahan yang dilakukan oleh beberapa peserta adalah tidak memperhatikan batasan tersebut dan memakai tipe data 32 bit untuk input dan output.

Solusi C++
#include<bits/stdc++.h> using namespace std; int main() { long long ntc,n,k; scanf("%lld",&ntc); for(int tc=1;tc<=ntc;tc++) { scanf("%lld %lld",&n,&k); long long cakupanMinimum = n/(2k+1); if(n%(2k+1)!=0) cakupanMinimum++; long long cakupanMaksimum = n/(k+1); if(n%(k+1)!=0) cakupanMaksimum++; printf("Kasus #%d: %lld %lld\n",tc,cakupanMinimum,cakupanMaksimum); } return 0; } oleh Felix Jingga
Solusi Pascal
var tc, ntc, n, k: Int64; cakupanMinimum, cakupanMaximum: Int64; begin readln(ntc); for tc := 1 to ntc do begin readln(n, k); cakupanMinimum := n div (2k+1); if n mod (2k+1) <> 0 then begin cakupanMinimum := cakupanMinimum+1; end; cakupanMaximum := n div (k+1); if n mod (k+1) <> 0 then begin cakupanMaximum := cakupanMaximum+1; end; writeln('Kasus #', tc, ': ', cakupanMinimum, ' ', cakupanMaximum ); end; end. oleh Suhendry Effendy

Selamat untuk 70 Siswa yang berhasil lolos ke babak final. Untuk list siswa yang lolos dapat dilihat pada tautan berikut: di halaman "Peserta Final"

Masih ada waktu sekitar 2 minggu sebelum Final. Pakailah waktu tersebut sebaik-baiknya untuk melatih diri kalian sehingga lebih siap nantinya.

Akhir kata, Sampai jumpa di babak final. Good luck and have fun!

PS: Jangan lupa makan banyak-banyak makanan yang disediakan untuk kalian

-- Felix Jingga