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 :)

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.

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
$ 

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...]

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.

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)
        }
}

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]