Lipat gandakan dan bagi

10

Diberikan nilai x menemukan nilai numerik terkecil lebih besar dari y yang mampu dikalikan dan dibagi dengan x sambil mempertahankan semua digit asli.

  • Angka-angka baru tidak kehilangan digit.
  • Angka-angka baru tidak mendapatkan angka.

Sebagai contoh:

Input: x = 2, y = 250000

  • Asli: 285714
    • Divisi: 142857
    • Perkalian: 571428

Ini benar karena 285714 lebih besar dari y ; kemudian ketika dibagi dengan x hasil di 142857 dan ketika dikalikan dengan x hasil di 571428 . Di kedua tes semua digit asli dari 285714 hadir dan tidak ada digit tambahan telah ditambahkan.


Aturan

  • X harus 2 atau 3 karena sesuatu yang lebih tinggi membutuhkan waktu terlalu lama untuk dihitung.
  • Y harus bilangan bulat lebih besar dari nol .
  • Kode terpendek menang.

Uji Kasus

Ini adalah kasus uji saya yang paling umum karena merupakan yang tercepat untuk diuji.

  • x = 2, y = 250000 = 285714
  • x = 2, y = 290000 = 2589714
  • x = 2, y = 3000000 = 20978514
  • x = 3, y = 31000000 = 31046895
  • x = 3, y = 290000000 = 301046895

Klarifikasi

  • Jenis pembagian tidak masalah. Jika Anda bisa mendapatkan 2,05, 0,25, dan 5,20 entah bagaimana maka jangan ragu.

Semoga beruntung untuk kalian semua!

Emma - AbadiJ
sumber
4
" X harus bernilai antara 2 dan 5. " - jika X> = 4, angka yang dikalikan dengan X akan setidaknya 16 kali lebih besar dari angka dibagi dengan X, jadi pasti akan memiliki lebih banyak digit
ngn
2
x tidak dapat berupa apa pun selain 2 atau 3 karena produk x ^ 2 kali hasil bagi dan keduanya harus memiliki jumlah digit yang sama. x = 1 akan menjadi kasus sepele. IMO, tidak ada solusi untuk x = 3 untuk setiap y meskipun saya mungkin salah.
Jatin Sanghvi
2
Apakah divisi float atau divisi integer?
Erik the Outgolfer
3
Test case akan menjadi luar biasa
Stephen
3
Saya curiga saya bukan satu-satunya orang yang menahan diri dari pemilihan untuk membuka kembali karena klarifikasi sebenarnya membuat tantangan lebih ambigu, karena jawaban yang benar dapat berubah tergantung pada apakah output floating point dipertimbangkan atau tidak. Saya menduga pertanyaan @EriktheOutgolfer bukan menanyakan tentang mengizinkan keluaran floating point, tetapi tentang apakah diizinkan menggunakan pemotongan integer division. (Dan saya minta maaf jika komentar saya menambah kebingungan.)
Ørjan Johansen

Jawaban:

4

Sekam , 14 byte

ḟ§¤=OoDd§¤+d*/

Cobalah online!

Penjelasan

ḟ§¤=O(Dd)§¤+d*/  -- example inputs: x=2  y=1
ḟ                -- find first value greater than y where the following is true (example on 285714)
 §               -- | fork
         §       -- | | fork
              /  -- | | | divide by x: 142857
                 -- | | and
             *   -- | | | multiply by y: 571428
                 -- | | then do the following with 142857 and 571428
                 -- | | | concatenate but first take
           +     -- | | | | digits: [1,4,2,8,5,7] [5,7,1,4,2,8]
          ¤ d    -- | | | : [1,4,2,8,5,7,5,7,1,4,2,8]
                 -- | and
       d         -- | | digits: [2,8,5,7,1,4]
      D          -- | | double: [2,8,5,7,1,4,2,8,5,7,1,4]
                 -- | then do the following with [2,8,5,7,1,4,2,8,5,7,1,4] and [1,4,2,8,5,7,5,7,1,4,2,8]
   =             -- | | are they equal
  ¤ O            -- | | | when sorted: [1,1,2,2,4,4,5,5,7,7,8,8] [1,1,2,2,4,4,5,5,7,7,8,8]
                 -- | : truthy
                 -- : 285714
ბიმო
sumber
Saya menyesuaikan nilai untuk y untuk mendapatkan titik awal yang lebih dekat dan hasilnya tidak benar untuk x = 3, y = 25000000 .
Emma - PerpetualJ
@PerpetualJ: Jika Anda tahu hasilnya maka Anda dapat dengan mudah menyesuaikan y , dan versi ini harus sedikit lebih cepat (hanya memeriksa jenis saja).
ბიმო
Saya telah menyesuaikannya setelah beberapa pemikiran dan mengedit komentar pertama saya.
Emma - PerpetualJ
@PpetpetJ: Saya sudah memperbaikinya: membuat asumsi tentang -yang salah.
ბიმო
1
@PerpetualJ: Saya menulis program;) Saya menambahkan penjelasan, sekarang semua orang harus mengerti apa yang terjadi.
ბიმო
5

Brachylog v2, 15 byte

t<.g,?kA/p.∧A×p

Cobalah online!

Mengambil input dalam formulir [x,y].

Penjelasan

t<.g,?kA/p.∧A×p
t                  Tail (extract y from the input)
 <                 Brute-force search for a number > y, such that:
  .                  it's the output to the user (called ".");
   g                 forming it into a list,
    ,?               appending both inputs (to form [.,x,y]),
      k              and removing the last (to form [.,x])
       A             gives a value called A, such that:
        /              first ÷ second element of {A}
         p             is a permutation of
          .            .
           ∧         and
            A×         first × second element of {A}
              p        is a permutation of {.}

Komentar

Kelemahan Brachylog dalam menggunakan kembali beberapa nilai beberapa kali muncul di sini; Program ini hampir semuanya plumbing dan algoritmanya sangat sedikit.

Dengan demikian, mungkin tampak lebih mudah untuk secara sederhana meng-hardcode nilai y (ada komentar pada pertanyaan ini dengan hipotesis bahwa 2 adalah satu-satunya nilai yang mungkin). Namun, sebenarnya ada solusi untuk y = 3, artinya sayangnya, pipa ledeng harus menangani nilai y juga. Yang terkecil yang saya sadari adalah sebagai berikut:

                         315789473684210526
315789473684210526 × 3 = 947368421052631578
315789473684210526 ÷ 3 = 105263157894736842

(Teknik yang saya gunakan untuk menemukan angka ini tidak sepenuhnya umum, jadi ada kemungkinan bahwa ada solusi yang lebih kecil menggunakan beberapa pendekatan lain.)

Anda tidak akan memverifikasi dengan program ini . Brachylog's pditulis dengan cara yang sangat umum yang tidak memiliki optimisasi untuk kasus-kasus khusus (seperti kasus di mana input dan output sudah diketahui, artinya Anda dapat melakukan verifikasi di O ( n log n ) melalui penyortiran, bukan daripada O ( n !) untuk pendekatan brute-force yang saya curigai gunakan). Sebagai akibatnya, dibutuhkan waktu yang sangat lama untuk memverifikasi bahwa 105263157894736842 adalah permutasi 315789473684210526 (Saya telah membiarkannya berjalan selama beberapa menit sekarang tanpa kemajuan yang jelas).

(EDIT: Saya memeriksa sumber Brachylog untuk alasannya. Ternyata jika Anda menggunakan pdua bilangan bulat yang diketahui, algoritme yang digunakan menghasilkan semua kemungkinan permutasi bilangan bulat yang dimaksud hingga menemukan yang sama dengan bilangan bulat keluaran, sebagai algoritme adalah "input → indigits, permute indigits → outdigits, outdigits → output". Algoritme yang lebih efisien adalah dengan mengatur hubungan outdigits / output terlebih dahulu , sehingga penelusuran ulang dalam permutasi dapat mempertimbangkan angka mana yang tersedia.)

ais523
sumber
Menggunakan garpu dapat mengurangi kode Anda sebesar 1 byte. Cobalah online!
Kroppeb
Juga menurut dokumen, tampaknya memeriksa apakah dua daftar yang diketahui permutasi adalah O (n²) swi-prolog.org/pldoc/man?predicate=permutation/2
Kroppeb
@ Kalpeb: masalahnya adalah bahwa Brachylog's ptidak berjalan permutation/2dengan dua daftar yang diketahui, bahkan ketika diberi dua bilangan bulat yang dikenal sebagai argumen; itu menghasilkan semua permutasi integer pertama (menggunakan permutation/2dengan satu daftar yang diketahui) dan kemudian membandingkannya dengan integer kedua.
ais523
4

Perl 6 , 56 54 byte

->\x,\y{(y+1...{[eqv] map *.comb.Bag,$_,$_*x,$_/x})+y}

Cobalah online!

Alternatif yang menarik, menghitung n * x k untuk k = -1,0,1:

->\x,\y{first {[eqv] map ($_*x***).comb.Bag,^3-1},y^..*}
nwellnhof
sumber
3

Bersihkan , 92 byte

import StdEnv
$n m=hd[i\\i<-[m..],[_]<-[removeDup[sort[c\\c<-:toString j]\\j<-[i,i/n,i*n]]]]

Cobalah online!

Cukup mudah. Penjelasan datang sebentar.

Suram
sumber
3

q, 65 byte

{f:{asc 10 vs x};while[not((f y)~f y*x)&(f y*x)~f"i"$y%x;y+:1];y}

Pisahkan angka pada basis 10, urutkan setiap kenaikan, dan periksa apakah sama. Jika tidak, tambahkan y dan lanjutkan lagi

Thaufeki
sumber
3

JavaScript (ES6), 76 73 69 byte

Disimpan 3 byte dengan menggunakan eval(), seperti yang disarankan oleh @ShieruAsakoto

Mengambil input sebagai (x)(y).

x=>y=>eval("for(;(g=x=>r=[...x+''].sort())(y*x)+g(y/x)!=g(y)+r;)++y")

Cobalah online!

Versi rekursif akan menjadi 62 byte , tetapi tidak cocok di sini karena banyaknya iterasi yang diperlukan.

Bagaimana?

g

Contoh:

g(285714) = [ '1', '2', '4', '5', '7', '8' ]

y×xy/xyg(y×x)g(y/x)g(y)

Ketika menambahkan dua array bersama-sama, masing-masing dari mereka secara implisit dipaksa ke string yang dipisahkan koma. Digit terakhir dari array pertama akan langsung digabungkan dengan digit pertama dari array kedua tanpa koma di antara mereka, yang membuat format ini tidak ambigu.

Contoh:

g(123) + g(456) = [ '1', '2', '3' ] + [ '4', '5', '6' ] = '1,2,34,5,6'

Tapi:

g(1234) + g(56) = [ '1', '2', '3', '4' ] + [ '5', '6' ] = '1,2,3,45,6'

Berkomentar

x => y =>                   // given x and y
  eval(                     // evaluate as JS code:
    "for(;" +               //   loop:
      "(g = x =>" +         //     g = helper function taking x
        "r =" +             //       the result will be eventually saved in r
          "[...x + '']" +   //       coerce x to a string and split it
          ".sort() + ''" +  //       sort the digits and coerce them back to a string
      ")(y * x) +" +        //     compute g(y * x)
      "g(y / x) !=" +       //     concatenate it with g(y / x)
      "g(y) + r;" +         //     loop while it's not equal to g(y) concatenated with
    ")" +                   //     itself
    "++y"                   //   increment y after each iteration
  )                         // end of eval(); return y
Arnauld
sumber
66: x=>F=y=>(g=x=>r=[...x+''].sort()+'')(y*x)!=g(y)|r!=g(y/x)?F(y+1):yDapat menyebabkan stack overflow jika Anda jauh dari solusi.
Shieru Asakoto
atau 75 menggunakan eval:x=>y=>eval("for(;(g=x=>r=[...x+''].sort()+'')(y*x)!=g(y)|r!=g(y/x);y++);y")
Shieru Asakoto
@ShieruAsakoto Terima kasih atas eval()idenya. Upaya pertama saya memang rekursif, tetapi saya menyerah karena tingginya jumlah iterasi yang diperlukan.
Arnauld
3

Haskell, 76 74 byte

Dua byte dicukur berkat komentar Lynn

import Data.List
s=sort.show
x#y=[n|n<-[y+1..],all(==s n)[s$n*x,s$n/x]]!!0
umnikos
sumber
1
Untuk jumlah byte yang sama, Anda fbisa f x y=[n|n<-[y+1..],all(==s n)[s$n*x,s$n/x]]!!0tetapi kemudian mendefinisikan jawaban Anda sebagai operator menghemat dua byte: x!y=…dan kemudian jawaban Anda adalah (!):)
Lynn
Tidak terpikir untuk menggunakan pemahaman daftar! Terima kasih atas sarannya: D
umnikos
2

Japt, 24 byte

Solusi yang cukup naif selama beberapa bir; Saya yakin ada cara yang lebih baik.

@[X*UX/U]®ì nÃeeXì n}a°V

Cobalah

Shaggy
sumber
Sayangnya ini menghasilkan hasil yang salah ketika x = 3 dan y = 25000 .
Emma - PerpetualJ
@PerpetualJ Mengasumsikan 315789473684210526adalah solusi pertama untuk x=3, Javascript atau Japt tidak dapat menghitung dengan benar karena tidak cocok dalam presisi ganda.
Bubbler
@PerpetualJ, memperbaikinya sebelumnya. Test case itu tidak akan pernah selesai, karena alasan Bubbler yang disebutkan di atas.
Shaggy
@ Shaggy Ini sekarang menghasilkan hasil yang benar dan solusi yang ditunjuk Bubbler bukanlah hasil yang benar pertama di atas 25000 . Lihat kasus pengujian saya jika Anda ingin tahu tentang itu. +1
Emma - PerpetualJ
1

Python 2 , 69 byte

S=sorted
x,y=input()
while(S(`y`)==S(`y*x`)==S(`y/x`))<1:y+=1
print y

Cobalah online!

Chas Brown
sumber
f=lambda x,y,S=sorted:y*(S(`y`)==S(`y*x`)==S(`y/x`))or f(x,y+1)harus bekerja, tetapi itu mencapai batas rekursi cukup cepat, dan saya tidak tahu apa aturan PPCG katakan tentang itu.
Lynn
1

Jelly ,  14  13 byte

-1 terima kasih kepada Erik the Outgolfer (`` menggunakan make_digits, jadi Dtidak diperlukan)
+2 memperbaiki bug (sekali lagi terima kasih kepada Erik the Outgolfer karena menunjukkan masalah yang tidak ada sama sekali)

×;÷;⁸Ṣ€E
‘ç1#

Program lengkap mencetak hasilnya (sebagai tautan diadik daftar panjang 1 dihasilkan).

Cobalah online!

Bagaimana?

×;÷;⁸Ṣ€E - Link 1, checkValidity: n, x               e.g. n=285714,  x=2
×        -     multiply -> n×x                       571428
  ÷      -     divide -> n÷x                         142857
 ;       -     concatenate -> [n×x,n÷x]              [571428,142857]
    ⁸    -     chain's left argument = n             285714
   ;     -     concatenate -> [n×x,n÷x,n]            [571428,142857,285714]
     Ṣ€  -     sort €ach (implicitly make decimals)  [[1,2,4,5,7,8],[1,2,4,5,7,8],[1,2,4,5,7,8]]
        E    -     all equal?                        1

‘ç1# - Main link: y, x
‘    - increment -> y+1
   # - count up from n=y+1 finding the first...
  1  - ...1 match of:
 ç   -   the last link (1) as a dyad i.e. f(n, x)

Perhatikan bahwa ketika pembagian tidak tepat instruksi desimal implisit (setara dengan a D) diterapkan sebelum pengurutan menghasilkan bagian fraksional
misalnya: 1800÷3D-> [6,0,0]
while 1801÷3D->[6.0,0.0,0.33333333333337123]

Jonathan Allan
sumber
Saya tidak begitu yakin jawaban ini valid; tantangannya menuntut hasil menjadi "lebih besar dari y ", yang saya tafsirkan sebagai "benar-benar lebih besar dari Y ". Anda juga tidak perlu D.
Erik the Outgolfer
Ah tempat yang bagus pada >=saya benar-benar merindukan itu! Tidak tahu ada make_digits ditetapkan di atasnya - terima kasih. Akan harus memperbaiki & memperbarui nanti ...
Jonathan Allan
1

Mathematica, 82 74 byte

x=Sort@*IntegerDigits;Do[If[x[i#]==x@Floor[i/#]==x@i,Break@i],{i,#2,∞}]&

-8 byte berkat tsh

Fungsi yang mengambil argumen sebagai [x,y]. Secara efektif, pencarian brute force yang memeriksa apakah daftar angka yang diurutkan y, y/xdan xysama.

Cobalah online!

numbermaniac
sumber
Saya tidak terbiasa dengan Mathematica. Tetapi dapat dibuktikan bahwa jawabannya masih benar jika Anda menjatuhkan bagian pecahan dari pembagian: Semua ans, ans / x, ans * x harus dapat dibagi oleh 9. Dan ini dapat membuat solusi Anda lebih pendek.
tsh
@ tsh Itu berhasil x=3, tapi saya tidak yakin itu benar untuk x=2.
Ørjan Johansen
@ ØrjanJohansen Let v = a[1]*10^p[1] + a[2]*10^p[2] + ... + a[n]*10^p[n], u = a[1] * 10^q[1] + ... + a[n] * 10^q[n]. Dan u-v = a[1]*(10^p[1]-10^q[1]) + ... + a[n]*(10^p[n]-10^q[n])Karena 10^x-10^y=0 (mod 9)selalu berlaku. u-v=0 (mod 9)selalu berlaku. Jika ada jawaban yang salah w, karena w*x-w=0 (mod 9), dan w-floor(w/x)=0 (mod 9): kita punya floor(w/x)=0 (mod 9). jika floor(w/x)*x <> w,, w-floor(w/x)*x>=9tetapi ini bertentangan dengan fakta bahwa w-floor(w/x)*x<xsementara x bisa 2 atau 3.
tsh
@ terima kasih! Demi kepentingan orang lain yang terlalu lama untuk mendapatkan poin ini, w=0 (mod 9)berikut adalah dari w*x-w=0 (mod 9)karena x-1tidak dapat dibagi oleh 3.
Ørjan Johansen
Jika saya mengecualikan IntegerQtes, itu menghasilkan beberapa kesalahan ketika mencoba melakukan IntegerDigitspada pecahan, tetapi Mathematica masih melewati mereka dan menghasilkan jawaban yang benar. Saya tidak yakin apakah kesalahan yang dimasukkan selama perhitungan akan diizinkan, bahkan jika jawaban akhirnya benar.
numbermaniac
0

APL (NARS), 490 karakter, 980 byte

T←{v←⍴⍴⍵⋄v>2:7⋄v=2:6⋄(v=1)∧''≡0↑⍵:4⋄''≡0↑⍵:3⋄v=1:5⋄⍵≢+⍵:8⋄⍵=⌈⍵:2⋄1}
D←{x←{⍵≥1e40:,¯1⋄(40⍴10)⊤⍵}⍵⋄{r←(⍵≠0)⍳1⋄k←⍴⍵⋄r>k:,0⋄(r-1)↓⍵}x}
r←c f w;k;i;z;v;x;y;t;u;o ⍝   w  cxr
   r←¯1⋄→0×⍳(2≠T c)∨2≠T w⋄→0×⍳(c≤1)∨w<0⋄→0×⍳c>3
   r←⌊w÷c⋄→Q×⍳w≤c×r⋄r←r+c
Q: u←D r⋄x←1⊃u⋄y←c×x⋄t←c×y⋄o←↑⍴u⋄→0×⍳o>10⋄→A×⍳∼t>9
M:                     r←10*o⋄⍞←r⋄→Q
A: u←D r⋄→M×⍳x≠1⊃u⋄→B×⍳∼(t∊u)∧y∊u⋄z←r×c⋄v←D z⋄→C×⍳(⍳0)≡v∼⍦u
B: r←r+1⋄→A
C: k←z×c⋄⍞←'x'⋄→B×⍳(⍳0)≢v∼⍦D k
   ⎕←' '⋄r←z

uji

  2 f¨250000 290000 3000000
xxxx 
1000000xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 
10000000xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 
285714 2589714 20978514 
 3 f¨ 31000000 290000000 
xxxxxxxxx 
100000000xxxxxxxxxxxxxxxxxxxxxxxxxx 
31046895 301046895 

Saya pikir masalahnya sebagai ra angka mudah yang dapat bervariasi sehingga seseorang memiliki 3 angka r, r * x, r * x * x dalam cara r mulai nilai yang r * x dekat y (di mana x dan y adalah input masalah menggunakan huruf yang sama dengan posting utama). Saya menggunakan pengamatan bahwa jika digit pertama r adalah d daripada di r harus muncul digit d * x dan d * x * x juga, untuk membuat r (atau lebih baik r * x) satu solusi.

RosLuP
sumber
0

05AB1E , 16 byte

[>©Ð²÷s²*)€{Ë®s#

Cobalah online. (CATATAN: Solusi yang sangat tidak efisien, jadi gunakan input yang dekat dengan hasilnya. Ini berfungsi untuk input yang lebih besar juga secara lokal, tetapi pada TIO akan habis setelah 60 detik.)

Penjelasan:

[                   # Start an infinite loop
 >                  #  Increase by 1 (in the first iteration the implicit input is used)
  ©                 #  Store it in the register (without popping)
   Ð                #  Triplicate it
    ²÷              #  Divide it by the second input
      s             #  Swap so the value is at the top of the stack again
       ²*           #  Multiply it by the second input
         )          #  Wrap all the entire stack (all three values) to a list
          €{        #  Sort the digits for each of those lists
             ®s     #  Push the value from the register onto the stack again
            Ë       #  If all three lists are equal:
               #    #   Stop the infinite loop
Kevin Cruijssen
sumber