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