TopCoder SRM 418 DIV 2

Problem	Check	Points
250	×	-
500	○	333.86
1000	×	-

うおぅ250落ちた！気が抜けてましたね・・・
そのかわりと言ってはなんだけど500は早く解けた！ていうか問題の制約がすっげーぬるかったので。2^8までしかないなら2重ループで余裕ですよね。

TopCoder Statistics: SRM 418 Problem Set & Analysis

Problem 250 Towers

問題

As a serious strategy-games player, you decided to solve one of the most common problems - attacking your opponent's guard towers.

Before the attack, you've got myUnits soldiers. Each soldier in a single round inflicts 1 hit point of damage to one of the towers.
Your opponent doesn't have any soldiers. However, he's got numT towers with hpT hit points each. Each tower kills attackT of your soldiers per round.

The course of one round:

1. Each soldier in your army attacks a tower of your choice for 1 hit point of damage. When a tower loses all its hit points, it is destroyed. You can pick the tower independently for each soldier.
2. Your opponent attacks. He will kill k*attackT of your soliders, where k is the number of remaining towers.

Your task is to destroy all the towers. If it is possible, return the minimum number of rounds you need to do this. Otherwise return -1.

My code

class Towers {
public:
  int attack(int myUnits, int hpT, int attackT, int numT) {
    int result = -1;


	int allT = hpT*numT;

	int turnNum = 1;
	int remainT = numT;

	//cout << "allT " << allT << endl;
	while(1){
		// my turn
		allT -= myUnits;
		remainT = allT/hpT;
		if(allT%hpT!=0) remainT++;

		if(allT<=0) return turnNum;

		// opponent turn
		myUnits -= remainT*attackT;

		if(myUnits <= 0) return -1;

		turnNum++;
	}

    return result;
  }
};

Problem 500 TwoLotteryGames

問題

Yesterday, when you were passing by the newsstand near your home, you saw an advertisement for lottery games. The advertisement said "Choose m different numbers between 1 and n, inclusive. We will also randomly pick m different numbers between 1 and n, inclusive, and if you have at least k numbers in common with us, you win!".
You want to know the probability of winning this lottery game. You are given three integers n, m, and k as described above. Return the probability of winning the game.

My code

int kk;

bool check(vector<int> v, vector<int> v2){
	int cnt= 0;
	for(int i=0 ; i<v.size() ; i++){
		if(v[i]==1 && v2[i]==1) cnt++;
	}
	if(cnt>= kk) return true;
	return false;
}

class TwoLotteryGames {
public:
  double getHigherChanceGame(int n, int m, int k) {
    double result = 0;

	kk = k;

	vector<int> v, v2;
	for(int i=0 ; i<n-m ; i++){
		v.push_back(0);
		v2.push_back(0);
	}
	for(int i=0 ; i<m ; i++){
		v.push_back(1);
		v2.push_back(1);
	}
	
	sort(v.begin() , v.end());
	sort(v2.begin() , v2.end());

	int cnt = 0;

	int allcnt = 0;
	do{
		do{
			if(check(v,v2)){
				cnt++;
			}

		}while(next_permutation(v2.begin(), v2.end()));
		allcnt++;
	}while(next_permutation(v.begin(),v.end()));
	

    return (double)cnt/((double)allcnt*(double)allcnt);
  }
};

Problem 1000 BarracksEasy

問題

As a serious strategy-games player, you decided to solve one of the most common problems - attacking your opponent's building (barracks), which constantly produces new soldiers.

Before the attack, you've got myUnits soldiers. In a single round, each soldier can either kill one of your opponent's soldiers or inflict 1 hit point of damage to the barracks.
Your opponent doesn't have any soldiers initially. However, his barracks has barHp hit points and produces unitsPerRound soldiers per round.

The course of one round:

1. Each solider from your army either kills one of your opponent's soldiers or inflicts 1 hit point of damage to the barracks. Each soldier can choose to do something different. When the barracks loses all of its hit points, it is destroyed.
2. Your opponent attacks. He will kill k of your soldiers, where k is the number of remaining soldiers he has.
3. If the barracks are not yet destroyed, your opponent will produce unitsPerRound new soldiers.

Your task is to destroy the barracks and kill all your opponent's soldiers. If it is possible, return the minimum number of rounds you need to do this. Otherwise return -1.