informatika/komputer 1. empek-empek 2. gunting ...halaman 2 o jika kasus uji tersebut tidak memenuhi...

OLIMPIADESAINSNASIONAL2016

DESKRIPSISOAL

Hari0(SesiLatihan)

1. Empek-empek2. GuntingKertas3. MatriksBiner

Waktu:2Jam

INFORMATIKA/KOMPUTER

HakCiptaDilindungiUndang-undang

Halaman1

Hari 0 / Soal 1 - Empek-empek BatasMemori :64MBBatasWaktu :1s

Deskripsi

SetelahPakDengklekberkonsultasidengankerabatnyayangmerupakanorangasliPalembang,PakDengklekmengetahuibahwauntukmembuatempek-empekdiperlukan3jenisbarang:ikan,tepungsagu,dangulaaren.

TerdapatsebuahpasardenganNtokoyangberadadalamsatubarisandarikirikekanan.Toko-tokotersebutada3macam,yaituyangdinomoridengan1menjualikan,nomor2menjualtepungsagu,dannomor3menjualgulaaren.

Pak Dengklek ingin berjalan dari kiri ke kanan pasar tersebut. Tetapi, Pak Dengklek tetap inginmemenuhi kebutuhannya sesuai urutan awalnya, yaitu ikan, tepung sagu, lalu gula aren.Dengankata lain, pada awalnya Pak Dengklek akanmencari sebuah toko yangmenjual ikan, setelah itutepungsagu,danterakhirgulaaren.

Terdapat sangatbanyakkemungkinanpenentuancarapemilihan toko sesuai alur yangdiinginkanolehPakDengklek,sehinggaAndapundibuatpenasaran:Adaberapabanyakcaramenentukantokoyangmenjualikan,kemudiantepungsagu,danterakhirgulaaren?

FormatMasukan

Barispertamaakanberisilabelkasusuji.Labelkasusujiadalahsebuahstringyangdijelaskansebagaiberikut:

• Panjangstringtersebutadalahbanyaknyasubsoalditambahsatu.

• Karakterke-0(indeksdimulaidari0)akanberisi0jikakasusujitersebutmerupakancontohkasusuji,atauberisi'.'(titik)jikabukan.

• Untuksetiapnilaiidiantara1hinggabanyaknyasubsoal,berlaku:

o jikakasusujitersebutmemenuhibatasansubsoalke-i,makakarakterke-iberisii,atau

Halaman2

o jikakasusujitersebuttidakmemenuhibatasansubsoalke-i,makakarakterke-iberisikarakter'.'(titik).

Sebagaicontohapabilalabelsebuahkasusujisebuahsoaladalah0..345,maka:

• Soaltersebutmemiliki5buahsubsoal,

• Kasusujitersebutmerupakancontohkasusuji,dan

• Kasusujitesebutmemenuhibatasansubsoalke-3,ke-4,danke-5.

BariskeduaberisisebuahbilanganbulatNyangmenyatakanbanyaknyatoko.BarisberikutnyasebuahstringberisiNdigityangmerepresentasikantokodarikirikekanan.Digittersebutberkisardari1sampai3.

FormatKeluaran

KeluarkansebuahbilanganbulatyangmenyatakanbanyaknyakemungkinankombinasiurutantokoyangdikunjungiolehPakDengklek.

ContohMasukan0..34571121332

ContohKeluaran

4

Penjelasan

Ada4kombinasiurutantokoyangdikunjungiolehPakDengklek,yakni:

• Tokoke-1,tokoke-3,lalutokoke-5.




Halaman3

SubsoalSubsoal1(7poin)Hanyaterdiridarikasusujiberikut:.1.34571213233

Subsoal2(13poin)Hanyaterdiridarikasusujiberikut:..2345101211312323

Subsoal3(20poin)

• 1≤N≤100Subsoal4(25poin)

• 1≤N≤1.000Subsoal5(35poin)

• 1≤N≤100.000

Halaman4

Hari0/Soal2-GuntingKertasBatasMemori :16MBBatasWaktu :100ms

Deskripsi

PakDengklekadalahorangyangsangatsukaberpikir.Suatuhari,PakDengklekterpikirakansebuahpermainansebagaiberikut:

• Permainantersebutdimainkanoleh2orang.

• Kepadapemainpertama,akandiberikansebuahkertasberukuranNxM(NdanMbilanganbulat). Pada setiap giliran, pemain yang bermain pada giliran tersebut harus memotongkertastersebutmenjadiduadanmembuangsalahsatupotongan.

• Potongankertasyangtidakdibuangharusberukuranpxqdenganpdanqyangdipilihharusmerupakanbilanganbulatpositif,dimanasalahsatukondisiberikutharusterpenuhi:

o p=Ndanq<M,atau

o p<Ndanq=M.

• Potonganyangtidakdibuangkemudiandiberikankepadapemainyanglain.Pemaintersebutakanbermainpadagiliranberikutnya.

Pemainyangkalahadalahpemainyangtidakdapatmemotongkertasyangmemenuhikriteriapxqdiatas,ataupemainyangmenerimapotongankertasberukuran1x1(ukuranterkecilkertasyangmungkin). Dengan kata lain, pemenang dari permainan ini adalah pemain yang dapatmemotongkertasmenjadiukuran1x1.

Saat ini, Anda ditantang oleh Pak Dengklek untuk memainkan permainan ini. Dapatkah AndamengalahkanPakDengklekdalampermainanini?

FormatInteraksi

Padasoaliniandaakanberinteraksidenganjuri.

Baris pertama akan berisi label kasus uji. Label kasus uji adalah sebuah string yang dijelaskansebagaiberikut:

Halaman5




o jika kasus uji tersebutmemenuhi batasan subsoal ke-i,maka karakter ke-i berisi i,atau

o jikakasusujitersebuttidakmemenuhibatasansubsoalke-i,makakarakterke-iberisikarakter'.'(titik).





SelanjutnyaprogramakanmenerimaduabuahbilanganNdanM(sesuaideskripsidiatas).

Lalu, secara berganti-gantian, program Anda dan program juri akan mengeluarkan dua buahbilanganpdanq,yangberartimemberikankertasberukuranpxqke lawan.Permainanberakhirapabila program Anda mengeluarkan nilai pdan q yang tidak valid atau salah satu dariprogramAndadanprogramjuriberhasilmemotongkertasmenjadiukuran1x1.

ContohInteraksi1KeluaranProgramAnda KeluaranProgramGrader

0..34554

53

33

32

31

11

(interaksiselesai)

Andamenangdanandamendapatkanpoinuntukkasusujiini.

Halaman6

ContohInteraksi2KeluaranProgramAnda KeluaranProgramGrader

0..34554

53

33

34

(interaksiselesai)

Programdiberhentikankarenanilaipdanqtidakvalid.Andatidakmendapatkanpoinuntuksoalini.

Andamendapatnilaiapabila:

• Andaberhasilmemotongkertasmenjadiukuran1x1,dan

• Andatidakmengeluarkanukuranyangtidakvalid

Andatidakmendapatnilaiapabila:

• Juriberhasilmemotongkertasmenjadiukuran1x1,atau

• Andamengeluarkanukuranyangtidakvalid

Subsoal

• MasukanNdanMdiberikansedemikianrupasehinggadijaminAndadapatmemenangkanpermainan apabila anda bermain secara optimal meskipun Pak Dengklek bermain secaraoptimal.

• Padasubsoal1,subsoal2,sertacontohinteraksi,PakDengklektidakselalubermainoptimal.Namun pada subsoal lainnya (subsoal 3 hingga 5), Pak Dengklek akan selalu bermainoptimal.

Subsoal1(15poin)

• N=3• M=8• Andadapatmemainkanpermainandisini.

Halaman7

Subsoal2(15poin)• N=6• M=8• Andadapatmemainkanpermainandisini.

Subsoal3(20poin)

• 1≤N,M≤5Subsoal4(20poin)

• 1≤N,M≤100Subsoal5(30poin)

• 1≤N,M≤10.000

Halaman8

Hari0/Soal3-MatriksBinerBatasMemori :0MBBatasWaktu :0s

Deskripsi

Matriksbinermerupakansebuahmatriksyangsetiapelemennyamerupakanangka1atau0.Karenamatriks inisangatsederhana,makaPakDengklekmemutuskanuntukmenggunakanmatriksbinerberukuran N * M sebagai password untuk membuka dokumen yang sangat rahasia, "KonspirasiMenaklukkanDunia".

Namun, karena sudah lama tidak membuka dokumen tersebut, Pak Dengklek lupa passwordrahasianya!Setelahberhari-hariberusahamengingatpasswordnyakembali,yangdapatdiingatolehPakDengklekadalahhasilXORdarisetiapbarisdankolomdarimatrikstersebut.Serta,tepat50%darielemenmatrikstersebutmerupakanangka1dansisanyamerupakanangka0.Dengankatalain,banyakangka1danbanyakangka0padamatrikstersebutsama.

HasilXORdarisemuaelemenpadabariske-iadalahRi.

HasilXORdarisemuaelemenpadakolomke-jadalahCj.

BantulahPakDengklekmenemukanpasswordrahasianya!

InformasiTipeSoal

Tipe soal seperti ini biasa disebut "output-only". Pada soal ini Anda diminta untuk langsungmenuliskankeluaranprogramkedalamsebuahberkaskeluaranperkasusuji.Setelahitu,kompressemuaberkaskeluarandalamsebuahberkas.zip.

Masukanuntuksoalinidapatdiunduhdisini.

Di dalam berkas zip tersebut ada 1 + 5 masukan untuk diselesaikan: osn-2016-matriks-biner_sample_1.in, osn-2016-matriks-biner_1_1.in, osn-2016-matriks-biner_2_1.in, ..., osn-2016-matriks-biner_5_1.in.Masukansampletidakdinilai.Untuksetiapberkasmasukanyangdiselesaikan(Anda tidak harus menyelesaikan semua masukan), buatlah berkas keluaran dengan nama osn-2016-matriks-biner_X_1.out, di mana X adalah nomor masukan (atau osn-2016-matriks-biner_sample_X.out untuk sample) sesuai format keluaran. Setelah itu, kompres semua berkaskeluarandalamsebuahberkas.zip.

Halaman9

FormatMasukan

Baris pertama akan berisi label kasus uji. Label kasus uji adalah sebuah string yang dijelaskansebagaiberikut:





o jika kasus uji tersebut tidakmemenuhi batasan subsoal ke-i,maka karakter ke-i berisikarakter'.'(titik).





Barisselanjutnyaberisi2buahbilanganbulatNdanM.

BarisselanjutnyaberisiNbuahbilanganbulat,bilanganke-ipadabaristersebutadalahRi.

BarisselanjutnyaberisiMbuahbilanganbulat,bilanganke-ipadabaristersebutadalahCi.

FormatKeluaran

Keluarkan N baris yang masing-masing berisi M buah bilangan 0 atau 1 yang masing-masingdipisahkanolehsebuahspasi,yangmerupakanmatriksrahasiaPakDengklek.Untuklebihjelasnya,lihatbagiancontohkeluaran.

ContohMasukan0.....36010011100

Halaman10

ContohKeluaran110110011010110000

Subsoal

Apabilamatrix yang Anda berikanmemenuhi kriteria Pak Dengklek (banyak angka 1 dan banyakangka 0 pada matriks tersebut sama), nilai anda akan dihitung menggunakan formula berikut:(X/(N+M))2*P

X adalah banyaknya baris dan kolom padamatriks Anda yang hasil XOR dari elemen-elemennyasesuaidenganingatanPakDengklek.PerhatikanbahwaAndatidakharusmemenuhisetiapRidanCi.PmerupakannilaimaksimalyangmungkinAndadapatkanpadakasusujitersebut.Subsoal1(15poin)

• Namaberkas:osn-2016-matriks-biner_1_1.in• N=2• M=3

Subsoal2(15poin)


Subsoal3(20poin)


Subsoal4(25poin)


Subsoal5(25poin)



DESKRIPSISOAL

Hari1

1. Pasar16Ilir2. MenjinakkanBom3. PosWisataSungai

Waktu:5Jam



1

Hari 1 / Soal 1 - Pasar 16 Ilir Timelimit:1500ms

Memorylimit:64MB

Deskripsi

DalamperjalanannyamenujuSungaiMusi,PakDengkleksukamelaluiPasar16Iliryangdikenalsebagaipasaryangmenjualberbagaijenispengananlezat.Setiaptokomenjualpengananyangberbeda,daniasudahmemilikidaftarhargalengkapdarisemuanya.Beruntungnya,beberapapemilik toko adalah kerabat Pak Dengklek yang apabila didatangi selain akan memberikanpenganannyasecaragratis,jugaakanmemberinyasejumlahtertentuuang.

Toko-toko di Pasar 16 Ilir diatur secara geometrismembentuk grid dari N XM persegi, satupersegipertoko,dandinomorisebagai(b,k)denganbadalahnomorbarisdankadalahnomorkolomdalamgrid.Jadi,tokodipojokutara-baratdinomori(1,1)dantokodipojokselatantimurdinomori(N,M).Gambar1mengilustrasikanadanya6tokodalamgrid2x3.

Jikapemilik toko ituadalahkerabatnya:PakDengklekakanmendapatkansatupenganandanmenerimasejumlahuang.Jikapemiliktokoitubukankerabatnya:PakDengklekakanmembelisatu penganan danmembayar harganya.Dalam perjalanannya di dalam Pasar, Pak Dengklekselalu tiba pertama kali di toko (1,1) dan berakhir di toko (N,M) karena SungaiMusi beradatepat setelah toko (N,M) itu. Dari suatu toko ia akan berjalan ke toko berikutnya denganmengikutiarah:utara,selatan,timur,ataubarat.Disetiaptokoyangdilaluinya,satudariduakemungkinankasusakanterjadi:

BilanganyangtertulisdalamsetiapkotakdiGambar1menyatakanbesarnyauangyangharusdikeluarkan jika Pak Dengklekmelalui toko itu. Bilangan positifmenyatakan harga penganan

2

disitu yang harus dibayar Pak Dengklek bilangan negatif menyatakan uang yang diberikankerabatpemiliktokoitukepadaPakDengklekselainpenganangratis.

SetiappengananituenaksehinggaPakDengklekinginselalumendapatkanpenganan-penganandisetiaptokoyangdilaluinya.Tetapi,iatelahmembatasipengeluaranuntukmendapatkannyaantara P sampai dengan Q rupiah. Selain itu, karena keterbatasan waktunya, ia tidak akanmengunjungitokoyangsamalebihdarisekali.

TugasAndaadalahmembantuPakDengklekmenghitungberapabanyakcarauntukpergidari(1,1)ke(N,M)sambilmenghabiskansejumlahuang,minimalPrupiahdanmaksimalQrupiah.Total uang yang dihabiskan adalah banyaknya uang yang dikeluarkan untuk membelimakanandikurangibanyaknyauangyangditerimasaatmengunjungikerabatnya.Karenabisasajamemperolehuangdalamjumlahyanglumayanbanyak,totalpengeluaranbisasajakurangdari0.

FormatMasukan

Baris pertama berisi dua buah bilangan bulat N dan M. N baris berikutnya berisi M buahbilanganbulatyangmenyatakanpengeluaranPakDengklekdiposisitersebut.JikaToko(i,j)≤0,Pak Dengklek mengunjungi tempat kerabatnya sehingga ia tidak perlu membayar makananbahkanmemperolehuangsumbangandarimereka.

Baris berikutnyaberisi sebuahbilanganbulatK, banyaknyapertanyaanPakDengklek. Kbarisselanjutnya masing-masing berisi dua buah bilangan bulat P dan Q, yaitu kisaran total(minimumdanmaksimum,inklusif)uangyangakandihabiskanPakDengklek.

FormatKeluaran

Keluaran terdiri dari K baris yang masing-masing berisi tepat sebuah bilangan bulat yangmerupakanjawabandaripertanyaanPakDengklekyangke-i.

ContohMasukan

0.....6789

23

123

456

2

0100

1212

3

ContohKeluaran

4

1

Penjelasan

Gambar1mengilustrasikancontohmasukandiatas.Terdapat4jalurberbedayangdapatdilaluiuntukpergidari(1,1)ke(2,3)yaitu:

• 1-4-5-6denganjumlah16



• 1-4-5-2-3-6denganjumlah21

Saatmenjawabpertanyaanpertama,karenakeempatjalurtersebutmempunyaijumlahdalamrentang0sampaidengan100,makakeluarkan4.

Saatmenjawabpertanyaankedua,hanyaterdapatsatujaluryangmempunyaijumlahtepat12,makakeluarkan1.

Subsoal

Untuksemuasubsoalberlaku:

• P≤Q

• PdanQdapatditampungdalam64-bitsignedinteger(longlonguntukC/C++danint64untukpascal).

Subsoal 1 (7 Poin)

Hanyaterdiriataskasusujiberikutini:

.1......89

52

1-5

4

23

101

-12

2-1

3

020

815

1320

Subsoal 2 (8 Poin)


..2.....89

33

10-510

-231

1018

5

020

110

0100

3235

1621

Subsoal 3 (6 Poin)

• N=1

• M≤36

• -10≤Toko(i,j)≤10

• K=1

5

Subsoal 4 (10 Poin)

• 1≤N*M≤10

• Toko(i,j)berbentuk2xdengan0≤x≤10

• Toko(i,j)unik

• 1≤K≤1.000

Subsoal 5 (10 Poin)

• 1≤N*M≤10

• Toko(i,j)berbentuk2xdengan0≤x≤10

• Toko(i,j)unik

• 1≤K≤100.000

Subsoal 6 (11 Poin)

• 1≤N*M≤10

• 0≤Toko(i,j)≤1.000

• 0≤sum(Toko(i,j))≤1.000

• 1≤K≤1.000

Subsoal 7 (11 Poin)

• 1≤N*M≤10

• 0≤Toko(i,j)≤1.000

• 0≤sum(Toko(i,j))≤1.000

• 1≤K≤100.000

6

Subsoal 8 (15 Poin)

• 1≤N*M≤20

• 1≤K≤1.000

• -109≤Toko(i,j)≤109

Subsoal 9 (22 Poin)

• 1≤N*M≤36

• 1≤K≤100.000

• -109≤Toko(i,j)≤109

Peringatan

• BagipenggunaC++,disarankanmenggunakanscanf/printfdaripadacin/cout.

8

Hari1/Soal2-MenjinakkanBomTimelimit:100ms

Memorylimit:16MB

Deskripsi

Jembatan Ampera, landmark terkenal kota Palembang, dalam bahaya! Seorang teroris telahmenanamkanbomtepatditengah-tengahjembatanAmpera.Bomitutidakdapatdisingkirkandanbisameledakkapansaja!

BommemilikiNbuahtombolyangbernomorkan1hinggaN.Bomakanmeledaktepatsetelahpenekanan tombol-tombol itu (mana saja) sebanyak T kali, kecuali dijinakkan dengan halberikutini.

Di antara tombol-tombol itu terdapat sebuah tombol, sebut saja X. Bom telah dirancangsehingga setelahXditekan, ia akanberbunyi “BIP” tetapidenganpenundaan sebanyakKkalipenekanan tombolberikutnya.Dengankata lain, jikaXditekanpadapenekanan tombol ke-i,suara“BIP”-nyabaruakanterdengarpadapenekanantombolke-(i+K).HargaKadalahantara0sampaidenganN-1.NilaiKinihanyadiketahuiolehterorisyangmemasangbom.

Apabila bom telah berbunyi "BIP" sebanyak N kali (tidak harus berturut-turut), bom akandijinakkan(di-nonaktifkan)asalkanbanyaknyapenekanantotalbelummelebihiTkali.

Diketahui juga terdapat dua jenis bom semacam ini: type-0 dan type-1. Bom type-0 adalahpersis seperti yang dijelaskan di atas. Bom type-1 memiliki tambahan perilaku yaitu akanmeledakjikasetelahsuatu“BIP”terdengar,bunyi“BIP”berikutnyabelumjugaterdengardalamNpenekananberikutnya.

PakDengklekadalahsalahsatupenjinakbomyanghandal,namunkasusinitidaksemudahyangdikiranya. Tugas anda adalah membantunya menemukan langkah-langkah penekanan yangbenaruntukmenjinakkanbomini.

InformasiTipeSoal

Tipe soal seperti ini biasa disebut "interaktif". Pada soal ini Anda akan berinteraksi denganprogram pengujimelalui standard input dan standard output. Perhatikan format interaksi dibawahinidengansaksama.

FormatInteraksi

Barispertamaakanberisi labelkasusuji. Labelkasusujiadalahsebuahstringyangdijelaskansebagaiberikut:

9


• Karakter ke-0 (indeks dimulai dari 0) akan berisi 0 jika kasus uji tersebut merupakan contohkasusuji,atauberisi'.'(titik)jikabukan.



o jika kasusuji tersebut tidakmemenuhi batasan subsoal ke-i,maka karakter ke-i berisikarakter'.'(titik).





Selanjutnya,programAndaakanmenerimainputbilngan-bilanganN,T,danR.BilanganNdanTadalahsepertidijelaskandiatas.BilanganRberharga0jikabommerupakanbomtype-0,atau1jikabommerupakanbomtype-1.

ProgramAndalaludimintauntukmengeluarkansebuahangkaantara1sampaidenganN,yangberarti anda menekan tombol dengan nomor tersebut. Program juri akan menjawab “BIP”apabilasetelahpenekanantomboltersebutbommengeluarkanbunyi“BIP”atauprogramjuriakanmenjawab“HENING”apabilatidak.Selamabombelumberhasildijinakkanataupunbelummeledak,Andatetapdimintauntukkembalimenekantombol.

ContohInteraksi

OutputProgram

Juri

OutputProgramPeserta

Penjelasan

0........

4200

3 MeskipuntombolX=3ditekan...

HENING ...bomtidaklangsungmengeluarkanbunyiBIP,...

2

HENING

10

3

BIP ...melainkanberbunyipadapenekananke-K=2berikutnya.

4

HENING

1 PerhatikanbahwatidakharusmenekantombolX,...

BIP ...bunyiBIPtetapterdengarakibatpenekakanke-Ksebelumnya.

4

HENING

3

HENING

1

HENING

1

BIP

1

HENING

1

HENING

3 MeskipunsudahN=4kalimenekantombolX,...

HENING ...tetapsajabombelumdijinakkan.

3

HENING HeningselamaNkaliberturut-turut,...

3 ...BOMAKANMELEDAKjikabommerupakanbomtype-1.

11

BIP BomakhirnyadijinakkansetelahbunyiBIPyangke-N.

(interaksiselesai)

ProgramAndaberhasilapabila(semuanyaharusdipenuhi):

• Bomdapatdijinakkankarenatelahmengeluarkanbunyi“BIP”sebanyakNkali.

• BanyaknyapenekanantombolyangdilakukantidaklebihdariTkali.

• Untuk bom yang merupakan bom type-1, setelah terdengar bunyi “BIP”, pada maksimal Npenekanantombolkemudianbunyi“BIP”berikutnyaharusterdengarlagi.

• Programberhentisebelumbataswaktu.

ProgramAndatidakberhasilapabila(cukupsalahsatuterpenuhi):

• ProgramAndatidakmengeluarkansebuahbilanganbulatataubilanganbulatyangdikeluarkantidakberadadiantara1sampaidenganN.

• ProgramAndamelakukanpenekanantombollebihdariTkali.

• Bombelumberhasildijinakkankarenabelummengeluarkanbunyi“BIP”sebanyakNkali.

• Untuk bom yang merupakan bom type-1, ada bunyi “BIP” yang diikuti dengan “HENING”sebanyakNkali.Dengankatalain,padaNpenekanantombolsetelahbunyi“BIP”tersebut,tidakterdengarbunyi“BIP”lagi.

• Program tidak berhenti sebelum batas waktu, termasuk akibat menunggu masukan dariprogramjuripadahalprogramjurisudahberhenti.

Subsoal

Pada setiap subsoal, berlaku

• 1≤X≤N

• 0≤K≤N-1

Subsoal 1 (8 poin)

• N=5

• T=30

12

• R=0

• Permainanbisadimainkandisini.

Subsoal 2 (9 poin)

• N=6

• T=42

• R=1

• Permainanbisadimainkandisini.

Subsoal 3 (8 poin)

• 7≤N≤36

• T=37N

• 0≤R≤1

Subsoal 4 (10 poin)

• 7≤N≤36

• T=21N

• 0≤R≤1

Subsoal 5 (11 poin)

• 7≤N≤36

• T=14N

• R=0

Subsoal 6 (13 poin)

• 7≤N≤36

13

• T=14N

• R=1

Subsoal 7 (16 poin)

• 7≤N≤36

• T=5N

• R=0

Subsoal 8 (25 poin)

• 7≤N≤36

• T=5N

• R=1

14

Hari1/Soal3-PosWisataSungaiTimelimit:1s

Memorylimit:64MB

Deskripsi

PakDengklekkinimenjadiMenteriPemeliharaandanPengembanganWisataSungaidiKerajaanBitaniaRaya.Dikerajaanini,semuaurusanpengendalianakandijalankanmelaluirangkaianbit-bit(bitadalahbinarydigityangbernilai0dan1)sertadenganoperasi-operasibitnya.

SungaiterpanjangdiKerajaanBitaniaRayamemilikiMbuahposwisatadisepanjangtepinya,dinomori1sampaidenganM.Pos-poswisataitudibukatidaksetiaphari.Melainkan,suatuposwisatayangdisuatuharidibuka,bisasajadikeesokanharinyaditutupatautetapdibuka,begitupun sebaliknya. Mekanisme pengaturan pos wisata yang dibuka dan ditutup di suatu haridilakukanmenggunakanrangkaianbitdanoperasi-operasinya.PakDengklekmemilikiproseduruntukmengaturnyayangsudahterimplementasikansebagaiberikut:

1. Seandainya W merupakan sebuah bilangan biner dengan M digit yangmerepresentasikandibukaatautidaknyapos-poswisatapadahariini.Untuk1≤i≤M,digitke-idariWakanbernilai1 jikaposwisatabernomor idibukapadahari tersebut,danakanbernilai0jikaposwisatatersebutditutup.

2. BuatsebuahbilanganbineracakMdigit,namakanbilanganbinerinisebagaiX.

3. HitungW’←WXORX(catatan:XORadalahoperasiexclusive-orbitdemibitantaraWdan X. Dalam bahasa C/C++, operasi XOR direpresentasikan sebagai operator^ dandalam bahasa Pascal sebagai xor. Lebih lanjut tentang operasi XOR, lihat catatan dibawah)

4. W’merepresentasikandibukaatautidaknyapos-poswisatapadahariselanjutnya

5. Dihariberikutnya,proseduriniakandiulangidenganmenggantikanWdenganW’.

15

Gambar2menunjukkanadanya3poswisatayangdiwakiliolehbilanganbiner3-bitW=110.Pos1 dan pos 2 dalam status buka sehingga bit-bit terkait berharga 1. Sementara, pos 3 dalamstatustutupsehinggabitterkaitberharga0.

PakDengkleksudahmemilikisederetanNbuahbilanganbinerX1,X2,X3,..,XNdenganXiuntukdigunakanharike-iberikutnyadarisekarang.Iamenjamin,padaharike-Ndarisekarang,akanadatepatKbuahposwisatayangdibuka.

AndapenasaranadaberapakemungkinanderetNbuahbilanganbinerberbedayangdimilikiPakDengklekjikakondisipos-poswisatahariinidiketahuisebagaiWsesuaiyangdideskripsikandibutir1prosedurdiatas.Catatan,duabuahderetNbilanganA1,A2,…,ANdanB1,B2,…,BNdikatakanberbeda jikaadaminimal satuharga juntuk1≤ j ≤N,dimanaAj ≠Bj. Saatuntuksituasi pada Gambar 2, W = 110, akan diberikan deretan berisi satu bilangan biner dandiharapkan tepat ada 1 pos saja yang bukamaka banyaknya kemungkinan deret ada 3 yaitu{010},{100},dan{111}.

Jawaban Anda, misalnya Z, bisa merupakan bilangan yang sangat besar. Untukmenyederhanakan,tuliskansajahasildari(Zmod1.000.000.007)atau(Zmod(109+7))sebagaikeluaranAnda.PenjelasanmengenaimoddapatdilihatpadabagianCatatan.

Format Masukan

Barispertamaakanberisi labelkasusuji. Labelkasusujiadalahsebuahstringyangdijelaskansebagaiberikut:


• Karakter ke-0 (indeks dimulai dari 0) akan berisi 0 jika kasus uji tersebut merupakan contohkasusuji,atauberisi'.'(titik)jikabukan.



o jika kasusuji tersebut tidakmemenuhi batasan subsoal ke-i,maka karakter ke-i berisikarakter'.'(titik).





Bariskeduaakanterdiridari3buahbilanganN,M,danK.

BarisketigaakanberisisebuahbilanganbinerWdenganbanyaknyabitM.

16

Format Keluaran

Sebuah baris berisi banyaknya kemungkinan himpunan N buah bilangan biner berbeda yangdimilikiPakDengklek.Keluarkanjawabantersebutdalammodulo1.000.000.007(atau109+7).

Contoh Masukan 1

0..3456789

131

110

Contoh Keluaran 1

3

Contoh Masukan 2

0..3456789

233

110

Contoh Keluaran 2

8

Penjelasan Untukcontohmasukan1,ketigahimpunanbilangantersebutadalah{010},{100},dan{111}.

Untukcontohmasukan2,kedelapanhimpunanbilangantersebutadalah{000,001},{001,000},{010,011},{011,010},{100,101},{101,100},{110,111},dan{111,110}.

17

Subsoal

Padasemuasubsoalberlaku:

• 0≤K≤M

Subsoal 1 (6 poin)

Hanyaterdiridarikasusujiberikutini:

.1.3456789

221

10

Subsoal 2 (8 poin)

Hanyaterdiridarikasusujiberikutini:

..2.456789

332

101

Subsoal 3 (8 poin)

• 1≤N≤2

• 1≤M≤5

Subsoal 4 (9 poin)

• 1≤N≤10

• 1≤M≤10

Subsoal 5 (13 poin)

• 1≤N≤50

18

• 1≤M≤50

Subsoal 6 (10 poin)

• 1≤N≤100

• 1≤M≤100

Subsoal 7 (15 poin)

• 1≤N≤1.000

• 1≤M≤1.000

Subsoal 8 (14 poin)

• 1≤N≤100.000

• 1≤M≤100.000

• 0≤K≤3

Subsoal 9 (17 poin)

• 1≤N≤1.000.000.000

• 1≤M≤1.000.000

• 0≤K≤3

Catatan

HasildarioperasiC←AXORBadalahdigitke-idariCakanbernilai1jikadigitke-idariAdandigit ke-i dari B berbeda, dan akanbernilai 0 jika digit ke-i dari A dandigit ke-i dari B sama.SebagaicontohjikaAadalah111000danBadalah110110,makanilaiCadalah001110.

Hasil dari operasi Amodulo Bmenghasilkan sisa pembagianA olehB. Sebagai contoh jikaAadalah15danBadalah4,makaAmodBadalah3.


DESKRIPSISOAL

Hari2

1. RobotPempek2. BelanjaSuvenir3. WisataPalembang

Waktu:5Jam



halaman 1

Hari2/Soal1–RobotPempek

BatasMemori 128MBBatasWaktu 0.5detik

DeskripsiSoal

Pak Dengklek sedang berkunjung ke Kota Palembang. Kota ini terkenal dengan “pempek”, penganankhasterbuatdariikanyangdiambildarisungaisetempat.Iainginmencobamembuatnyasendiri,jadiiaberusaha mendapatkan ikan-ikan dari sungai. Teman dekatnya menyarankan Pak Dengklek untukmendapatkanbelidasebagaibahanutamapempek.

Pak Dengklek membawa robot bernama Rempek, ia ingin menguji kemampuan Rempek untukmenangkap ikan-ikan belida. Pak Dengklekmemiliki peta berisikan lokasi-lokasi terbaik penangkapanikanbelida.Dalampeta terdapat K posisi terbaik penangkapan ikanbelidadimana ikan-ikanbiasanyaberkumpul.TerdapatKposisidalammapdanposisi-posisiiniakandigunakanolehRempek.

Peta berukuran N x M dengan posisi paling kiri atas adalah (1, 1) dan kanan bawah adalah (N, M).Rempek hanya dapat berjalan satu langkah ke empat arah, yaitu dari posisi (r, c), robot dalam satulangkahdapatberpindahkesalahkesatudari(r-1,c),(r,c+1),(r+1,c),(r,c-1).

Mula-mulaPakDengklekakanmenempatkanRempekdiposisi (x,y),kemudianRempekakanmencarilokasiikanbelidaterdekatdenganposisinyayangjaraknyalebihdari0langkah.Satudariduakasusiniakanterjadi:1. Jikaterdapatlebihdarisatuposisiikandenganjumlahlangkahminimaldariposisirobotyangsama,

makaRempekberhenti.2. JikahanyaterdapatsatuposisiikandenganjumlahlangkahminimaldariposisiRempek:

a. Jikalokasitersebutpernahdikunjungisebelumnya,Rempekakanberhenti.b. Jikatidak,kunjungilokasitersebut,ambilikanbelidasebanyak-banyaknyadisitu,kemudian

ulangipencarianlokasiterdekatberikutnyadenganmengulangiprosedurini.

IkandisetiaplokasisangatlahbanyaksehinggaketikaRempekmengambilikandilokasimanapun,ikan-ikanitutidakakanpernahhabis.

PakDengklekinginmengetahuidimanaRempekposisiterakhirrempekuntuklokasiawal(x,y). Iaakanmenanyakansejumlahskenariopenempatanawaldanuntuksetiapskenarioandamendapatkanposisi-posisiakhirnya.

FormatMasukan

Barispertamaakanberisi label kasusuji. Label kasusuji adalah sebuahstring yangdijelaskan sebagaiberikut:

● Panjangstringtersebutadalahbanyaknyasubsoalditambahsatu.● Karakter ke-0 (indeks dimulai dari 0) akan berisi 0 jika kasus uji tersebut merupakan contoh

kasusuji,atauberisi'.'(titik)jikabukan.● Untuksetiapnilaiidiantara1hinggabanyaknyasubsoal,berlaku:

halaman 2

○ jikakasusujitersebutmemenuhibatasansubsoalke-i,makakarakterke-iberisii,atau○ jika kasusuji tersebut tidakmemenuhi batasan subsoal ke-i,maka karakter ke-i berisi

karakter'.'(titik).

Sebagaicontohapabilalabelsebuahkasusujisebuahsoaladalah0..345,maka:● Soaltersebutmemiliki5buahsubsoal,● Kasusujitersebutmerupakancontohkasusuji,dan● Kasusujitesebutmemenuhibatasansubsoalke-3,ke-4,danke-5.

Bariskeduaberisi4buahbilanganbulatN,M,K,danQ.

Nbarisberikutnyamasing-masingberisitepatMbuahkarakter,‘.’atau‘X’.Karakter‘X’padabariske-ikolom ke-j menyatakan adanya lokasi ikan belida di posisi (i, j). Banyaknya karakter ‘X’ akan samadenganK.

Q baris berikutnyamasing-masing berisi dua buah bilangan bulat x dan y, yangmenyatakan skenariopenempatanposisiawalRempekolehPakDengklek.DijaminbahwaposisiawaliniRempekbukanlokasikeberadaan ikan. Satu barismerupakan posisi awal dari satu skenario. Jadi terdapatQ skenario yangmasing-masingharusdijawab.Diawalsetiapskenariosetiaplokasiikanadalahbelumdikunjungi.

FormatOutput

UntuksetiapskenariopenempatanposisiawalRempek,keluarkanjawabanyangdimintadalam1baris.

Contohmasukan

0...456710 10 6 3X..........X..........X................................X.............................X........X.....6 54 49 5

ContohKeluaran

10 52 29 5

halaman 3

Penjelasan

Petayangdiberikanadalahsebagaiberikut:

Petak berwarna kuning menandakan lokasi ikan belida, sementara petak yang diberi nomor adalahposisiawalRempek,sesuaipadaurutanskenariodalammasukan.

Padaskenariopertama,Rempekberadapada(6,5).Lokasi ikanterdekatadalahpada(7,6),kemudianlokasi ikanterdekatdari(7,6)adalah(9,6).Lokasiberikutnyayangterdekatadalah(10,5).Dariposisitersebut, lokasi ikan terdekatnya adalah (9, 6), tetapi sudah pernah dikunjungi sebelumnya, makaRempekberhentidi(10,5).

Pada skenario kedua, Rempek berada pada (4, 4). Selanjutnya Rempek akan bergerak ke (3, 3),kemudianke(2,2).Saatberadadi(2,2),terdapat2lokasiikanterdekat(yangsamadekatnya)yaitu(1,1)dan(3,3),makaRempekberhentidi(2,2).

Pada skenario ketiga, Rempek berada di (9, 5). Dari sini terdapat dua lokasi terdekat dengan banyaklangkahminimalyangsama,yaitu(10,5)dan(9,6).MakaRempekberhentidi(9,5).

Subsoal

Padasemuasubsoal,berlaku:

● 1≤x≤N ● 1≤y≤M

Subsoal1


halaman 4

.1..45678 10 6 3.X.......X.............................................X..............X...X....X4 41 61 5

Subsoal2

Hanyaterdiriataskasusujiberikutini:..2.4567 20 20 15 10 XX.................. ..................X. .X..X............... .................... ............X....... .................... ....X............... .................... .................... ..................X. .................... .................... ...........X........ .................... .................... ......X............. .................... ...................X ...................X .X...............X.X 16 17 1 15 7 9 6 13 18 6

halaman 5

1 20 4 3 3 1 20 16 17 8

Subsoal3

● 1≤N,M,K≤200● Q=1

Subsoal4

● 1≤N,M,K≤200● 1≤Q≤200

Subsoal5● 1≤N,M,K≤2.000● 1≤Q≤2.000

Subsoal6

● 1≤N,M,K≤2.000● 1≤Q≤300.000

Subsoal7

● 1≤N,M≤2.000● 1≤K,Q≤300.000

halaman 6

Hari2/Soal2:BelanjaSuvenirBatasMemori 128MBBatasWaktu 1detik

DeskripsiSoal

KwikdanKwaksedangberliburdiPalembangdenganmengikutisaturombonganwisata.Hariini,acaraturakanmemberimerekakesempatanuntukmengunjungiN tokosuveniryang tersebardi sepanjangjalanraya.Jarakantaratokocukupjauhsehinggarombonganakandibawamengunjungisatudemisatutoko.Masing-masingtokomenjualsatupodukkhas–tokoke-imenjualsatuprodukunggulanTi.Hanyasaja, Kwik dan Kwak harus mengerjakan PR mereka bersamaan dengan acara ini, sehingga merekamenerapkanstrategiberikutiniagardapatmembelisuvenir(mereka=KwikdanKwak):

● Ketikarombonganmengunjungisebuahtoko,maksimumsatusajadiantaramerekayangbolehmasuk.

● Supayaadil,merekamasing-masingakanmasukketepatMtoko.● Masukkesuatutokoberartijugamembeliprodukunggulanditokoitu.● Merekamasing-kasingakanmemasukitoko-tokodalamsaturentang(deretan),tanpasatutoko

punyangdilewati.● Karenamereka akanmembeli produk unggulan saja, mereka tidakmaumasuk ke toko yang

memilikiprodukunggulanyangsamadenganyangtelahdibeli sebelumnya.PerhatikanbahwajikaKwiksudahpernahmasukketokodenganprodukunggulanx,Kwaktetapdapatmasukketokodenganprodukunggulanx,seandainyaKwakbelumpernahmembeliprodukunggulanxditokolain.

Kwik dan Kwak ingin dapat membeli sebanyak mungkin suvenir. Oleh karena itu, mereka inginmemaksimalkannilaiM.Mengingatturhariiniakandimulaidalambeberapamenit,bantulahKwikdanKwakmenentukantokomanasajayangakanmerekamasuki!

FormatMasukan

Barispertamaakanberisi label kasusuji. Label kasusuji adalah sebuah string yangdijelaskan sebagai

berikut:

● Panjangstringtersebutadalahbanyaknyasubsoalditambahsatu.

● Karakter ke-0 (indeks dimulai dari 0) akan berisi 0 jika kasus uji tersebut merupakan contoh

kasusuji,atauberisi'.'(titik)jikabukan.

● Untuksetiapnilaiidiantara1hinggabanyaknyasubsoal,berlaku:

1 2 1 1 2 3 4 5

1 2 3 4 5 6 7 8

Gambar2.Ilustrasiada8tokodanmasing-masingproduknya(dituliskandidalamkotak)

halaman 7

○ jikakasusujitersebutmemenuhibatasansubsoalke-i,makakarakterke-iberisii,atau

○ jika kasusuji tersebut tidakmemenuhi batasan subsoal ke-i,maka karakter ke-i berisi

karakter'.'(titik).


● Soaltersebutmemiliki5buahsubsoal,

● Kasusujitersebutmerupakancontohkasusuji,dan

● Kasusujitesebutmemenuhibatasansubsoalke-3,ke-4,danke-5.

BariskeduaberisisebuahbilanganbulatN,banyaknyatoko.BarisketigaakanberisiNbuahbilanganTi,produkunggulantokoke-i.

FormatKeluaran

Keluarkan4buahbilanganbulata,b,c,dand,yangmenyatakanrentang-rentangtoko-tokoyangKwikdanKwakakanmasuki.TokoyangKwikmasukiadalahtokopadarentang[a,b],sedangkanKwakakanmemasuki tokopada rentang [c,d]. Jika ada lebihdari 1 keluaran yangmungkin, keluarkan salah satuyangmanasaja.

ContohMasukan1

0..3456771 2 3 4 5 6 7

ContohKeluaran1

1 3 4 6

ContohMasukan2

0..3456781 2 1 1 2 3 4 5

ContohKeluaran21 2 7 8

halaman 8

ContohMasukan3

0..34567102 1 1 1 1 2 3 1 2 3

ContohKeluaran3

5 7 8 10

Penjelasan

Untukcontohmasukan1,Kwikmasukketokopertamasampaiketiga,dimanaiamasukketokodenganprodukunggulan[1,2,3].Sementaraitu,Kwakmasukketokokeempatsampaikeenam,dimanaiamasukketokodenganprodukunggulan[4,5,6].

Untukcontohmasukan2(Gambar2mengilustrasikannya),Kwikmasukketokopertamasampaikedua,dimana iamasukke tokodenganprodukunggulan [1,2]. Sementara itu,Kwakmasukke tokoketujuhsampaikedelapan,dimanaiamasukketokodenganprodukunggulan[4,5].Kwiktidakdapatmasukketokoketiga,karenaiaakanmemasukitokodenganprodukunggulanyangsudahpernahialihat.

Untukcontohmasukan3,Kwikmasukketokokelimasampaiketujuh,dimanaiamasukketokodenganprodukunggulan [1,2,3]. Sementara itu,Kwakmasukke tokokedelapan sampai kesepuluh,dimana iamasuk ke toko dengan produk unggulan [1,2,3]. Perhatikan bahwa Kwik dan Kwak boleh membeliprodukunggulanyangsama.

Subsoal

Padasemuasubsoal,berlaku:

● 2≤N≤2.000.000● 1≤Ti≤N

Subsoal1


.1..4567181 6 3 8 10 8 6 4 9 9 1 10 7 7 6 7 2 8

Subsoal2


halaman 9

..2.45674523 8 22 22 19 2 23 13 7 17 10 18 16 19 2 14 7 4 15 13 16 14 10 23 22 12 17 12 25 13 23 9 21 7 20 12 24 15 13 3 20 11 21 8 2

Subsoal3

● 2≤N≤10Subsoal4



● 2≤N≤2.000Subsoal7

● 2≤N≤2.000.000

halaman 10

Hari2/Soal3:WisataPalembangBatasMemori -

BatasWaktu -

DeskripsiSoalPakDengklekdanbebek-bebeknyasenangberwisatakuliner.Merekabersyukurberkesempatanberadadi Kota Palembang yang kaya berbagai lokasiwisata kuliner untuk dikunjungi.Merekamempersiakanrencana berkeliling kota berdasarkan suatu daftar berisi N-1 lokasi kuliner terfavorit di kota ini. yangdinomorimulaidari2sampaidenganN.Nomor1adalahhotelmerekasebagaititikmulaidanakhirdariperjalananmereka.Tabelberikutinimengilustrasikansuatucontohlisttersebut.

Lokasi Makanan/Minuman

2 Pempek

3 Tekwan

4 Model

5 Laksan

6 Celimpungan

7 KerupukKemplang

8 MartabakKari

9 LapisLegitMaksuba

10 EsKacangMerah

Sayangnya,informasijarakruasjalanantarlokasitidaktersedia,kecualibahwaantarsetiaplokasidalamlist,termasukhotel,selaluterdapatruasjalanduaarahyangmenghubungkannyadenganpanjangyangtidak lebih dari L. Kemudian, dengan informasi itu PakDengklekmenyusun rute perjalanannyamulaidarilokasi1(hotelmereka),lalumengunjungi(N-1)lokasikulinerdalamlistitu,dalamurutantertentu,danberakhirkembalikehotel.Setiaplokasikulinerhanyaakandikunjungitepatsekali.

Jika panjang ruas-ruas jalan itu diketahui tentunya total jarak yang akan ditempuh dapat diketahui,sepertidiilustrasikanpadaGambar3berikut.

halaman 11

A--5---B |\ /| | 4 / | 2 \/ 3 | /\ |

| 2 \ | |/ \| C--1---D

Gambar3.ContohRuas-ruasjalanuntukN=4,M=2danL=5.

Maka,daricontohitusemuakemungkinanrutebesertatotal-totaljaraknyaadalahsebagaiberikut.

A--B--C--D--A:5+2+1+4=12A--B--D--C--A:5+3+1+2=11A--C--B--D--A:2+2+3+4=11A--C--D--B--A:2+1+3+5=11A--D--B--C--A:4+3+2+2=11A--D--C--B--A:4+1+2+5=12

Darisemuarutetersebut,terdapat2buahkemungkinantotaljarakberbeda,yaitu11dan12.Sekarang,ia sedang terpancing memikirkan pertanyaan kebalikannya. Jika diketahui banyaknya kemungkinantotal jarak berbeda tidak kurang dariM, denganN dan L sesuai penjelasan sebelumnya, bisakah iamendapatkan satu kemungkinan panjang-panjang ruas jalan yang memenuhi? Asumsikan bahwapanjang-panjangruasjalanitubilanganbulat.

PakDengklekmemintapertolonganandauntukmenemukanjawabanyangmemenuhibatasan-batasantersebut (N,MdanL). Ingatbahwaandahanyamenemukansatukemungkinan sajadan jika jawabanandamemangmemenuhibatasan-batasantersebutandaakanmemperolehnilaipenuh.Jikatidak,PakDengklekmasihmemberikan suatu kelonggaranmengenai batasan L untukmendapatkan nilai parsialselamabatasannilaiMterpenuhi.Perhitungannilaiparsial iniditentukanmenurutrumusperhitunganyangdijelaskandibagianSubsoal(bagianterakhir).

InformasiTipeSoal

Soal iniadalahsoal“output-only”.Dalamsoal ini,andaharusmenuliskankeluaranprogramdalamfilekeluaranuntuksetiapkasusuji.Kemudian,compressseluruhfilemenjadisebuahfile.zip.

Masukanuntuk soal inidapatdiunduhdi sini.Didalamberkas zip tersebutada1+8masukanuntukdiselesaikan: wisata_sample_1.in, wisata_1.in, wisata_2.in, ..., wisata_8.in. Masukan sample tidakdinilai. Untuk setiap berkas masukan yang diselesaikan (Anda tidak harus menyelesaikan semuamasukan),buatlahberkaskeluarandengannamawisata_X.out,dimanaXadalahnomormasukan(atauwisata_sample_X.out untuk sample) sesuai format keluaran. Setelah itu, kompres semua berkaskeluarandalamsebuahberkas.zip.

halaman 12

FormatMasukan

Barispertamaakanberisi label kasusuji. Label kasusuji adalah sebuahstring yangdijelaskan sebagaiberikut:

● Panjangstringtersebutadalahbanyaknyasubsoalditambahsatu.● Karakter ke-0 (indeks dimulai dari 0) akan berisi 0 jika kasus uji tersebut merupakan contoh

kasusuji,atauberisi'.'(titik)jikabukan.● Untuksetiapnilaiidiantara1hinggabanyaknyasubsoal,berlaku:

○ jikakasusujitersebutmemenuhibatasansubsoalke-i,makakarakterke-iberisii,atau○ jika kasusuji tersebut tidakmemenuhi batasan subsoal ke-i,maka karakter ke-i berisi

karakter'.'(titik).Sebagaicontohapabilalabelsebuahkasusujisebuahsoaladalah0..345,maka:

● Soaltersebutmemiliki5buahsubsoal,● Kasusujitersebutmerupakancontohkasusuji,dan● Kasusujitesebutmemenuhibatasansubsoalke-3,ke-4,danke-5.

Kemudian,barisberikutnyaberisitigabuahbilanganbulatN,M,danL,yangberturut-turutmenyatakanbanyaknya lokasi, banyaknya total jarak berbeda yang diinginkan Pak Dengklek, dan parameterpenilaian. Nilai L akan digunakan untukmenentukan nilai pada suatu kasus uji. Lihat bagian Subsoaluntuklebihjelasnya.

FormatKeluaran

Keluaran terdiridariNbaris, yangmenjelaskanpanjang jalanyangdiinginkan.Bariske-iberisiNbuahbilangan bulat, dengan bilangan ke-j pada baris ini adalah nilai Aij. Nilai Aii harus 0 dan nilai Aij harussamadengannilaiAji.Bilangan-bilangandalamsatubarisdipisahkanolehspasi.

Pastiterdapatsetidaknyasatujawabanyangmemenuhipersyaratan,yaituterdapatpalingtidakMbuahtotal jarakyangberbeda.Andadapatmengeluarkan jawabanmanapunyangsah,dannilaiAndaakanbergantungkepadakeluaranyangAndahasilkan.

ContohMasukan

Namafile:wisata_sample_1.in

0........ 4 2 5

ContohKeluaran

Namafile:wisata_sample_1.out

0 5 2 4 5 0 2 3 2 2 0 1 4 3 1 0

halaman 13

Subsoal

Setiap subsoal hanya terdiri atas satu kasus uji. Nilai untuk setiap kasus uji adalah 0 jika ada kriteriaberikutyangtidakterpenuhi:

● keluaransesuaiformatyangtelahdijelaskanpadaformatkeluaran,● 1≤A_ij=A_ji≤1017untuki,j=1..Ndani≠j,● A_ii=0untuki=1..N,dan● terdapat paling tidak M buah kemungkinan total jarak berbeda di antara semua urutan

pengunjungan.Jikaseluruhkriteriadiatastelahterpenuhi,makanilaiAndauntukkasusujitersebutadalah:

● Kasusuji1,2,3,4,5,dancontoh:

● Kasusuji6,7,8:

dengan P adalah poin maksimum untuk kasus uji yang bersangkutan (P bernilai 100 untuk kasus ujicontoh).

Subsoal1

● Namafile:wisata_1.in● N=4● M=3● L=2

Subsoal2


Subsoal3


Subsoal4

● Namafile:wisata_4.in

halaman 14

● N=5● M=12● L=6

Subsoal5


Subsoal6

● Namafile:wisata_6.in● N=8● M=2.520● L=40.000

Subsoal7

● Namafile:wisata_7.in● N=9● M=20.160● L=2.250.000

Subtask8

● Namafile:wisata_8.in● N=10● M=181.440● L=200.000.000

informatika/komputer 1. empek-empek 2. gunting ...halaman 2 o jika kasus uji tersebut tidak memenuhi...

Documents