[Topcoder] SRM396 ~ 403 연습

SRM396 DIV2

class VerifyCreditCard
{
public:

    string checkDigits(string c)
    {   
        int odd = 1;
        if( c.size()%2 == 0) odd = 0;

        stringstream in;
        REP(i, c.size())
        {
            int v = c[i] - '0';
            if( odd == 1)
            {
                if( i%2 == 1) in << 2*v;
                else in << v;
            }
            else
            {
                if(i%2 == 0) in << 2*v;
                else in << v;
            }
        }
        string s = in.str();
        int sum = 0;
        REP(i, s.size())
            sum += s[i] - '0';

        if( sum % 10 == 0) return "VALID";
        else return "INVALID";
   
    }
};

SRM397 DIV2

class BreakingTheCode
{
public:

    string decodingEncoding(string c, string m)
    {   
        stringstream in;
        if(isalpha(m[0]))
        {
            REP(i, m.size())
            {
                int index = c.find(m[i]) + 1;
                if(index < 10) in << "0";
                in << index;
            }
        }
        else
        {
            for(int i=0; i<m.size(); i += 2)
            {
                int index = (m[i]-'0')*10 + m[i+1]-'0' -1;
                in << c[index];
            }
        }

        return in.str();
    }   
};

SRM398 DIV2

class MinDifference
{
public:

    int closestElements(int A0, int X, int Y, int M, int n)
    {   
        VI d(1, A0);       
        for(int i=1; i<n; i++)
        {
            d.pb((d[i-1]*X + Y) % M);
        }

        sort(ALL(d));
        int ret = INT_MAX;
        for(int i = 1; i<d.size(); i++)
        {
            int dif = abs(d[i]-d[i-1]);
            if( ret > dif ) ret = dif;

        }

        return ret;
    }   
};

SRM399 DIV2

class CircularLine
{
public:

    int longestTravel(vector <int> t)
    {   
        VI d;
        REP(i, t.size())
        {           
            for(int j=i+1; j<t.size(); j++)
            {
                int c1 = 0, c2 = 0;
                for(int k=i; k < j; k++) c1 += t[k];
                for(int k=j; k< t.size(); k++) c2 += t[k];
                for(int k=0; k< i; k++) c2 += t[k];
                d.pb(min(c1, c2));
            }
        }
        sort(d.rbegin(), d.rend());
        return d[0];
    }   
};

O(n제곱)으로 다시 풀어본 소스
class CircularLine
{
public:

    int longestTravel(vector <int> t)
    {   
        int sum = 0, ret = 0;
        REP(i, t.size()) sum += t[i];
        REP(i, t.size())
        {       
            int cur = 0;
            for(int j=i; j<t.size()-1; j++)
            {
                cur += t[j];
                ret = max(ret, min(cur, sum-cur));
            }
        }
        return ret;
    }   
};

SRM400 DIV2

class GrabbingTaxi
{
public:

    int minTime(vector <int> tXs, vector <int> tYs, int gX, int gY, int walkTime, int taxiTime)
    {   
        int ret = (abs(gX)+abs(gY))*walkTime;
        REP(i, tXs.size())
        {
            ret = min(ret, (abs(tXs[i])+abs(tYs[i]))*walkTime + (abs(gX-tXs[i])+abs(gY-tYs[i]))*taxiTime);
        }

        return ret;
    }   
};

SRM401 DIV2

class DreamingAboutCarrots
{
public:

    int carrotsBetweenCarrots(int x1, int y1, int x2, int y2)
    {   
        int x = min(x1,x2);
        int y = min(y1,y2);
        int mx = max(x1,x2);
        int my = max(y1,y2);
       
        int ret = 0;
        for(int i=x; i<=mx; i++)
        {
            for(int j=y; j<=my; j++)
            {
                if(( i == x1 && j == y1)||(i==x2&& j==y2)) continue;
                else if( (y2-y1)*(i-x1) == (j-y1)*(x2-x1) ) ret++;
            }
        }

        return ret;
    }   
};

SRM402 DIV2

class WordAbbreviation
{
public:

    vector <string> getAbbreviations(vector <string> w)
    {   
        REP(i, w.size())
        {
            string s = w[i];
            for(int j=1; j<= s.size(); j++)
            {
                string tmp = s.substr(0, j);
                int ok = 1;
                REP(k, w.size())
                {
                    if( i!=k && tmp == w[k].substr(0, j))
                    {
                        ok = 0;
                        break;               
                    }
                }
                if(ok == 1)
                {
                    w[i] = tmp;
                    break;
                }
            }
        }

        return w;
    }   
};

SRM403 DIV2

class TheLargestLuckyNumber
{
public:

    int find(int n)
    {   
        for(int i=n; i>3; i--)
        {
            int a = i;
            while(1)
            {
                if( a%10 != 4 && a%10 != 7) break;
                a = a/10;
                if(a == 0) return i;
            }
        }
    }   
};