Olimpiade Sains Provinsi (OSP) 2015 - Komputer, Nomor 11
Pak Dengklek sedang membagi kertas ujian di kelasnya. Tumpukan kertas sebanding banyaknya lembar kertas ujian. Karena malas, Pak Dengklek langsung memberikan sebuah tumpukan kertas ujian ke seorang murid. Kemudia Pak Dengklek menyuruh murid itu untuk mencari kertas ujiannya sendiri, dan membagi tumpukan kertas ujian itu menjadi dua tumpukan yang sama tinggi seusai murid itu mendapatkan kertas ujiannya. Kedua tumpukan itu diberikan ke dua murid lain yang belum mendapatkan kertas ujiannya. Jika tinggi tumpukan adalah x, maka seorang murid perlu x detik untuk mendapatkan kertas ujiannya dari tumpukan tersebut. Lalu, seorang murid perlu 10 detik untuk menyerahkan dua tumpukan ke dua murid lain. Jika Dedew, seorang murid Pak Dengklek, menerima hanya 1 lembar kertas dan dia telah menunggu selama 50 detik, berapa banyak murid Pak Dengklek?
7 jawaban
Fajar Adi10 tahun lalu
5
Ingat, kalau misal awalnya ada 8 siswa, nanti di bagi jadi 4 dan 3 (karena udah dikurangi 1, yaitu si pembagi), bukan jadi 4 dan 4.
alvin setyadhamskuy6 tahun lalu
salah tolol
Kopi Putih7 tahun lalu
1
Soal ini bisa diselesaikan dengan graf, penjelajahan Graf yaitu BFS. Awalnya inisialisasikan node 1, karena dedew hanya mendapat satu buah kertas. Anggap sebuah edge memiliki nilai 10, yaitu lama waktu memberikan setumpuk kertas ujian. Setelah itu cari node apa saja yang bisa terhubung dari node 1.
Jika pada suatu murid tersisa 2 kertas, maka waktu pencariannya 2 menit, diambil 1 menjadi tinggal 1 kertas, akan dibagi dua menjadi 1 dan 0
Jika pada suatu murid tersisa 3 kertas, maka waktu pencariannya 3 menit, diambil 1 menjadi tinggal 2 kertas, akan dibagi dua menjadi 1 dan 1
Jika pada suatu murid tersisa 4 kertas, maka waktu pencariannya 4 menit, diambil 1 menjadi tinggal 3 kertas, akan dibagi dua menjadi 2 dan 1
Jika pada suatu murid tersisa 5 kertas, maka waktu pencariannya 5 menit, diambil 1 menjadi tinggal 4 kertas, akan dibagi dua menjadi 2 dan 2.
Sehingga kemungkinan node 1 hanya ada 2,3,dan 4. Selain itu, juga dapat dirumuskan bahwa node n memiliki tetangga yang lebih besar dari n ( yang menerima kertas sebelum seorang murid menerima kertas ke n ) { n*2, n*2+1, n*2+2 }. Setiap edge memiliki bobot 10, edge memiliki bobot sesuai nomornya. Untuk Lebih Jelasnya lihat graf di bawah ini:
( Maaf Kalau Gambarnya tidak terlihat )
Pada panah warna Hijau adalah jalur yang menghasilkan jumlah 50, yaitu 2+10+6+10+12=50.
Melakukan Bread First Search pada graf tersebut dari mulai nomor 1, dengan 2 buah struktur data queue. Satu queue untuk menampung banyaknya tumpukan kertas saat itu, queue satunya lagi untuk menampung durasi.
#include <bits/stdc++.h>
using namespace std;
int main() {
queue<int> q;//menampung nomor node
queue<int> s;//menampung durasi
q.push(1);
s.push(0);
int target=50;
int now_q,now_s;//menampung q front dan s front
while(1){
now_q=q.front();
now_s=s.front();
if(now_s>=target){
if(now_s>target){
cout<<"Tidak Mungkin"<<endl;
return 0;
}
else{
break;
}
}
q.pop();
s.pop();
for(int i=now_q*2;i<=now_q*2+2;i++){
q.push(i);
s.push(i+10+now_s);
}
}
cout<<now_q<<endl;
}
Sehingga pada saat queue yang menampung durasi mencapai 50, queue yang menampung jumlah kertas saat itu memiliki elemen paling depan 12.
Masuk untuk menulis jawaban
bukanya tumpukan sama banyak setelah di ambil satu dan /2 ? brarti awalnya gnajil kan ?