SHOW:
|
|
- or go back to the newest paste.
1 | // Author : Saurav Kalsoor | |
2 | - | // String Transformations - JAVA |
2 | + | // String Transformations - KOTLIN |
3 | ||
4 | ||
5 | - | import java.util.*; |
5 | + | import java.util.* |
6 | - | |
6 | + | |
7 | - | public class Test { |
7 | + | var sc = Scanner(System.`in`) |
8 | - | |
8 | + | |
9 | - | static Scanner sc = new Scanner(System.in); |
9 | + | fun main() { |
10 | - | public static void main(String[] args) { |
10 | + | val n = sc.nextInt() |
11 | - | int n = sc.nextInt(); |
11 | + | val k = sc.nextInt() |
12 | - | int k = sc.nextInt(); |
12 | + | val str = sc.next() |
13 | println(stringTransformations(n, k, str)) | |
14 | - | String str = sc.next(); |
14 | + | |
15 | - | |
15 | + | |
16 | - | |
16 | + | fun stringTransformations(n: Int, k: Int, s: String): Int { |
17 | - | System.out.println(stringTransformations(n, k, str)); |
17 | + | val str = s.toCharArray() |
18 | - | } |
18 | + | var first = -1 |
19 | - | |
19 | + | var last = -1 |
20 | - | public static int stringTransformations(int n, int k, String s){ |
20 | + | for (i in 0 until n) { |
21 | - | char[] str = s.toCharArray(); |
21 | + | if (str[i] == '1') { |
22 | - | int first = -1, last = -1; |
22 | + | if (first == -1) { |
23 | - | for(int i = 0;i < n; i++){ |
23 | + | first = i |
24 | - | if(str[i] == '1'){ |
24 | + | } else { |
25 | - | if(first == -1){ |
25 | + | last = i |
26 | - | first = i; |
26 | + | } |
27 | - | }else{ |
27 | + | } |
28 | - | last = i; |
28 | + | } |
29 | - | } |
29 | + | if (first == -1) { |
30 | - | } |
30 | + | return 0 |
31 | - | } |
31 | + | } else if (last == -1) { |
32 | return 1 | |
33 | - | if(first == -1){ |
33 | + | } |
34 | - | return 0; |
34 | + | var count = 2 |
35 | - | }else if(last == -1){ |
35 | + | str[first] = '2' |
36 | - | return 1; |
36 | + | str[last] = '2' |
37 | - | } |
37 | + | var prevChanged = first |
38 | while (prevChanged < last) { | |
39 | - | int count = 2; |
39 | + | if (last - prevChanged <= k) return count |
40 | - | str[first] = '2'; |
40 | + | var i = -1 |
41 | - | str[last] = '2'; |
41 | + | for (j in prevChanged + 1..Math.min(n - 1, prevChanged + k)) { |
42 | if (str[j] == '1') { | |
43 | - | int prevChanged = first; |
43 | + | i = j |
44 | } | |
45 | - | while(prevChanged < last){ |
45 | + | } |
46 | if (i == -1) { | |
47 | - | if(last - prevChanged <= k) |
47 | + | return -1 |
48 | - | return count; |
48 | + | } |
49 | - | |
49 | + | prevChanged = i |
50 | - | int i = -1; |
50 | + | str[prevChanged] = '2' |
51 | - | for(int j = prevChanged+1; j <= Math.min(n - 1, (prevChanged + k)); j++){ |
51 | + | count++ |
52 | - | if(str[j] == '1'){ |
52 | + | } |
53 | - | i = j; |
53 | + | return count |
54 | - | } |
54 | + | } |