[Topcoder] SRM361 ~ 369 연습

SRM361 DIV2

class SearchBox
{
public:

    int find(string t, string search, string w, int start)
    {   
        int n = search.size();

        for(int i=start; i+n <= t.size() ; i++)
        {
            string s = t.substr(i, n);
            if(w == "Y")
            {
                if( s == search && (i == 0 || t[i-1] == ' ') && (i+n == t.size() || t[i+n] == ' ')) return i;
            }
            else if(w == "N")
            {
                if( s == search) return i;           
            }
        }

        return -1;
    }
};

SRM362 DIV2
: 첫번째 공을 그냥 반복문 안에 포함시키는게 나았다.

class ThrowTheBall
{
public:

    int timesThrown(int N, int M, int L)
    {   
        if(M == 1) return 0;

        VI d(N, 0);
        d[0] = 1;

        int pos = 0, ret = 0;
        while(1)
        {
            if( d[pos] % 2 == 1) pos = (pos + L)%N;
            else  pos = (pos - L + N)%N;

            d[pos]++;
            ret++;
            if( d[pos] == M) return ret;           
        }

        return ret;
    }
};

SRM363 DIV2
: 앞에 0을 채우려면 sprintf 할때 %02d 로 써야한다. %2d로 하니 앞자리가 공백이 되어서 그냥 stream썼음..

class MirroredClock
{
public:

    string whatTimeIsIt(string t)
    {   
        istringstream in(t);
        int a, b;
        int a1, b1;
        char c;
        in >> a >> c >> b;

        a1 = (12 - a) % 12;
        if( b != 0) a1--;
        b1 = (60 - b)%60;       

        ostringstream out;
        if( a1 < 10) out << "0";
        out << a1 << ":";
        if(b1 < 10) out << "0";
        out << b1;

        return out.str();
    }
};

SRM364 DIV2

class MorselikeCode
{
public:

    string decrypt(vector <string> l, string m)
    {   
        string ret;
        vector< pair<string, string> > d;

        REP(i, l.size())
            d.pb( make_pair(l[i].substr(0, 1), l[i].substr(2)) );

        istringstream in(m);
        string s;
        while(in >> s)
        {
            int ok = 0;
            REP(i, d.size())
            {
                if( s == d[i].second )
                {
                    ok = 1;
                    ret += d[i].first;
                }
            }
            if(ok == 0) ret += "?";
        }

        return ret;
    }
};

SRM365 DIV2
: 문제파악이 시간이 좀 걸렸다. 다시 풀어볼 것.

class TournamentsAmbiguityNumber
{
public:

    int scrutinizeTable(vector <string> t)
    {   
        int n = t[0].size();
        int ret = 0;
        REP(i, t.size())
            REP(j, n)
                REP(k, n)
                    if(t[i][j] == '1' && t[j][k] == '1' && t[k][i] == '1') ret++;

        return ret;
    }
};

SRM366 DIV2
: 좋은 문제.

class SerialNumbers
{
public:

    int serial(string a, string b)
    {
        if( a.size() > b.size() )
            return -1;
        else if(a.size() < b.size())
            return 1;
       
        int a1 = 0, b1 =0;
        REP(i, a.size())
            if( isdigit(a[i]) ) a1 += a[i]-'0';
        REP(i, b.size())
            if( isdigit(b[i]) ) b1 += b[i]-'0';

        if( a1 < b1) return 1;
        else if(a1 > b1) return -1;
        else return 0;
    }

    vector <string> sortSerials(vector <string> s)
    {   
        sort(ALL(s));

        REP(i, s.size())
        {
            string temp = s[i];
            int index = i;
            for(int j=i+1; j<s.size(); j++)
            {
                if(serial(temp, s[j]) < 0 )
                {
                    temp = s[j];               
                    index = j;
                }
            }
            swap(s[i], s[index]);
            sort(s.begin()+i+1, s.end());
        }
       
        return s;
    }
};

다시 짜본 소스( sort함수에 인자로 넣을 cmp함수는 클래스 밖에서 선언해야 함)
bool cmp(string a, string b)
{
    if( a.size() != b.size() ) return a.size() < b.size();
   
    int a1 = 0, b1 =0;
    REP(i, a.size())
        if( isdigit(a[i]) ) a1 += a[i]-'0';
    REP(i, b.size())
        if( isdigit(b[i]) ) b1 += b[i]-'0';

    if( a1 != b1) return a1 < b1;
    return a < b;
}

class SerialNumbers
{
public:

    vector <string> sortSerials(vector <string> s)
    {   
        sort(ALL(s), cmp);   
        return s;
    }
};

SRM367 DIV2

class WhiteCells
{
public:

    int countOccupied(vector <string> b)
    {   
        int ret = 0;
        REP(i, b.size())
        {
            REP(j, b[i].size())
            {
                if((i+j)%2 == 0 && b[i][j] == 'F') ret++;
            }
        }       
        return ret;
    }
};

SRM368 DIV2
: 1/sqrt(2.0)을 곱해주기 보다는 sqrt(2.0)/2 를 곱해주는 센스

class PirateTreasure
{
public:

    double getDistance(vector <int> s, vector <string> d)
    {   
        double x =0, y=0;
        REP(i, s.size())
        {
            string t = d[i];
            if(t == "NORTH") y += s[i];
            if(t == "SOUTH") y -= s[i];
            if(t == "EAST") x += s[i];
            if(t == "WEST") x -= s[i];
            if(t == "NORTHEAST")
            {
                x += s[i]/sqrt(2.0);
                y += s[i]/sqrt(2.0);
            }
            if(t == "NORTHWEST")
            {
                x -= s[i]/sqrt(2.0);
                y += s[i]/sqrt(2.0);
            }
            if(t == "SOUTHEAST")
            {
                x += s[i]/sqrt(2.0);
                y -= s[i]/sqrt(2.0);
            }
            if(t == "SOUTHWEST")
            {
                x -= s[i]/sqrt(2.0);
                y -= s[i]/sqrt(2.0);
            }
        }
   
        return sqrt(x*x + y*y);
    }
};

SRM369 DIV2

class ChainOfRectangles
{
public:

    int getMaximalArea(vector <int> w, vector <int> h, string c)
    {   
        map<char, int> d;
        REP(i, c.size())
        {           
            int area = w[i]*h[i];
            d[c[i]] += area;
            if(i>0)
            {
                d[c[i-1]] -= area;
            }
        }
        int ret = 0;
        for(map<char, int>::iterator pos = d.begin(); pos != d.end(); pos++)
            ret = max(ret, pos->second);
       
        return ret;
    }
};