BNPC-HS 2008 ( BNPCHS 2008 ) Qualification Round & Problemset Review & Solution
Categories: Algoritma, Cerita, Programming | December 9th, 2008 | by Felix J | No CommentsProblem A : Hasil UAN
Writer : Suhendry Effendy
Ini adalah soal termudah dalam penyisihan kali ini. Diberikan N nilai, kita harus menentukan Nilai tertinggi, dan banyaknya nilai tertinggi tersebut. Solusi untuk problem ini cukup gampang, pertama kita tinggal mencari berapakah nilai tertingginya, kemudian setelah dapat nilai tertingginya, sekali lagi lakukan iterasi ke N buah data tersebut dan hitung ada berapa data yang sama dengan nilai maksimum. Solusinya dapat dilihat dibawah.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | #include<algorithm> #include<cstdio> // Felix J's AI v1.0 #define FOR(i,a,b) for(int i=(a),_n=(b); i<=_n; i++) #define REP(i,n) FOR(i,0,(n)-1) #define FORD(i,a,b) for(int i=(a),_n=(b);i>=_n; i--) #define FILL(i,v) memset((i),(v),sizeof((i))) using namespace std; typedef long long LL; int arr[1002]; int main() { int ntc; scanf("%d", &ntc); while (ntc--) { int n,maxval=0,res=0; scanf("%d", &n); REP(i,n) scanf("%d", &arr[i]), maxval >?= arr[i]; REP(i,n) if (arr[i]==maxval) res++; printf("%d %d\n", maxval, res); } return 0; } |
Problem B : Pita Biner
Writer : Andrian Kurniady
Soal kedua hanya soal yang lebih susah, karena kita diperintahkan untuk membaca angka dalam sebuah format yang sudah diberikan (Mirip seperti gambar). Sehingga dalam soal ini, dibutuhkan ketelitian dan pemahaman soal.
Soal kedua ini penuh dengan jebakan jika tidak membaca soal dengan teliti dan memahami maksudnya. Untuk pertama kali, kita perlu mengecek apakah baris ke 1 dan 6 memiliki minimal 1 buah angka 1. Jika ada 1 buah saja angka 1, maka cetak “PITA RUSAK”. Kedua, kita perlu cek apakah kolom ke 1 dan kolom ke n (n adalah nilai yang diinput) memiliki minimal 1 buah angka 1 lagi. Jika ya, Maka cetak “PITA RUSAK”.
Kemudian, kita mulai dari kolom ke-2, sampai ke kolom n. Untuk masing-masing kolom, kita cek apakah di kolom itu, kita bisa bentuk angka 1 atau 0. Jika tidak bisa keduanya, maka cetak “PITA RUSAK”, Jika bisa salah satu, maka tambahkan angka yang bisa kedalam output kita. Jika ditemukan 1, maka tambahkan kolom sebanyak 2 kolom (Setelah angka, akan ada 1 kolom isi kosong semua), namun jika ditemukan 0, maka tambahkan kolom sebanyak 4 kolom.
Btw, tidak ada case dimana n!=panjang string (Asumsi ini diambil beberapa peserta karena sample test case ke-2, n=10 tapi panjangnya 11. Tapi itu murni typo dan sudah di fix setelah kami menyadarinya. *Karena tidak ada peserta yang minta klarifikasi, jadi kami agak terlambat menyadari.*
Untuk lebih jelasnya, anda bisa lihat pada implementasi berikut:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 | #include<algorithm> #include<string> #include<cstdio> // Felix J's AI v1.0 #define FOR(i,a,b) for(int i=(a),_n=(b); i<=_n; i++) #define REP(i,n) FOR(i,0,(n)-1) #define FORD(i,a,b) for(int i=(a),_n=(b);i>=_n; i--) #define FILL(i,v) memset((i),(v),sizeof((i))) using namespace std; typedef long long LL; char s[9][1050]; inline bool check(int idx, int n, int mode) { switch (mode) { case 0 : FOR(i,1,4) if ( s[i][idx]=='0' || s[i][idx+2]=='0' || s[i][idx+3]=='1' ) return 0; if ( s[1][idx+1]=='0' || s[4][idx+1]=='0' || s[2][idx+1]=='1' || s[3][idx+1]=='1' ) return 0; return 1; case 1 : FOR(i,1,4) if ( s[i][idx]=='0' || s[i][idx+1]=='1' ) return 0; return 1; case 2 : REP(i,n) if ( s[0][i]=='1' || s[5][i]=='1' ) return 0; REP(i,6) if ( s[i][0]=='1' || s[i][n-1]=='1' ) return 0; return 1; } } string solve(int n) { string res = ""; if ( check(-1,n,2)==0 ) return "PITA RUSAK"; int j = 1; while (j<n) { bool checkone = check(j,n,1),checkzero = check(j,n,0); if ( checkone==0 && checkzero==0 ) return "PITA RUSAK"; if ( checkzero ) res+="0",j+=4; if ( checkone ) res+="1",j+=2; } return res; } int main() { int ntc,n; scanf("%d", &ntc); while(ntc--) { scanf("%d", &n); FILL(s,'0'); REP(i,6) scanf("%s", s[i]); puts( solve(n).c_str() ); } return 0; } |
Problem C : Promo Permen Pahitos
Writer : Suhendry Effendy
Problem ini sebenarnya mudah, tapi karena k yang sangat tinggi, tidak memungkinkan untuk melakukan linear search. Salah satu caranya adalah dengan menggunakan Binary Search dengan cara menebak apakah dengan Jumlah beli yang sekarang, Si Manisa dapat menikmati setidaknya k permen pahitos. Untuk mencari tahu dengan jumlah yang sekarang, apakah bisa menikmati k permen pahitos, dapat dilakukan dengan mensimulasinya saja.
Cara kedua adalah dengan linear search yang lebih pintar. Caranya adalah dengan rumus, kita mencari lower bound yang terdekat agar bisa mendapatkan setidaknya menikmati k permen pahitos.
Untuk lebih jelasnya, saya sertakan dua buah solusi:
1. Solusi Binary Search
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | #include<algorithm> #include<cstdio> // Felix J's AI v1.0 #define FOR(i,a,b) for(int i=(a),_n=(b); i<=_n; i++) #define REP(i,n) FOR(i,0,(n)-1) #define FORD(i,a,b) for(int i=(a),_n=(b);i>=_n; i--) #define FILL(i,v) memset((i),(v),sizeof((i))) using namespace std; typedef long long LL; int n,m,k; int howmany(int x) { int res=0,sisa=0; while ( x > 0 && k>res ) res+=x,sisa+=x,x=sisa/m*n,sisa%=m; return res; } int solve() { int lo=1,hi=k; while (lo<=hi) { int mid = (lo+hi)/2; if ( howmany(mid) >= k ) hi = mid - 1; else lo = mid + 1; } return lo; } int main() { int ntc; scanf("%d", &ntc); while(ntc--) { scanf("%d %d %d", &m,&n,&k); printf("%d\n", solve()); } return 0; } |
2. Solusi Rumus
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 | #include<algorithm> #include<cstdio> // Felix J's AI v1.0 #define FOR(i,a,b) for(int i=(a),_n=(b); i<=_n; i++) #define REP(i,n) FOR(i,0,(n)-1) #define FORD(i,a,b) for(int i=(a),_n=(b);i>=_n; i--) #define FILL(i,v) memset((i),(v),sizeof((i))) using namespace std; typedef long long LL; int n,m,k; int howmany(int x) { int res=0,sisa=0; while ( x > 0 && k>res ) res+=x,sisa+=x,x=sisa/m*n,sisa%=m; return res; } int main() { int ntc; scanf("%d", &ntc); while(ntc--) { scanf("%d %d %d", &m,&n,&k); int ans = k * (m-n) / m; while( howmany(ans) < k ) ans++; printf("%d\n", ans); } return 0; } |
Untuk soal, sepertinya tidak lama lagi akan segera di publish langsung di website resmi BNPC-HS 2008