Latar Belakang
Sebuah urutan Davenport-Schinzel memiliki dua parameter bilangan bulat positif d
dan n
. Kami akan menunjukkan set semua urutan Davenport-Schinzel untuk parameter yang diberikan oleh DS(d,n)
.
Pertimbangkan semua urutan dari alam nomor 1
untuk n
, inklusif, yang memenuhi:
- Tidak ada dua angka berurutan dalam urutan yang identik.
- Tidak ada urutan (tidak harus berturut-turut) dengan panjang lebih besar dari
d
, yang bergantian antara dua angka yang berbeda.
Biarkan L
menunjukkan panjang maksimum urutan seperti itu (diberikan d
dan n
). Kemudian, DS(d,n)
adalah himpunan semua urutan tersebut dengan panjang L
.
Beberapa contoh mungkin membantu. Mari d = 4
, n = 3
. Urutan terpanjang yang mungkin dengan kendala ini miliki L = 8
. Jadi yang berikut ini adalah anggota dari DS(4,3)
:
[1, 2, 1, 3, 1, 3, 2, 3]
Tidak ada angka identik yang berurutan dan ada panjang berurutan 4
, tetapi tidak lagi:
1 2 1 2
1 2 1 2
1 3 1 3
1 3 1 3
2 3 2 3
2 3 2 3
1 3 1 3
1 3 1 3
Contoh berikut tidak ada di DS(4,3)
:
[1, 2, 2, 3, 1, 3, 2, 3] # Two consecutive 2's.
[1, 2, 1, 3, 1, 3, 2, 1] # Contains alternating subsequences of length 5.
[1, 2, 1, 3, 1, 3, 2] # Longer valid sequences for d = 4, n = 3 exist.
Untuk informasi lebih lanjut, lihat MathWorld dan OEIS dan referensi yang mereka daftarkan.
Tantangan
Diberi dua bilangan bulat positif, n
dan d
, menghasilkan urutan Davenport-Schinzel di DS(d,n)
. Perhatikan bahwa ini umumnya tidak unik, jadi hasilkan setiap hasil yang valid.
Anda dapat menulis program atau fungsi, mengambil input melalui STDIN (atau alternatif terdekat), argumen baris perintah atau argumen fungsi, dan mengembalikan hasilnya dari fungsi atau mencetaknya ke STDOUT (atau alternatif terdekat).
Anda dapat menggunakan string atau format daftar yang mudah digunakan untuk output.
Ini adalah kode golf, jadi pengiriman terpendek (dalam byte) menang.
Panjang Urutan
Karena urutannya tidak unik, tidak banyak digunakan untuk contoh individu dalam tantangan ini. Namun, dua masalah validitas umum cukup mudah untuk memeriksa output, jadi pertanyaan utamanya adalah apakah urutannya memiliki panjang yang tepat (atau ada urutan yang lebih panjang yang valid). Oleh karena itu, berikut adalah daftar 1 yang diketahui L
diberikan d
dan n
:
\
d\n 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
\-----------------------------------------------------------
1 | 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
3 | 1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39
4 | 1 4 8 12 17 22 27 32 37 42 47 53 58 64 69 75 81 86 92 98
5 | 1 5 10 16 22 29 ...
6 | 1 6 14 23 34 ...
7 | 1 7 16 28 41 ...
8 | 1 8 20 35 53 ...
9 | 1 9 22 40 61 ...
10 | 1 10 26 47 73 ...
Anda tidak boleh meng-hardcode informasi apa pun dari tabel ini ke dalam kiriman Anda.
1 Tabel ini berasal dari tahun 1994, jadi mungkin ada lebih banyak kemajuan sejak saat itu, tetapi saya ragu bahwa pengiriman apa pun akan dapat menangani entri yang lebih besar dalam tabel ini dalam jumlah waktu yang wajar.
sumber