To moje pierwsze pytanie, więc mam nadzieję, że pójdzie dobrze.

Tło:

To nie rzeki, o których możesz myśleć. Pytanie dotyczy koncepcji cyfrowych rzek. Cyfrowa rzeka to ciąg liczb, w którym liczba następująca njest npowiększona o sumę jej cyfr.

Wyjaśnienie:

Po 12345 następuje 12360, ponieważ 1 + 2 + 3 + 4 + 5 = 15, a więc 12345 + 15 daje 12360. podobnie po 145 następuje 155. Jeśli pierwszą liczbą cyfrowej rzeki jest nazwa Mrzeki M.

Na przykład: Rzeka 480 to początek sekwencji {480,492,507,519 ....}, a rzeka 483 to początek sekwencji {483,498,519, ....}. Normalne strumienie i rzeki mogą się spotkać, to samo dotyczy cyfrowych rzek. Dzieje się tak, gdy dwie rzeki cyfrowe mają te same wartości.

Przykład:

Rzeka 480 spotyka się z rzeką 483 w 519. Rzeka 480 spotyka się z rzeką 507 w 507 i nigdy nie spotyka się z rzeką 481. Każda cyfrowa rzeka ostatecznie spotka rzekę 1, rzekę 3 lub rzekę 9.

Napisz program, który może określić dla danej liczby całkowitej nwartość, w której rzeka nnajpierw spotyka jedną z tych trzech rzek.

Wejście

Dane wejściowe mogą zawierać wiele przypadków testowych. Każdy przypadek testowy zajmuje osobną linię i zawiera liczbę całkowitą n( 1 <= n <= 16384). Przypadek testowy o wartości 0for nkończy dane wejściowe i nie można go przetwarzać.

Wynik

Dla każdego przypadku testowego na wejściu pierwsze wyjście numer przypadku testowego (zaczynając od 1), jak pokazano na wyjściu próbki. Następnie na osobnym wyjściu linii wiersz „najpierw spotyka rzekę x w punkcie y”. Tutaj y jest najniższą wartością, w której rzeka nnajpierw styka się z rzeką x(x = 1 lub 3 lub 9). Jeśli rzeka nspotyka rzekę xna ydłużej niż jedną wartość x, wyjście najniższej wartości. Wydrukuj pustą linię między dwoma kolejnymi przypadkami testowymi.

Przypadek testowy

Wejście:

86
12345
0

Wynik:

Case #1

first meets river 1 at 101

Case #2

first meets river 3 at 12423

Punktacja:

Najszybszy algorytm wygrywa. W przypadku remisu. Wygra ten z krótszym kodem.

Dzięki mbomb007 za wskazanie mojego błędu.

ps: Chcę mieć najszybsze rozwiązanie, a nie najmniejsze. Mam też moje wolne rozwiązanie. Aby zobaczyć to tutaj .

Uwaga:

Użyję tego do testowania kodu. I sprawdzanie wydajności.

C, 320 294 bajtów

Skompiluj z -std = c99

#include<stdio.h>
int s(int i){for(int j=i;j;j/=10)i+=j%10;return i;}int main(){int c=0,i;while(scanf("%d",&i)){c++;if(!i)continue;int j,o[]={1,3,9},p[]={1,3,9};Q:for(j=0;j<3;j++){if(o[j]==i)goto D;else if(o[j]<i){o[j]=s(o[j]);goto Q;}}i=s(i);goto Q;D:printf("Case #%d\n\nfirst meets river %d at %d\n\n",c,p[j],o[j]);}}

Nie golfowany:

#include <stdio.h>

int s(int i)
{
    for(int j = i; j; j /= 10)
        i += j % 10;
    return i;
}

int main()
{
    int c = 0, i;
    while(scanf("%d", &i))
    {
        c++;
        if(!i)
            continue;
        int j,o[]={1,3,9},p[]={1,3,9};
        Q: for(j = 0; j < 3; j++)
        {
            if(o[j] == i)
                goto D;
            else if(o[j] < i)
            {
                o[j] = s(o[j]);
                goto Q;
            }
        }
        i = s(i);
        goto Q;
        D: printf("Case #%d\n\nfirst meets river %d at %d\n\n", c, p[j], o[j]);
    }
}

Wypróbuj to!

Zasadniczo rzeki „docelowe” są zwiększane, dopóki nie będą większe niż rzeka, na której testujemy, a następnie rzeka testowa jest zwiększana. Jest to powtarzane, aż rzeka testowa będzie równa jakiejś innej rzece.

Nie czytam parametrów z wiersza poleceń w tym programie i nie jestem pewien, czy powinieneś. Teraz możesz przekazać parametry do STDIN. Możesz zakończyć, przekazując dane nienumeryczne.

_{Również cholernie pobity przez pół godziny.}

JavaScript (ES6)

To dość szybka odpowiedź przy użyciu dość wolnego języka. Naprawdę, wykonanie czasu nie powinno stanowić problemu przy użyciu dowolnego języka z tabelami skrótów. Wszystkie moje testy poniżej 100 ms.

Metoda anonimowa z listą przypadku testowego jako parametrem wejściowym.

F=cases=>{
  var t0 = +new Date
  var result = 0
  var spots = []
  var top=[,1,3,,9]
  var rivers=[,1,3,1,9,1,3,1]
  cases.forEach((n,i)=>{
    var found = result = spots[n]
    for (;!found;)
    {
      found = top.some((v,i)=>{
        for(;spots[v] |= i, v<n; top[i] = v)
          [...v+''].forEach(d=>v-=-d)
        return result = v-n ? 0 : i;
      }) || (
        [...n+''].forEach(d=>n-=-d),
        result = spots[n]
      )
    }  
    console.log(`Case #${i+1}\nfirst meets river ${rivers[result]} at ${n}`)
  })  
  return 'Time (ms) ' + (new Date-t0)
}  

console.log(F([86, 12345, 123, 456, 789, 16384]))

Java 7, 519 505 bajtów

import java.util.*;String c(int i){if(i<=0)return"";ArrayList<Long>r=f(1),s=f(3),t=f(9),x=f(i);String z="first meets river ";for(int j=0;j<r.size();j++){long u=r.get(j),v=s.get(j),w=t.get(j);if(x.contains(u))return z+1+" at "+u;if(x.contains(v))return z+3+" at "+v;if(x.contains(w))return z+9+" at "+w;}return"";}ArrayList f(long i){ArrayList<Long>l=new ArrayList();l.add(i);for(long j=0,x;j<9e4;j++){x=l.get(l.size()-1);for(char c:(x+"").toCharArray())x+=new Long(c+"");l.add(x);if(x>16383)return l;}return l;}

Tak, jest długi, brzydki i bez wątpienia można go całkowicie zmienić na golfa kodowego. Jestem rozkojarzony i zmęczony, więc może powinienem go po prostu usunąć
. Szczerze mówiąc, było to dość trudne wyzwanie. , Ale przynajmniej masz swoją pierwszą odpowiedź ...;) (która może być nawet dłuższa niż twój oryginalny nieoznakowany program w C ++ .. xD)

Przypadki bez golfa i testy:

Wypróbuj tutaj.

import java.util.*;
class M{
  static String c(int i){
    if(i <= 0){
      return "";
    }
    ArrayList<Long> r = f(1),
                    s = f(3),
                    t = f(9),
                    x = f(i);
    String z = "first meets river ",
           y = " at ";
    for(int j = 0; j < r.size(); j++){
      long u = r.get(j),
           v = s.get(j),
           w = t.get(j);
      if(x.contains(u)){
        return z+1+y+u;
      }
      if(x.contains(v)){
        return z+3+y+v;
      }
      if(x.contains(w)){
        return z+9+y+w;
      }
    }
    return "";
  }

  static ArrayList f(long i){
    ArrayList<Long> l = new ArrayList();
    l.add(i);
    for(long j = 0, x; j < 9e4; j++){
      x = l.get(l.size() - 1);
      for(char c : (x + "").toCharArray()){
        x += new Long(c+"");
      }
      l.add(x);
      if(x > 16383){
        return l;
      }
    }
    return l;
  }

  public static void main(String[] a){
    System.out.println(c(86));
    System.out.println(c(12345));
    System.out.println(c(0));
  }
}

Wynik:

first meets river 1 at 101
first meets river 3 at 12423
(empty output)

Scala, 774 bajty

Fiddle: http://scalafiddle.net/console/4ec96ef90786e0f2d9f7b61b5ab0209b

Nie mam ochoty na golfa. Znajduje rozwiązanie postawionego problemu w ciągu 50 ms

Użycie może nie być dokładnie takie, jak chcesz:

scala river.scala

Teraz możesz w sposób ciągły wprowadzać liczby, a następnie Enter. I zakończ program za pomocą 0. Wynik zostanie wydrukowany, jak tylko naciśniesz Enter.

io.Source.stdin.getLines.map(_.toInt)
  .takeWhile(_ != 0)
  .map(stream(_).takeWhile(_ < 16383))
  .zipWithIndex
  .map { cur =>
    Seq(1, 3, 9).map { i =>
      val s = stream(i).takeWhile(_ < 16383)
      (cur._2+1, i, s.intersect(cur._1).headOption)
    }
  }.foreach { opts =>
    val options = opts.filterNot(_._3.isEmpty)

    if(options.isEmpty) {
      println("No result")
    } else {
      val opt = options(0)
      println(s"Case #${opt._1}\n\nfirst meets ${opt._2} at ${opt._3.get}\n\n")
    }
  }

def stream(i:Int): Stream[Int] = {
  def sub: Int => Stream[Int] = {
    i => i #:: sub(a(i))
  }
  sub(i)
}

def a(i:Int): Int = i + i.toString.map{_.asDigit}.sum

C 228 283 300 bajtów

Jest to modyfikacja kodu Jakowa, aby wykorzystać wzorce rzeczne. To sprawia, że ​​~ 3x szybciej. Ponadto liczby całkowite bez znaku unikają cltodkary na komputerach 64-bitowych, więc jest kilka bajtów dłuższych, ale ułamkowo szybszych.

#define sum(z) for(y=z;y;y/=10)z+=y%10;
n,x;main(){unsigned i,j,y;while(scanf("%d",&i)){if(i){j=x=1+!(i%3)*2+!(i%9)*6;do{while(j<i)sum(j)}while(j^i&&({sum(i)i;}));printf("Case #%u\n\nfirst meets river %u at %u\n\n",++n,x,i);}}}

Nie golfowany:

#define sum(z) for(y=z;y;y/=10)z+=y%10;
n, x;
main() {
    unsigned i, j, y;
    while(scanf("%d", &i)) {
        if(i){
            j = x = 1 + !(i%3)*2 + !(i%9)*6;
            do{
                while (j < i) sum(j)
            }
            while(j^i&&({sum(i)i;}));
            printf("Case #%u\n\nfirst meets river %u at %u\n\n", ++n, x, i);
        }
    }
}

Wyjaśnienie:

j = x = 1 + !(i%3)*2 + !(i%9)*6;

To wybiera właściwą rzekę. Rzeka 1 spotyka się z każdą inną rzeką, dlatego używamy tego jako przypadku rezerwowego. Jeśli 3 jest największym wspólnym dzielnikiem testowej rzeki, wybieramy rzekę 3 (1 + !(i%3)*2 ). Jeśli 9 jest największym wspólnym dzielnikiem rzeki testowej, zastępujemy poprzednie wartości i wybieramy rzekę 9.

Dlaczego to działa? Rzeka 9 płynie 9, 18, 27, 36 itd. Za każdym razem jest to wielokrotność 9, więc zawsze będzie to najkrótsza droga do siostrzanej rzeki. Rzeka 3 pokona wielokrotność 3 za każdym razem: 3, 6, 12, 15, 21 itd. Podczas gdy rzeki, które są wielokrotnością 9, są również wielokrotnością 3, najpierw wybieramy je jako rzekę 9, pozostawiając tylko wielokrotności 3. Pozostała część spotka się najpierw z rzeką 1: 1, 2, 4, 8, 16, 23, 28 itd.

Po wybraniu właściwej rzeki przeprawiamy się przez obie rzeki, aż się spotkają.

Python 3, 144 bajty

r,a,b,c,i={int(input())},{1},{3},{9},1
while i:
  for x in r,a,b,c:t=max(x);x|={sum(int(c)for c in str(t))+t}
  if r&(a|b|c):i=print(*r&(a|b|c))

do

Bardzo proste, wygląda tak długo, ponieważ rozwinąłem wszystkie 3 rzeki. Najpierw generuje 3 rzeki RIVER_LENGTH( do których mam nadzieję, że jest wystarczająco duży), a następnie dla każdego kroku Ndokonuje binarnego przeszukiwania wszystkich trzech strumieni, aby sprawdzić, czy jest w którymkolwiek z nich. Działa to, ponieważ strumienie są już posortowane, dzięki czemu możemy wykonać sprawdzenie w log(n)czasie.

#include <stdio.h>

#define RIVER_LENGTH 10000

int main() {
    int num_cases;
    scanf("%d", &num_cases);
    int cases[num_cases];
    int N;
    int s1[RIVER_LENGTH] = {1};
    int s3[RIVER_LENGTH] = {3};
    int s9[RIVER_LENGTH] = {9};
    int i;
    int temp;

    for (i = 1; i < RIVER_LENGTH; i++) {
        s1[i] = temp = s1[i-1];
        while (temp) {
            s1[i] += temp % 10;
            temp /= 10;
        }
    }

    for (i = 1; i < RIVER_LENGTH; i++) {
        s3[i] = temp = s3[i-1];
        while (temp) {
            s3[i] += temp % 10;
            temp /= 10;
        }
    }

    for (i = 1; i < RIVER_LENGTH; i++) {
        s9[i] = temp = s9[i-1];
        while (temp) {
            s9[i] += temp % 10;
            temp /= 10;
        }
    }

    int start;
    int end;
    int pivot;

    for (i=1; i <= num_cases; i++) {
        scanf("%d", &cases[i]);
    }

    for (i=1; i <= num_cases; i++) {
        printf("Case #%d\n\n", i);
        N = cases[i];

        while (1) {

            temp = N;
            while (temp) {
                N += temp % 10;
                temp /= 10;
            }

            start = 0;
            end = RIVER_LENGTH;
            pivot = 1;

            while (end != start && pivot != RIVER_LENGTH - 1) {
                pivot = start + ((end - start) >> 1);
                if (s1[pivot] == N) {
                    printf("first meets river 1 at %d\n\n", N);
                    goto case_done;
                } else if (N < s1[pivot]){
                    end = pivot;
                } else {
                    start = pivot+1;
                }
            }

            start = 0;
            end = RIVER_LENGTH;
            pivot = 1;

            while (end != start && pivot != RIVER_LENGTH - 1) {
                pivot = start + ((end - start) >> 1);
                if (s3[pivot] == N) {
                    printf("first meets river 3 at %d\n\n", N);
                    goto case_done;
                } else if (N < s3[pivot]){
                    end = pivot;
                } else {
                    start = pivot+1;
                }
            }

            start = 0;
            end = RIVER_LENGTH;
            pivot = 1;

            while (end != start && pivot != RIVER_LENGTH - 1) {
                pivot = start + ((end - start) >> 1);
                if (s9[pivot] == N) {
                    printf("first meets river 9 at %d\n\n", N);
                    goto case_done;
                } else if (N < s9[pivot]){
                    end = pivot;
                } else {
                    start = pivot+1;
                }
            }
        }

        case_done:;

    }
}

Najpierw potrzeba liczby dla liczby przypadków, zamiast 0ograniczania końca danych wejściowych, ponieważ wiesz, że C. Jest to tylko dla wygody i tak naprawdę nie wpływa na nic, więc mam nadzieję, że jest w porządku.