[SRM 456] 2009년 마지막 SRM

오늘 아침 11시 2009년의 마지막 SRM 이 열렸다..
비록 챌을 실패해서 좀 아쉽게 됐지만.. 나름 문제이해를 빨리해서 rating 을 48 점이나 올렸다..
내년에는 좀더 도전적인 문제를 많이 풀어서 yellow 로 올라가야겠다..

Level1 - SilverDistance

Problem Statement
     
In Japanese Chess, there is a piece called Silver. A Silver piece located in cell (x,y) can move to any of the following cells in one step: (x-1,y+1), (x,y+1), (x+1,y+1), (x-1,y-1), (x+1,y-1). In other words, it can move one cell in any of the four diagonal directions, or it can move one cell vertically in the positive y direction. 

Initially, there's a Silver piece in cell (sx,sy) of an infinitely large board. Return the minimal number of steps required to move to cell (gx,gy).
Definition
    
Class:
SilverDistance
Method:
minSteps
Parameters:
int, int, int, int
Returns:
int
Method signature:
int minSteps(int sx, int sy, int gx, int gy)
(be sure your method is public)
    
 
Constraints
-
sx, sy, gx and gy will each be between -1,000,000 and 1,000,000 inclusive.
Examples
0)
 
    
1
0
1
9
Returns: 9
Move up vertically in the positive y direction 9 times.
1)
 
    
0
0
-4
3
Returns: 5
Follow the path : (0,0) -> (-1,1) -> (-1,2) -> (-2,3) -> (-3,2) -> (-4,3)
2)
 
    
0
0
5
8
Returns: 8
Move up vertically in the postive y direction 3 times, then move diagonally up and to the right 5 times.
3)
 
    
-487617
826524
892309
-918045
Returns: 1744571
 
4)
 
    
-27857
31475
-27857
31475
Returns: 0
The Silver is already in the goal.
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.

chess 판에서 unit 은 그림과 같이 5 방향으로 이동할 수 있다.. (sx, sy) -> (gx, gy) 로 이동하는 최단거리 구하기..

문제가 약간 tricky 해서 if 문으로 다 나눠서 생각하려하는데.. 자세히 보니 경우의 수가 두가지밖에 없다..
|sx-gx| 와 |sy-gy| 의 parity 가 같으면 돌아가는 길 없이 바로 갈 수 있다..
그렇지 않은 경우는 반드시 (0, +1) 방향으로 한번 이동해야한다..
언제 이동하는 것은 상관 없으므로 나는 그냥 (gx, gy-1) 까지의 거리를 구하고 1 을 더했다..

  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
 11 class SilverDistance {
 12 public:
 13
 14 int minSteps(int sx, int sy, int gx, int gy)
 15 {
 16     int dx, dy;
 17     int res;
 18     dx = abs(sx-gx);
 19     dy = abs(sy-gy);
 20     if (dx % 2 == 0 && dy % 2 == 0) {
 21         res = max(dx, dy);
 22     }
 23     else if (dx % 2 == 0 && dy % 2 == 1) {
 24         res = minSteps(sx, sy, gx, gy-1) + 1;
 25     }
 26     else if (dx % 2 == 1 && dy % 2 == 0) {
 27         res = minSteps(sx, sy, gx, gy-1) + 1;
 28     }
 29     else {
 30         res = max(dx, dy);
 31     }
 32     return res;
 33 }
 34
 35 };

Level2 - CutSticks

Problem Statement
     
John has some sticks of various lengths. You are given a vector <int> sticks, where each element is the length of a single stick.  He is allowed to perform at most C cuts. With each cut, he chooses one of his sticks and divides it into exactly two sticks of arbitrary positive lengths (the sum of their lengths must equal the length of the original stick). Each of these sticks can then be chosen again when making subsequent cuts.  After he performs all his cuts, he sorts the sticks in non-increasing order by length and chooses the K-th (1-based) stick. Return the maximal possible length of the stick he chooses. Note that he must perform at least as many cuts as are required to end up with K or more sticks.
Definition
    
Class:
CutSticks
Method:
maxKth
Parameters:
vector <int>, int, int
Returns:
double
Method signature:
double maxKth(vector <int> sticks, int C, int K)
(be sure your method is public)
    
 
Notes
-
Your return value must have an absolute or relative error less than 1e-9.
Constraints
-
sticks will contain between 1 and 50 elements, inclusive.
-
Each element of sticks will be between 1 and 1,000,000,000, inclusive.
-
C will be between 1 and 1,000,000,000, inclusive.
-
K will be between 1 and n + C, inclusive, where n is the number of elements in sticks.
Examples
0)
 
    
{5, 8}
1
1
Returns: 8.0
John can make at most one cut. He should either cut the stick of length 5 (it doesn't matter where) or not make any cuts at all. If he makes no cuts, then after he sorts the sticks, they will be in the following order: {8, 5}. He chooses the 1st stick, which has length 8.
1)
 
    
{5, 8}
1
2
Returns: 5.0
Again, the easiest thing to do here is not make any cuts.
2)
 
    
{5, 8}
1
3
Returns: 4.0
John has 2 sticks and he can make at most one cut. In this case, since K is 3, he is required to make a cut so he can end up with 3 sticks. He should cut the longest stick into two equal sticks of length 4. After he sorts the sticks, they will be in the following order: {5, 4, 4}. He will choose the 3rd stick, which has length 4.
3)
 
    
{1000000000, 1000000000, 1}
2
5
Returns: 1.0
 
4)
 
    
{76, 594, 17, 6984, 26, 57, 9, 876, 5816, 73, 969, 527, 49}
789
456
Returns: 34.92
 
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.

막대기가 여러개있는데.. 최대 C번까지 cut 을 할 수 있다.. K번째 긴 막대기의 길이를 최대화하기..

일단 문제부터 잘 이해가 안되는 문제.. -_-;;
일단 전형적인 binary search 문제인데 조건이 하나 더 추가되면서 상당히 까다로워진 문제..
editorial 을 보고 풀었다..

binary search 를 이용해 답을 계속 탐색하는데.. 다음 두가지 조건을 만족하면 valid 이다

1) 길이가 최소 mid 인 막대기를 만든다 치면.. 각 막대기를 floor(stick[i] / mid) 개로 만들 수 있다..
따라서 sum{i=1...n} floor(stick[i] / mid) >= K

2) 최대 c 번만 cut 할 수 있다.. 한번 cut 하면 막대기가 하나 더 생기므로..
이미 mid 보다 긴 막대기 수 + c >= K

아... 어렵다.. ㅠ_ㅠ

  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 CutSticks {
 13 public:
 14
 15 double maxKth(vector <int> sticks, int C, int K)
 16 {
 17     int n;
 18     int iter, i;
 19     long long a, b;
 20     double l, r, mid;
 21     l = 0;
 22     r = 1000000000.0;
 23     iter = 300;
 24     n = sticks.size();
 25     while (iter--) {
 26         mid = (l+r) * 0.5;
 27         a = b = 0;
 28         for (i = 0; i < n; i++) {
 29             a += (long long)((double)sticks[i] / mid);
 30             if ((double)sticks[i] >= mid)
 31                 b++;
 32         }
 33         if (a >= K && b + C >= K)
 34             l = mid;
 35         else
 36             r = mid;
 37     }
 38     return mid;
 39 }
 40
 41 };

Level3 - FunctionalEquation

Problem Statement
     
f is a function from integers to integers. In other words, f is defined over integers, and f(x) is an integer for all integers x. You are given an integer C. f is called C-beautiful if the following equality is satisfied for all integers x:

Use the following recursive definitions to generate the sequences x and y:
x[0] = xzero
For all integer i between 1 and N-1, inclusive, x[i] = (x[i-1] * xprod + xadd) % xmod
y[0] = yzero
For all integer i between 1 and N-1, inclusive, y[i] = (y[i-1] * yprod + yadd) % ymod
Definition
    
Class:
FunctionalEquation
Method:
minAbsSum
Parameters:
int, int, int, int, int, int, int, int, int, int
Returns:
long long
Method signature:
long long minAbsSum(int C, int N, int xzero, int xprod, int xadd, int xmod, int yzero, int yprod, int yadd, int ymod)
(be sure your method is public)
    
 
Notes
-
64-bit integers should be used to generate the sequences x and y to avoid overflow.
Constraints
-
C will be between 1 and 16, inclusive.
-
N will be between 1 and 10,000, inclusive.
-
xmod and ymod will each be between 1 and 1,000,000,000, inclusive.
-
xzero, xprod and xadd will each be between 0 and xmod - 1, inclusive.
-
yzero, yprod and yadd will each be between 0 and ymod - 1, inclusive.
Examples
0)
 
    
3
10
0
1
1
456
1
1
1
456
Returns: 0
f(x) = x + 1 is a 3-beautiful function. Since x = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} and y = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, the sum of |f(x[i]) - y[i]| is 0.
1)
 
    
4
10
0
1
1
456
1
1
1
456
Returns: 5
x and y are the same as in example 0, but f(x) = x + 1 is not a 4-beautiful function.
2)
 
    
16
10000
654816386
163457813
165911619
987654321
817645381
871564816
614735118
876543210
Returns: 3150803357206
 
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..