Biorąc pod uwagę r i n, znajdź pierwsze n liczb x, gdzie przesunięcie pierwszej cyfry x na ostatnią daje x / r = y


11

Cel

Biorąc pod uwagę dane wejściowe ri nznajdź pierwsze nliczby naturalne x, które po obróceniu pierwszej cyfry do ostatniego miejsca uzyskamy x/r.

Możesz założyć, że 2 <= r <= 9i 1 <= n <= 65535.

Możesz napisać program, który pobiera dane wejściowe z argumentów stdin lub wiersza poleceń; lub możesz napisać funkcję, która przyjmuje ri njako parametry. Wyjście jednak powinno być na standardowe wyjście. Wynik powinien wynosić jeden wiersz na wartość x, sformatowany jako x/r=y, w kolejności rosnącej x.

Twoje rozwiązanie musi być w stanie obsłużyć wszystkie ważne sprawy w ciągu jednej minuty na rozsądnym komputerze stacjonarnym.

Przypadki testowe

Wejście: 4 5
Wyjście:

102564/4=25641  
205128/4=51282  
307692/4=76923  
410256/4=102564  
512820/4=128205

Wejście: 5 1
Wyjście:714285/5=142857

To jest golf golfowy, więc najmniej bajtów wygrywa. Zwycięska odpowiedź zostanie zaakceptowana za 4 tygodnie (2014-09-19).

Podziękowania za to pytanie należą się mojemu koledze, który pozwolił mi zamieścić to pytanie tutaj :)


Ograniczenie czasowe jest trudne z wymaganą wydajnością. Zgodnie z tym gprof, jeden przypadek wejściowy dla mojego programu spędza mniej niż pół sekundy w moim kodzie, ale zajmuje łącznie około 80 sekund, co, jak zakładam, musi w większości blokować wyjście.
aschepler

Ach, udało mi się obejść, unikając printf.
aschepler

Odpowiedzi:


7

Haskell, 182 179

Druga wersja, prawdopodobnie dalsza gra w golfa, ale tym razem z „właściwym” algorytmem. W szczególności kończy się w ciągu kilku minut za pomocą r=4i n=65535, ale znowu mój komputer nie jest ani rozsądny, ani stacjonarny, więc są szanse, że pozostanie w ciągu minuty na innych komputerach.

n#r=take n$[s(10^k*a+d)++'/':s r++'=':s d++s a|k<-[0..],a<-[1..9],let(d,m)=divMod(a*(10^k-r))(10*r-1),m<1]
s=show
main=interact$unlines.(\(r:n:_)->n#fromIntegral r).map read.words

Opiera się na pomyśle x=10^k*a + m, w którym pierwsza cyfra 0≤a≤9jest przenoszona do końca w celu uzyskania y=10*m+a. Trochę matematyki wynika, że mmożna otrzymać jak a*(10^k-r)/(10*r-1), więc po prostu zeskanować aponad [1..9]dla każdego kod 0 do nieskończoności, i zachować i wydrukować pierwsze nwyniki, dla których powyższe wyrażenie mjest integralny.

fromIntegralJest wymagane, ponieważ reading listę z njako jeden z jej elementów main, w połączeniu z zastosowaniem nw take, zmusi raby Intprzez cały czas, co powoduje nieprzyjemnych przelewów z dużych liczb w pytaniu. Mógłbym użyć genericTake, ale to wymaga import.

Ten kod ma również tę zaletę, że można go prawie trywialnie rozszerzyć na bazy inne niż 10.

Dane wejściowe są odczytywane stdin, dwie wartości można oddzielić dowolnymi spacjami.


Twój kod powinien być krótszy, jeśli pozbędziesz się backsticks
dumny haskeller

@proudhaskeller: nie jestem pewien, ponieważ wokół nich nie ma nawiasów oddzielających operatora i operand bez spacji.
TheSpanishInquisition

Nie umiem czytać Haskella, więc nie jestem całkowicie pewien, co robisz. Czy to rozwiąże się r = 5; n = 65535w ciągu minuty?
Martin Ender

@ MartinBüttner: Czekałem na ten komentarz. Tak, prawdopodobnie tak będzie, ale nie na moim komputerze (lub w rzeczywistości, czy ktokolwiek inny jest teraz). Myślę, że problem wymaga bardziej zaawansowanego algorytmu. :(
TheSpanishInquisition

@TheSpanishInquisition Ale ahould można zastąpić y`mod`10z mod y10, który jest char krótszy
dumny haskeller

1

Pure Bash (bez zewnętrznych narzędzi), 80 bajtów

for((;++x,c<$2;));{
y=$[10#${x:1}${x:0:1}]
((y*$1==x))&&echo $x/$1=$y&&((c++))
}

Uwaga: bash wykonuje tylko arytmetykę liczb całkowitych, a nie zmiennoprzecinkowe, więc sprawdzamy, czy x == y * rzamiast x / r == y. Również mnożenie powinno zasadniczo być szybsze. Mimo to nie jest to wcale blisko spełnienia wymagań dotyczących wydajności.

Wynik:

$ ./rotdiv.sh 4 5
102564/4=25641
205128/4=51282
307692/4=76923
410256/4=102564
512820/4=128205
$ ./rotdiv.sh 5 1
714285/5=142857
$ 

1

C 468

#include <stdlib.h>
#include <stdio.h>
#define a(s)fputs(s,stdout);
#define b(c)putchar(c);
int r;int z(char*s,int m){for(int i=0;i++<=m;)a(s)b(47)b(r+48)b(61)char*t=s;
while(*++t==48);a(t)while(m--)a(s)b(*s)b(10)}char x[10][60];
int main(int c,char**v){r=atoi(v[1]);int n=atoi(v[2]),q=10*r-1,d=0,p;
while(d++<9){p=r*d;char*y=x[d];do{p*=10;*y++=p/q+48;p%=q;}while(p!=r*d);}
d=1;p=q=0;while(n--){r==5&p<6?z(x[7],7*q+p++):(z(x[d],(r==5&d==7)?7*q+6:q),
++d>9?q+=d=1,p=0:0);}}

(Niektóre znaki nowej linii, które nie są liczone w liczbie bajtów, zostały dodane powyżej, aby wyeliminować paski przewijania. Tak, liczona jest nowa linia).

Oczekuje argumentów w wierszu poleceń i zakłada, że ​​standardowe wyjście akceptuje ASCII. Środowisko wykonawcze to O (liczba wyjściowych bajtów) = O (n * n).

Nie, nie mogę użyć printf. To zajmuje zbyt dużo czasu i przesuwa program ponad limit minut na moim pulpicie. W tej chwili niektóre przypadki testowe zajmują około 30 sekund.

Algorytm traktuje dane wyjściowe jako ciągi, a nie liczby, ponieważ szybko stają się one ogromne, a na wydruku są silne wzorce.

Nieco golfisty:

#include <stdlib.h>
#include <stdio.h>

/* r is as in the problem description */
int r;

void show_line(const char* num, int repeats) {
    for (int i=0; i <= repeats; ++i)
        fputs(num, stdout);
    printf("/%c=", '0'+r);

    /* Assume the repeated num is a solution. Just move the first
       digit and skip any resulting leading zeros. */
    const char* num_tail = num;
    ++num_tail;
    while (*num_tail=='0')
        ++num_tail;
    fputs(num_tail, stdout);
    while (repeats--)
        fputs(num, stdout);
    printf("%c\n", *num);
}

/* sol[0] is unused. Otherwise, sol[d] is the repeating digits in the
   decimal representation of (r*d)/(10*r-1). */
char sol[10][60];

int main(int argc, char** argv) {
    r = atoi(argv[1]);
    int n = atoi(argv[2]);
    int q = 10*r-1;
    int d = 0;

    /* Populate the strings in sol[]. */
    while (d++<9) {
        int p = r*d;
        char* sol_str = sol[d];

        /* Do the long division p/q in decimal, stopping when the remainder
           is the original dividend. The integer part is always zero. */
        do {
            p *= 10;
            *sol_str++ = p/q + '0';
            p %= q;
        } while (p != r*d);
    }

    /* Output the answers. */
    d = 1;
    int repeats = 0;
    int r5x7_repeats = 0;
    while (n--) {
        if (r==5 && r5x7_repeats<6) {
            show_line(x[7], 7*repeats + r5x7_repeats);
        } else {
            if (r==5 && d==7)
                show_line(x[d], 7*repeats + 6);
            else
                show_line(x[d], repeats);
            if (++d > 9) {
                d = 1;
                ++repeats;
                r5x7_repeats = 0;
            }
        }
    }
}

Dowód

że program rozwiązuje problem:

(Na dowód, przyjmujemy, że wszystkie operatory i funkcje są prawdziwymi funkcjami matematycznymi, a nie operacjami komputerowymi, które je przybliżają. ^Oznacza potęgowanie, a nie bitowe xor.)

Dla jasności użyję funkcji ToDecdo opisania zwykłego procesu zapisywania liczby jako ciągu cyfr dziesiętnych. Jego zasięg to zestaw uporządkowanych krotek {0...9}. Na przykład,

ToDec(2014) = (2, 0, 1, 4).

Dla dodatniej liczby całkowitej nnależy zdefiniować L(n)liczbę cyfr w reprezentacji dziesiętnej n; lub,

L(n) = 1+floor(log10(n)).

Dla dodatniej liczby całkowitej ki nieujemnej liczby całkowitej nz L(n)<k, zdefiniuj Rep_k(n)jako liczbę rzeczywistą uzyskaną przez dodanie zer przed cyframi dziesiętnymi n, jeśli to konieczne, aby uzyskać kliczby całkowite, a następnie nieskończone powtarzanie tych kcyfr po przecinku. Na przykład

Rep_4(2014) = .201420142014...
Rep_5(2014) = .020140201402...

Mnożenie Rep_k(n) * 10^kdaje cyfry nprzed kropką dziesiętną, a cyfry (wypełnione zerą) nnieskończenie powtarzane po kropce dziesiętnej. Więc

Rep_k(n) * 10^k = n + Rep_k(n)
Rep_k(n) = n / (10^k - 1)

Biorąc pod uwagę dodatnią liczbę całkowitą r, załóżmy, że xjest to rozwiązanie problemu, i

ToDec(x) = ( x_1, x_2, ..., x_k )

gdzie x_1 != 0i k = L(x).

Rozwiązaniem xjest wielokrotność ri

ToDec(x/r) : ( x_2, x_3, ..., x_k, x_1 ).

Zastosowanie Rep_kfunkcji daje ładne równanie:

10*Rep_k(x) = x_1 + Rep_k(x/r)

Używając zamkniętego formularza z góry,

10x / (10^k - 1) = x_1 + x / r / (10^k - 1)
x = x_1 * r * (10^k-1) / (10r - 1)

x_1musi być w zestawie {1 ... 9}. rzostał określony w zestawie {2 ... 9}. Teraz jedynym pytaniem jest, dla jakich wartości kpowyższej formuły xpodaje dodatnią liczbę całkowitą? Rozważymy każdą możliwą wartość rindywidualnie.

Gdy r= 2, 3, 6, 8 lub 9, 10r-1wynosi odpowiednio 19, 29, 59, 79 lub 89. We wszystkich przypadkach mianownik p = 10r-1jest liczbą pierwszą. W liczniku 10^k-1może być tylko wielokrotność p, co dzieje się, gdy

10^k = 1 (mod p)

Zestaw roztworów jest zamykany w trakcie dodawania i odejmowania, co nie skutkuje liczbą ujemną. Tak więc zestaw zawiera wszystkie wielokrotności jakiegoś wspólnego czynnika, który jest również najmniej pozytywnym rozwiązaniem k.

Kiedy r = 4i 10r-1 = 39; lub kiedy r = 7i 10r-1 = 69mianownik ma 3 razy inną liczbę pierwszą p=(10r-1)/3. 10^k-1jest zawsze wielokrotnością liczby 3 i ponownie żaden inny czynnik licznika nie może być wielokrotnością p, więc ponownie problem zmniejsza się do

10^k = 1 (mod p)

i znowu wszystkie rozwiązania są wielokrotnościami najmniej pozytywnego rozwiązania k.

[Nie skończony...]


0

Python - 91 90

Oto pierwszy strzał:

r,n=input();i=1
while n:
 if int(`i`[1:]+`i`[0])*r==i:print'%d/%d=%d'%(i,r,i/r);n-=1
 i+=1

Edycja: Ok, prawdopodobnie jest to sposób na spowolnienie, aby osiągnąć wymagany 1-minutowy limit czasu dla liczb 65K.


1
Czy przetestowałeś to pod kątem wymagań dotyczących wydajności?
Peter Taylor,

2
Mam wątpliwości, czy uda się znaleźć 65 000 takich liczb, zanim wybuchnie słońce.
Martin Ender

0

JavaScript - 145

function f(a,b){for(d=0;d<b;d++)for(i=1;;i++){c=i/a;if(c==parseInt(i.toString().substring(1)+i.toString().charAt(0)))console.log(i+'/'+a+'='+c)}}

nie grał w golfa:

function f(a,b){
    for(d=0;d<b;d++) //loop for the right amount
        for(i=1;;i++){ //iterating loop
            c=i/a; //actual result of the division
            if(c==parseInt(i.toString().substring(1)+i.toString().charAt(0)))
                console.log(i+'/'+a+'='+c)
        }
}

Nie mogę tego w ogóle zadziałać, ale nawet jeśli tak, wątpię, czy spełniłby wymagania wydajnościowe.
Martin Ender

@ MartinBüttner działa dla mnie idealnie. może być tak, że nie spełnia wymagań dotyczących wydajności, ale w tym momencie komputer jest dość słaby ... Co zrobiłeś, aby ten fragment kodu zadziałał?
Armin

1
Skopiowałem go do konsoli i dołączyłem (5,4). Powodem, dla którego nie zadziała, jest to, że liczby stają się bardzo duże. a) Znacznie większa niż liczba w JS może dokładnie reprezentować ib) zdecydowanie zbyt duża, ponieważ byłoby możliwe, aby iterować po wszystkich liczbach, aby się tam dostać.
Martin Ender

0

Python 3 - 223 179 bajtów

Implementacja rozwiązania TheSpanishInquisition w języku Python:

r,n=map(int,input().split());k=0
while 1:
 for a in range(1,10):
  D,M=divmod(a*(10**k-r),10*r-1)
  if M==0:
   print("%d/%d=%d"%(a*10**k+D,r,10*D+a));n-=1
   if n==0:exit()
 k+=1

Biegać:

  • python3 <whatever you named it>.py
  • Pobiera dane wejściowe na standardowe wejście
  • Oddzielona przestrzeń wejściowa

Wynik:

$python3 <whatever you named it>.py
4 8
102564/4=25641
205128/4=51282
307692/4=76923
410256/4=102564
512820/4=128205
615384/4=153846
717948/4=179487
820512/4=205128

Wyniki:

https://oeis.org/A092697 to pierwsza wartość dla każdego r.

Wydaje się, że tylko niektóre wartości k dają odpowiedzi, a przedział jest regularny. Np. Dla r = 4:

Form: k [a, a, ...]
0 []
1 []
2 []
3 []
4 []
5 [1, 2, 3, 4, 5, 6, 7, 8, 9]
6 []
7 []
8 []
9 []
10 []
11 [1, 2, 3, 4, 5, 6, 7, 8, 9]
12 []
13 []
14 []
15 []
16 []
17 [1, 2, 3, 4, 5, 6, 7, 8, 9]
18 []
19 []
20 []
21 []
22 []
23 [1, 2, 3, 4, 5, 6, 7, 8, 9]

Interwały są następujące:

  • 2 = 18
  • 3 = 28
  • 4 = 6
  • 5 = 6 (5 wydaje się być anomalią, ponieważ dla większości wartości r istnieją skupiska 9, 5 tworzą skupiska 9 i 1 (przy pracy tylko a = 7), patrz poniżej)
  • 6 = 58
  • 7 = 22
  • 8 = 13
  • 9 = 44

To tworzy https://oeis.org/A094224 .

Korzystając z tych wartości, można zbudować bardziej wydajną wersję:

import math

def A094224(n):
    return [18,28,6,6,58,22,13,44][n-2]


r,n=map(int,input().split());k=A094224(r)-1
H={}
while 1:
    for a in range(1,10):
        D,M=divmod(a*10**k-a*r,10*r-1)
        if M==0:
            print("%d/%d=%d"%(a*10**k+D,r,10*D+a));n-=1
            if n==0:exit()
    k+=A094224(r)

Nie mogę jednak (jeszcze) udowodnić, że jest to kontynuowane matematycznie.

Wyniki dla r = 5:

0 []
1 []
2 []
3 []
4 []
5 [7]
6 []
7 []
8 []
9 []
10 []
11 [7]
12 []
13 []
14 []
15 []
16 []
17 [7]
18 []
19 []
20 []
21 []
22 []
23 [7]
24 []
25 []
26 []
27 []
28 []
29 [7]
30 []
31 []
32 []
33 []
34 []
35 [7]
36 []
37 []
38 []
39 []
40 []
41 [1, 2, 3, 4, 5, 6, 7, 8, 9]

2
Czy przetestowałeś to z wejściem 9 65535?
Peter Taylor

Powinienem prawdopodobnie unsigned long longdo tego użyć i sprawić, aby było to wielordzeniowe, aby zrobić to w ciągu jednej minuty.
matsjoyce

1
Jeśli unsigned long longma 64 bity, nie jest wystarczająco duży.
Peter Taylor

To prawda, przełączyłem się na rozwiązanie @ TheSpanishInquisition i zamiast tego użyłem Pythona.
matsjoyce,
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.