Hackerrank – Popis problému
Celý popis zadania sa nacháza – Hackerrank.
Riešenie
Pre každé číslo robím nasledujúci postup:
Príklad pre 1234
Určím si počiatok skúmania. Začnem prvým jednociferným číslom od začiatku:
1
a skúmam zvyšok reťazca. Ten bude 234.
Ďalej skúmam každú číslicu väčšiu ako 1 vo zvyšku reťazca 234.
Druhá číslica väčšia ako 1 je 2
Tá sa nachádza na začiatku 234>. Urobím si zvyšok, ten bude 34.
Nasledovať by mala číslica 3, tá sa nachádza vo zvyšku 34. A nasleujúci zvyšok bude 4.
Potom nasleduje číslica 4 a tá je rovnaká ako zvyšok, čiže to bude beautiful string.
Príklad 101103
Určím si počiatok skúmania. Začnem prvým jednociferným číslom od začiatku:
1
a skúmam zvyšok reťazca. Ten bude 01103.
Nasledovať by mala číslica 2, ale zvyšok na ňu nezačína. Pokúsim sa začať dvojciferným číslom.
Ak začnem 10, zvyšok reťazca bude 1103.
Nasleduje číslo 11, to je na začiatku reťazca a zvyšok bude 03.
Naledovať by malo číslo 12, ale to nie je zhodné s 03.
Tak skúsim číslo 101 a zvyšok bude 103.
Nasledovať by malo 102, ale to nie je rovnaké ako 103, tak 101103 prehlásim, že nie je beautiful.
Javascript riešenie nefunguje pre čísla 9007199254740992
Vytvoril som riešenie v týchto programovacích jazykoch:
Všetky riešenia sú dostupné aj na mojom GitHub profile.
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
import java.util.*; public class Solution { public static void main(String[] args) { Scanner stdin = new Scanner(System.in); int tests = Integer.parseInt(stdin.nextLine()); t: for(int i = 0; i < tests; i++) { String s = stdin.nextLine(); for(int j = 1; j <= s.length() / 2; j++) { String head = s.substring(0, j); long headVal = Long.parseLong(head); long next = headVal + 1; String rest = s.substring(j); if(isContinous(rest, next)) { System.out.println("YES " + head); continue t; } } System.out.println("NO"); } stdin.close(); } private static boolean isContinous(String rest, long next) { String nextS = String.valueOf(next); int i = nextS.length(); while(i <= rest.length()) { if(!rest.startsWith(nextS)) { return false; } else { next = next + 1; rest = rest.substring(i); nextS = String.valueOf(next); i = nextS.length(); } } if(!rest.isEmpty()) { return false; } return true; } } |
Javascript
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 |
'use strict'; const isContinous = (rest, next) => { let nextS = next; let i = nextS.length; while(i <= rest.length) { if(!rest.startsWith(nextS)) { return false; } else { next = parseInt(next) + 1; rest = rest.substring(i); nextS = next.toString(); i = nextS.length; } } if(rest.length !== 0) { return false; } return true; } const processData = input => { const lines = input.split('\n'); const max = Number.MAX_SAFE_INTEGER; t: for(let i = 1; i < lines.length; i++) { const s = lines[i]; for(let j = 1; j <= parseInt(s.length / 2); j++) { const head = s.substring(0, j); const headVal = parseInt(head); let next; if (headVal > max) { let lastChar = parseInt(head.charAt(head.length - 1)) + 1; next = head.substring(0, j - 1) + lastChar; } else { next = (headVal + 1).toString(); } const rest = s.substring(j); if(isContinous(rest, next)) { console.log("YES " + head); continue t; } } console.log("NO"); } }; process.stdin.resume(); process.stdin.setEncoding("ascii"); let _input = ""; process.stdin.on("data", input => _input += input); process.stdin.on("end", () => processData(_input)); |