SRM 395 Div1

좀 오래 지났지만 이제야 겨우 후기를 남기네..
아침 11시에 열렸던 매치.. 역시.. 첫문제부터 코딩에서 말리더니.. 결국 한문제도 못풀었다.. 흐미..
500점짜리 문제는 풀수 있었는데.. 상금매치도 다가오고.. 굳이 풀지 않았다..;; (핑계)
이렇게해서 별 소득없이.. 다시 Div2로 복귀 ㅠ_ㅠ;; 이제부터는 좀 열심히 해야지..!!
근데.. 밀려있는 문제.. 언제다풀지..????

방 16등 전체 367등..


[250] StreetWalking

Problem Statement
     
You are walking home from school through the city. The city is infinite in size, with vertical streets located at every integer X value and horizontal streets located at every Y value. You are currently located at (0,0) and are trying to get to your home, located at (X, Y). You have two methods of travel available to you: you can walk along the street to proceed to a horizontally or vertically adjacent intersection (which takes walkTime seconds), or you can sneak across the block diagonally to the opposite corner (taking sneakTime seconds). You can walk or sneak in any of the eight directions shown in the image (see example 2).

  
Return the least amount of time that it will take you to return home. See the examples for clarification.
Definition
   
Class:
StreetWalking
Method:
minTime
Parameters:
int, int, int, int
Returns:
long long
Method signature:
long long minTime(int X, int Y, int walkTime, int sneakTime)
(be sure your method is public)
   
 
Constraints
-
X will be between 0 and 1,000,000,000, inclusive.
-
Y will be between 0 and 1,000,000,000, inclusive.
-
walkTime will be between 1 and 10000, inclusive.
-
sneakTime will be between 1 and 10000, inclusive.
Examples
0)
 
   
4
2
3
10
Returns: 18
The fastest way to your home is to not sneak at all.
1)
 
   
4
2
3
5
Returns: 16
In this case, it is faster to sneak across twice, following the path (0,0)->(1,0)->(2,1)->(3,1)->(4,2). This takes 10 seconds for the sneaking, and 6 seconds for the walking.
2)
 
   
2
0
12
10
Returns: 20
One possible path is (0,0)->(1,1)->(2,0).
3)
 
   
25
18
7
11
Returns: 247
 
4)
 
   
24
16
12
10
Returns: 240
 
5)
 
   
10000000
50000000
800
901
Returns: 41010000000
 
6)
 
   
135
122
43
29
Returns: 3929
 
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.

walkTime은 건물을 한블럭 지나는데 걸리는 시간.. sneak는 건물을 대각선으로 가로질러 가는데 걸리는 시간일때.. (0, 0)에서 (x, y)까지 가는데 걸리는 최소시간 구하기..

음.. 실제 매치때는 괜히 어렵게 생각해서 못풀었다..
다음과 같이 나눠서 생각하면 쉽다..

1) sneakTime >= 2*walkTime -> 그냥 다 walk로만 다니면 된다..
2) walkTime <= sneakTime < 2*walkTime -> 최대한 sneak로 쭈욱 가다가 남은거는 walk로 간다..
3) wakTime > sneakTime -> 무조건 대각선으로만 가도록 노력한다.. (x+y) 가 짝수이면 sneak로만 다닐수 있지만 홀수이면 한번은 walk로 이동해야한다..

  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 class StreetWalking {
 10 public:
 11
 12 long long minTime(int X, int Y, int walkTime, int sneakTime)
 13 {
 14     long long sum;
 15     if (X > Y)
 16         X^=Y^=X^=Y;
 17     if (walkTime * 2 <= sneakTime) {
 18         sum = (long long)walkTime * X + (long long)walkTime * Y;
 19         return sum;
 20     }
 21     else if (walkTime <= sneakTime && walkTime * 2 > sneakTime) {
 22         sum = (long long)sneakTime * X + (long long)walkTime * (Y-X);
 23         return sum;
 24     }
 25     if ((X+Y) % 2 == 0) {
 26         sum = (long long)sneakTime * Y;
 27         return sum;
 28     }
 29     sum = (long long)sneakTime * (Y-1) + walkTime;
 30     return sum;
 31 }
 32
 33 };

[500] Skyscrapers

Problem Statement
     
The skyline of the city of Terrapin City has N buildings all in a straight line; each building has a distinct height between 1 and N, inclusive. The building at index i is considered visible from the left is there is no building with a smaller index that is taller (formally, height[j] < height[i] for all j < i). Similarly, a building is visible from the right if there is no taller building with a higher index (height[j] < height[i] for all j > i). For example, if the buildings in order are {1, 3, 5, 2, 4}, then three buildings are visible from the left (1, 3 and 5), but only two are visible from the right (4 and 5).
You will be given N, leftSide and rightSide, corresponding to the total number of buildings, the buildings visible from the left, and the buildings visible from the right, respectively. Return the number of permutations of the buildings that are consistent with these values; as this can be a large number, you should return it modulo 1000000007.
Definition
   
Class:
Skyscrapers
Method:
buildingCount
Parameters:
int, int, int
Returns:
int
Method signature:
int buildingCount(int N, int leftSide, int rightSide)
(be sure your method is public)
   
 
Constraints
-
N will be between 1 and 100, inclusive.
-
leftSide and rightSide will be between 1 and N, inclusive.
Examples
0)
 
   
3
2
2
Returns: 2
There are two arrangements of buildings that match these requirements: {1, 3, 2} and {2, 3, 1}.
1)
 
   
3
2
1
Returns: 1
Only {2, 1, 3} fits these requirements.
2)
 
   
5
3
2
Returns: 18
 
3)
 
   
12
1
1
Returns: 0
With 12 buildings, it is impossible for you to only see one building from each side.
4)
 
   
8
3
2
Returns: 4872
 
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 명이 있을때, 왼쪽에서 보면 leftSide 만큼 보이고 오른쪽에서 보면 rightSide 만큼 보이도록 가능한경우의 수

이 문제는 매우 잘 알려진 문제이고 UVa 10128 - Queue 문제와 같다..

쉽게 DP 와 약간의 combinatoric 알고리즘을 이용해야 하지만..

쉽게 memoization 으로 푼 코드를 발견했다..

memo[n][left][right] = n 명이 남아있을때 왼쪽에서 left, 오른쪽에서 right 만큼 보이는 경우의 수..

  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 long long memo[101][101][101];

 13 int mod;

 14

 15 long long recur(int n, int left, int right)

 16 {

 17     long long res;

 18     if (n == 1) {

 19         if (left == 1 && right == 1)

 20             return 1;

 21         return 0;

 22     }

 23     if (n <= 0)

 24         return 0;

 25     if (left == 0 || right == 0)

 26         return 0;

 27     if (left > n || right > n)

 28         return 0;

 29     if (memo[n][left][right] != -1)

 30         return memo[n][left][right];

 31     /* 젤 작은거를 왼쪽에 두는 경우 +

 32        젤 작은거를 오른쪽에 두는 경우 +

 33        중간 아무데나 두는 경우

 34      */

 35     res = recur(n-1, left-1, right) + recur(n-1, left, right-1) + (n-2)*recur(n-1, left, right);

 36     res %= mod;

 37     return memo[n][left][right] = res;

 38 }

 39

 40 class Skyscrapers {

 41 public:

 42

 43 int buildingCount(int N, int leftSide, int rightSide)

 44 {

 45     long long res;

 46     memset(memo, -1, sizeof(memo));

 47     mod = 1000000007;

 48     res = recur(N, leftSide, rightSide);

 49     return (int)res;

 50 }

 51

 52 };

[900] PubTrivia

Problem Statement
     
You and your friends have gotten together for a Trivia night at the local pub. There are N questions asked during the night. Each question is worth a number of points; the i-th element of the points array corresponds to the score received if you correctly answer the i-th question, but you lose that many points if you answer it incorrectly. The questions are given in the order specified, and you must answer each question before the next is asked.
In addition, after each correct answer you will receive a token. If you then have tokensNeeded tokens, the pub will immediately take all of your tokens and award you additional bonus points. However, if you get the question wrong, the pub will take away all of your tokens without giving you any bonuses. The bonuses change after each question; element i of the bonuses array corresponds to the bonus you receive if you win the bonus on question i. Note that it is possible to receive multiple bonuses during the game.
To generate the arrays points and bonuses described above, you should use the following pseudo-code on the arrays p and b, respectively.
Input array:  X
Output array:  P (size N)
k := 0
M := size of X
For i=0 to N-1
 P[i] := X[k]
 s := (k+1)%M
 X[k] := ( ( X[k] ^ X[s] ) + 13 ) % G
 k := s
In the above code, use the value 1001 for G when generating points, and 10001 when generating bonus; this guarantees that all questions will be worth between 0 and 1000 points, inclusive, and that all bonuses will be worth between 0 and 10,000 points, inclusive. In the above code, % represents the modulo operator, and ^ is the binary XOR operator (see the Notes section for the implementation in your language).
You know the answer to all the questions and want to maximize the number of points that you receive. Return the maximum points that you can receive if you correctly choose which questions to answer.
Definition
     
Class:
PubTrivia
Method:
maximumScore
Parameters:
int, int, vector <int>, vector <int>
Returns:
long long
Method signature:
long long maximumScore(int N, int tokensNeeded, vector <int> p, vector <int> b)
(be sure your method is public)
   
 
Notes
-
The input is only coded for convenience. The intended solution does not rely on any property of the number generation; it just generates both arrays and works on them.
-
If x and y are ints, (x^y) represents the bitwise XOR operation on them in C++, Java, and C#. In VB.net, (x BitXor y) does it.
Constraints
-
N will be between 1 and 500,000, inclusive.
-
tokensNeeded will be between 1 and 500,000, inclusive.
-
p and b will each contain between 1 and 50 elements, inclusive.
-
Each element of p will be between 0 and 1000, inclusive.
-
Each element of b will be between 0 and 10000, inclusive.
Examples
0)
 
   
5
5
{1, 2, 3, 4, 5}
{0, 0, 0, 2, 5}
Returns: 20
The best strategy here is to answer all five questions correctly. You score 15 points for the questions, and a 5 point bonus for answering five questions in a row.
1)
 
   
5
3
{1, 2, 3, 4, 5}
{0, 0, 0, 2, 5}
Returns: 16
This time, it is best to answer all of the questions correctly except for the second question. You then receive the bonus on the final question for answering three in a row.
2)
 
   
5
3
{1, 2, 3}
{7, 0}
Returns: 98
Here the question values are {1, 2, 3, 16, 14}, and the bonuses are {7, 0, 20, 33, 66}.
3)
 
   
4
4
{998, 1}
{9998, 1}
Returns: 1056
 
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.