Latar Belakang
Amerika Serikat memiliki kecintaan khusus pada persekongkolan - manipulasi yang disengaja dari suatu daerah pemilihan untuk memprediksi hasil pemilihan tertentu. Baru-baru ini ada kasus persekongkolan yang dibawa ke Mahkamah Agung. Gerrymandering, terutama yang terkait dengan ras, dianggap ilegal dan menghasilkan persyaratan untuk menggambar ulang garis kabupaten.
Diberikan peta persegi panjang kotamadya (array 2d), Anda akan menggambar garis distrik untuk membantu pesta Anda mendapatkan representasi terbanyak. Yaitu, Anda akan berpasangan. Setiap kota memiliki dua pihak, 0
dan 1
. Peta akan terdiri dari kotak dengan salah satu 0
atau 1
di atasnya. Ini contoh peta:
Tantangan
Anda akan mengelompokkan peta ke dalam distrik sehingga 1
partai akan mendapatkan setidaknya jumlah distrik yang ditentukan oleh Input.
Memasukkan
Input akan terdiri dari peta, jumlah distrik yang akan diundi, dan jumlah minimum distrik yang 1
harus dimenangkan oleh partai (skor minimum).
Keluaran
Outputnya akan menjadi peta kabupaten. Setiap distrik akan secara unik terdiri dari huruf besar alfabet. Ya, ini berarti tidak akan ada lebih dari 26 kabupaten.
Jika tidak ada output yang memungkinkan di mana pihak yang diinput memenangkan cukup distrik, baik:
- Cetak “Kami mencoba ...”
- Kesalahan fatal karena partai itu tidak dapat diperbaiki karena hasil pemilu
- Atau keduanya
Aturan (juga sangat penting)
- Semua distrik harus bersebelahan
- Kabupaten mungkin tidak memiliki kabupaten lain di dalamnya
- Setiap kabupaten harus memiliki setidaknya empat node di dalamnya. Masukan akan konsisten dengan aturan, artinya setidaknya akan ada
number_of_districts * 4
simpul di peta - Skor dari masing-masing pihak adalah jumlah kabupaten yang memiliki mayoritas
- Jika suatu kabupaten memiliki jumlah
0
s dan1
s yang sama, maka tidak ada pihak yang mendapat manfaat darinya - Aturan larangan normal
- Ini adalah kode-golf , jadi kode terpendek dalam byte menang.
Uji kasus
1. Input 1. Output 2. Input 2. Output 3. Input 3. Output
districts: 5 Image and map districts: 3 Image below districts: 3 fatal error
min wins: 3 min wins: 3 min wins: 3
map: map: map:
00000110000 AAAAAAAAAAA 101101 101101
10000010000 AAAAAAAAAAA 100000 100000
10010000011 AAAAAAAAAAA 011011 011011
11001110000 BBBBBBBAAAA 111111 100111
00111111000 BBBBBBBAAAA
01111111000 CCCCCDDDAAA
01111111001 CCCCCDDDAAA
01000111100 EEEEEDDDDDD
00000001000 EEEEEDDDDDD
Tentu saja, program Anda harus bekerja untuk setiap kasus uji yang valid, bukan hanya yang ini.
sumber
Jawaban:
R ,
938896858952 byteCobalah online!
Solusi
> 900> 800(nggak!)> 900 byte. Kode berfungsi sebagai berikut. Biarkan N menjadi jumlah daerah pemilihan dan M jumlah minimum kabupaten di mana 1 ingin memiliki mayoritas.Pertama, kode ini secara acak menetapkan N distrik ke berbagai kelompok. Selanjutnya, itu memperluas mereka secara acak, yaitu menambahkan kabupaten ke kelompok yang dipilih secara acak, memastikan bahwa kabupaten tersebut di sebelah kabupaten yang sudah menjadi milik kelompok itu. Dalam proses perluasan, ia lebih diutamakan dari sebuah distrik dengan mayoritas 1, jika kelompok distrik belum menjadi mayoritas penuh 1; jika grup sudah menjadi mayoritas 1, maka diutamakan untuk 0 distrik. Ini berlanjut sampai semua distrik ditugaskan.
Setiap grup di mana ada mayoritas untuk 1 pihak disimpan, dan distriknya dikunci. Jika setidaknya ada kelompok M dengan mayoritas 1, maka semuanya baik dan
kita dapat mencetak hasilnyakita dapat memeriksa apakah ada setidaknya 4 kabupaten di masing-masing kelompok. Jika cutoff 4 distrik terpenuhi, maka kita dapat dengan senang hati mencetak hasilnya. Jika tidak, kode akan mencoba menetapkan kembali distrik yang tidak dikunci ke grup sebanyak yang tersedia, yaitu N - # grup yang tersimpan.Kode mencoba beberapa kali (9 kali). Jika gagal, ini akan mengatur ulang segalanya dan mulai lagi. Ia melakukannya selama 9 kali sebelum menyerah dan mencetak "kami mencoba ...".
Jika kode tidak berhasil pada awalnya, coba lagi beberapa kali. Saya menyetel jumlah pengulangan sehingga bisa berjalan di TIO kurang dari satu menit. Namun jika ada solusi, kode ini dapat (akhirnya) menemukannya. Bagian keacakan dari algoritma memberikan probabilitas bukan nol bahwa, jika ada solusi, ia dapat menemukannya. Terbatasnya jumlah percobaan adalah satu-satunya faktor pembatas untuk sukses.
EDIT: menambahkan kontrol bahwa tidak ada kelompok kabupaten dapat sepenuhnya dikelilingi oleh yang lain, kecuali kelompok kabupaten memiliki kabupaten di tepi alun-alun yang diberikan. Saya pikir saya melewatkannya pada awalnya.
sumber
==0
dengan<1
ketika variabel itu benar-benar bilangan bulat dan positif.if...else
pernyataan, swappingc
untukas.vector
, mengubah"\n"
dengan baris baru literal, dan menggunakan fakta bahwa>
akan secara otomatis nomor memaksa untuk karakter diam-diam dan membandingkan codepoints mereka. Mungkin ada beberapa golf lain yang saya lakukan yang tidak dapat saya ingat tapi ini awal. Saya pikir ada beberapa hal lagi yang dapat kita atur tetapi saya tidak 100% yakin saya memahami kode ...