Yuk bantu teman kamu belajar dengan menambahkan soal di Kujawab. Klik disini..

Olimpiade Sains Nasional (OSN) 2014 - Komputer , Nomor 10

10

1s, 32MB

Tahukah anda apa itu suten? Suten, sut, suit (suwit), atau pingsut adalah cara mengundi untuk dua orang dengan cara mengadu jari untuk menentukan siapa yang menang.

Di Indonesia, jari yang dipergunakan dalam suten adalah ibu jari yang diumpamakan sebagai gajah, jari telunjuk yang diumpamakan sebagai manusia, dan jari kelingking yang diumpamakan sebagai semut. Dua orang yang bersuten secara serentak mengacungkan jari yang dipilihnya. Hasilnya seri terjadi bila kedua belah pihak yang bersuten mengacungkan jari yang berkekuatan sama, misalnya: kelingking melawan kelingking. Biasanya, apabila terjadi seri maka suten diulang hingga ada pihak yang menang, namun peraturan ini tidak berlaku untuk saat ini.

Jari yang menjadi pemenang suten:

Ibu jari versus telunjuk: pemenang adalah ibu jari.
Telunjuk versus kelingking: pemenang adalah telunjuk.
Kelingking versus ibu jari: pemenang adalah kelingking.
Anda, sebagai salah satu finalis OSN Komputer 2014, diminta untuk menyelesaikan tantangan berikut.

Ada N anak yang bermain suten bersama-sama. Anak-anak ini memiliki jari favorit mereka masing-masing sehingga setiap melakukan suten, mereka selalu mengeluarkan jari favoritnya untuk diadu. Setiap anak melakukan suten dengan anak lainnya tepat sekali, sehingga ada (N × (N - 1)) / 2 buah pertandingan suten yang akan dilakukan.

Diberikan nilai N, Anda (dan program Anda) akan ditanyakan (N × (N - 1)) / 2 buah pertandingan suten dan menentukan siapa pemenangnya (atau menentukan adanya seri). Apabila Anda salah menjawab, maka secara otomatis Anda gagal menyelesaikan tantangan dan akan mendapatkan nilai 0.

Karena Anda tidak mengetahui jari favorit masing-masing anak, Anda diperbolehkan untuk memilih PASS atau memilih untuk tidak menjawab sebuah pertandingan. Apabila Anda memilih untuk PASS, maka anda akan diberikan hasil pertandingan tersebut. Anda diminta untuk memilih PASS sesedikit mungkin, dengan kata lain Anda diminta untuk menjawab setiap hasil pertandingan sebanyak mungkin.

Format Interaksi

Pada awalnya, program Anda akan menerima label kasus uji. Label kasus uji berisi sebuah string yang dijelaskan sebagai berikut:

Panjang string tersebut adalah banyaknya subsoal ditambah satu.
Digit pertama dari label adalah karakter ke-0, digit kedua dari label adalah karakter ke-1, dan seterusnya.
Karakter ke-0 akan berisi 0 jika kasus uji tersebut merupakan contoh kasus uji, dan berisi '.' jika bukan.
Untuk setiap nilai i di antara 1 hingga banyaknya subsoal, berlaku:
jika kasus uji tersebut memenuhi batasan subsoal ke-i, maka karakter ke-i berisi i, atau
jika kasus uji tersebut tidak memenuhi batasan subsoal ke-i, maka karakter ke-i berisi karakter '.'
Sebagai contoh apabila label sebuah kasus uji sebuah soal adalah 0..345, maka:

Soal tersebut memiliki 5 buah subsoal,
Kasus uji tersebut merupakan contoh kasus uji, dan
Kasus uji tesebut memenuhi batasan subsoal ke-3, ke-4, dan ke-5.
Kemudian, program Anda akan menerima input sebuah bilangan N yaitu banyaknya anak yang bermain suten. Kemudian, sebanyak (N × (N - 1)) / 2 kali program Anda akan menerima input 2 buah bilangan X dan Y yang menandakan pertandingan suten antara anak ke-X dan anak ke-Y. Anda diminta untuk mencari tahu hasil pertandingan suten tersebut satu per satu.

Keluaran yang dapat Anda keluarkan adalah:

Apabila pertandingan suten dimenangkan oleh anak ke-Z, program Anda diminta untuk mengeluarkan output Z MENANG.
Apabila pertandingan suten berlangsung seri, program Anda diminta untuk mengeluarkan output SERI.
Apabila Anda memilih untuk PASS atau tidak menjawab, program Anda diminta untuk mengeluarkan output PASS. Apabila memilih PASS, maka program Anda akan menerima hasil pertandingan suten tersebut dalam bentuk Z MENANG ataupun SERI.
Contoh Interaksi

Keluaran Program Peserta Umpan Balik Grader
  0....567
  4
  1 2
SERI  
  1 3
3 MENANG  
  1 4
1 MENANG  
  2 3
PASS  
  3 MENANG
  2 4
PASS  
  2 MENANG
  3 4
4 MENANG  
  (interaksi selesai)

Subsoal

Pada semua subsoal, berlaku:

  • 3 ? N ? 100
  • Dimisalkan P adalah banyaknya PASS paling banyak yang boleh dilakukan peserta.

Subsoal 1 (6 poin)

  • N = 5
  • P = 6
  • Untuk setiap pertandingan, berlaku X < Y.
  • Input pertandingan akan diurutkan dengan aturan berikut:
    • Pertandingan diurut mula-mula dari nilai X terkecil.
    • Apabila 2 buah pertandingan memiliki nilai X yang sama, maka diurut mula-mula dari nilai Y terkecil.

Subsoal 2 (12 poin)

  • N = 8
  • P = 7

Khusus untuk subsoal 1 dan subsoal 2:

  • Hanya terdapat sebuah kasus uji (satu subsoal dinyatakan oleh satu kasus uji), yang dapat dimainkan di sini.
  • Anda boleh memainkan permainan ini berulang kali tanpa mendapatkan penalti.
  • Jika Anda sudah memenangkan permainan untuk subsoal tertentu, Anda dapat memilih pilihan pada permainan untuk mengeluarkan source code yang dapat langsung Anda kirimkan ke grader dan menjawab dengan benar pada subsoal yang telah Anda menangkan.
  • Anda tidak diwajibkan memainkan permainan ini untuk mengerjakan kedua subsoal ini. Anda diperbolehkan untuk menulis kode Anda sendiri untuk mengerjakan kedua subsoal ini.

Subsoal 3 (8 poin)

  • N = 3
  • P = 2

Subsoal 4 (13 poin)

  • P = (N × (N - 1)) / 2 - N + 2

Subsoal 5 (14 poin)

  • P = N - 1
  • Untuk setiap pertandingan, berlaku X < Y
  • Input pertandingan akan diurutkan dengan aturan berikut:
    • Pertandingan diurut mula-mula dari nilai X terkecil.
    • Apabila 2 buah pertandingan memiliki nilai X yang sama, maka diurut mula-mula dari nilai Y terkecil.

Subsoal 6 (19 poin)

  • P = N - 1
  • Untuk N - 1 pertandingan pertama, berlaku X < Y.
  • Untuk N - 1 pertandingan pertama, pada pertandingan ke-i nilai Y = i + 1.

Subsoal 7 (28 poin)

  • P = N - 1