pengantar
Anda adalah seorang teman kurator untuk sebuah museum seni, yang baru-baru ini senang mendapatkan seni modern dari empat seniman ( beberapa di antaranya mungkin memberi kurator nol karya seni, bajingan muda ). Karena ini adalah seni modern, semua karya seniman yang ada terlihat persis sama. Teman Anda ingin menggunakan komputer untuk membantu memutuskan urutan penempatan potongan-potongan ini.
Persyaratan Program
Program Anda harus mengambil lima bilangan bulat (diteruskan ke fungsi atau diinput melalui stdin (atau yang lainnya)). Empat yang pertama adalah jumlah lukisan yang disediakan oleh masing-masing dari empat seniman. Nilai terakhir adalah indeks permutasi i
(dihitung dari 1, bukan 0). Kurator ingin melihat i
permutasi ke-3 dengan urutan leksikografis dari lukisan-lukisan tersebut.
Program Anda harus menampilkan permutasi ini dalam format apa pun yang masuk akal: misalnya abbccd
atau [0 1 1 2 2 3]
. Waktu kerja untuk input yang berjumlah kurang dari sepuluh lukisan harus memakan waktu kurang dari satu jam (semoga ini tidak menjadi masalah).
Anda tidak diizinkan untuk menggunakan fungsi bawaan untuk mengerjakan permutasi
Contohnya
Input: 0 1 2 0 2
Mengingat bahwa kita memiliki satu lukisan oleh seniman B dan dua oleh seniman C (dan mereka semua terlihat sama), permutasi dalam urutan leksikografis adalah:
['bcc', ' cbc ', 'ccb']
Permutasi yang disorot akan menjadi output yang benar, karena ini adalah yang kedua dalam urutan leksikografis.
Input: 1 2 0 1 5
['abbd', 'abdb', 'adbb', 'babd', ' badb ', 'bbad', 'bbda', 'bdab', 'bdba', 'dabb', 'dbab', 'dbab', 'dbba']
Pengujian
Berikut ini beberapa tes yang harus benar.
1 2 4 1 5 - ABBDCCCC
2 2 3 1 86 - ABBCACDC
4 1 2 0 24 - AACACBA
1 4 3 2 65 - ABBCBBDCDC
Sepotong kode pendek dalam Python3 yang seharusnya secara acak menghasilkan input dan output tersedia di sini (tidak berlaku untuk entri, ini menggunakan impor permutasi Python):
from itertools import permutations
from random import randint
a,b,c,d,n = randint(1,2),randint(1,2),randint(1,3),randint(1,3),randint(1,15)
print(str(a) + " " + str(b) + " " + str(c) + " " + str(d) + " " + str(n) + " - " + str(sorted(set([''.join(p) for p in permutations(a * "a" + b * "b" + c * "c" + d * "d")]))[n-1]))
Papan angka
Optimizer - CJam - 39 - Confirmed - Bruteforce
EDC65 - JavaScript - 120 - Confirmed - Bruteforce
Jakube - Python2 - 175 - Confirmed - Algorithmic
sumber
{:A.a.{~97+[:I.}:
valid J dan berfungsi, tetapi digunakanA.
untuk sebagian besar pekerjaan, jadi itu tidak valid. Jika Anda bisa menulis fungsi yang menggantikanA.
dan menggantikannya dalam fungsi ini, Anda akan memiliki jawaban yang valid.{:A.[:I.}:
... Masalahnya adalah itu, tapi saya masih berpikirA.
itu tidak valid: jsoftware.com/help/dictionary/dacapdot.htmJawaban:
Python 2:
175163 karakterIni bukan jawaban golf yang serius. Dengan algoritma yang berbeda saya mencapai 138 byte. Hanya ingin memposting ini di sini, karena tidak menggunakan kekerasan. Kompleksitas adalah Theta (gambar #).
Pemakaian:
edit:
Algoritma yang sama, hanya beberapa bermain golf: jangan mengimpor metode faktorial dan sedikit perubahan dalam urutan perhitungan.
Terjemahan Pyth: 61 karakter
Tidak ada yang istimewa di sini, terjemahan tepat dari kode python saya. Terlalu lama. Saya terlalu banyak menggunakan hal-hal yang jelek (panjang). 9 huruf pertama saja adalah definisi faktorial.
Juga hal-hal seperti
Q[j]-=1
terlalu lama:XQNt@QN
(1 karakter lebih dari Python !!!)Pemakaian:
Cobalah di sini: Pyth Compiler / Executor . Nonaktifkan mode debug dan gunakan
[2, 2, 3, 1, 86]
sebagai input.sumber
from math import*
luar fungsi. Menambahkan Anda ke leaderboard!CJam,
50 4339 byteIni bisa bermain golf banyak.
Mengambil input dari STDIN dalam format berikut:
Keluaran lukisan. Misalnya untuk input di atas:
Cobalah online di sini
Perhatikan bahwa kompiler online menyerah untuk ukuran lukisan yang lebih besar. Anda harus mencoba input yang lebih besar pada versi Java
sumber
JavaScript (ES6) 120
138 147Sebagai fungsi dengan lima parameter yang diperlukan, output melalui konsol.
Menggunakan simbol 0,1,2,3. Saya menghitung total simbol, lalu membangun dan memeriksa setiap nomor basis 4 yang memiliki jumlah digit yang diperlukan. Angka dengan angka yang salah dari digit apa pun akan dibuang.
Catatan: dengan JavaScript 32 bit integer ini berfungsi hingga 15 lukisan.
Sunting Lebih Pendek (hindari .toString) dan lebih cepat (kondisi keluar yang dimodifikasi). Waktu untuk setiap tes di bawah 1 detik.
Edit2 tidak ada perubahan algoritma, pegolf lagi (lekukan ditambahkan agar mudah dibaca)
Tidak Disatukan dan tidak perlu FireFox
Uji di konsol FireBug / FireFox
Keluaran
sumber
Pyth , 20
Coba di sini.
Input dalam bentuk daftar Python, mis
[1, 2, 4, 1, 5]
Output juga dalam bentuk daftar Python, misalnya
[0, 1, 1, 3, 2, 2, 2, 2]
untuk input di atas.Solusinya adalah kekerasan, dan membutuhkan waktu sekitar 10 detik, kasus terburuk, pada mesin saya.
Bagaimana itu bekerja:
sumber