Coffee Pot

Programmer Linas decided to change his occupation and lifestyle. Without much thought, Linas moved to Paris and got employed to wash dishes in a small restaurant. He works hard in the small kitchen. To have more fun during breaks, Linas has brought a coffee pot.

During lunch time, dirty plates are passed to Linas through a small window. There are K different sizes of plates, and Linas sorts the plates to K different piles. When Linas gets a new plate, he washes it, quickly dries it and then, depending on the size of the plate, places it on the appropriate pile.

Since there’s not much room in the kitchen, Linas keeps his coffee pot on top of a pile of plates. If Linas wants to place a new plate on a pile with the coffee pot, he has to move the coffee pot to another pile.

Linas can’t stop thinking: “if I knew the order in which plates arrive, I could move the coffee pot less often.” Can you help Linas solve this task?

Task

Given the order of the plates that are passed to Lines, find the smallest possible number of coffee pot moves. At the beginning the pot can be placed on any pile.

Input

The first line contains two integers: the number of plates N and the number of piles
K.

Each of the next N lines contains a single integer a_i (1 \leq a_i \leq K), the pile where i-th plate has to be placed. These numbers are provided in the order of Linas getting the plates.

Output

Output a single integer – the smallest possible number of coffee pot moves Linas would have to make while washing the dishes.

Sample Input

8 3
3
1
2
1
1
3
3
2

Sample Output

2

The minimum number of coffee pot moves is 2. Before he starts his work, Linas can put the coffee pot on the first pile, and after washing the second plate – move the pot to the third pile. After washing the sixth plate, Linas should move the pot back to the first pile.

It is not possible to finish the job with fewer coffee pot moves, however the same result can be achieved differently.

Problem Source : Lithuanian Olympiad in Informatics

Solution

#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>

using namespace std;

int main(){

    int N, K;
    cin >> N >> K;

    // create vector
    vector<int> dish;
    int d;
    for (int i=0; i<N; i++){
        cin >> d;

        dish.push_back(d);
    }

    // remove similar consecutives
    vector<int>::iterator it = unique(dish.begin(), dish.end());
    dish.resize(distance(dish.begin(), it));

    // start search
    bool pile[K+1];
    memset(pile, 0, sizeof(pile));
    int move = 0;
    int full = 0;
    for (it = dish.begin(); it != dish.end(); it++){
        
        if (full == -1){
            full = 0;
            move++;
        }
        
        if (pile[*it] == 0){
            full++;
            pile[*it] = 0;
        }

        if (full == K-1){
            full = -1;
            memset(pile, 0, sizeof(pile));
        }

    }

    cout << move << endl;

    return 0;
}
Advertisements
Coffee Pot

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s