12583 – Memory Overflow UVA Solution

This is an easy problem from uva judge http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4028

Iterative Complete search.

How I did it

• I read the number of cases.
• Red the number of people, the days to remember(rem) and the group of people who remember (str string in my case).
• Traverse the str string. First check if the current person is remembered(map<char,int>), if the map value is greater than 0, increment the recognition with one.
• I traverse the map and decrease all element with -1. (One day less).
• Set the current element in the map with the (rem) days.
• Print the recognitions.
• Accepted! 😀

Hints

• You need to check the last (rem) days in the current day.
• If the sultan remember a person the map[char] is greater than 0..

Code

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int casos, people, rem;
    int recog;
    string str;
    char meet;
    map<char,int>mapa;

    scanf("%d", &casos);

    for(int i=1; i<=casos; i++)
    {
        scanf("%d %d", &people, &rem);
        cin>>str;

        recog = 0;

        for(int x=0; x<str.size(); x++)
        {
            meet = str[x];
            if(mapa[meet]>0)
                recog++;

            for(map<char,int>::iterator it=mapa.begin(); it!=mapa.end(); it++)
                mapa[it->first]--;
            mapa[meet] = rem;
        }
        printf("Case %d: %d\n", i, recog);
        mapa.clear();
    }
return 0;
}