[Topcoder] SRM334 ~ 347 연습

SRM334 DIV2
: 같은 값이 나올 수 있다는 걸 못 보고 실수할 수 있음.
푼 내용중에 g[0]+g[2] >= 50 인 경우는 어차피 밑에 경우랑 같은 경우였다..
그냥 0, 1, 2 순으로 더하면서 50넘을때마다 10빼주면 되는 문제였음.

class SupermarketDiscount
{
public:

    int minAmount(vector <int> g)
    {   
        sort(ALL(g));

        int ret = 0;
        if( g[0] >= 50) ret = g[0] + g[1] + g[2] -30;
        else if( g[0] + g[1] >= 50) ret = g[0] + g[1] + g[2] - 10 - g[2]/50*10;
        else if( g[0] + g[2] >= 50) ret = g[0] + g[1] + g[2] - 10 - g[1]/50*10;
        else if(  g[0] + g[1] + g[2] >= 50) ret = g[0] + g[1] + g[2] - 10;
        else ret = g[0] + g[1] + g[2] ;

        return ret;
    }
};

SRM335 DIV2
: 나의 풀이 - 모든 가능한 string을 찾아서 크기가 제일 작은거 리턴..
 - 참고할 풀이 : 펠린드롬인 가장 큰 substring을 찾아서 reverse해서 붙임.
어차피 붙여질 substring은 팰린드롬한 오른쪽 substring 을 뺀 왼쪽 부분을 뒤집어서 붙인 string

class Palindromize
{
public:

    int ispalind(string s)
    {
        int n = s.size();
        REP(i, n/2)
            if(s[i] != s[n-1-i]) return 0;
        return 1;
    }
    string minAdds(string s)
    {   
        string s1 = s;
        reverse(ALL(s1));

        vector<string> d;
        for(int i=0; i < s.size(); i++)
        {
            for(int j=0; j+i <= s.size(); j++)
            {
                string s2 = s +  s1.substr(i, j);
                if( ispalind(s2) && !s2.empty() ) d.pb(s2);
            }
        }

        string ret = s + s1;
        REP(i, d.size())
            if( d[i].size() < ret.size()) ret = d[i];

        return ret;
    }
};

다시 짜본 소스
class Palindromize
{
public:
    string minAdds(string s)
    {   
        for(int i=0; i<s.size(); i++)
        {
            string sub = s.substr(0, i);
            reverse(ALL(sub));
            string T1 = s + sub;
            string T2 = T1;
            reverse(ALL(T2));
            if(T1 == T2) return T1;
        }
    }
};

SRM336 DIV2
: 모음이 아닌 string과 모음인 string을 구해서 그냥 더해주는게 더 심플한 솔루션..

class VowelLatin
{
public:
    string translate(string w)
    {   
        int n = w.size();
        int index = 0;
        REP(i, n)
        {           
            char c = w[index];
            if( c=='a' || c=='A' || c=='e' || c=='E' || c=='i' || c=='I' || c=='o' || c=='O' || c=='u' ||c=='U')
                w = w.substr(0, index) + w.substr(index+1) + c;
            else
                index++;           
        }
        return w;
    }
};

SRM337 DIV2
: 아예 조건 나눌 필요없이 min(s[i], s[n-1-i])를 둘다 넣어줘도 된다.

class Palindromize2
{
public:

    string minChanges(string s)
    {   
        int n = s.size();
        REP(i, n/2)
        {
            if(s[i] != s[n-1-i])
            {
                if( s[i] > s[n-1-i]) s[i] = s[n-1-i];
                else s[n-1-i] = s[i];
            }
        }
        return s;
    }
};

SRM338 DIV2
: 짧게 짠 소스 이렇게 짤 수도 있구나..good
for(int i=x.size()-1; i>=0;--i)
   if(x[i] == '1') x[i] = '0';  else{x[i] = '1';  return x;}
return "1"+string(x.size(), '0');

class BinaryIncrementation
{
public:

    string plusOne(string x)
    {   
        string ret;
        reverse(ALL(x));
        int pos = x.size();
        REP(i, x.size())
        {
            if(x[i] == '0')
            {
                pos = i;
                break;
            }
        }

        REP(i, pos) ret += "0";
        ret += "1";

        for(int i=pos+1; i<x.size(); i++)
            ret += x[i];
        reverse(ALL(ret));
        return ret;
    }
};

SRM339 DIV2

class BettingStrategy
{
public:

    int finalSum(int init, string o)
    {   
        int ret = init;
        int bet = 1;
        REP(i, o.size())
        {
            if(o[i] == 'W')
            {
                ret += bet;
                bet = 1;
            }
            else
            {
                ret -= bet;
                bet *= 2;
                if( ret - bet < 0) return ret;
            }
        }
        return ret;
    }
};

SRM340 DIV2

class CssPropertyConverter
{
public:

    string getCamelized(string c)
    {   
        string ret;
        REP(i, c.size())
        {
            if( c[i] == '-')
            {
                i++;
                ret += toupper(c[i]);
            }
            else
                ret += c[i];
        }
        return ret;
    }
};

SRM341 DIV2
: 문제파악을 잘못해서 엉뚱하게 풀고 있었음. 나중에 다시 한번 풀어볼 것

class ChangingString
{
public:


    int distance(string A, string B, int K)
    {   
        VI d;
        REP(i, A.size())
            d.pb( abs(A[i]-B[i]));

        sort(ALL(d));
        reverse(ALL(d));

        int ret = 0, cnt = 0;
        REP(i, d.size())
        {
            if(i >= K)
            {
                ret += d[i];
            }
            else if( d[i] == 0)
                ret++;
        }

        return ret;
    }
};

SRM342 DIV2
: pi = 2.0 * acos(0.0); 의 의미를 확인해 두자.

class DegreesToRadians
{
public:

    double convertToRadians(int d, int m, int s)
    {   
        double pi = 3.141592653589793;
        double n = d*3600 + m*60 + s;
        double ret = (n/3600) * pi / 180;

        return ret;
    }
};

SRM343 DIV2

class PersistentNumber
{
public:

    int getPersistence(int n)
    {   
        int ret = 0;
        if( n / 10 == 0) return ret;
        while(1)
        {
            int num = 1;
            while(n > 0)
            {
                num *= n % 10;
                n /= 10;           
            }
            ret++;
            if( num / 10 == 0) return ret;
            n = num;
        }
    }
};

SRM344 DIV2
: 8번째 자리를 잘못 생각해서 fail났다.
무조건 규칙을 찾으려고 하지말고, 심플하게 생각될 방법을 찾자. 숫자일 경우 num-1 해주면 간단해짐..

class Chessboard
{
public:

    int toInt(string s)
    {
        stringstream s1(s);
        int t;
        s1 >> t;
        return t;
    }

    string toStr(int num)
    {
        stringstream s;
        s << num;
        return s.str();
    }

    string changeNotation(string c)
    {   
        string ret = "";
        if( c.size() == 2 && isalpha(c[0]))
        {
            int num = c[0]-'a'+1 + (c[1]-'0'-1)*8;
            ret = toStr(num);
        }
        else
        {
            int num = toInt(c);
            ret += (num+7) % 8+'a';
            ret += (num-1)/8 +'1';
        }
        return ret;
    }
};

SRM345 DIV2

class Trekking
{
public:


    int findCamps(string f, vector <string> p)
    {   
        int ret = 1000000;
        REP(i, p.size())
        {
            string s = p[i];
            int cnt = 0, isok = 1;
            REP(j, s.size())
            {           
                if( s[j] == 'C') cnt++;
                if(f[j] == '^' && s[j] == 'C')
                {
                    isok = 0;
                    break;
                }
            }
            if(isok == 1) ret = min(ret, cnt);
        }
        if(ret == 1000000) return -1;
        return ret;
    }
};

SRM346 DIV2

class DiamondHunt
{
public:

    int countDiamonds(string m)
    {   
        int left = 0, ret = 0;
        REP(i, m.size())
        {
            if( m[i] == '<')
                left++;
            else if(m[i] == '>' && left > 0 )
            {
                ret++;
                left--;
            }
        }
        return ret;
    }
};

SRM347 DIV2

class CarBuyer
{
public:

    double lowestCost(vector <string> c, int f, int a, int y)
    {   
        double ret = 1e100;
        REP(i, c.size())
        {
            double cost, tax, eff;
            istringstream in(c[i]);
            in >> cost >> tax >> eff;
            double tot = cost + tax * y + (double)f*a*y/eff;
            ret = min(ret , tot);
        }
        return ret;
    }
};