[Topcoder] SRM418 DIV2

새벽1시에 하길래 잠좀 자다가 참여할려고 했는데, 못 일어났다.;;

월요일에 다시 한번 풀어봄.

250 : Tower hp를 전체적으로 보는게 핵심. 예전에 비슷한 류를 몇번 풀고나니 이런 문제는 이제 해법이 빨리 보이는거 같다.

class Towers
{
public:

 int attack(int m, int hT, int aT, int nT)
 { 
  int T = hT * nT;
  int ret = 1;
  while(1)
  {
   T -= m;
   if( T <= 0) break;
   nT = (T+hT-1)/ hT;
   m -= aT * nT;
   if(m <= 0) return -1;
   ret++;
  }

  return ret;  
 }
};

500 : 경우의 수를 구해서 품.
대부분의 경우 배열로 넣어서, 개수를 구했던데.. 나중에 한번 이해해보자. 이번에도 next_permutation이 사용될 수 있음..

class TwoLotteryGames
{
public:

 int getC(int n, int m)
 {
  int a = 1, b = 1, c = 1;
  for(int i=1; i<= n; i++)
   a *= i;

  for(int i=1; i<= m; i++)
   b *= i;

  for(int i=1; i<= n-m; i++)
   c *= i;

  return a / (b*c);

 }

 double getHigherChanceGame(int n, int m, int k)
 { 
  double ret = 0;
  int tot = getC(n, m);
  int child = 0;
  for(int i=k; i<= m; i++)
   child += getC(m,i)*getC(n-m, m-i);

  ret = 1.0*child/tot;
  return ret > 1 ? 1 : ret;  
 }
};