Tantangan:
Program Anda akan mengambil dua bilangan bulat n
dan k
sebagai input, dan menghasilkan bilangan bulat terkecil yang lebih besar dari (tetapi tidak sama dengan) n
yang berisi paling tidak k
kemunculan angka tersebut 5
.
Anda dapat mengasumsikan 1 ≤ k ≤ 15
dan 1 ≤ n < 10**15
.
Ini adalah tantangan waktu terbatas . Program Anda harus berjalan pada TIO untuk semua kasus uji dan selesai dalam 10 detik total.
Aturan umum:
Ini adalah kode-golf , jadi jawaban tersingkat dalam byte menang.
Jangan biarkan bahasa kode-golf mencegah Anda memposting jawaban dengan bahasa non-codegolf. Cobalah untuk memberikan jawaban sesingkat mungkin untuk bahasa pemrograman apa pun .Aturan standar berlaku untuk jawaban Anda dengan aturan I / O default , sehingga Anda diizinkan untuk menggunakan STDIN / STDOUT, fungsi / metode dengan parameter yang tepat dan tipe pengembalian, program penuh. Panggilanmu. Parameter fungsi dapat diambil dalam urutan apa pun, tetapi harap tentukan dalam jawaban Anda.
- Celah default tidak diperbolehkan.
- Anda harus menambahkan tautan dengan tes untuk kode Anda (yaitu TIO ).
- Header jawaban harus mencantumkan skor dalam byte tetapi juga total waktu yang diambil untuk semua kasus uji pada TIO
- Jika bahasa Anda tidak pada TIO, kode harus selesai jauh di bawah 10 detik pada mesin Anda sehingga Anda yakin itu cukup cepat pada komputer yang masuk akal.
- Menambahkan penjelasan untuk jawaban Anda sangat disarankan.
Kasus uji:
(n, k) -> output
(53, 2) -> 55
(55, 1) -> 56
(65, 1) -> 75
(99, 1) -> 105
(555, 3) -> 1555
(557, 1) -> 558
(5559, 3) -> 5565
(6339757858743, 5) -> 6339757859555
(99999999999999, 15) -> 555555555555555
Contoh Program:
Program ini benar.
(n, k) = (45, 1)
adalah50
? Beberapa jawaban salah.Jawaban:
R + stringr,
858476 byte, .062 pada TIOCobalah online!
-1 byte terima kasih kepada Robert S.
-8 byte terima kasih kepada Giuseppe.
Solusi rekursif sederhana adalah dengan menambah 1 hingga jawabannya ditemukan, tetapi ini tidak akan memenuhi batasan waktu. Untuk memenuhi batasan waktu, fungsi ini menggunakan fakta bahwa jika ada p yang hilang 5s, kita dapat menambah 2 * 10 ^ (p-2).
Perhatikan bahwa ketika p = 1, kenaikannya menjadi 0,2. Ini OK, karena setelah 5 langkah kita kembali ke bilangan bulat, dan tidak ada angka desimal yang ditemui dalam waktu rata-rata yang memiliki 5. tambahan. Jika sebaliknya kita harus menambah 5 * 10 ^ (p-2) atau dengan 1 * 10 ^ (p-2), maka kita akan menemukan f (24, 1) = 24,5 bukan 25 misalnya.
sumber
if
varian fungsi.a
sedang dilakukan, jadi saya menghapusnya dan sepertinya OK.Jelly , 37 byte 0,113 detik pada TIO
Cobalah online!
Ini bekerja dengan
k
, dan membuat angka dengan balita sebanyak itusumber
[557,1]
(menghasilkan558
bukannya560
); test case dalam deskripsi tampaknya salah, karena[557,2]
seharusnya menghasilkan558
gantinya.05AB1E ,
3332 bytePort dari pendekatan @NickKennedy yang luar biasa dalam jawaban Jelly-nya , jadi pastikan untuk mendukungnya !!
Mengambil sebagai input pertama; sebagai yang kedua.k n
Cobalah secara online atau verifikasi semua kasus uji .
Penjelasan:
sumber
Stax , 17 byte (6,861 detik total pada TIO)
Jalankan dan debug itu
Program ini mengambil
k
dann
menggunakan input standar yang dipisahkan oleh ruang. Stax tidak memiliki cara yang mudah untuk menjalankan beberapa test case di TIO, jadi saya menjalankan setiap input secara terpisah dan menambahkan waktu. 99% dari waktu dalam startup proses juru bahasa. Menggunakan penerjemah javascript di staxlang.xyz, semua kasus uji berjalan dalam 50 milidetik.Test case terakhir di Coba online!
Prosedur :
5
, hentikan dan cetakt
= jumlah jejak5
di angka10 ** t
sumber
Python 2 ,
7068 byte (0,025 detik pada TIO)Cobalah online!
Ini mungkin sedikit peregangan; itu benar dalam semua kasus, dan selesai dalam waktu yang dapat diabaikan untuk kasus uji, tetapi tidak selesai dalam waktu yang wajar untuk beberapa kasus lainnya. Namun secara teknis memenuhi persyaratan.
Singkatnya, jika angka terkecil dengan
k
balita lebih besar daripadan
, kita menggunakan angka itu karena jelas solusi yang tepat. Jika tidak, kami menggunakan pendekatan rekursif standar.sumber
Perl 5
-pl
, 44 byteCobalah online!
Menemukan nomornya tanpa angka 5. Menambah porsi itu dengan 1. Berlanjut sampai cukup 5s ada dalam angka. Membutuhkan sekitar 0,012 pada TIO untuk menjalankan semua kasus uji.
sumber
Python 3 ,
144988675 byteCobalah online!
Ini , (waktu sistem .008 pada TIO) dan telah bermain golf dengan baik dengan saran dari ASCII saja.O(k)
Algoritma ini untuk mengumpulkan setiap digit (mulai dari yang paling signifikan) ke nilai terdekat 5 hingga representasi desimal angka baru memiliki jumlah yang diinginkan.
Pendekatan asli menggunakan pemahaman daftar gagal (D = iter (rentang (k)) dan daftar (D) di sini), tetapi @ ASCII-only telah meyakinkan saya bahwa tidak akan pernah memenangkan golf kode. Saya tidak menyukai rekursi, tetapi jika algoritma ini ditulis untuk meminimalkan kedalaman rekursi, maka kompiler / juru bahasa di masa depan akan cukup pintar untuk mengimplementasikannya kembali sebagai loop sementara.
sumber
(-(-~n//l+5))%10
sebabnyaPython 3 , 59 byte
Solusi rekursif. Kedalaman rekursi adalah masalah (harus diubah untuk angka yang lebih tinggi), tetapi itu benar.
Cobalah online!
sumber
Python 3, 72 byte
Cobalah online!
sumber
Java 8, 69 byte, 60+ detik pada TIO dengan test case terakhir, ~ 1,5 detik tanpa.
Adakah yang tahu bagaimana cara lulus ujian terakhir?
sumber
PHP ,
10997 byte, (<0,03 detik pada TIO)Cobalah online!
Berdasarkan algoritma @ rekursif .
sumber
Retina , 63 byte
Cobalah online! Mengambil
n
dank
pada baris yang berbeda, tetapi tautan menyertakan header yang mengubah suite pengujian ke dalam format yang sesuai. Penjelasan:Konversikan
k
ke unary.Penambahan
n
. The*
mengulangi argumen kanan (di sini pertama_
karakter) jumlah kali diberikan oleh argumen kiri (yang, seperti di sini, default untuk pertandingan). Ini menghasilkan string dengan panjang itu. The$(
(yang)
tersirat) kemudian merangkai bahwa dengan kedua_
dan.
menyebabkan panjang yang dihasilkan harus diambil. (Sebenarnya Retina 1 lebih pintar dari itu dan hanya melakukan perhitungan pada panjang yang mendasarinya di tempat pertama.)Tes apakah cukup
5
s dapat ditemukann
untuk mencocokkan dengan_
representasi unaryk
. Tes ini telah golf dan akan tiga kali lebih cepat dengan^
ditambahkan setelah inisial/
dan lebih cepat lagi jika[^5]
digunakan sebagai gantinya.
.Sampai tes berlalu ...
... increment
n
tetapi tidak termasuk trailing5
s.Hapus
k
.sumber
Clam , 30 byte, ~ 0.2s pada TIO
Transpile ke JS ini (paket uji lengkap ditambahkan untuk penentuan waktu tentu saja), di mana
inputs
terdapat array input (n
pertama,k
kedua)Terima kasih @ ArBo untuk pendekatannya
Penjelasan
sumber
C (gcc) ,
159158152150149 byte, ~ 0,04 dtkMenghasilkan jawaban untuk STDOUT, dengan nol terkemuka.
-3 byte terima kasih kepada ceilingcat
Cobalah online!
sumber