Olimpiade Sains Provinsi (OSP) 2017 - Komputer, Nomor 46
GRID BERPOLA
Diberikan grid berukuran N baris dan M kolom. Dari baris teratas hingga terbawah dinomori dengan baris 1 hingga baris N, dan dari kolom terkiri hingga terkanan dinomori dengan kolom 1 hingga kolom M. Setiap petak pada grid diberi nomor dengan aturan pola berikut. Dimulai dari lapisan terluar grid diberi nomor 1, lapisan berikutnya yang lebih dalam diberi nomor 2, lapisan berikutnya diberi nomor 3, dan seterusnya. Berikut adalah contoh grid berukuran 7 baris dan 8 kolom yang telah diberi nomor.
Diberikan nilai N, M, X, dan Y. Anda diminta untuk membuat sebuah program yang menentukan nomor berapa yang ada di baris ke-X dan kolom ke-Y dari grid berukuran N baris dan M kolom.
Batasan :
1 N, M
10^9
1 X
N
1 Y
M
Format Input :
Sebuah baris yang berisi 4 bilangan bulat bertururt-turut yakni N, M, X, dan Y.
Format Output :
Sebuah baris yang berisi sebuah bilangan bulat yang menandakan nomor berapa yang ada di baris ke-X dan kolom ke-Y dari grid berukuran N baris dan M kolom.
Sample input dan output :
| 7 8 1 1 | 1 |
| 7 8 3 6 | 3 |
| 7 8 6 5 | 2 |
| 7 8 4 5 | 4 |
| 7 8 7 8 | 1 |
| 999 999 500 500 | 500 |
2 jawaban
Mamat Rahmat8 tahun lalu
TOKI 2012, IF ITB 2012. http://olimpiadeinformatika.com
8
Berikut adalah gambar yang hilang dari deskripsi soal
Perhatikan bahwa nomor pada sel adalah jarak terpendek menuju ke luar (kiri/kanan/atas/bawah). Jika sel berada pada baris x kolom y
- Jarak ke atas adalah x
- Jarak ke bawah adalah N-x+1
- Jarak ke kiri adalah y
- Jarak ke kanan adalah M-x+1
var
M, N, x, y : longint;
begin
readln(M, N, x, y);
// asumsikan kita memiliki fungsi min(a,b) yang akan mengembalikan nilai terkecil diantara a dan b
writeln(min(min(x, N-x+1), min(y, M-y+1)))
end;
Khun Ran7 tahun lalu
1
Pertama-tama mari membagi grid menjadi 4 bagian, yakni
Bagian atas-kanan (sebut saja kuadran 1)
Bagian atas-kiri (kuadran 2)
Bagian bawah-kiri (kuadran 3)
Bagian bawah-kanan (kuadran 4)
Pada kuadran satu, maka nilai dari grid adalah nilai minimum dari x dan y. Sedangkan untuk kuadran lainnya, kita hanya perlu merefleksikannya secara vertikal, horizontal, ataupun keduanya. Mengapa boleh seperti itu? karena grid ini simetris secara horizontal dan vertikal.
|
program gridBerpola; else min:=x; |
Algoritma ini sudah saya uji bahkan untuk n=10^17 dan m=10^17, program ini mampu memberikan output dalam hitungan milliseconds saja.
Semoga membantu :)
P. s. : Maap kontainer code snippetnya gak berfungsi
Masuk untuk menulis jawaban