“PARADE LAMPU”
Posted November 6, 2008
on:Apa tuh parade lampu?????? penasaran ya???
nie soal lengkapnya,….
Ehya, soal nie pernah keluar di OSN, sebelum itu pernah dibuat juga di lomba IOI’98
Nama Soal : Parade Lampu
Kategori : Sedang
Problem Setter : Rully
Deretan lampu warna-warni dipasang untuk memeriahkan acara pesta.
Jumlah lampu yang dipasang sebanyak N yang diberi nomor 1 sampai
dengan N. Lampu-lampu tersebut terhubung pada rangkaian pengendali yang
mempunyai 4 buah tombol. Masing-masing tombol tersebut berfung-si
sebagai berikut :
Tombol 1 : Jika tombol ini ditekan, maka semua lampu yang terhubung
akan berubah statusnya. Artinya, lampu yang semula
MENYALA akan PADAM, sedang lampu yang semula
PADAM akan MENYALA.
Tombol 2 : Jika tombol ini ditekan, maka semua lampu yang bernomor
ganjil akan berubah statusnya.
Tombol 3 : Jika tombol ini ditekan, maka semua lampu yang bernomor
genap akan berubah statusnya.
Tombol 4 : Jika tombol ini ditekan, maka semua lampu yang bernomor
3K+1 akan berubah statusnya. K adalah bilangan bulat ≥ 0.
Pada rangkaian pengendali, terdapat counter C yang mencatat banyaknya
penekanan tombol yang telah dilakukan. Ketika acara dimulai, kondisi semua
lampu MENYALA dan counter C diset 0 (nol). Untuk menyatakan status
lampu yang MENYALA, digunakan nilai 1 (satu). Sedangkan untuk lampu
yang PADAM, digunakan nilai 0 (nol).
Buatlah program untuk menentukan semua konfigurasi akhir yang
mungkin dari status semua lampu sebanyak N tersebut berdasarkan
informasi yang diberikan. Informasi yang diberikan meliputi nilai akhir counter
C serta status akhir dari sebagian lampu. Semua konfigurasi akhir yang
mungkin tersebut tidak diperbolehkan berulang.
INPUT
Input terdiri atas 4 baris. Baris pertama menyatakan banyaknya N buah lampu.
Baris kedua menyatakan nilai akhir counter C. Batasan nilai N dan C adalah
sebagai berikut : 10 ≤ N ≤ 100, 1 ≤ C ≤ 10000. Baris ketiga, berisi daftar
nomor lampu yang MENYALA pada akhir acara. Setiap nomor dipisah-kan
oleh spasi dan diakhir baris diberikan nilai -1. Baris keempat, berisi daftar
nomor lampu yang PADAM pada akhir acara. Setiap nomor dipisahkan oleh
spasi dan diakhir baris diberikan nilai -1.
OUPUT
Output berisi semua konfigurasi akhir yang mungkin dari status semua lampu
sebanyak N tersebut berdasarkan informasi yang diberikan. Tidak
diperbolehkan adanya konfigurasi yang berulang. Tiap konfigurasi yang
mungkin harus dituliskan pada baris yang berbeda. Urutan konfigurasi boleh
sebarang.
CONTOH INPUT
10
1
-1
7 -1
Pada kasus diatas, terdapat 10 lampu dan hanya sekali terjadi penekanan
tombol. Hanya diketahui informasi bahwa, lampu nomor 7 statusnya PADAM
diakhir acara.
CONTOH OUTPUT
0000000000
0110110110
0101010101
Pada kasus diatas, ada 3 kemungkinan konfigurasi lampu diakhir acara,
yaitu :
• Semua lampu PADAM.
• Lampu nomor 1, 4, 7 dan 10 PADAM; sedangkan LAMPU 2, 3, 5, 6, 8
dan 9 MENYALA.
• Lampu nomor 1, 3, 5, 7 dan 9 PADAM, sedangkan LAMPU 2, 4, 6, 8
dan 10 MENYALA.
nah,….silahkan di bwt latihan dulu ya….
ayo temukan!!!!!!!!!!!!!!
Oktober 15, 2009 pada 9:30 am
waduh…tuch soal tugasku dr pak Rully…
btw, pak Rully itu dosenku lho…
orangnya super duper cerdas bgt….
ntar dech kalo udah selesai ngerjain aku bls lg
Bubye…