어제 새벽 1시에 열린 매치.. 이번에도 삽질하면서 rating이 더 떨여졌다.. ㅠ_ㅠ
어제 술좀 마시고 늦게 들어와서 피곤한 상태에서 했더니.. 이거 머리가 안돌아가네..
500점 짜리는 좀 생각해보면 풀수 있었는데.. 아쉽다..
문제가 좀 트리키 했는지.. rating은 생각보다 많이 떨어지지는 않았다..
div1은 다음 기회에.. -_-
Level1 - Towers
Problem Statement
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.
Definition
Class:
Towers
Method:
attack
Parameters:
int, int, int, int
Returns:
int
Method signature:
int attack(int myUnits, int hpT, int attackT, int numT)
(be sure your method is public)
Notes
-
More than one soldier can attack the same tower in the same round.
Constraints
-
myUnits will be between 1 and 1000000, inclusive.
-
hpT, attackT, numT will each be between 1 and 10000, inclusive.
Examples
0)
13
2
3
8
Returns: 2
Round 1: - Your soldiers destroy 6 towers leaving one tower with 1 hit point and one tower with 2 hit points. - Your opponent attacks and kills 2*3=6 of your soldiers. Round 2: - You have 7 soldiers remaining, which is more than enough to take out the 3 hit points of the remaining towers.
1)
10
6
8
2
Returns: 2
2)
10
6
9
2
Returns: -1
3)
1
1
1
1
Returns: 1
4)
10000
10
2
2789
Returns: 10
5)
2
1
1
3
Returns: 2
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
나에게 myUnit 만큼의 병사가 있가 numT개의 타워를 부셔야 한다. 각각의 타워는 hpT 만큼 때려야 부술수 있다.. 각 병사가 한번에 1씩 공격한다. 각 병사들은 임의의 타워를 공격하도록 조종할 수 있다.. 이때 최소 몇 round까지 가야 이길수 있는지 구하기.. 못이기면 -1 return
처음에 무슨말인지 몰라서 한참 생각했다.. 각 병사들이 모두 같은 타워를 공격할 필요는 없다는게 핵심..;
나눗셈과 모듈러연산을 이용하여 그냥 시뮬레이션 하면 되는 문제..
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7
8 class Towers {
9 public:
10
11 int attack(int myUnits, int hpT, int attackT, int numT)
12 {
13 int r, a;
14 int left;
15 r = 1;
16 left = 0;
17 while (1) {
18 a = (myUnits+left) / hpT;
19 left = (myUnits+left) % hpT;
20 numT -= a;
21 if (numT <= 0)
22 break;
23 myUnits -= numT * attackT;
24 if (myUnits <= 0)
25 return -1;
26 r++;
27 }
28 printf("return %d\n", r);
29 return r;
30 }
31
32 };
Level2 - TwoLotteryGames
Problem Statement
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.
Definition
Class:
TwoLotteryGames
Method:
getHigherChanceGame
Parameters:
int, int, int
Returns:
double
Method signature:
double getHigherChanceGame(int n, int m, int k)
(be sure your method is public)
Notes
-
Your return must have relative or absolute error less than 1E-9.
Constraints
-
n will be between 2 and 8, inclusive.
-
m will be between 1 and n-1, inclusive.
-
k will be between 1 and m, inclusive.
Examples
0)
3
2
1
Returns: 1.0
Here you and the organizers will choose 2 numbers among 3. It will be 4 numbers in total, so at least 1 number in your and their sets will repeat for sure.
1)
3
1
1
Returns: 0.3333333333333333
Now you and the organizers will choose 1 number. These numbers will be the same with probability 1/3.
2)
8
2
1
Returns: 0.4642857142857143
3)
8
4
2
Returns: 0.7571428571428571
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
1~n 범위의 n개의 숫자중에서 m개를 선택한다. 이렇게 두번 선택했을때 각각의 뽑은 숫자 셋 중에 겹치는 수가 k개 이상일 확률 구하기..
n의 최대 크기가 8인것을 보고 그냥 backtracking을 통해서 모든 경우의 수를 다구해서 계산했는데.. 설마 했더니 time limit에 걸렸다.. ㅠ_ㅠ 젠장.. 그런데 나와 같은방법으로 풀었는데 bitmask를 이용한 녀석은 pass했다.. 흐미.. 뭐 이래~~!!
매치 에디토리얼을 참조하여 풀었다..
n개의 숫자 중에서 m개를 선택하는것을 두번 할때 서로
한개의 숫자가 겹칠 확률은 mC1 * (n-m)C(m-1) / nCm
두개의 숫자가 겹칠 확률은 mC2 * (n-m)C(m-2) / nCm
...
...
아.. 역시 확률은 정말 쥐약이구만.. ㅠ_ㅠ
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <set>
7 using namespace std;
8
9 int combi(int n, int r)
10 {
11 int i, j;
12 int c;
13 c = 1;
14 for (i = 1, j = n; i <= r; i++, j--) {
15 c *= j;
16 c /= i;
17 }
18 return c;
19 }
20
21 class TwoLotteryGames {
22 public:
23
24 double getHigherChanceGame(int n, int m, int k)
25 {
26 int p, a;
27 int i;
28 p = 0;
29 a = combi(n, m);
30 for (i = k; i <= m; i++) {
31 p += combi(m, i) * combi(n-m, m-i);
32 }
33 printf("return %lf\n", (double)p / (double)a);
34 return (double)p / (double)a;
35 }
36
37 };
Level3 - BarracksEasy
Problem Statement
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.
Definition
Class:
BarracksEasy
Method:
attack
Parameters:
int, int, int
Returns:
int
Method signature:
int attack(int myUnits, int barHp, int unitsPerRound)
(be sure your method is public)
Constraints
-
myUnits, barHp, unitsPerRound will each be between 1 and 50, inclusive.
Examples
0)
10
11
15
Returns: 4
Round 1: - All your soldiers attack the barracks, leaving it with 1 hit point. - Your opponent has no soldiers, so he cannot kill any of your soldiers. - Your opponent's army increases from 0 soldiers to 15 soldiers. Round 2: - One of your soldiers destroys the barracks. The other nine kill 9 of your opponent's soldiers. - Your opponent has 6 soldiers, so he kills 6 of your soldiers. - The barracks have been destroyed, so no new soldiers are produced. Round 3: - You have got 4 soldiers, so you decrease your opponent's army to 2 soldiers. - Your opponent kills 2 of your soldiers. - The barracks have been destroyed, so no new soldiers are produced. Round 4: - You kill 2 remaining soldiers.
1)
3
10
4
Returns: -1
2)
2
10
1
Returns: 9
3)
11
12
9
Returns: 2
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
