Olimpiade Sains Provinsi (OSP) 2016 - Komputer, Nomor 22–23

Question

Apabila pada 1 hari dapat dilakukan 1 rapat rutin untuk tim-tim yang tidak memiliki anggota yang sama, berapa hari minimal supaya sang pimpinan proyek dapat memastikan bahwa seluruh tim sudah melakukan rapat bulanan? Ternyata, terdapat sebuah modul proyek yang belum ditangani oleh tim I sampai VI sehingga sang pimpinan proyek membentuk sebuah tim kecil (tim VII) yang terdiri dari Abdul, Dono, dan Gogo. Berapa hari minimum supaya yang pimpinan proyek dapat memastikan bahwa tim I sampai VII sudah

galangkangin gotera · Accepted Answer

22.
ada observasi greedy yang bisa dilakukan:
cepat atau lambat, semua tim pasti akan mengadakan pertemuan, jadi adalah optimal untuk setiap hari mengambil sebuah tim acak, lalu selama ada tim lain yang dapat dipilih, pilih tim tersebut. jadi strateginya selama masih ada tim, pilih tim dengan nomor terkecil, lalu cek apakah ada tim yang bisa ditambahkan
hari 1 -> tim 1 rapat

hari 2 -> tim 2 rapat (karena tim 3 dapat dimasukkan, maka tim 3 juga rapat)

hari 3 -> tim 4 rapat
hari 4 -> tim 5 rapat
hari 5 -> tim 6 rapat

23.
sama caranya, perhatikan tim 7 dapat dimasukkan ke hari 4, jadi hari tetap 5

Glenda Emanuella Sutanto · Answer

22.

	Abdul	Chika	Dono	Edgar	Gogo	Farhan	Beni
Tim I	v	v	v
Tim II		v		v	v
Tim III	v					v
Tim IV	v			v			v
Tim V		v				v	v
Tim VI			v		v		v

Perhatikan bahwa Beni termasuk ke Tim IV, V, dan VI sekaligus maka rapat tim IV, V dan VI harus beda hari (+3)

Perhatikan untuk Tim I, rapatnya juga harus di sendirikan karena semuanya anggotanya masuk ke >=1 tim (+1)

Tim II dan Tim III tidak memiliki anggota persekutuan, maka hari nya bisa di barengin (+1)

Banyak hari minimal yang diperlukan = 3 + 1 + 1 = 5

23. Anggota tim VII = Abdul, Dono, Gogo

Perhatikan bahwa tim V dan tim VII tidak memiliki anggota persekutuan, jadi harinya bisa dibarengin

Maka, tidak perlu tambahan hari

Banyak hari minimal yang diperlukan = 5

CMIIW

Yusril Albi · Answer

22. Gunakan konsepp himpunan ; Tim 1 = tidak memiliki irisan dengan tim manapun jadi harus melakukan rapat sendiri = 1 hari Tim 2 = dapat melakukan rapat bersama tim 3 = 1 hari Tim 3 = dapat melakukan rapat bersama tim 2 , karena telah melakukan rapat dengan tim 2 = 0 hari Tim 4 = tidak memiliki irisan dengan tim manapun jadi harus melakukan rapat sendiri = 1 hari Tim 5 = tidak memiliki irisan dengan tim manapun jadi harus melakukan rapat sendiri = 1 hari Tim 6 = dapat melakukan rapat bersama ti

Olimpiade Sains Provinsi (OSP) 2016 - Komputer, Nomor 22–23

3 jawaban