TopCoder SRM 458 Div 1
Problem Solving/TopCoder logs 2010. 1. 17. 17:47
지난주 금요일 새벽 1시에 열린 매치..
이번에도 Member SRM 이라서 문제가 완전히 로또였다..
level2, level3 는 왜 450 , 900 인지 모르겠다능..
250을 그나마 빨리풀어서 rating 을 제법 올렸다..
Level1 - BouncingBalls
공들이 1차원 좌표계위에 놓여있고.. 서로 임의의 방향으로 같은 속도로 동시에 움직이기 시작한다.. 그러다가 공이 충돌하면 왔던 방향으로 역시 같은 속도로 되돌아간다.. 처음 공이 오른쪽으로 움직일 확률과 왼쪽으로 움직일 확률이 같을때 공이 평균 몇번 충돌할까..?
이 문제는 UVa 10714 - Ants 를 풀어본 사람은 쉽게 해결할 수 있다.
이 문제를 푸는 핵심은 공이 서로 충돌해도 그냥 투과한다고 생각하고 풀면 된다..
왜냐하면 A와 B가 충돌해서 방향이 바뀌더라도.. A를 B, B를 A라고 생각하면 같은 상태가 되기 때문이다..
위 트릭을 간파한 경우 나처럼 O(n^2) 으로 풀수도 있고.. O(n * logn) 도 가능하다..
그런데 n 의 최대 크기가 12 밖에 안되서.. 모든 공에 대해서 모든 방향을 다 시도하는 O(2^n) 도 가능하다..
n 이 너무 작아서.. 오히려 헷갈린 문제..
쓸데없는 코드가 좀 남아있지만.. 챌하는사람들이 헷갈리도록 그냥 뒀음..;
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7 //#define min(x, y) ((x) > (y) ? (y) : (x))
8 //#define max(x, y) ((x) > (y) ? (x) : (y))
9 //#define INF 999999999
10 //#define EPS 1e-14
11
12 int graph[20][20];
13 int n;
14
15 class BouncingBalls {
16 public:
17
18 double expectedBounces(vector <int> x, int T)
19 {
20 int i, j;
21 int d;
22 int cnt;
23 double p;
24 n = x.size();
25 memset(graph, 0, sizeof(graph));
26 cnt = 0;
27 p = 0;
28 for (i = 0; i < n; i++) {
29 for (j = i+1; j < n; j++) {
30 d = abs(x[i]-x[j]);
31 if (d <= 2*T)
32 p += 0.25;
33 }
34 }
35 return p;
36 }
37
38 };
Level2 - NewCoins
{X1, X2, X3, ..., XN} 으로 이루어진 동전 set 이 있다 X1 = 1 이고 Xk % Xk-1 = 0 조건이 항상 만족한다
주어진 price 를 모두 나타내기 위한 최소 동전 개수 구하기
일단 임의의 값 p 를 나타내기 위해서는 p 보다 작거나 같은 가장 큰 동전을 사용해야한다.. 즉, Greedy
왜냐하면 Xk % Xk-1 = 0 조건때문에..
그렇게 하면 p 를 나타내기 위한 최소 동전 개수는
p / Xk + (p % Xk) / Xk-1 + (p % Xk-1) / Xk-2 + ... + (p % X2) / X1 가 된다..
구현은 sieve 를 응용하여 할 수 있다..
실제 매치때 sieve 응용이라는걸 대략 간파했는데.. 끝내 구현 실패.. ㅠ_ㅠ
주어진 price 를 모두 나타내기 위한 최소 동전 개수 구하기
일단 임의의 값 p 를 나타내기 위해서는 p 보다 작거나 같은 가장 큰 동전을 사용해야한다.. 즉, Greedy
왜냐하면 Xk % Xk-1 = 0 조건때문에..
그렇게 하면 p 를 나타내기 위한 최소 동전 개수는
p / Xk + (p % Xk) / Xk-1 + (p % Xk-1) / Xk-2 + ... + (p % X2) / X1 가 된다..
구현은 sieve 를 응용하여 할 수 있다..
실제 매치때 sieve 응용이라는걸 대략 간파했는데.. 끝내 구현 실패.. ㅠ_ㅠ
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7 #define min(x, y) ((x) > (y) ? (y) : (x))
8 //#define max(x, y) ((x) > (y) ? (x) : (y))
9 #define INF 999999999
10 //#define EPS 1e-14
11
12 class NewCoins {
13 public:
14
15 int minCoins(vector <int> price)
16 {
17 int n;
18 int i, j, k;
19 int temp;
20 int sieve[100001];
21 for (i = 0; i <= 100000; i++) {
22 sieve[i] = INF;
23 }
24 n = price.size();
25 for (i = 100000; i >= 1; i--) {
26 sieve[i] = 0;
27 for (j = 0; j < n; j++) {
28 sieve[i] += price[j] / i;
29 }
30 for (j = 2; i*j <= 100000; j++) {
31 temp = sieve[i*j];
32 for (k = 0; k < n; k++) {
33 temp += (price[k] % (i*j)) / i;
34 }
35 sieve[i] = min(sieve[i], temp);
36 }
37 }
38 return sieve[1];
39 }
40
41 };
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7 #define min(x, y) ((x) > (y) ? (y) : (x))
8 //#define max(x, y) ((x) > (y) ? (x) : (y))
9 #define INF 999999999
10 //#define EPS 1e-14
11
12 class NewCoins {
13 public:
14
15 int minCoins(vector <int> price)
16 {
17 int n;
18 int i, j, k;
19 int temp;
20 int sieve[100001];
21 for (i = 0; i <= 100000; i++) {
22 sieve[i] = INF;
23 }
24 n = price.size();
25 for (i = 100000; i >= 1; i--) {
26 sieve[i] = 0;
27 for (j = 0; j < n; j++) {
28 sieve[i] += price[j] / i;
29 }
30 for (j = 2; i*j <= 100000; j++) {
31 temp = sieve[i*j];
32 for (k = 0; k < n; k++) {
33 temp += (price[k] % (i*j)) / i;
34 }
35 sieve[i] = min(sieve[i], temp);
36 }
37 }
38 return sieve[1];
39 }
40
41 };
Level3 - ModuloFourDivisor
to be updated..
'Problem Solving > TopCoder logs' 카테고리의 다른 글
| SRM 466 (0) | 2010.04.05 |
|---|---|
| TopCoder Open 2010 일정.. (0) | 2010.03.31 |
| SRM 464 (0) | 2010.03.18 |
| TopCoder SRM 463 (2) | 2010.03.06 |
| TopCoder SRM 459 Div 1 (0) | 2010.01.20 |
| TopCoder SRM 457 Div 1 (0) | 2010.01.06 |
| [SRM 456] 2009년 마지막 SRM (0) | 2009.12.23 |
| TopCoder SRM 455 Div 1 (0) | 2009.12.19 |
| TopCoder SRM 454 Div 1 (0) | 2009.12.07 |
| TopCoder SRM 453.5 (??) Div 1 (0) | 2009.11.26 |