## Mock CCC '24 Contest 1 J4/S1 - Magical Magnetic Marbles

View as PDF

Points: 5 (partial)
Time limit: 1.0s
Memory limit: 512M

Author:
Problem type

You are given a row of slots numbered from to . Each slot can either be vacant (0) or contain a magnetic marble (1). The magnetic forces in these marbles prompt adjacent ones to merge into a single marble, settling in the slot of the rightmost merging marbles. Marbles merge immediately when adjacent, including in the starting configuration. Your task is to place exactly marbles such that the resulting number of marbles is the minimum possible.

#### Input Specification

The input will consist of two lines. The first line will contain two integers and , representing the number of slots and number of marbles that you can add respectively.

The second line will contain a string of 0 and 1 of length .

The following table shows how the available marks are distributed.

Marks Awarded
marks
marks

#### Output Specification

The output will consist of a single integer indicating the minimum possible number of marbles in the slots after all marbles have been placed.

#### Sample Input 1

6 1
010111

#### Sample Output 1

2

#### Explanation for Sample 1

In the given example, the row of slots can be represented as 010111 at the beginning. We can perform a merge immediately, and the configuration becomes 010001. We can place one marble at the first slot and result in the configuration 110001. Then, another merge can be performed, and our final configuration becomes 010001 which has the minimum possible number of marbles after all marbles are placed and merged.

#### Sample Input 2

30 9
100010000000001001001000001001

#### Sample Output 2

3

• commented on Feb. 20, 2024, 2:48 a.m.

Can someone take a look at my submission. I keep getting WA for the 3rd test case. Thanks

• commented on Jan. 30, 2024, 3:44 a.m.

can someone explain case sanple 2?

• commented on Jan. 30, 2024, 5:51 a.m. edited

30 9

100010000000001001001000001001

(9 marbles remaining you have to add)

it is optimal to first use 2 marbles here

100010000000001001001000001001

Now: 100010000000001111001000001001 -- > 100010000000000001001000001001

(7 marbles remaining)

it is optimal to then use 2 marbles here

100010000000000001001000001001

Now: 100010000000000001001000001111 -- > 100010000000000001001000000001

(5 marbles remaining)

it is optimal to then use 2 marbles here

100010000000000001001000000001

Now: 100010000000000001111000000001 -- > 100010000000000000001000000001

(3 marbles remaining)

Finally, use 3 marbles here

100010000000000000001000000001

Now: 111110000000000000001000000001 -- > 000010000000000000001000000001

there are 3 marbles left in the slots at the end. the order of the operations could have been switched but hope this helps

• commented on Jan. 30, 2024, 12:37 p.m.

It is a bit hard to understand the example when you haven't put in the merging of the marbles into the explanation. But thank you so much, helped a lot!