Programmiererforum

Dies war also eine Frage zu einer der Herausforderungen, die ich vor einigen Tagen in einem Online -Wettbewerb gestoßen habe. < /p>

Akzeptieren Sie zwei Eingänge. < /p>


Eine große Anzahl von [b] n < /em> < /strong> Ziffern, < /li>
Die Anzahl der Fragen q [/b] zu stellen. < /li>
< /ol>

In jeder der Frage müssen Sie feststellen, ob die Anzahl der von der Zeichenfolge zwischen Indizes [b] l < /em> [/b] [b] i [/b] und [b] r [/b] [b] i [/b] ist durch 7 teilbar oder nicht. P>

Die erste Zeile enthält die Zahl, die auf [b] n < /em> < /strong> Ziffern besteht. Die nächste Zeile enthält q [/b], die die Anzahl der Fragen bezeichnet. Jede der nächsten [b] q [/b] Linien enthält 2 Ganzzahlen [b] l [/b] [b] i [/b] < /sub> und [b] r [/b] [b] i [/b] .

[b] Ausgabe: < /strong> < /p>

Für jede Frage drucken Sie "Ja" oder "Nein", wenn die von der gebildete Nummer String zwischen Indizes l [/b] [b] i [/b] und [b] r [/b] [b] i [/b] ist durch 7 teilbar. > Einschränkungen: < /strong> < /p>

1 ≤ n ≤ 10 5 < /sup> < /p>

1 ≤ q ≤ 10 5

1 ≤ l i , r i ≤ N < /p>

[b] Beispieleingang: < /strong> < /p>

357753

3

1 2

2 3

4 4
< /P>

Beispielausgabe: < /strong> < /p>

Ja

nein

Ja
< / p>

Erläuterung: < /strong> < /p>

Für die erste Abfrage ist die Zahl 35, was eindeutig teilbar ist Mit 7. Jede Eingabedatei. < /p>

Speichergrenze: < /em> < /strong> 256 mb < /p>

< Strong> Quellgrenze: < /em> < /strong> 1024 kb < /p>



Mein Ansatz : [/b]

Jetzt gemäß den Einschränkungen kann die maximale Länge der Zahl d. H. [b] n [/b] bis zu [b] betragen 10 [/b] [b] 5 [/b] . Diese große Zahl kann nicht in eine numerische Datenstruktur eingebaut werden, und ich bin mir ziemlich sicher, dass dies nicht der effiziente Weg ist. Strong> < /p>

Ich dachte an diesen Algorithmus, die generischen Regeln der Teilung auf jede einzelne Ziffer der Zahl anzuwenden. Dies würde sich in der linearen Zeit untersuchen, d. H. [b] o (n) < /strong>. < /P>

static String isDivisibleBy(String theIndexedNumber, int divisiblityNo){

int moduloValue = 0;

for(int i = 0; i < theIndexedNumber.length(); i++){

moduloValue = moduloValue * 10;
moduloValue += Character.getNumericValue(theIndexedNumber.charAt(i));
moduloValue %= divisiblityNo;
}

if(moduloValue == 0){
return "YES";
} else{
return "NO";
}

}
< /code>

Aber in diesem Fall muss der Algorithmus auch alle Werte von q < /strong> durchlaufen, was auch bis zu 10 [/b] [b] 5 [/b] .

Daher wird die Zeit, die zur Lösung des Problems benötigt wird >. Daher überquerte dies die angegebene Zeitgrenze und war nicht effizient. BR />
Nachdem dies nicht funktioniert habe, habe ich versucht, nach einer -Schivisbarkeitsregel von 7 < /strong> zu suchen. Alle, die ich gefunden habe, umfassten Berechnungen basierend auf jeder einzelnen Ziffer der Zahl. Daher würde dies wieder zu einem linearen Zeitalgorithmus führen. Und daher würde es in Kombination mit der Anzahl der Fragen eine quadratische Zeit ausmachen Pohlman -Mass -Methode der Spaltbarkeit durch 7 < /strong>, was < /p>


verwendet hat > 42,341,530
-> 530 -341 = 189 + 42 = 231 -> 23 -(1 × 2) = 21 Ja < /p>
< /blockquote>

< P> Aber alles, was tat, war die Zeit 1 /3. Q.n, was nicht viel half. Vermisse ich hier etwas? Kann mir jemand helfen, einen Weg zu finden, um dies effizient zu lösen?>