Sesuai permintaan Luke dan penambahan Peter Taylor untuk tantangan ini.
pengantar
Semua orang tahu permainan tic-tac-toe, tetapi dalam tantangan ini, kami akan memperkenalkan sedikit twist. Kami hanya akan menggunakan salib . Orang pertama yang menempatkan tiga umpan silang berturut-turut kalah. Fakta yang menarik adalah bahwa jumlah maksimum salib sebelum seseorang kalah, sama dengan 6 :
X X -
X - X
- X X
Itu berarti bahwa untuk papan 3 x 3, jumlah maksimum adalah 6 . Jadi untuk N = 3, kita perlu output 6.
Contoh lain, untuk N = 4, atau papan 4 x 4:
X X - X
X X - X
- - - -
X X - X
Ini adalah solusi optimal, Anda dapat melihat bahwa jumlah maksimum salib sama dengan 9 . Solusi optimal untuk papan 12 x 12 adalah:
X - X - X - X X - X X -
X X - X X - - - X X - X
- X - X - X X - - - X X
X - - - X X - X X - X -
- X X - - - X - - - - X
X X - X X - X - X X - -
- - X X - X - X X - X X
X - - - - X - - - X X -
- X - X X - X X - - - X
X X - - - X X - X - X -
X - X X - - - X X - X X
- X X - X X - X - X - X
Ini menghasilkan 74 .
Tugas
Tugas Anda adalah menghitung hasilnya secepat mungkin. Saya akan menjalankan kode Anda pada test case 13
. Ini akan dilakukan 5 kali dan kemudian rata-rata diambil dari run time. Itu adalah skor akhir Anda. Semakin rendah, semakin baik.
Uji kasus
N Output
1 1
2 4
3 6
4 9
5 16
6 20
7 26
8 36
9 42
10 52
11 64
12 74
13 86
14 100
15 114
Informasi lebih lanjut dapat ditemukan di https://oeis.org/A181018 .
Aturan
- Ini adalah kode tercepat , jadi pengiriman tercepat menang!
- Anda harus menyediakan program lengkap .
- Harap berikan juga bagaimana saya harus menjalankan program. Saya tidak terbiasa dengan semua bahasa pemrograman dan bagaimana mereka bekerja, jadi saya perlu sedikit bantuan di sini.
- Tentu saja, kode Anda perlu menghitung hasil yang benar untuk setiap kasus uji.
Pengajuan:
- feersum (C ++ 11): 28s
- Peter Taylor (Jawa): 14m 31s
Jawaban:
C ++ 11, 28s
Ini juga menggunakan pendekatan pemrograman dinamis berdasarkan baris. Butuh 28 detik untuk menjalankan argumen 13 untuk saya. Trik favorit saya adalah
next
fungsi yang menggunakan sedikit bashing untuk menemukan pengaturan baris leksikografis berikutnya yang memuaskan topeng dan aturan no-3-in-a-row.Instruksi
g++ -std=c++11 -march=native -O3 <filename>.cpp -o <executable name>
<executable name> <n>
sumber
Java, 14m 31s
Ini pada dasarnya adalah program yang saya posting ke OEIS setelah menggunakannya untuk memperpanjang urutan, jadi ini adalah referensi yang baik untuk dikalahkan oleh orang lain. Saya telah men-tweak untuk mengambil ukuran papan sebagai argumen baris perintah pertama.
Simpan ke
A181018.java
; kompilasi sebagaijavac A181018.java
; jalankan sebagaijava A181018 13
. Di komputer saya, dibutuhkan sekitar 20 menit untuk menjalankan input ini. Mungkin akan layak untuk diparalelkan.sumber
n=16
; Saya memperkirakan bahwa itu akan memakan waktu sekitar satu bulann=17
, jadi saya tidak mencoba menjalankannya untuk itu. Penggunaan memori juga menjadi gangguan utama. (PS Saat ini saya menggunakan 2 dari 4 core saya untuk tantangan pemrograman non-PPCG: azspcs.com/Contest/Tetrahedra/Standings )