[Topcoder] SRM144 ~ 148 DIV2 500pt 연습

Topcoder DIV2 medium문제들을 한번 풀어보자.

SRM144 550pt.
: encrypt된 문자를 decrypt하는 문제. 문제는 어렵지 않았으나 예외처리 같은 부분에 시간이 좀 소요

class BinaryCode
{
public:

    vector <string> decode(string m)
    {
        vector<string> ret;
        int n = m.size();

        vector<int> d;
        REP(i, n) d.pb( m[i] - '0');
       
        int inx = 0;
        while(inx < 2)
        {
            vector<int> out;
            bool is_fail = false;
            for(int i=0; i<n; i++)
            {
                int p;
                if( i == 0 ) p = inx;
                else if( i == 1 ) p = d[i-1] - out[i-1];
                else p = d[i-1] - out[i-1] - out[i-2];

                if( p > 1 || p < 0 )
                {
                    is_fail = true;
                    break;
                }
                else
                {
                    out.pb(p);
                }
            }       
            inx++;


            if( is_fail || ( n == 1 && out[n-1] != d[n-1]) || (n > 1 && out[n-1] + out[n-2] != d[n-1]))
               ret.pb("NONE");
            else
            {           
                string s;
                REP(i, out.size())
                    s.pb(out[i]+'0');
                ret.pb(s);

            }
        }

        return ret;
    }   
};


SRM145 500pt.
: 문제해석이 잘 안되던 문제.. 뭘 원하는건지 이해하기가 어려웠다..
단위 work의 시간이 주어졌고, 퍼센트가 정수로 떨어질 경우만 퍼센트가 올라가는 머신이 있을 때,
단위 work가 끌날 시점에 몇 퍼센트를 가리키고 있을까가 문제다.

결국 현재까지 초와 100간의 gcd(s,100)-1 을 묻는 문제였음..

class ExerciseMachine
{
public:

    int getPercentages(string time)
    {
        REP(i, time.size())
            if(time[i] == ':') time[i] = ' ';
        istringstream in(time);

        int h, m, s;
        in >> h >> m >> s;
        int sec = h*3600 + m * 60 + s;
       
        int ret = 0;
        for(int i =1; i < sec; i++)
        {
            for(int j=1; j < 100; j++)
            {
                if( j*sec == 100*i )
                    ret++;
            }
        }

        return ret;
    }   
};

SRM146 500pt.
: 사이즈 (w, h)인 직사각형안에 들어갈 수 있는 사이즈(x, y) 사각형의 개수는 (w-x+1)*(h-y+1)개라는 부분을 파악하면 풀이는 쉽다.

class RectangularGrid
{
public:

    long long countRectangles(int w, int h)
    {
        long long ret  = 0;
        for(int i=1; i <= max(w, h); i++)
        {
            for(int j=1; j <= max(w, h); j++)
            {
                if( i == j) continue;

                int x = w - i + 1;
                int y = h - j + 1;
                if( x > 0 && y > 0 )
                {
                    ret += x * y;
                }
            }
        }

        return ret;
    }   
};

SRM147 500pt.
class PeopleCircle
{
public:

    string order(int m, int f, int K)
    {
        int n = m+f;
        string ret(n, 'M');
       
        int p = 0;
        REP(i, f)
        {
            int cnt = K;
            while(cnt > 1)
            {
                if(ret[p] == 'M') cnt--;
                p = (p+1)%n;
            }
            while( ret[p] != 'M')
            {
                p = (p + 1)%n;
            }

            ret[p] = 'F';

            if( i == f-1) return ret;
            while( ret[p] != 'M')
            {
                p = (p + 1)%n;
            }
        }
       

        return ret;
    }   
};

SRM148 600pt.
: 600점이라 어려울 줄 알았는데 생각보다 쉬운 문제..

class CeyKaps
{
public:

    string decipher(string t, vector <string> switches)
    {
        REP(i, switches.size())
        {
            string s = switches[i];           
            REP(j, t.size())
            {
           
                if( t[j] == s[0])
                {                   
                    t[j] = s[2];
                }
                else if( t[j] == s[2])
                {
                    t[j] = s[0];
                }
            }
        }
       
        return t;
    }   
};