SHOW:
|
|
- or go back to the newest paste.
1 | // Author : Saurav Kalsoor | |
2 | - | // Basket Full of Balls - JAVA |
2 | + | // String Transformations - JAVA |
3 | ||
4 | ||
5 | import java.util.*; | |
6 | ||
7 | public class Test { | |
8 | - | |
8 | + | |
9 | - | static Scanner sc = new Scanner(System.in); |
9 | + | static Scanner sc = new Scanner(System.in); |
10 | public static void main(String[] args) { | |
11 | - | public static void main(String[] args) { |
11 | + | int n = sc.nextInt(); |
12 | - | int n = sc.nextInt(); |
12 | + | |
13 | ||
14 | String str = sc.next(); | |
15 | - | ArrayList<Integer> arr = new ArrayList<>(); |
15 | + | |
16 | - | for(int i=0; i < n ;i++){ |
16 | + | |
17 | - | arr.add(sc.nextInt()); |
17 | + | System.out.println(stringTransformations(n, k, str)); |
18 | } | |
19 | ||
20 | - | System.out.println(bucketFullOfBalls(n, k, arr)); |
20 | + | public static int stringTransformations(int n, int k, String s){ |
21 | - | } |
21 | + | char[] str = s.toCharArray(); |
22 | int first = -1, last = -1; | |
23 | - | public static int bucketFullOfBalls(int n, int k, ArrayList<Integer> arr){ |
23 | + | for(int i = 0;i < n; i++){ |
24 | - | HashMap<Integer, Integer> count = new HashMap<>(); |
24 | + | if(str[i] == '1'){ |
25 | - | for(int x : arr){ |
25 | + | if(first == -1){ |
26 | - | count.put(x, count.getOrDefault(x, 0) + 1); |
26 | + | first = i; |
27 | }else{ | |
28 | last = i; | |
29 | - | ArrayList<Integer> temp = new ArrayList<>(); |
29 | + | } |
30 | - | for(Map.Entry<Integer, Integer> m : count.entrySet()){ |
30 | + | } |
31 | - | if(m.getValue() >= k){ |
31 | + | |
32 | - | temp.add(m.getKey()); |
32 | + | |
33 | if(first == -1){ | |
34 | return 0; | |
35 | }else if(last == -1){ | |
36 | - | int m = temp.size(); |
36 | + | return 1; |
37 | - | if(m == 0){ |
37 | + | |
38 | - | return -1; |
38 | + | |
39 | int count = 2; | |
40 | str[first] = '2'; | |
41 | str[last] = '2'; | |
42 | ||
43 | - | int l = temp.get(0), r = l, i = 1; |
43 | + | int prevChanged = first; |
44 | - | while(i < m){ |
44 | + | |
45 | - | int j = i - 1; |
45 | + | while(prevChanged < last){ |
46 | - | while(i < m && temp.get(i) == temp.get(i-1) + 1){ |
46 | + | |
47 | - | i++; |
47 | + | if(last - prevChanged <= k) |
48 | return count; | |
49 | - | i--; |
49 | + | |
50 | int i = -1; | |
51 | - | if(temp.get(i) - temp.get(j) > r - l){ |
51 | + | for(int j = prevChanged+1; j <= Math.min(n - 1, (prevChanged + k)); j++){ |
52 | - | l = temp.get(j); |
52 | + | if(str[j] == '1'){ |
53 | - | r = temp.get(i); |
53 | + | i = j; |
54 | } | |
55 | } | |
56 | - | i+=2; |
56 | + | |
57 | if(i == -1){ | |
58 | return -1; | |
59 | - | return r - l; |
59 | + | |
60 | ||
61 | prevChanged = i; | |
62 | str[prevChanged] = '2'; | |
63 | count++; | |
64 | ||
65 | } | |
66 | ||
67 | return count; | |
68 | } | |
69 | ||
70 | } | |
71 | ||
72 |