OLIMPIADESAINSNASIONAL2016

DESKRIPSISOAL

Hari2

1. RobotPempek2. BelanjaSuvenir3. WisataPalembang

Waktu:5Jam

INFORMATIKA/KOMPUTER

HakCiptaDilindungiUndang-undang

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

Hanyaterdiriataskasusujiberikutini:

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).

Sebagaicontohapabilalabelsebuahkasusujisebuahsoaladalah0..345,maka:

● 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

Hanyaterdiriataskasusujiberikutini:

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

Subsoal2

Hanyaterdiriataskasusujiberikutini:

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≤50Subsoal5

● 2≤N≤200Subsoal6

● 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

● Namafile:wisata_2.in● N=5● M=5● L=2

Subsoal3

● Namafile:wisata_3.in● N=5● M=8● L=3

Subsoal4

● Namafile:wisata_4.in

halaman 14

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

Subsoal5

● Namafile:wisata_5.in● N=10● M=70● L=9

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