Spesies angsa yang dikenal sebagai Alex A dikenal berada di kisi-kisi segitiga yang terdiri dari 64 sel:
(Gambar diambil dari masalah Project Euler yang tidak terkait ini .)
Kami akan label setiap sel dengan angka 0
untuk 63
mulai dari baris atas dan kemudian bergerak dari kiri ke kanan pada setiap baris di bawah itu. Jadi sel atas 0
dan sel kanan bawah 63
.
Setiap sel memiliki tiga batas. Kami dapat memberi label pada setiap perbatasan dalam bentuk di a,b
mana a
dan b
merupakan jumlah sel yang berbagi perbatasan itu. Misalnya, batas antara sel 0
dan 2
akan dipanggil 0,2
atau 2,0
(tidak masalah urutan apa yang Anda masukkan).
Sistem pelabelan untuk batas di tepi grid berbeda, karena sel di tepi grid memiliki batas yang tidak dibagikan dengan sel lain. Jika perbatasan hanya bagian dari satu sel, kami akan menggunakan surat itu X
. Misalnya, tiga perbatasan sel 0
yang 0,2
, 0,X
, dan 0,X
.
Beberapa sel mengandung angsa . Namun, angsa-angsa ini akan dibunuh oleh rubah jahat (yang berasal dari luar perbatasan grid) jika Anda tidak melindungi mereka. Dan jika semua angsa mati maka BrainSteel akan sedih. Karena itu kami akan menulis sebuah program yang membangun pagar di sekitar angsa untuk melindungi mereka dari rubah. Angsa harus ada dalam satu poligon pagar yang tertutup sepenuhnya. Anggaran pagar kami cukup rendah, jadi gunakan pagar sesedikit mungkin.
Deskripsi Input
Daftar angka, dipisah koma, dari 0
ke 63
, mewakili sel yang mengandung angsa. Contoh:
6,12
Deskripsi Output
Daftar perbatasan yang perlu memiliki pagar dibangun di atasnya untuk melindungi angsa dengan sukses. Ini harus menjadi pagar sekecil mungkin. Contoh:
5,6 6,7 11,12 12,13
sumber
Jawaban:
C #, 530 byte
Selesaikan program C #, ambil input sebagai satu baris dari STDIN, dan output satu baris ke STDOUT, dengan trailing "".
Ini agak lama ... dan memiliki terlalu banyak pengulangan x / y / z, tapi saya belum bisa menguranginya menjadi sesuatu yang masuk akal sejauh ini, dan memiliki ujian dalam 2 jam, mungkin akan kembali ke besok.
Diagram ini menjelaskan sebagian besar dari apa yang terjadi.
Ketahuilah bahwa karena kita tidak dapat memiliki bagian 0-lebar, "segi enam" selalu akan menjadi bentuk termurah (dan memiliki manfaat memberi angsa ruang maksimum untuk bergerak).
Program ini bekerja dengan terlebih dahulu menerjemahkan semua indeks sel input ke dalam x / y / z coords, dan menemukan min / max masing-masing x / y / z.
Selanjutnya, ia melewati setiap indeks sel, dan memeriksa apakah itu cocok dengan 'segi enam' yang telah kami jelaskan. Jika ya maka ia memeriksa apakah ada di salah satu tepi ekstrim batas (yaitu x = xmin, atau y = ymax) dan menambahkan tepi yang sesuai jika itu. Itu harus bekerja di luar indeks tepi sebelahnya. Untuk x dan z, kami hanya menambah / mengurangi mereka seperti yang kami inginkan, dan kemudian menggunakan rumus berikut:
Perhatikan bahwa "paritas" selalu berubah, dan bahwa Anda tidak terlibat. Untuk y, kita tidak perlu mengubah apa pun, tetapi kodenya agak berantakan karena harus melakukan pemeriksaan "segitiga" untuk mendeteksi apakah sel di sebelahnya harus "X" atau tidak.
Contoh solusi (Sel dengan angsa hanya dari tiga sudut):
Kode lebih rapi dengan komentar:
sumber
using System;
.using Q=System.Console;Q.Write();Q.ReadLine()
(45 Bytes) versus saran Andausing System;Console.Write();Console.ReadLine()
(47 Bytes).i
,x
,y
,z
, danp
ke 0.