Latar Belakang
Pertimbangkan rantai batang (tertutup), yang masing-masing memiliki panjang bilangan bulat. Berapa banyak polyomino bebas lubang yang bisa Anda bentuk dengan rantai tertentu? Atau dengan kata lain, berapa banyak poligon yang tidak berpotongan sendiri yang berbeda dengan sisi yang selaras sumbu yang dapat Anda bentuk dengan rantai tertentu?
Mari kita lihat sebuah contoh. Pertimbangkan rantai tertentu yang terdiri dari 8 batang dengan panjang 1 dan 2, yang dapat kita wakili [1, 1, 2, 2, 1, 1, 2, 2]
. Hingga rotasi dan terjemahan, hanya ada 8 kemungkinan polyomino (kami menghitung refleksi yang berbeda):
Batang pertama ini berwarna biru tua, dan kemudian kita melintasi poligon dalam arti berlawanan arah jarum jam .
Perasaan rotasi tidak mempengaruhi hasil dalam contoh di atas. Tapi mari kita pertimbangkan rantai lain [3, 1, 1, 1, 2, 1, 1]
, yang menghasilkan 3 polyomino berikut:
Perhatikan kami melakukannya tidak menyertakan refleksi dari polyomino terakhir, karena itu akan memerlukan traverse searah jarum jam.
Jika kita memiliki rantai yang lebih fleksibel dengan panjang yang sama [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
, kita sebenarnya dapat membentuk kedua refleksi di antara beberapa polyonino lainnya, dengan total 9:
Tantangan
Diberikan deskripsi rantai, sebagai array atau sejenisnya, tentukan jumlah polyomino berbeda yang dapat Anda bentuk (hingga rotasi dan terjemahan) dengan menggunakan batang sesuai urutan sambil berkeliling di sekeliling perimeter dalam arti berlawanan arah jarum jam.
Silakan tulis program lengkap dan sertakan perintah untuk dikompilasi (jika ada) dan jalankan kode Anda dari baris perintah. Harap sertakan juga tautan ke kompiler / juru bahasa gratis untuk bahasa Anda.
Program Anda harus membaca input dari STDIN. Baris pertama akan berisi integer M . Baris M berikutnya akan menjadi kasus uji, yang masing-masing akan menjadi daftar panjang batang yang dipisahkan ruang. Program Anda harus mencetak garis M ke STDOUT, yang masing-masing terdiri dari bilangan bulat tunggal - jumlah poliomino berbeda yang dapat dibentuk.
Anda hanya harus menggunakan utas tunggal.
Program Anda tidak boleh menggunakan lebih dari 1 GB memori kapan saja. (Ini bukan batas yang sepenuhnya ketat, tapi saya akan memantau penggunaan memori Anda yang dapat dieksekusi, dan membunuh proses apa pun yang secara konsisten menggunakan lebih dari 1 GB, atau lonjakan secara signifikan di atasnya.)
Untuk mencegah jumlah pra-komputasi yang berlebihan, kode Anda tidak boleh lebih dari 20.000 byte, dan Anda tidak boleh membaca file apa pun.
Anda juga harus tidak mengoptimalkan terhadap kasus uji tertentu yang dipilih (misalnya dengan meng-hardcoding hasil mereka). Jika saya menduga Anda melakukannya, saya berhak untuk membuat set benchmark baru. Set tes acak, sehingga kinerja program Anda pada mereka harus representatif untuk kinerjanya pada input sewenang-wenang. Satu-satunya asumsi yang Anda boleh buat adalah bahwa jumlah panjang batang adalah genap.
Mencetak gol
Saya telah menyediakan set tolok ukur untuk rantai N = 10, 11, ..., 20 batang. Setiap set tes berisi 50 rantai acak dengan panjang antara 1 dan 4 inklusif.
Skor utama Anda adalah N terbesar di mana program Anda menyelesaikan seluruh rangkaian tes dalam waktu 5 menit (pada mesin saya, di bawah Windows 8). Tie breaker adalah waktu yang sebenarnya diambil oleh program Anda pada set tes tersebut.
Jika ada yang mengalahkan set tes terbesar, saya akan terus menambahkan yang lebih besar.
Uji Kasus
Anda dapat menggunakan test case berikut untuk memeriksa kebenaran implementasi Anda.
Input Output
1 1 0
1 1 1 1 1
1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 3
1 1 1 1 1 1 1 1 1 1 9
1 1 1 1 1 1 1 1 1 1 1 1 36
1 1 1 1 1 1 1 1 1 1 1 1 1 1 157
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 758
1 1 2 2 1 1 2 2 8
1 1 2 2 1 1 2 2 1 1 23
1 1 2 2 1 1 2 2 1 1 2 2 69
1 2 1 2 1 2 1 2 3
1 2 1 2 1 2 1 2 1 2 1 2 37
1 2 3 2 1 2 3 2 5
1 2 3 2 1 2 3 2 1 2 3 2 23
3 1 1 1 2 1 1 3
1 2 3 4 5 6 7 1
1 2 3 4 5 6 7 8 3
1 2 3 4 5 6 7 8 9 10 11 5
2 1 5 3 3 2 3 3 4
4 1 6 5 6 3 1 4 2
3 5 3 5 1 4 1 1 3 5
1 4 3 2 2 5 5 4 6 4
4 1 3 2 1 2 3 3 1 4 18
1 1 1 1 1 2 3 3 2 1 24
3 1 4 1 2 2 1 1 2 4 1 2 107
2 4 2 4 2 2 3 4 2 4 2 3 114
Anda menemukan file input dengan ini di sini .
Papan peringkat
User Language Max N Time taken (MM:SS:mmm)
1. feersum C++ 11 19 3:07:430
2. Sp3000 Python 3 18 2:30:181
sumber
Jawaban:
C ++ 11
Pembaruan: Menambahkan baris pertama
c
yang pecah lebih awal jika jaraknya terlalu jauh dari titik asal (yang merupakan seluruh tujuan variabelrlen
, tetapi saya lupa menuliskannya dalam versi pertama). Saya mengubahnya untuk menggunakan memori jauh lebih sedikit, tetapi dengan biaya waktu. Sekarang memecahkan N = 20 hanya di bawah 5 menit untuk saya.Kompilasi dengan
sumber
#define
s thoPython 3 (dengan PyPy ) - N = 18
Jalankan dengan
./pypy <filename>
.Ini adalah implementasi referensi yang saya tulis ketika membahas pertanyaan dengan Martin. Itu tidak dibuat dengan kecepatan dalam pikiran dan cukup hacky, tetapi harus memberikan dasar yang baik untuk memulai sesuatu.
N = 18 membutuhkan sekitar 2,5 menit pada laptop sederhana saya.
Algoritma
Rotasi diperiksa dengan mengubah setiap bentuk menjadi serangkaian
F
untuk maju,A
untuk berbelok berlawanan arah jarum jam danC
untuk mengubah arah jarum jam pada setiap titik kisi pada batas bentuk - Saya menyebutnya string sudut . Dua bentuk identik secara rotasi jika string sudutnya adalah permutasi siklik. Daripada selalu memeriksa ini dengan membandingkan dua string sudut secara langsung, ketika kami menemukan bentuk baru, kami mengonversi ke bentuk kanonik sebelum menyimpan. Ketika kita memiliki kandidat baru, kita beralih ke bentuk kanonik dan memeriksa apakah kita sudah memiliki ini (sehingga mengeksploitasi hashing, daripada iterasi melalui seluruh set).String sudut juga digunakan untuk memeriksa bahwa bentuknya dibentuk berlawanan arah jarum jam, dengan memastikan bahwa jumlah
A
s melebihi jumlahC
s dengan 4.Simpang-sendiri diperiksa secara naif dengan menyimpan setiap titik kisi pada batas bentuk, dan melihat apakah suatu titik dikunjungi dua kali.
Algoritma inti sederhana, menempatkan batang pertama ke kanan, lalu mencoba semua kemungkinan untuk batang yang tersisa. Jika batang mencapai titik yang terlalu jauh dari titik asal (yaitu jumlah panjang batang yang tersisa kurang dari jarak titik Manhattan dari titik asal), maka kami sebelum waktunya berhenti mencari subtree itu.
Pembaruan (terbaru lebih dulu)
sumber