SCHEMATICS 2011 PEMBAHASAN BABAK PENYISIHAN SCHEMATICS

SCHEMATICS

SCHEMATICS 2011 – PEMBAHASAN BABAK PENYISIHAN

Dream, Think, Code !! | Panitia NPC – Schematics 2011

Schematics 2011 – Pembahasan Babak Penyisihan NPC 2011

DAFTAR ISI – PROBLEM PENYISIHAN Bagi-Bagi Permen ........................................................................................................................ 2 JAM ............................................................................................................................................... 6 KOIN ........................................................................................................................................... 11 KOLA ........................................................................................................................................... 13 M I Lucky .................................................................................................................................... 18 Perang Galaksi ........................................................................................................................... 21 Permutasi ................................................................................................................................... 25 SIHIR ........................................................................................................................................... 28

1


Bagi-Bagi Permen Cak Matik mempunyai banyak sekali anak. Pada suatu hari ia ingin mengajak semua anaknya pergi berkemah. Untuk itu setiap anak diharuskan membawa sekantung permen. Celakanya, ia lupa mengatakan berapa permen yang harus ditaruh dalam satu kantung permen. Agar tidak terjadi perselisihan diantara anak-anaknya, Cak Matik memutuskan membuka semua kantung permen dan memindahkan permen-permen itu dari kantung yang memiliki permen banyak ke kantung yang memiliki permen sedikit sehingga semua kantung memiliki jumlah permen yang sama. Hitunglah perpindahan minimum yang mungkin sehingga semua kantung permen memiliki jumlah permen yang sama. Penjelasan masukan Masukan terdiri dari beberapa blok data. Setiap blok data akan diawali dengan bilangan N(1<= N <= 10000) yang menyatakan jumlah kantung permen yang ada. Diikuti N baris dibawahnya yang berisi permen setiap kantung. Isi setiap kantung tidak akan melebihi 100 permen. Setelah blok data terakhir akan diikuti angka -1, yang menyatakan tidak ada lagi blok data. Penjelasan Keluaran Keluaran terdiri dari beberapa baris. Setiap baris berisi perpindahan minimum permen permen pada sebuah blok data. Satu perpindahan didefinisikan sebagai perpindahan satu buah permen dari suatu kantung ke kantung lainnya. Jika tidak mungkin membuat semua kantung permen memiliki jumlah permen yang sama, cetak -1. Contoh Masukan 5 10 4 15 6 10 3 99 99 98 -1 Contoh Keluaran 8 -1 Algoritma Penyelesaian Kunci soal ini terletak pada kalimat “semua kantung memiliki jumlah permen yang sama”. Hal pertama yang harus dilihat adalah ada 2 kondisi akhir yaitu semua kantung memiliki jumlah permen yang sama apa tidak. Ini mudah saja, jika jumlah semua permen habis dibagi dengan jumlah kantung maka pastilah jumlah permen di semua kantung bisa disamakan. Jika jumlah

2


semua permen tidak habis dibagi dengan jumlah kantung yang ada pastilah tidak mungkin jumlah permen di semua kantung sama. Contohnya jika katung permen ada 5 dan jumlah semua permen adalah 9 maka pastilah tidak mungkin 5 kantung tersebut memuat jumlah permen yang sama. Permasalahan kedua adalah bagaimana menetukan perpindahan minimum. Berdasarkan contoh kasus pada contoh input: Kantung 1 2 3 4 5 jumlah permen 10 4 15 6 10 permen total 45 Karena total permen ada 45 buah, maka pastilah 1 buah kantung memuat 45/5 = 9 buah permen. Perpindahan pasti dilakukan dari kantung yg memiliki jumlah permen lebih dari seharusnya. Berdasarkan kasus diatas, kantung yang memiliki lebih dari 9 buah permen adalah kantung 1, kantung 3, kantung 5. Ketiga kantung tersebut tentulah harus dikurangi jumlah permennya. Inilah yang dihitung sebagai perpindahan. Sehingga total perpindahan adalah: jumlah permen kantung 1 – 9 = 10 – 9= 1 jumlah permen kantung 3 – 9 =15 – 9= 6 jumlah permen kantung 5 – 9 = 10 – 9=1 Maka pastilah dibutuhkan 1+6+1= 8 buah perpindahan sehingga kantung 1,kantung 3, kantung 5 memiliki jumlah permen yang sama. Pseudocode read(jumlah_kantung) while (jumlah_kantung <> -1) begin total=0; for i=1 to jumlah_kantung do begin read(kantung[i]) total=total+kantung[i] end if (total mod jumlah_kantung > 0) print(-1) else begin jumlah_perpindahan=0 rata_rata_permen=total div jumlah_kantung for i=1 to jumlah_kantung do begin if (kantung[i]>rata_rata_permen) jumlah_perpindahan=jumlah_perpindahan+(kantun g[i]-rata_rata_permen) end print(jumlah_perpindahan) end end

3


Bahasa Pascal var n,sum,i,mean,hasil:integer; candy: array[1..10000] of integer; begin read(n); while (n>0) do begin sum:=0; for i:=1 to n do begin read(candy[i]); sum:=sum+candy[i]; end; if (sum mod n = 0) then begin mean:=sum div n; hasil:=0; for i:=1 to n do begin if (candy[i] > mean) then hasil:=hasil+(candy[i]-mean); end; writeln(hasil); end else writeln('-1'); read(n); end; end.

Bahasa C / C++ #include <stdio.h> #include int main() { int test,sum,hasil,i,candy[10010],mean; scanf("%d",&test); while (test>0) { sum=0; for (i=0;i
4


sum=sum+candy[i]; } if ((sum%test)==0) { mean=sum/test; hasil=0; for (i=0;i
5


JAM Om Yongkru adalah bisnisman yang super sibuk dan kurang kerjaan, tiap hari dia mencatat kegiatan apa yang ia lakukan dan menghitung berapa lama ia melakukan kegiatan tersebut, kemudian ia menjumlahkan total waktunya. sisa dari waktu tersebut(dalam sehari) ia gunakan untuk beristirahat(makan,dan sebagainya). Karena ia tidak suka matematika, ia menyuruh seorang programmer bernama Enpicy untuk menghitung total waktu istirahat Om Yongkru. Catatan: -1 hari = 24 jam, 1 jam = 60 menit, 1 menit = 60 detik. -Total waktu kegiatan om yongkru tidak mungkin melebihi 24 jam. Input: baris pertama adalah T(test case), kemudian setiap test case terdiri dari n(jumlah kegiatan) ,kemudian diikuti n baris dengan format input seperti berikut hh mm ss(jam menit detik) 0<=hh<=24 0<=mm,ss<=60 Output: Total waktu istirahat Om Yongkru Contoh: Input 2 4 01 00 00 02 00 00 03 00 00 04 00 00 2 11 00 30 11 00 31 Output: 14 00 00 01 58 59

6


Algoritma: -Pertama Waktu istirahat Om Yongkru di set menjadi 24 jam 0 menit 0 detik. -Kemudian Waktu istirahatnya dikurangkan dengan setiap kegiatan yang ia lakukan dalam sehari. -Selesai :D. Test Case: Input 4 010000 020000 030000 040000 2 110030 110031 3 073051 021543 092339 5 010203 040506 030201 060504 010101 24 010000 010000 010000 010000 010000 010000 010000 010000 010000 010000 010000 010000 010000 010000 010000 010000 010000 010000

Output 140000

015859

044947

084445

000000

7


010000 010000 010000 010000 010000 010000 1 235959 1 000001 3 230000 005900 000059 4 105432 032938 041651 022220 5 095959 000002 010101 000059 105959

000001 235959 000001

025639

015800

8


Bahasa Pascal var n,i,jam1,menit1,detik1,t,j,jam,menit,detik:longint; begin read(n); for i:=1 to n do begin jam1:=24; menit1:=0; detik1:=0; read(t); for j:=1 to t do begin read(jam,menit,detik); detik1:=detik1-detik; if (detik1<0) then begin detik1:=detik1+60; menit1:=menit1-1; if (menit1<0) then begin menit1:=menit1+60; jam1:=jam1-1; end; end; menit1:=menit1-menit; if (menit1<0) then begin menit1:=menit1+60; jam1:=jam1-1; end; jam1:=jam1-jam; end; if (jam1<10) then write('0'); write(jam1,':'); if (menit1<10) then write('0'); write(menit1,':'); if (detik1<10) then write('0'); writeln(detik1); end; end.

9


Bahasa C / C++ #include<stdio.h> int main() { int T,N,jam,menit,detik; int jam1,menit1,detik1; scanf("%d",&T); while(T--) { jam1=24; menit1=0; detik1=0; scanf("%d",&N); while(N--) { scanf("%d:%d:%d",&jam,&menit,&detik); detik1-=detik; if(detik1<0) { detik1+=60; menit1--; if(menit1<0) { menit1+=60; jam1--; } } menit1-=menit; if(menit1<0) { menit1+=60; jam1--; } jam1-=jam; } if(jam1<10) printf("0"); printf("%d:",jam1); if(menit1<10)printf("0"); printf("%d:",menit1); if(detik1<10)printf("0"); printf("%d\n",detik1); } }

10


KOIN Yotsuba punya banyak sekali koin berwarna-warni. Koin2 tersebut dibentuknya menjadi 3 tumpukan yang sangat tinggi, terdiri dari a,b, dan c koin (0 <= a,b,c <= 1000000000). Seperti biasa Yotsuba mengganggu Chen yang lagi belajar karena bosan dengan koin-koinnya dan bingung mau diapakan koin-koin tersebut. Chen ada ide untuk membuat permainan. Pada satu giliran, pemain memilih satu tumpukan, misalnya A. Ia mengambil 1 koin di tumpukan tersebut dan menyimpan di kantongnya. Kemudian ia memilih satu tumpukan lagi selain tumpukan tadi, misalnya C. Dari tumpukan ini 1 koin dipindahkan ke tumpukan sisanya, yaitu B. Sehingga konfigurasi tumpukan dari a-b-c menjadi (a-1)-(b+1)-(c-1). Pemain yang tidak bisa melakukan gerakan dialah yang kalah. Kali ini Chen yang mendapat giliran pertama, tentukan siapa pemenangnya dengan asumsi Chen dan Yotsuba (yang diajari Chen) bermain optimal! Input: 3 integer a,b,c. Input berakhir ketika a=b=c=-1. Output: Sesuai soal. Contoh: Input: 312 451 10 10 10 -1 -1 -1 Output: Chen Chen Yotsuba

11


Bahasa Pascal var i,j,k,idx:longint; arr:array[0..1] of integer; begin read(i,j,k); while (i<>-1)and(j<>-1)and(k<>-1) do begin arr[0]:=0; arr[1]:=0; idx:=i mod 2; arr[idx]:=arr[idx]+1; idx:=j mod 2; arr[idx]:=arr[idx]+1; idx:=k mod 2; arr[idx]:=arr[idx]+1; if (arr[1]>arr[0]) then writeln('Chen') else writeln('Yotsuba'); read(i,j,k); end; end. Bahasa C / C++ #include "cstdio" #include "cstring" using namespace std; int main(void) { int i,j,k,arr[2]; scanf("%d%d%d",&i,&j,&k); while(!(i==-1 && j==-1 && k==-1)) { arr[0]=arr[1]=0; arr[i%2]++; arr[j%2]++; arr[k%2]++; if(arr[1]>arr[0])printf("Chen\n"); else printf("Yotsuba\n"); scanf("%d%d%d",&i,&j,&k); } return 0; }

12


KOLA Koke-Kola sedang diambang kebangkrutan, karenanya perusahaan ini mengadakan promosi besarbesaran untuk menjual produknya. setiap 3 botol kosong Koke-Kola bisa ditukarkan 1 Botol KokeKola baru. Dan Ternyata Taktik mereka berhasil, produk mereka laku berkali-kali lipat dan tentu saja menghasilkan segenap orang menjadi "GILA KOLA". Om Yongkru sangat suka Koke-Kola, ia membeli 8 Kola dan menukarkan sesuai prosedurnya. Ilustrasi nya dapat digambarkan sebagai berikut:

berdasarkan gambar diatas, Om Yongkru mendapatkan total 11 kola, dan 2 botol kosong yang tidak bisa ditukar. Ditengah jalan menuju pulang ,sambil membawa 2 botol kosong Om Yongkru bertemu dengan Enpicy temannya. Enpicy : "Dari mana bro?" Om Yongkru : "dari warung beli 8 kola, aku meminum 11 kola hari ini :D " Enpicy : "hey om,aku bisa meminum lebih dari 11 kola dengan hanya membeli 8 kola" Om Yongkru : "Bagaimana caranya?" Enpicy :"Sini kupinjam satu botol kosongmu, nanti kukembalikan" 30 menit kemudian, ia mengembalikan botol kosong yang ia pinjam dan berkata, "Aku baru saja meminum 12 Botol Kola :D" Kok Bisa? untuk lebih jelasnya lihat ilustrasinya berikut:

13


Permasalahan: dengan menggunakan cara Enpicy, berapa maksimal botol Kola yang bisa diminum jika membeli N botol? 0<=N<=100000 Input: Baris Pertama adalah T(test case), kemudian tiap test case terdiri dari N(Jumlah botol Kola yang dibeli) Output: Maksimal botol kola yang diminum. Contoh: Input 8 14 Output 12 21

14


Algoritma: -Kuncinyayaitu :Setiap 2 Botol kosong sisa bisa ditukarkan dengan satu Kola baru dengan cara meminjam 1 botol Kola dari orang lain, kemudian setelah di minum botolnya dikembalikan. Simulasi X=cola milikenpicy Y=cola kosong yang dipinjam Enpicy misalnya membeli 8 kola. XXX XXX XX = 8+2 XXXX <- Karenasisanya 4, makakitabutuh 4/2=2 botolpinjaman. XXY XXY = 10+2 XX <- Dikembalikan Hasil = 12 Contohlagi, misalnyauntuk 20 kola. XXX XXXXXXXXXXXXXXX XX = 20 + 6 XXXXXXXX <- Sisa = 8 ,butuh 8/2=4 pinjaman XXY XXYXXYXXY = 26 + 4 XXXX <- Dikembalikan Hasil = 30

Test Case: Input 1 2 3 10 36 47 63 100 125 150 189 212 429 561 643 891

Output 1 3 4 15 54 70 94 150 187 225 283 318 643 841 964 1336

15


1024 1341 1578 1980 2011 2568 3891 5720 7528 9125 11234 14000 19234 24652 27532 30000 32501 36721 41254 47812 50000 52158 55123 58721 61234 63825 78732 80000 88723 90185 95791 98765 100000

1536 2011 2367 2970 3016 3852 5836 8580 11292 13687 16851 21000 28851 36978 41298 45000 48751 55081 61881 71718 75000 78237 82684 88081 91851 95737 118098 120000 133084 135277 143686 148147 150000

16


Bahasa Pascal var n,i,x,a,b,c,hasil:longint; begin read(n); for i:=1 to n do begin read(x); a:=x div 3; b:=x mod 3; c:=(a+b) div 2; hasil:=x+a+c; writeln(hasil); end; end. Bahasa C/C++ #include<stdio.h> int main() { int n,x,y,z,T,yong,enpy,zz; scanf("%d",&T); while(T--) { scanf("%d",&n); x=n/3; y=n%3; z=(x+y)/2; zz=(x+y)/3; enpy=n+x+z; printf("%d\n",enpy); } }

17


M I Lucky Pak TC sangat suka bermain angka. Pada suatu hari ia pergi ke stadion gelora bung karno untuk melihat pertandingan Indonesia melawan Uruguay. Sambil menonton, Pak TC ingin mencoba keberuntungannya dengan ikut taruhan. Dia pun akhirnya mendapat ticket taruhan yang terdiri dari 1-9 digit dengan angka tiap digit 1-9. Pak TC merasa akan beruntung jika mendapat nomer yang ia anggap nomer keberuntungannya. Pak TC mempunyai cara yang unik untuk menentukan nomernya lucky atau tidak. Caranya seperti ini: Ia membentuk nomer baru dengan mengalikan semua digit angka pada karcisnya, lalu melihat digit-digit angka baru yang telah terbentuk tadi. Bila digit angka tersebut genap kecuali angka empat maka angka tersebut merupakan angka baik. Selain itu, ia anggap angka buruk. Setelah itu, ia membandingkan banyaknya angka baik dan buruk. Jika angka baik lebih banyak atau sama dengan angka buruk maka ticket tersebut membawa keberuntungan, dan sebaliknya. Tentukan nomer ticket yang didapatkan pak TC termasuk Lucky atau tidak. INPUT baris pertama menyatakan banyak test case. Berikutnya nomer yang didapat Pak TC pada ticketnya. OUTPUT Angka baru yang terbentuk. Cetak "LUCKY" jika Ticket tersebut merupakan angka keberuntungan. Cetak "NO" jika sebaliknya. Contoh Input: 3 1221 2345 757356 Output: 4 NO 120 LUCKY 22050 LUCKY

18


Bahasa Pascal + Penjelasan var n,i,x,total,lucky,bad:longint; begin read(n); for i:=1 to n do begin read(x); total:=1; // inisialisasi while (x>0) do begin total:=total*(x mod 10); //perkalian semua digit dengan dibagi 10 untuk mengambil angka perdigit x:=x div 10; end; write(total,' '); lucky:=0; bad:=0; while (total>0) do begin x:=total mod 10;//ambil digit paling belakang if (x=4)or(x mod 2 =1) then bad:=bad+1 //penghitungan LUCKY atau NO else lucky:=lucky+1; total:=total div 10;//menghilangkan digit terakhir end; if (lucky>=bad) then writeln('LUCKY') else writeln('NO'); end; end. Bahasa C / C++ #include <stdio.h> #include using namespace std; int main() { int n,nwnm,b,l,i; scanf("%d",&i); while(i>0) { b=l=0; nwnm=1; scanf("%d",&n); while(n!=0) { nwnm=nwnm*(n%10); n/=10; }

19


printf("%d ",nwnm); while(nwnm!=0) { n=nwnm%10; if(n==4 || n%2==1) b++; else l++; nwnm/=10; }

if(l>=b) printf("LUCKY\n"); else printf("NO\n");

i--; } return 0; }

20


Perang Galaksi Pada jaman dahulu kala hidup di galaksi NPC sangatlah tentram. Namun semua berubah saat robot api menyerang. Hanya Cak Matik yang menguasai berbagai robot-robot elemen yang bisa menaklukkan robot api. Namun saat galaksi mebutuhkannya, iapun berperang. Pasukan Cak Matik dan Robot Api terdiri dari sekumpulan robot. Kekuatan setiap robot direpresentasikan dengan angka. Perang ini terdiri dari beberapa pertarungan.Dalam setiap pertarungan, robot yg memiliki kekuatan terendah dari kedua pasukan akan mati. Jika ada lebih dari 1 robot yang memiliki kekuatan terendah dan berada pada pasukan yang sama, maka salah satu dari robot tersebut mati. Jika robot terlemah di pasukan Cak Matik dan Robot Api memiliki kekuatan yang sama, maka robot terlemah pada pasukan Robot Api yang akan mati. Perang akan berakhir jika robot-robot pada salah satu pasukan telah habis. Penjelasan Masukan Pada baris pertama akan diisi oleh angka T(1<= T <= 100) yang menunjukkan jumlah kasus. Setiap kasus akan dipisahkan oleh sebuah baris kosong. sebuah kasus terdiri dari 3 baris. Baris pertama berisi 2 buah angka N(1< N < 100) dan M(1< M < 100). Angka N menyatakan banyaknya robot pada pasukan Cak Matik. Angka M menyatakan banyaknya robot pada pasukan Robot Api. Baris kedua terdapat N buah angka yang menyatakan kekuatan robot-robot di pasukan Cak Matik. Baris ketiga terdapat M buah angka yang menyatakan kekuatan robot-robot di pasukan Robot Api. Kekuatan robot dipastikan tidak akan melebihi 100. Penjelasan Keluaran Diberikan semua kekuatan robot-robot pada kedua pasukan tersebut, tentukanlah hasil perang ini. Cetak kalimat “Cak Matik” jika pemenangnya adalah pasukan Cak Matik. Cetak kalimat “Robot Api” jika pemenangnya adalah pasukan Robot Api. Cetak kalimat “Tidak Pasti” jika pemenangnya tidak dapat ditentukan. Satu baris untuk satu kasus.

Contoh Masukan 2 2 2 3 3 3 3 5 1 1 2 5 7 9 18 Contoh Keluaran Cak Matik Robot Api

21


Penyelesaian Kunci penyelesaian soal ini berada pada peraturan petarungan yang ada. Pertama, setiap pertarungan robot terlemah diantara semua robot yang ada pasti mati,jika ada 2 buah robot yang memiliki kekuatan terlemah,salah satunya pasti mati.Misal: Robot 1 Robot 2 Robot 3 Cak Matik 5 10 5 Robot Api 7 8 9 -pada pertarungan 1, kekuatan terlemah ada pada 2 buah robot Cak Matik, yaitu Robot 1 dan Robot 5. Sehingga salah satu dari mereka harus mati. Jika dilihat baik baik, setiap pertarungan pastilah robot yang terlemah akan mati. Secara logis bisa disimpulkan yang tersisa di akhir adalah robot terkuat. Permasalahanya adalah ada di pasukan siapa robot terkuat itu. Jika robot terkuat ada di pasukan Cak Matik, maka Cak Matik pemenangnya. Sebaliknya, jika robot terkuat ada di pasukan Robot Api, maka Robot Api pemenangnya. Kesimpulannya adalah pemenangnya ditentukan oleh robot terkuat di masing masing pasukan, sehinnga robot robot yang lainnya tidak perlu diperhatikan. Kasus yang perlu diperhatikan adalah bagaimana jika robot terkuat di pasukan Cak Matik dan pasukan Robot Api memiliki kekuatan yang sama. Sesuai peraturan pemenangnya adalah robot dari pasukan Cak Matik. Pseudocode read(jumlah_kasus) for i = 1 to jumlah_kasus do begin read(jumlah_robot_CM) read(jumlah_robot_RA) kekuatan_max_CM=0 for j = 1 to jumlah_robot_CM do begin read(strength) if (kekuatan_max_CM<strength) kekuatan_max_CM=strength end kekuatan_max_RA=0 for j = 1 to jumlah_robot_RA do begin read(strength) if (kekuatan_max_RA<strength) kekuatan_max_RA=strength end if (kekuatan_max_CM >= kekuatan_max_RA) print(Cak Matik) else print(Robot Api) end

22


Bahasa Pascal var i,n,a,b,j,x,max,max2:integer; begin read(n); for i:=1 to n do begin read(a,b); max:=0; for j:=1 to a do begin read(x); if (max<x) then max:=x; end; max2:=0; for j:=1 to b do begin read(x); if (max2<x) then max2:=x; end; if (max2>max) then writeln('Robot Api') else writeln('Cak Matik'); end; end. Bahasa C / C++ #include <stdio.h> int main() { int test,i,j,m,g,win,max,n; scanf("%d",&test); for (i=0;i
23


} j=0; while (j<m) { scanf("%d",&n); if (max
24


Permutasi Chen dan Yotsuba mengadu konsentrasi. Pertama, mereka memilih suatu permutasi angka sebagai Key. Permutasi ini terdiri dari N angka yaitu 1 sampai N (1 <= N <= 50). Setelah itu permainan dimulai dengan susunan N angka yang berurutan. Permainannya adalah, pemain selanjutnya harus mengucapkan bilangan ke-Key-i dari bilangan yang disebutkan sebelumnya. Misalnya untuk permainan 4 angka dipilihlah 3-1-2-4 sebagai Key. Permainan dimulai dengan Yotsuba menyebutkan 1-2-3-4 (permainan dimulai dengan susunan angka terurut). Chen kemudian menyebutkan 3-1-2-4. Selanjutnya Yotsuba menyebutkan 2-3-1-4, karena bilangan pertama dari Key adalah 3, dan bilangan ke-3 yang disebutkan Chen adalah 2, sehingga 2 terpilih sebagai angka pertama dan seterusnya. Permainan berakhir ketika ada pemain yang menyebutkan bilangan terurut kembali yaitu 1-2-3-4. Kadang-kadang permainan mereka berakhir terlalu cepat, kadang-kadang sangat lama. Tentukan langkah terpanjang yang bisa terjadi apabila Chen dan Yotsuba bermain N angka! Input: Input terdiri dari N hingga N=0. Output: Tampilkan langkah terbanyak. Contoh: Input: 4 5 0 Output: 4 6 Penjelasan output: Salah satu Key yang bisa mencapai 6 langkah untuk N=5 adalah 5-4-2-3-1, berikut langkahlangkahnya: 1-2-3-4-5 5-4-2-3-1 1-3-4-2-5 5-2-3-4-1 1-4-2-3-5 5-3-4-2-1 1-2-3-4-5

25


Bahasa Pascal var c,z:longint; function max(a,b:longint):longint; begin if(a>=b)then max:=a; max:=b; end; function gcd(x,y:longint):longint; begin while (x<>0) do begin z:=x; x:=y mod x; y:=z; end; gcd:=y; end; function lcm(x,y:longint):longint; begin lcm:=x*(y div gcd(x,y)); end; function mac(cur,t,n:longint):longint; var r:longint; begin r:=cur; if (t<=n) then r:=max(r,mac(lcm(cur,t),t+1,n-t)); if (t0) do begin if (c=1) then begin writeln('1'); read(c); continue; end; writeln(mac(1,2,c)); read(c); end; end.

26


Bahasa C / C++ #include "cstdio" #include "algorithm" using namespace std; int gcd(int,int); int lcm(int,int); int mac(int,int,int); int main(void) { int n; scanf("%d",&n); while(n!=0) { if(n==1) { printf("1\n"); scanf("%d",&n); continue; } printf("%d\n",mac(1,2,n)); scanf("%d",&n); } return 0; } int gcd(int x, int y) { while (x!=0) { int z = x; x = y%x; y = z; } return y; } int lcm(int x, int y) { return x*(y/gcd(x,y)); } int mac(int cur,int t,int n) { int r; r=cur; if(t<=n)r=max(r,mac(lcm(cur,t),t+1,n-t)); if(t
27


SIHIR Di sebuah kerajaan, hiduplah sepasang kekasih(pangeran dan permaisuri) yang saling mencintai, mereka berencana akan bertunangan bulan depan. Pada awalnya semuanya berjalan lancar,sampai ada seorang nenek sihir yang tidak suka jika mereka berdua bersatu. ia pun berusaha memisahkan mereka dengan mengutuk mereka menjadi sebuah Jam Dinding. Sang Pangeran diubah menjadi jarum jam dan Sang permaisuri diubah menjadi jarum menit. Mereka hanya bisa bertemu dan berpelukan jika Jarum jam dan jarum menit bertemu(contoh : jam 12:00). dalam jangka waktu hh1:mm1 sampai hh2:mm2 berapa kalikah mereka bisa berpelukan? Keterangan : -Jika mereka bertemu di titik start, mereka tidak berpelukan. -Jarum pendek dan jarum panjang dianggap bertemu ketika jarum panjang melewati jarum pendek. Misalnya ketika jam 01.05,kedua jarum belum dianggap bertemu karena kedua jarum bertemu pada jam 01.05 lebih sedikit. Input : Baris pertama adalah T(test case), setiap test case terdiri dari 1 baris yaitu hh1 mm1 hh2 mm2. 00:00<=hh1:mm1 && hh2:mm2 <=23:59 Output : berapa kali mereka berpelukan

Contoh: Input 00 00 00 30 00 00 12 00 Output 0 11

Algoritma: -Dalam 12 Jam jarum menit dan jarum jam bertemu sebanyak 11 kali (24 jam = 22 kali). -jarum jam dan jarum menit bertemu setiap 12 Jam/11 = 1 jam 5 menit 27,27detik. Test Case Input 0000 1200 0100 1300

Output 11 11

28


0430 0630 1200 2000 0001 1159 1830 2240 0107 0210 1945 2359 1123 1435 1655 2310 1100 1159 0000 1159 1234 2143 1345 1543 2230 2359 0145 1845 0359 2000 0000 2356 0555 2241 0000 2359

1 7 10 4 0 3 3 6 0 10 8 2 1 16 15 21 15 21

Bahasa Pascal var i,j,h1,m1,n,h2,m2,temua,temub,bef,ef:longint; jam:array[0..22] of longint; begin jam[0]:=0; jam[1]:=10527; jam[2]:=21054; jam[3]:=31623; jam[4]:=42149; jam[5]:=52721; jam[6]:=63246; jam[7]:=73809; jam[8]:=84319; jam[9]:=94903; jam[10]:=105431; jam[11]:=120000; jam[12]:=130527; jam[13]:=141054; jam[14]:=151623; jam[15]:=162149; jam[16]:=172721; jam[17]:=183246; jam[18]:=193809; jam[19]:=204319; jam[20]:=214903; jam[21]:=225431; jam[22]:=240000; read(n); for j:=1 to n do begin read(h1,m1,h2,m2); bef:=h1*10000 + m1*100; ef:=h2*10000 + m2*100; for i:=0 to 22 do begin if (jam[i]>bef) then begin temua :=i; break; end; end; 29


for i:=0 to 22 do begin if (jam[i]>ef) then begin temub :=i; break; end; end; writeln(temub-temua); end; end. Bahasa C / C++ #include<stdio.h> int main() { int jam[]={0,10527,21054,31623,42149,52721,63246,73809,84319,94903,105 431,120000,130527,141054,151623,162149,172721,183246,193809,204319 ,214903,225431,240000}; int test,sjam,smnit,fjam,fmnit,bef,af,temua,temub,i; //freopen("SIHIR.in","r",stdin); //freopen("SIHIR.out","w",stdout); scanf("%d",&test); while(test--) { scanf("%d:%d",&sjam,&smnit); bef=sjam*10000 + smnit*100; scanf("%d:%d",&fjam,&fmnit); af=fjam*10000 + fmnit*100; for(i=0;i<23;i++) { if(jam[i]>bef) {temua=i; break;} } for(i=0;i<23;i++) { if(jam[i]>af) {temub=i; break;} } printf("%d\n",temub-temua); } }

30

SCHEMATICS 2011 PEMBAHASAN BABAK PENYISIHAN SCHEMATICS

Recommend Documents