Definisi
Dari uraian tentang OEIS A006345 :
Untuk menemukan
a(n)
, pertimbangkan a1
atau a2
. Untuk masing-masing, cari sufiks berulang yang terpanjang, yaitu, untuk masing-masinga(n)=1,2
, temukan urutan terpanjangs
dengan properti yanga(1),...,a(n)
diakhiri dengan urutan tersebutss
. Gunakan digit yang menghasilkan akhiran yang lebih pendek.a(1) = 1
.
Contoh Berolahraga
a(1)=1
.
Jika a(2)=1
, kita akan memiliki urutan di 1 1
mana substring terlipat ganda dari akhir berada 1
. Jika a(2)=2
sebaliknya, maka itu akan menjadi substring kosong. Oleh karena itu a(2)=2
.
Kapan n=6
, kami memilih antara 1 2 1 1 2 1
dan 1 2 1 1 2 2
. Dalam pilihan pertama, 1 2 1
digandakan secara berurutan dari akhir. Dalam pilihan kedua, itu 2
malah. Oleh karena itu, a(6)=2
.
Kapan n=9
, kami memilih antara 1 2 1 1 2 2 1 2 1
dan 1 2 1 1 2 2 1 2 2
. Pada pilihan pertama, substring berurutan terpanjang dua kali lipat adalah 2 1
, sedangkan pada pilihan kedua 1 2 2
digandakan berturut-turut di akhir. Oleh karena itu a(9)=1
.
Tugas
Diberikan n
, kembali a(n)
.
Spesifikasi
n
akan positif.- Anda dapat menggunakan 0-diindeks bukannya 1-diindeks. Jika demikian, sebutkan jawaban Anda. Juga, dalam hal ini,
n
bisa0
juga.
Testcases
Testcases diindeks 1. Namun, Anda dapat menggunakan 0-diindeks.
n a(n)
1 1
2 2
3 1
4 1
5 2
6 2
7 1
8 2
9 1
10 1
11 2
12 1
13 2
14 2
15 1
16 1
17 2
18 1
19 1
20 1
Referensi
- WolframMathWorld
- OEIS Wajib A006345
sumber
n=9
, pilihan pertama1 2 1 1 2 2 1 2 1
memiliki substring ganda2 1
di akhir.Jawaban:
Haskell,
146140137133118 bytesumber
(\x->(\s->...
? Kalau tidak, Anda bisa menulis(\x s->...
.div ...
, Anda bisa menggunakan yang lebih pendekn
. Semua perbandingan ekstra akan menghasilkan false dan tidak mengubah hasilnya.Python, 137 byte
Solusi ini menggunakan pengindeksan berbasis 0.
sumber
Jelly ,
25242220 byte2 byte berkat Dennis.
Cobalah online!
Port jawaban saya di Pyth .
sumber
Mathematica, 84 byte
sumber
Jelly ,
3029282724 byteCobalah online! atau verifikasi semua kasus uji .
sumber
MATL , 34 byte
Cobalah online! atau verifikasi semua kasus uji .
Penjelasan
sumber
Python 2, 94 byte
Menggunakan pengindeksan berbasis 0. Uji di Ideone .
sumber
Pyth , 26 byte
Suite uji.
Penjelasan
Kapan
n = 6
, kami memilih antara1 2 1 1 2 1
dan1 2 1 1 2 2
.Kami menghasilkan dua kemungkinan ini, dan kemudian melihat sufiks mereka.
Untuk yang pertama, akhiran adalah:
1
,2 1
,1 2 1
,1 1 2 1
,2 1 1 2 1
,1 2 1 1 2 1
.Kami memfilter sufiks berlipat ganda dengan memeriksa apakah sufiksnya sama setelah memutarnya dengan panjang dibagi 2 (ternyata pemeriksaan ini tidak sempurna, karena menegaskan
1
dan2
juga).Kami mengambil akhiran dua kali lipat terakhir dan kemudian panjangnya.
Kami kemudian memilih kemungkinan yang sesuai dengan panjang minimum yang dihasilkan di atas.
Kemudian kita lanjutkan ke nilai selanjutnya dari
n
.Untuk tujuan program ini, pemain golflah yang menghasilkan array yang terbalik.
sumber
Pyth,
4629 byteMengambil beberapa inspirasi dari jawaban Pyth yang sangat bagus dari @Leaky Nun. Mencoba melihat apakah ada cara yang lebih pendek menggunakan string. Masih 3 byte pendek!
Anda bisa mencobanya di sini .
sumber
u
ce bukannya for-loop secara eksplisit menghemat 4 byteRetina ,
5142 byte9 byte berkat Martin Ender.
Cobalah online!
Port jawaban ini .
sumber
Perl, 40 byte
Panjang kode 39 byte dan membutuhkan
-p
sakelar ( +1 byte).Loop diilhami oleh solusi Perl pada yang relevan halaman OEIS yang , meskipun saya muncul secara independen dengan ekspresi reguler.
Uji di Ideone .
sumber
JavaScript (ES6), 84
Basis indeks 0
Kurang golf
Uji
sumber