F-Crown

Pak udin meninggalkan rumahnya jam 6 pagi untuk memerah sapi di peternakannya. Namun, sehari sebelumnya ada hujan lebat yang menyebabkan padang rumput menjadi berlumpur. Pak Udin berangkat dari titik (0, 0) dan bergerak ke arah kandang sapi yang berada di (x, y) (-500 <= x <= 500); (-500 <= y <= 500).
Pak Udin dapat melihat semua N (1 <= N <= 100) kubangan lumpur yang ada di titik (a,b), -500 <= a <= 500); (-500 <= b <= 500) yang terdapat di padang rumput. Setiap kubangan hanya menempati sebuah titik saja. Karena pak Udin baru saja membeli sepatu boot baru, dia tidak ingin mengotori sepatu karena terperosok ke salah satu kubangan, tapi juga ingin mencapai kandang sapinya secepat mungkin. Jika Pak Udin hanya dapat bergarak secara paralel (sejajar) terhadap sumbu yang ada dan bebelok pada titik dengan koordinat bilangan bulat, berapakah jarak terdekat yang harus dilalui untuk mencapai kandang sapinya tanpa mengotori sepatunya? Dijamin selalu ada cara untuk mencapai kandang sapi tanpa mengotori sepatu pak Udin.
FORMAT INPUT:
Baris pertama input berupa sebuah bilangan integer K yang menunjukkan jumlah kasus yang harus dikerjakan. Selanjutnya, untuk tiap kasus akan berisi:
Baris 1 : tiga bilangan bulat dipisahkan spasi: x, y, dan n
Baris 2.n+i : dua bilangan bulat dipisahkan spasi: ai dan bi
FORMAT OUTPUT
Untuk tiap kasus akan berisi:
Baris 1 : jarak minimum yang harus ditempuh pak Udin untuk mencapai kandang sapi tanpa mengotori sepatunya.

CONTOH INPUT:
1 2 7
0 2
-1 3
3 1
1 1
4 2
-1 1
2 2
Kandang sapi ada di posisi (1, 2). Pak Udin melihat 7 kubangan pada posisi (0, 2); (-1, 3); (3, 1); (1, 1); (4, 2); (-1, 1) dan (2, 2).
4 . . . . . . . .
3 . M . . . . . . M = Kubangan Lumpur
Y 2 . . M S M . M . S = Kandang Sapi
1 . M . M . M . . * = Pak Udin
0 . . * . . . . .
-1 . . . . . . . .
-2 -1 0 1 2 3 4 5
X
CONTOH OUTPUT
11
PEMBAHASAN:
Rute terbaik bagi pak udin adalah (0, 0) (-1, 0); (-2, 0); (-2, 1); (-2, 2); (-2, 3); (-2, 4); (-1, 4); (0, 4); (0, 3); (1, 3); dan (1,2).
4 * * * . . . . .
3 * M * * . . . . M = Kubangan Lumpur
Y 2 * . M S M . M . S = Kandang Sapi
1 * M . M . M . . * = Pak Udin
0 * * * . . . . .
-1 . . . . . . . .
-2 -1 0 1 2 3 4 5
X
Jadi yang harus dileswati pak udin sebanyak 11 langkah, sesuai dengan jumlah * pada gambar diatas.
 Klo Mau Tahu Source Codenya Klik Disini

Sumber NPC..

Algoritma

Sejarah istilah "algoritma"

Jenis-jenis Algoritma

• Divide and Conquer, paradigma untuk membagi suatu permasalahan besar menjadi permasalahan-permasalahan yang lebih kecil. Pembagian masalah ini dilakukan terus menerus sampai ditemukan bagian masalah kecil yang mudah untuk dipecahkan. Singkatnya menyelesaikan keseluruhan masalah dengan membagi masalah besar dan kemudian memecahkan permasalahan-permasalahan kecil yang terbentuk.

• Dynamic programming, paradigma pemrograman dinamik akan sesuai jika digunakan pada suatu masalah yang mengandung sub-struktur yang optimal (, dan mengandung beberapa bagian permasalahan yang tumpang tindih . Paradigma ini sekilas terlihat mirip dengan paradigma Divide and Conquer, sama-sama mencoba untuk membagi permasalahan menjadi sub permasalahan yang lebih kecil, tapi secara intrinsik ada perbedaan dari karakter permasalahan yang dihadapi.

• Metode serakah. Sebuah algoritma serakah mirip dengan sebuah Pemrograman dinamik, bedanya jawaban dari submasalah tidak perlu diketahui dalam setiap tahap; dan menggunakan pilihan "serakah" apa yang dilihat terbaik pada saat itu.

Sumber Wikipedia

ALGORITMA EUCLIDEAN
menurut forumbeck Algoritma Euclidean adalah algoritma untuk mencari PBB dari dua buah bilangan bulat. Euclid, penemu algoritma euclidean adalah seorang matematikawan Yunani yang menuliskan Algoritmanya tersebut dalam bukunya yang terkenal “ Element “.
Diberikan dua buah bilangan bulat tak negatif m dan n ( m ≥ n ). Algoritma Euclidean berikut mencari pembagi bersama terbesar dari m dan n.
Sisa pembagian terakhir sebelum 0 adalah 4, maka PBB ( 80, 12) 4.
Teorema 1 ( teorema euclidean ) misalnya m dan n adalah dua buah bilangan bulat dengan syarat n > 0. Jika m dibagi dengan n maka terdapat dua buah bilangan bulat unik q ( quotient ) dan r ( remainder ), sedemikian sehingga :
m = n . q + r
dengan 0 ≤ r ≤ n
contoh : ( i ) 1987 dibagi dengan 97 memberikan hasil bagi 20 dan sisa 47.
1987 = 97 . 20 + 47
( ii ) – 22 dibagi dengan 3 memberikan hasil bagi – 8 dan sisa 2 :
-22 = 3 ( – 8 ) + 2
Tetapi – 22 = 3 ( – 7 ) – 1 salah, karena r = – 1 tidak memenuhi syarat
0 ≤ r ≤ n.
Pembagi Bersama Terbesar ( PBB )
Misalkan a dan b adalah dua buah bilangan bulat tidak nol pembagi bersama terbesar ( PBB – Greatest Common Divisor atau GCD ) dari a dan b adalah bilangan bulat terbesar d sedemikian sehingga d | a dan d | b. Dalam hal ini kita nyatakan bahwa PBB ( a, b ) = d.
Contoh :
Faktor Pembagi 45 : 1, 3, 5, 9, 15, 45
Faktor Pembagi 36 : 1, 2, 3, 4, 9, 12, 18, 36
Faktor Pembagi bersama dari 45 dan 36 PBB ( 45, 36 ) = 9