[Topcoder] SRM291 ~ 296 연습

SRM291 DIV2
: 문제에서 A에서 B사이에 par prime을 구하라고 했는데, A+10에서 B-10이라고 잘못 이해해서 sys test에서 fail;;

class FarFromPrimes
{
public:

    int prime(int p)
    {
        if(p%2==0) return 0;
        int sqrn = sqrt(1.0*p);
        for(int i=3; i<=sqrn+1; i+=2)
            if( p%i == 0) return 0;
        return 1;
    }

    int count(int A, int B)
    {
        if(A>B) swap(A, B);
        int ret = 0;
        for(int i=A; i<=B; i++)
        {
            int ok = 0;
            for(int j=i-10; j<= i+10; j++)
                if( prime(j)) ok = 1;

            if( ok == 0) ret++;
        }
       
        return ret;  
    }
};

SRM292 DIV2

class FowlRoad
{
public:

 int crossings(int r, vector <int> X, vector <int> Y)
 { 
  int ret = 0, under = 0;
  if( r < Y[0]) under = 1;

  REP(i, X.size())
  {
   if(under == 0 && Y[i] > r)
   {
    ret++;
    under = 1;
   }
   else if(under == 1 && Y[i] < r)
   {
    ret++;
    under = 0;
   }
  }
  return ret;
 }
};

SRM293 DIV2
: 리스트중 가장 작은 것과 큰것만 비교하면 될걸로 잘못 생각했던 문제.

class Aquarium
{
public:

 int peaceful(int minSize, int maxSize, vector <int> f)
 { 
  sort(ALL(f));
  int ret = 0;
  for(int i = minSize; i<= maxSize; i++)
  {
   int ok = 0;
   REP(j, f.size())
   {
    if( !((i < (f[j]+9)/10 || i > f[j]/2 ) && ( i < f[j] * 2 || i > f[j]*10)))
    {
     ok = 1;
     break;
    }
   }
   if(ok == 0) ret++;
  }

  return ret;
 }
};

SRM294 DIV2
int c[3] = ( 0, 1, 0};로 해두고, L, R, E일때 swap을 하는 방법도 있구나..(good)

class ThreeCardMonte
{
public:

 string position(string s)
 { 
  int index = 1;
  REP(i, s.size())
  {
   if(s[i] == 'L' && index == 0)
    index = 1;
   else if(s[i] == 'L' && index == 1)
    index = 0;
   else if(s[i] == 'R' && index == 1)
    index = 2;
   else if(s[i] == 'R' && index == 2)
    index = 1;
   else if(s[i] == 'E' && index == 0)
    index = 2;
   else if(s[i] == 'E' && index == 2)
    index = 0;

  }
  if(index == 0) return "L";
  if(index == 1) return "M";
  if(index == 2) return "R";

 }
};

SRM295 DIV2
: 문제파악이 오래걸렸음. 시간단축 필요..

class PaperRockScisQuals
{
public:

 int whoPassed(vector <string> p)
 { 
  int ret = 0;
  double find_player = 0;
  REP(i, p.size())
  {
   double index = 0;
   REP(j, p.size())
   {
    if(i==j) continue;
    string a = p[i];
    string b = p[j];

    double score = 0;
    REP(k, 5)
    {
     if( (a[k] == 'P' && b[k] == 'R') || ( a[k] == 'R' && b[k] == 'S') || ( a[k] == 'S' && b[k] == 'P'))
      score += 1;
     else if( a[k] == b[k])
      score += 0.5;      
    }
    if( score > 2.5) index += 1;
    else if( score == 2.5) index += 0.5;   
   }
   if(find_player < index)
   {
    find_player = index;
    ret = i;
   }
  }
  return ret;
 }
};

SRM296 DIV2
: 문제 해법을 잘못 잡아서 시간소모가 좀 있었음. 다시 풀어볼 것.

class EratosthenSieve2
{
public:

 VI removeVI(VI a, int s)
 {
  VI ret;
  REP(i, a.size())
  {
   if( (i%s) != (s-1)) ret.pb(a[i]);
  }
  return ret;

 }
 int nthElement(int n)
 { 
  VI N;
  REP(i, 1000) N.pb(i+1);

  for(int i=2; i<=10; i++)
  {
   N = removeVI(N, i);
  }

  return N[n-1];
 }
};