pengantar
Sebuah disk adalah wadah linear dengan blok diindeks 0
melalui size-1
.
File adalah daftar nama indeks blok yang digunakan oleh file itu.
Contoh filesystem diekspresikan seperti ini:
15 ALPHA=3,5 BETA=11,10,7
"Disk memiliki 15 blok, blok pertama file ALPHA adalah blok disk di indeks 3 ..."
Peta disk dapat digambar seperti ini:
Block Index 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14
Contents | | | |A0 | |A1 | |B2 | | |B1 |B0 | | | |
Disk dianggap defrag ketika semua file di dalamnya disimpan secara berdekatan.
TUJUAN ANDA:
Memancarkan urutan langkah hukum terpendek yang akan mendefrag disk yang diberikan.
Pergerakan Hukum
Langkah berisi tiga informasi: nama file, indeks blok dalam file yang akan dipindahkan, dan indeks blok disk yang dipindahkannya.
Sebagai contoh
ALPHA:1>4
"Pindahkan blok 1 dari file ALPHA untuk memblokir 4 disk."
Setelah langkah ini, sistem file contoh sekarang ini
15 ALPHA=3,4 BETA=11,10,7
Block Index 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14
Contents | | | |A0 |A1 | | |B2 | | |B1 |B0 | | | |
Blok disk yang sebelumnya dihuni secara implisit dihapus. Secara setara, Anda dapat melihat ini sebagai menukar dua blok pada disk tetapi salah satu blok dalam swap harus kosong .
Data tidak dapat dihancurkan. File tidak dapat berbagi blok pada tahap apa pun dan gerakan harus berada dalam jangkauan disk. Bergerak berikut ini ilegal : ALPHA:0>10
(dimiliki oleh BETA), ALPHA:3>0
(tidak ada blok seperti itu di ALPHA), ALPHA:0>-1
(tidak ada indeks disk seperti itu), ALPHA:0>15
(indeks disk terlalu besar)
Contoh 1
Mengatasi contoh di atas secara penuh.
ALPHA:0>4
BETA:0>9
BETA:2>11
File tidak harus bersebelahan dalam solusi, hanya terus menerus dalam diri mereka.
Contoh 2
Ini kasus yang lebih terbatas
Memasukkan:
10 A=1,2,3 B=6,7,8 C=4,5,0
Keluaran:
B:2>9
B:1>8
B:0>7
C:2>6
Kemajuan sistem file ini adalah:
Block Index 00 01 02 03 04 05 06 07 08 09
Contents |C2 |A0 |A1 |A2 |C0 |C1 |BO |B1 |B2 | |
|C2 |A0 |A1 |A2 |C0 |C1 |BO |B1 | |B2 |
|C2 |A0 |A1 |A2 |C0 |C1 |BO | |B1 |B2 |
|C2 |A0 |A1 |A2 |C0 |C1 | |B0 |B1 |B2 |
| |A0 |A1 |A2 |C0 |C1 |C2 |B0 |B1 |B2 |
Cara alternatif untuk mendefrag ini adalah dengan C:2>9
kemudian A
menurunkan langkah, lalu C
menjatuhkan langkah, lalu lakukan C:2>5
tetapi ini tidak akan menjadi solusi hukum karena mengandung lebih banyak gerakan daripada alternatif .
Perwakilan
Anda dapat menggunakan representasi apa pun untuk input selama cukup dekat dengan string dasar. Bergantung pada bahasa Anda, input ke contoh pertama mungkin dinotasikan sebagai
"15 ALPHA=3,5 BETA=11,10,7"
[15," ","ALPHA","=",3,",",5," ","BETA","=",11,",",10,",",7]
(15,(("ALPHA",(3,5)),("BETA",(11,10,7))))
etc
Demikian pula, hasilnya bisa apa saja yang nyaman untuk bahasa Anda sebagai log karena dicetak, dapat dibaca oleh manusia, dan mewakili daftar langkah hukum yang diatur, setiap gerakan dijelaskan oleh 1) nama file, 2) file-blok-indeks , 3) indeks-disk-blok-baru
"ALPHA:1>6 BETA:2>9"
(0=>(0=>"ALPHA",1=>"1",2=>"6"), 1=>(0=>"BETA",1=>"2",2=>"9"))
["ALPHA",1,6,"BETA",2,9]
etc
Persyaratan
Kode Anda harus menerima disk ukuran apa pun, dan jumlah dan ukuran file apa pun.
Input yang tidak menjelaskan status sistem file awal yang legal dapat menyebabkan perilaku yang tidak terdefinisi.
Kode Anda harus menghasilkan solusi pemindahan terpendek , untuk setiap input yang terdefinisi dengan baik.
Semua gerakan yang Anda hasilkan harus legal; sistem file harus dalam keadaan valid setelah menerapkan setiap langkah yang Anda hasilkan.
Kode Anda harus diakhiri untuk semua input yang valid, yaitu kode tidak boleh macet dalam satu lingkaran, sistem file harus dalam keadaan yang jelas baru setelah setiap gerakan diterapkan.
Di mana ada lebih dari satu solusi terpendek, solusi apa pun dapat dipilih sebagai valid.
Kode terpendek menang. Silakan kirim setidaknya satu input contoh nontrivial baru dan hasilnya dengan kode Anda.
Jawaban:
Python 3 , 295 byte
Cobalah online!
Kasus uji lain
Versi tidak disatukan .
sumber