Digital River (kürzeste und schnellste Lösung)

9

Dies ist meine erste Frage, also hoffe ich, dass es gut geht.

Hintergrund:

Es sind nicht die Flüsse, an die Sie denken könnten. Die Frage dreht sich um das Konzept der digitalen Flüsse. Ein digitaler Fluss ist eine Folge von Zahlen , bei denen die Zahl hinter nist nplus die Summe der Ziffern.

Erläuterung:

Auf 12345 folgt 12360, da 1 + 2 + 3 + 4 + 5 = 15, und 12345 + 15 ergibt 12360. In ähnlicher Weise folgt 145 auf 155. Wenn die erste Nummer eines digitalen Flusses lautet M, nennen wir ihn Fluss M.

Zum Beispiel: Fluss 480 ist der Sequenzbeginn {480.492.507.519 ....} und Fluss 483 ist der Sequenzbeginn {483.498.519, ....}. Normale Bäche und Flüsse können sich treffen, und das gilt auch für digitale Flüsse. Dies geschieht, wenn zwei digitale Flüsse dieselben Werte teilen.

Beispiel:

Der Fluss 480 trifft den Fluss 483 um 519. Der Fluss 480 trifft den Fluss 507 um 507 und trifft nie den Fluss 481. Jeder digitale Fluss trifft schließlich auf den Fluss 1, den Fluss 3 oder den Fluss 9.

Schreiben Sie ein Programm, das für eine bestimmte Ganzzahl nden Wert bestimmen kann, bei dem der Fluss nzuerst auf einen dieser drei Flüsse trifft.

Eingang

Die Eingabe kann mehrere Testfälle enthalten. Jeder Testfall belegt eine separate Zeile und enthält eine Ganzzahl n( 1 <= n <= 16384). Ein Testfall mit dem Wert 0für nbeendet die Eingabe und dieser Testfall darf nicht verarbeitet werden.

Ausgabe

Geben Sie für jeden Testfall in der Eingabe zuerst die Testfallnummer (ab 1) aus, wie in der Beispielausgabe gezeigt. Dann wird auf einer separaten Zeilenausgabe die Zeile "trifft zuerst auf den Fluss x bei y". Hier ist y der niedrigste Wert, bei dem der Fluss nzuerst auf den Fluss trifft x(x = 1 oder 3 oder 9). Wenn Fluss ntrifft Fluss xan yfür mehr als einen Wert von x, Ausgabe der niedrigste Wert. Drucken Sie eine leere Zeile zwischen zwei aufeinander folgenden Testfällen.

Testfall

Eingang:

86
12345
0

Ausgabe:

Case #1

first meets river 1 at 101

Case #2

first meets river 3 at 12423

Wertung:

Der schnellste Algorithmus gewinnt. Im Falle einer Krawatte. Der mit dem kürzeren Code gewinnt.

Vielen Dank an mbomb007 für den Hinweis auf meinen Fehler.

ps: Ich möchte eher die schnellste als die kleinste Lösung haben. Ich habe auch eine Lösung von mir, die langsam ist. Dafür schauen Sie hier .

Hinweis:

Ich werde dies für Code-Tests verwenden. Und Leistungsprüfung.

Kishan Kumar
quelle
3
Ich bin mir nicht sicher, ob Sie so punkten können. Was ist, wenn jemandes Code O ist (log (log n))? Sie können nicht alle abdecken, also müssen Sie nur sagen, dass der schnellste Algorithmus gewinnt, aber im Falle eines Unentschieden gewinnt der kürzeste Code und der erste veröffentlichte Gewinn, wenn beide gleich lang sind.
mbomb007
3
Ich kann nichts zum Urheberrecht oder zur Verwendbarkeit alter ACM-ICPC-Herausforderungen finden, aber ich kann diese Herausforderung auf der Archivseite finden. Darf hier verwendet werden?
Geobits
1
Das hat nichts mit Urheberrecht zu tun. Im Zweifelsfall ist es normalerweise am einfachsten, den Website-Eigentümern eine E-Mail zu senden und zu fragen.
Geobits
3
" Wenn die letzte Ziffer eines digitalen Flusses ist M, nennen wir ihn FlussM " ist aus zwei Gründen nicht sinnvoll: Erstens, wenn ein Fluss eine unendliche Folge von Zahlen ist, hat er keine letzte Ziffer; und zweitens bedeutet Fluss im nächsten Absatz den FlussM , der bei Nummer beginnt M.
Peter Taylor
2
Aus der verknüpften CR.SE-Frage geht hervor, dass ein Fluss die Nummer ist, mit der in der Serie begonnen wurde, aber hier ist die letzte Ziffer. Welches ist richtig?
Celeo

Antworten:

3

C 320 294 Bytes

Kompilieren Sie mit -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]);}}

Ungolfed:

#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]);
    }
}

Versuch es!

Im Wesentlichen werden die "Ziel" -Flüsse erhöht, bis sie größer sind als der Fluss, gegen den wir testen, und danach wird der Testfluss erhöht. Dies wird wiederholt, bis der Testfluss einem anderen Fluss entspricht.

Ich lese in diesem Programm keine Parameter über die Befehlszeile und bin mir nicht sicher, ob Sie das sollen. Jetzt können Sie Parameter an STDIN übergeben. Sie können den Vorgang beenden, indem Sie eine nicht numerische Eingabe übergeben.

Auch verdammt, um eine halbe Stunde geschlagen.


quelle
Ich arbeite gerade an Testfällen. Nur 3 Eingabetestfälle sind nicht sehr geeignet.
Kishan Kumar
bitte würde es Ihnen etwas ausmachen, Eingaben von stdin zu nehmen.
Kishan Kumar
3

JavaScript (ES6)

Dies ist eine ziemlich schnelle Antwort mit einer ziemlich langsamen Sprache. In Wirklichkeit sollte die Ausführung von Zeit kein Problem sein, wenn eine Sprache mit Hash-Tabellen verwendet wird. Alle meine Tests unter 100 ms.

Anonyme Methode mit der Liste der Testfälle als Eingabeparameter.

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

edc65
quelle
1

Java 7, 519 505 Bytes

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

Ja, es ist lang, hässlich und kann ohne Zweifel komplett auf Code-Golf umgestellt werden. Ich bin sowohl abgelenkt als auch müde, also sollte ich es vielleicht einfach wieder löschen.
Es war eine ziemlich schwierige Herausforderung, um ehrlich zu sein. Aber zumindest hast du deine erste Antwort ..;) (Die könnte sogar länger sein als dein ursprüngliches ungolviertes C ++ - Programm .. xD)

Ungolfed & Testfälle:

Probieren Sie es hier aus.

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

Ausgabe:

first meets river 1 at 101
first meets river 3 at 12423
(empty output)
Kevin Cruijssen
quelle
Ich werde dein Programm mit meinem vergleichen. Ich werde auch meine Lösung veröffentlichen. Warum eine langsame Sprache verwenden? Verwenden Sie eine schnelle Sprache.
Kishan Kumar
Ich habe das Tag mit dem schnellsten Algorithmus erst später bemerkt. Ich poste hier immer Java 7-Code-Golf-Antworten. Es wird definitiv weder in kürzester noch in kürzester Zeit gewinnen. Übrigens, Ihr Rextester gibt Fehler aus, wenn er nur Warnungen geben sollte mangels Casts / Typ-Initialisierungen. Es funktioniert auf Ideone (und in Eclipse IDE).
Kevin Cruijssen
in Ordnung. Lass mich sehen. Der Rextester gibt die Kompilierungs- und Ausführungszeit an. Also habe ich es benutzt
Kishan Kumar
Nun, das ist hier ein Problem. Ich werde nach anderen Online-Compilern suchen, die die Kompilierungs- und Ausführungszeit
angeben
@KishanKumar Ich habe die Casts in meinen Code eingefügt, was sich nicht auf die Zeit auswirken sollte. Hier ist der funktionierende Rextester-Code mit dem Ergebnis: Compilation time: 0.62 sec, absolute running time: 0.14 sec, cpu time: 0.11 sec, memory peak: 22 Mb, absolute service time: 0,77 secfür mich vor Ort. Also ja, es ist ziemlich langsam.
Kevin Cruijssen
1

Scala, 774 Bytes

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

Ich habe keine Lust, Golf zu spielen. Es findet eine Lösung für das gestellte Problem innerhalb von 50 ms

Die Verwendung entspricht möglicherweise nicht genau Ihren Wünschen:

scala river.scala

Jetzt können Sie fortlaufend Zahlen eingeben, gefolgt von einer Eingabe. Beenden Sie das Programm mit 0. Das Ergebnis wird gedruckt, sobald Sie die Eingabetaste drücken.

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
AmazingDreams
quelle
Ich weiß nicht viel über Scala. Könnten
Kishan Kumar
Ich habe versucht, es dort abzulegen, aber beim Kompilieren ist die Zeit abgelaufen.
AmazingDreams
ok @AmazingDreams
Kishan Kumar
@ KishanKumar sogar die Standardeinstellung einmalig, so dass die Website für Scala gebrochen zu sein scheint
AmazingDreams
@KisthanKumar Verwenden Sie dieses eine skalafiddle.net/console/4ec96ef90786e0f2d9f7b61b5ab0209b es unterstützt jedoch nicht stdin, so dass ich einige kleinere Dinge ändern musste.
AmazingDreams
1

C 228 283 300 Bytes

Dies ist eine Modifikation von Yakovs Code, um die Flussmuster auszunutzen. Dies macht es ~ 3x schneller. Ganzzahlen ohne Vorzeichen vermeiden außerdem die cltodStrafe auf 64-Bit-Computern, sodass sie einige Bytes länger, aber geringfügig schneller sind.

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

Ungolfed:

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

Erläuterung:

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

Dies wählt den richtigen Fluss aus. Fluss 1 trifft auf jeden anderen Fluss, daher verwenden wir diesen Fall als Fallback-Fall. Wenn 3 der größte gemeinsame Teiler des Testflusses ist, wählen wir Fluss 3 ( 1 + !(i%3)*2). Wenn 9 der größte gemeinsame Teiler des Testflusses ist, überschreiben wir die vorherigen Werte und wählen Fluss 9 aus.

Warum funktioniert das? Fluss 9 geht 9, 18, 27, 36 usw. Dies wird jedes Mal um ein Vielfaches von 9 schrittweise durchgeführt, sodass es immer der kürzeste Weg zu einem Schwesterfluss ist. Fluss 3 wird jedes Mal um ein Vielfaches von 3 schrittweise ausgeführt: 3, 6, 12, 15, 21 usw. Während Flüsse, die ein Vielfaches von 9 sind, auch ein Vielfaches von 3 sind, wählen wir sie zuerst als Fluss 9 aus und lassen nur den Vielfache von 3. Der Rest trifft zuerst auf Fluss 1: 1, 2, 4, 8, 16, 23, 28 usw.

Sobald wir unseren richtigen Fluss ausgewählt haben, gehen wir die beiden Flüsse entlang, bis sie sich treffen.

Seth
quelle
1

Python 3, 144 Bytes

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))
Trelzevir
quelle
0

C.

Sehr einfach, es sieht nur so lange aus, weil ich alle 3 Flüsse ausgerollt habe. Es generiert zuerst die 3 Flüsse bis zu RIVER_LENGTH(was hoffentlich groß genug ist) und führt dann für jeden Schritt Neine binäre Suche in allen drei Strömen durch, um festzustellen, ob es sich in einem von ihnen befindet. Dies funktioniert, da die Streams bereits sortiert sind, sodass wir die Eincheckzeit für die Enthaltene durchführen log(n)können.

#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:;

    }
}

Es wird zuerst eine Zahl für die Anzahl der Fälle benötigt, anstatt 0das Ende der Eingaben abzugrenzen, da Sie wissen, C. Dies dient nur der Bequemlichkeit und hat keinen wirklichen Einfluss auf irgendetwas. Ich hoffe, es ist in Ordnung.

Maltysen
quelle
Dieses Programm erreicht ein Zeitlimit, das auf ideone für Eingaben 86.12345,0 überschritten wurde
Kishan Kumar
ideone.com/mHCeef hier ist der Link. Und es gibt ein Kill-Signal am Rextester ausgegeben
Kishan Kumar
@KishanKumar Es wird zuerst eine Zahl für die Anzahl der Fälle benötigt, anstatt 0 zu verwenden, um das Ende der Eingaben abzugrenzen, weil Sie wissen, C. Dies dient nur der Bequemlichkeit und hat keinen wirklichen Einfluss auf irgendetwas, also hoffe ich, dass es in Ordnung ist.
Maltysen
@ KishanKumar versuchen Sie dieses stattdessen: rextester.com/XRJK89444
Maltysen
Es ist in Ordnung. Kein Problem. Aber ich muss ein zusätzliches Skript für Ihr Programm schreiben. Da muss ich mir die durchschnittliche Zeit des gesamten Eingabebereichs nehmen.
Kishan Kumar