TopCoder TCO08 Online Round 1

TCO08 R1.. 새벽 3시에 열렸는데.. 뭐 힘한번 못써보고 삽질만 하다가 결국 탈락.. 허무하다.. ㅠ_ㅠ
문제가 좀 어려웠는데.. 결론적으로 다 나의 실력 부족이었다.. 내년에는 R1 통과를 목표로 열심히 준비해야겠다..

앗.. 그런데 이제보니 우리나라가 9위네.. 앞서있던 크로아티아를 밀어내고.. 네덜란드와 접전중..;

방 24등(최하위 ㅠ_ㅠ;;) 전체 1390등..

[250] DiscountCombination

Problem Statement
     
There's a shoe store in which some models are popular, and some are not. In order to sell more unpopular models, the store introduced a system of discounts. Each discount works in the following way: if you buy an unpopular model for a cost of COST, then you can buy a popular model with a PERCENT% discount. However, the owner of the store is greedy, and therefore only discounts with PERCENTs equal to 1, 2 and 3 were introduced.
After it became obvious that such low discounts didn't work well, the store allowed people to apply more than one discount to the same pair of shoes. For example, you can buy three unpopular models, obtain three discounts and use all three to reduce the cost of the same popular model. When many discounts are applied to the same model, they are applied one after another. For example, if you apply 2% and 3% discounts to a model with cost 100, it's cost will be 0.98 * 0.97 * 100 = 95.06.
The available discounts are given in a vector <string> discounts, each element of which is formatted "COST PERCENT" (quotes for clarity). Different elements of discounts correspond to different unpopular models. You want to buy a popular model, which costs price. In order to reduce the model's cost, you can buy some unpopular models and obtain discounts from them, but you don't wish to buy the same unpopular model more than once. Return the minimum amount of money you need to spend in order to buy the desired popular model.
Definition
   
Class:
DiscountCombination
Method:
minimumPrice
Parameters:
vector <string>, int
Returns:
double
Method signature:
double minimumPrice(vector <string> discounts, int price)
(be sure your method is public)
   
 
Notes
-
The returned value must be accurate to within a relative or absolute value of 1E-9.
Constraints
-
discounts will contain between 1 and 50 elements, inclusive.
-
Each element of discounts will be formatted "COST PERCENT" (quotes for clarity), where COST and PERCENT are integers with no leading zeros.
-
Each COST will be between 1 and 10,000,000, inclusive.
-
Each PERCENT will be between 1 and 3, inclusive.
-
price will be between 1 and 1,000,000,000, inclusive.
Examples
0)
 
   
{"1 1", "1 2", "1 3"}
100
Returns: 97.06
The best choice is to take 3% and 2% discounts. You pay 2 for unpopular models and reduce the cost of the popular model to 95.06.
1)
 
   
{"1000 1", "100 2", "10 3"}
33
Returns: 33.0
It doesn't make sense to use any discounts.
2)
 
   
{"10 2", "2 3", "6 2", "3 2", "3 1",
 "2 3", "9 3", "4 3", "2 3", "10 1"}
1000000000
Returns: 7.921497975738132E8
price is very large and discounts are cheap, so we use all of them.
3)
 
   
{"8667276 2",
 "3833771 1",
 "9208836 1",
 "5081823 3",
 "3367749 1",
 "4393655 2",
 "552508 1",
 "8648685 2",
 "3798496 2",
 "8104796 1"}
246918635
Returns: 2.415526549689562E8
 
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.

input으로 사고자하는 물건의 가격과.. 기타 다른 물건의 가격이 주어진다.. 기타 다른 물건을 사면 최대 1%에서 3%까지 원래 사고자하는 물건의 가격을 깎아준다.. 사고자하는 물건을 가장 싸게 얼마에 살 수 있는지 구하는 문제..

흠.. 생각보다 쉽지않은 문제였다.. 대회중에 우선 모든 경우를 다 따져봐야 한다고 생각했는데.. input이 50이라 O(2^50) = TLE 그래서 다른사람들도 나름대로 빨리 풀고있고.. 뭔가 쉬운방법이 있을것같아서 greedy하게 생각했는데.. 우선 샀을경우 가격을 낮추는 상품은 모두 골랐다.. 당연히 답이 나오면 안되는데 sample이 다 통과하길래 그냥 submit.. 나중에 여유가 있고 다른게 떠오르면 resubmit하려고했는데.. 그럴 기회가 없었다..;; 젠장.. 결국 challenge fail.. 정말 오랜만에 챌당해보았다..

솔루션은 match editorial을 참고했다..

우선 모든 경우를 다 search해야하는것은 맞다.. 그러나 해당하는 discount가 1, 2, 3% 밖에 없다는 것을 감안하여.. 상품들은 세개의 셋으로 구분한다.. 각 셋에대해서 discount 비율이 같으므로 무조건 싼것부터 사야한다.. 즉, 더 비싼것을 사고 싼것을 않사는 경우는 최적이 될 수 없다는 점을 이용하여 pruning 한다.

매치중에 나한테는 생각하기 힘든 문제였다..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <cmath>
  7 using namespace std;
  8
  9 int d[4][100];
 10
 11 int comp(const void* x, const void* y)
 12 {
 13     int* a = (int*)x;
 14     int* b = (int*)y;
 15     return (*a) - (*b);
 16 }
 17
 18 class DiscountCombination {
 19 public:
 20
 21 double minimumPrice(vector <string> discounts, int price)
 22 {
 23     int n;
 24     int i, j, k, l;
 25     int a, b;
 26     int cnt1, cnt2, cnt3;
 27     char buf[100];
 28     double sum, min1;
 29
 30     n = discounts.size();
 31     cnt1 = cnt2 = cnt3 = 0;
 32     for (i = 0; i < n; i++) {
 33         strcpy(buf, discounts[i].c_str());
 34         sscanf(buf, "%d%d", &a, &b);
 35         if (b == 1) {
 36             d[1][cnt1] = a;
 37             cnt1++;
 38         }
 39         else if (b == 2) {
 40             d[2][cnt2] = a;
 41             cnt2++;
 42         }
 43         else {
 44             d[3][cnt3] = a;
 45             cnt3++;
 46         }
 47     }
 48
 49     qsort(d[1], cnt1, sizeof(int), comp);
 50     qsort(d[2], cnt2, sizeof(int), comp);
 51     qsort(d[3], cnt3, sizeof(int), comp);
 52
 53     min1 = price;
 54     for (i = 0; i <= cnt1; i++) {
 55     for (j = 0; j <= cnt2; j++) {
 56     for (k = 0; k <= cnt3; k++) {
 57         sum = 0.0;
 58         for (l = 0; l < i; l++) {
 59             sum += d[1][l];
 60         }
 61         for (l = 0; l < j; l++) {
 62             sum += d[2][l];
 63         }
 64         for (l = 0; l < k; l++) {
 65             sum += d[3][l];
 66         }
 67         sum += price * pow(0.99, (double)i) * pow(0.98, (double)j) * pow(0.97, (double)k);
 68         if (sum < min1) {
 69             min1 = sum;
 70         }
 71     }
 72     }
 73     }
 74     return min1;
 75 }
 76
 77 };

[500] Chomp

Problem Statement
     
The game Chomp starts with a grid 3 cells high and N cells wide. Two players take turns selecting a remaining cell in the grid, and chomping (removing) all the cells to the right and above the selected cell (including the chosen one). The player who chomps the lower-leftmost cell loses the game. Here is a sample of two moves in the game:
3 XX                          XX                   
2 XXXX    => chomp(4,1) =>    XXX  => chomp(1,2) =>
1 XXXXX                       XXX                      XXX
  12345                       12345                    12345
Determine which player wins if each player plays optimally, and how many total (for both players combined) turns it takes (the last move is the losing move). The player who will win when playing optimally plays to win as quickly as possible, while the player who is destined to lose plays to make the game last as long as possible. If player 1 will win, return the total number of moves required. Otherwise, return the negation of the number of moves required.
Definition
   
Class:
Chomp
Method:
moves
Parameters:
int
Returns:
int
Method signature:
int moves(int N)
(be sure your method is public)
   
 
Constraints
-
N will be between 1 and 100, inclusive.
Examples
0)
 
   
1
Returns: 2
The optimal game is simple:
 X      .      .
 X  =>  .  =>  .
 X      X      .
1)
 
   
2
Returns: 6
 
2)
 
   
4
Returns: 8
 
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.

가로가 N, 세로가 3인 보드가 주어진다.. 임의의 지점 (i, j)를 선택하면 (i, j) cell을 포함하여 우측 위방향 (1사분면)을 제거한다.. 이와 같은 방법으로 서로 번갈아가면서 cell을 제거해나갈때 가장 왼쪽 아래 (1, 1) cell 을 take하는 사람이 지게된다.. 첫번째 플레이어가 이기는경우 최소 몇번만에 이기는지.. 진다면 최대 몇번만에 지는지 구하는 문제..

게임이론을 이용하여 풀 수 있다.. 현재 상태에서 갈 수 있는 상태가 모두 이기는 상태이면 현재 상태는 지는 상태이고.. 지는 상태로 갈 수 있는 경우가 하나라도 있으면 현재 상태는 이기는 상태이다..

첫번째(바닥)줄의 cell이 a개 두번째(가운데)줄의 cell이 b개 세번째(맨위)줄의 cell이 c개일때.. 상태를 (a, b, c)로 나타낼 수 있다.. 이 상태에서 모든 가능한 경우를 다 고려해서 다음 상태로 넘어가면 된다.. recursion + memo로 쉽게 풀 수 있다..

아.. 이 매치가 올해 2월에 열렸는데.. 이제야(2008-11-30) 이 문제를 해결했구나.. ㅠ_ㅠ 좋은문제..

  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
  9 int memo[101][101][101];
 10
 11 /*
 12 XXXXXXXXX       <--- c 개
 13 XXXXXXXXXXX     <--- b 개
 14 XXXXXXXXXXXXX   <--- a 개
 15 */
 16 int recur(int a, int b, int c)
 17 {
 18     int res, i, x;
 19
 20     if (memo[a][b][c])
 21         return memo[a][b][c];
 22     if (a == 1 && b == 0 && c == 0)
 23         return memo[a][b][c] = -1;
 24
 25     res = -1;
 26     for (i = 1; i < a; i++) {
 27         x = recur(i, min(i, b), min(i, c));
 28         if (x < 0) {
 29             if (res < 0)
 30                 res = 1-x;
 31             else
 32                 res = min(res, 1-x);
 33         }
 34         else {
 35             // 다음 상태가 모두 이기는 상태이면 현재 상태는 지는 상태
 36             if (res < 0)
 37                 res = min(res, -x-1);
 38         }
 39     }
 40     for (i = 0; i < b; i++) {
 41         x = recur(a, i, min(i, c));
 42         if (x < 0) {
 43             if (res < 0)
 44                 res = 1-x;
 45             else
 46                 res = min(res, 1-x);
 47         }
 48         else {
 49             // 다음 상태가 모두 이기는 상태이면 현재 상태는 지는 상태
 50             if (res < 0)
 51                 res = min(res, -x-1);
 52         }
 53     }
 54     for (i = 0; i < c; i++) {
 55         x = recur(a, b, i);
 56         if (x < 0) {
 57             if (res < 0)
 58                 res = 1-x;
 59             else
 60                 res = min(res, 1-x);
 61         }
 62         else {
 63             // 다음 상태가 모두 이기는 상태이면 현재 상태는 지는 상태
 64             if (res < 0)
 65                 res = min(res, -x-1);
 66         }
 67     }
 68     return memo[a][b][c] = res;
 69 }
 70
 71 class Chomp {
 72 public:
 73
 74 int moves(int N)
 75 {
 76     memset(memo, 0, sizeof(memo));
 77     return recur(N, N, N);
 78 }
 79
 80 };

[1000] BoxFilling

Problem Statement
     
We have a box that consists of (sizeX x sizeY x sizeZ) = N unit cubes. These cubes have coordinates ranging from (1,1,1) to (sizeX,sizeY,sizeZ).
We want to number the unit cubes, using integers from 1 to N. We will do this algorithmically.
We will call a box "1-dimensional (1D)" if at least two of its dimensions are 1, "2-dimensional (2D)" if exactly one of its dimensions is 1, and "3-dimensional (3D)" otherwise.
The algorithm used to number a 1-dimensional box is simple: order the cubes according to the sums of their coordinates (in ascending order), and number them in this order.
To number a 2-dimensional box, we follow this algorithm:
If X size is greater than 1, consider all cubes with both Y and Z coordinates minimal, number them as a 1D box, and throw them away.
If we still have a 2D box, if Y size is greater than 1, consider all cubes with both X and Z coordinates minimal, number them as a 1D box, and throw them away.
If we still have a 2D box, if Z size is greater than 1, consider all cubes with both X and Y coordinates minimal, number them as a 1D box, and throw them away.
Recursively number the rest of the box.
For example, a 4x5x1 box filled using this algorithm looks as follows:
z=1
   x:1  2  3  4
 y:+--+--+--+--+
  1| 1| 2| 3| 4|
   +--+--+--+--+
  2| 5| 9|10|11|
   +--+--+--+--+
  3| 6|12|15|16|
   +--+--+--+--+
  4| 7|13|17|19|
   +--+--+--+--+
  5| 8|14|18|20|
   +--+--+--+--+
To number a 3-dimensional box, we follow this algorithm:
Consider all cubes with the Z coordinate minimal, number them as a 2D box, and throw them away.
If we still have a 3D box, consider all cubes with the Y coordinate minimal, number them as a 2D box, and throw them away.
If we still have a 3D box, consider all cubes with the X coordinate minimal, number them as a 2D box, and throw them away.
Recursively number the rest of the box.
For example, a 4x3x3 box filled using this algorithm looks as follows:
z=1
   x:1  2  3  4
 y:+--+--+--+--+
  1| 1| 2| 3| 4|
   +--+--+--+--+
  2| 5| 7| 8| 9|
   +--+--+--+--+
  3| 6|10|11|12|
   +--+--+--+--+
 
z=2
   x:1  2  3  4
 y:+--+--+--+--+
  1|13|14|15|16|
   +--+--+--+--+
  2|21|25|26|27|
   +--+--+--+--+
  3|22|28|29|30|
   +--+--+--+--+
 
z=3
   x:1  2  3  4
 y:+--+--+--+--+
  1|17|18|19|20|
   +--+--+--+--+
  2|23|31|32|33|
   +--+--+--+--+
  3|24|34|35|36|
   +--+--+--+--+
You will be given the box dimensions sizeX, sizeY, and sizeZ, and the coordinates of a single cube (cubeX,cubeY,cubeZ). Write a method that will compute the number assigned to the cube at the given coordinates, when using the algorithm described above.
Definition
     
Class:
BoxFilling
Method:
getNumber
Parameters:
int, int, int, int, int, int
Returns:
long long
Method signature:
long long getNumber(int sizeX, int sizeY, int sizeZ, int cubeX, int cubeY, int cubeZ)
(be sure your method is public)
     
 
Notes
-
Note that the box described by sizeX, sizeY, and sizeZ is not necessarily a 3D box.
Constraints
-
sizeX, sizeY and sizeZ will be between 1 and 109, inclusive.
-
The volume of the box will not exceed 1018.
-
cubeX will be between 1 and sizeX, inclusive.
-
cubeY will be between 1 and sizeY, inclusive.
-
cubeZ will be between 1 and sizeZ, inclusive.
Examples
0)
 
   
4
5
1
2
4
1
Returns: 13
This is the box from the first example in the problem statement.
1)
 
   
4
3
3
2
2
2
Returns: 25
This is the box from the second example in the problem statement.
2)
 
   
4
3
3
4
2
1
Returns: 9
Same box, different cube coordinates.
3)
 
   
2
2
2
1
1
1
Returns: 1
 
4)
 
   
43633
35453
34533
2344
32442
34221
Returns: 9416237809215
 
5)
 
   
3
1
10
3
1
2
Returns: 14
 
6)
 
   
4
2
4
3
2
3
Returns: 28
 
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.

to be updated..