2010/01/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' 카테고리의 다른 글
| TopCoder SRM 463 (2) | 2010/03/06 |
|---|---|
| TopCoder SRM 459 Div 1 (0) | 2010/01/20 |
| TopCoder SRM 458 Div 1 (0) | 2010/01/17 |
| 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 |
Trackback Address :: http://helloneo.pe.kr/trackback/330
|
Tracked from 「 Я чайка 」 | 2010/03/12 16:37 | DEL
최근 학교 일등 여러가지 사정으로(뭐 핑계지만...), SRM에 거의 참가하지를 못했는데, 요즘 들어서 지나쳐버린 이전 SRM 문제들을 한번씩 풀어보고 있다. 그 중에 내가 좀 놀랜 기발한 문제... Problem Statement John is playing with balls. All of the balls are identical in weight and considered to have a zero radius. All balls are lo.. |
