TopCoder SRM 363 Div 2 (완료)

두번째 시도한 SRM.. 사실 SRM362 결과가 취소되면서 첫번째 시도인거나 마찬가지다..
근데 어처구니없게도 uva에있는 문제와 거의 똑같은 문제가 나오면서..
한문제를 거저먹었다.. 덕분이 방 1등, 전체 32등.. -_-;
지금 실력에 비해 rating이 너무 높아서 걱정이다..;;

 
[250] MirroredClock

Problem Statement
   
You are sitting in front of a mirror and looking at the image of a clock located behind you. You want to know what time it is. The clock is a traditional clock with a 12-hour board (without numbers written on it), a minute and an hour hand (the hour hand is shorter, so that you can distuniguish them). You are given a string time denoting the time as it is seen in the mirror. The time will be formatted as "HH:MM" (quotes for clarity), where HH is the two digit hour and MM is the two digit minute. The hour will be between 00 and 11, inclusive, where 00 represents 12 o' clock. Return a string in the same format denoting the actual time. See examples for further clarification.
Definition
   
Class:
MirroredClock
Method:
whatTimeIsIt
Parameters:
string
Returns:
string
Method signature:
string whatTimeIsIt(string time)
(be sure your method is public)
   
 
Constraints
-
time will be formatted as "HH:MM" (quotes for clarity), where HH is a two digit integer between 00 and 11, inclusive, and MM is a two digit integer between 00 and 59, inclusive.
Examples
0)
 
   
"10:00"
Returns: "02:00"

 

1)
 
   
"01:15"
Returns: "10:45"
 


2)
 
   
"03:40"
Returns: "08:20"


 
3)
 
   
"00:00"
Returns: "00:00"
Although it doesn't happen often, sometimes we can see the actual time right in the mirror.
4)
 
   
"11:53"
Returns: "00:07"
 
 
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.

거울에 반사된 시계의 시간을 보고 실제 시간 구하기..
그냥 조금만 생각해보면 된다..;;

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 class MirroredClock {
      9 public:
     10
     11 string whatTimeIsIt(string time)
     12 {
     13     char buf[10];
     14     int a, b, c, d;
     15     string ret;
     16     strcpy(buf, time.c_str());
     17     sscanf(buf, "%d:%d", &a, &b);
     18
     19     d = 60 - b;
     20     c = 12 - a;
     21     if (d > 0 && d < 60)
     22         c--;
     23     if (c == 12)
     24         c = 0;
     25     if (d == 60)
     26         d = 0;
     27     sprintf(buf, "%02d:%02d", c, d);
     28     ret = buf;
     29     return ret;
     30 }
     31
     32 };

[500] HandsShaking

Problem Statement
     
Consider a meeting of n businessmen sitting around a circular table. To start the meeting, they must shake hands. Each businessman shakes the hand of exactly one other businessman. All handshakes happen simultaneously. We say that the shake is perfect if no arms cross each other. Given an int n, return the number of perfect shakes that exist for n businessmen. See examples for further clarification.
Definition
   
Class:
HandsShaking
Method:
countPerfect
Parameters:
int
Returns:
long long
Method signature:
long long countPerfect(int n)
(be sure your method is public)
   
 
Notes
-
Businessmen are distinguishable. Rotating a perfect shake can yield a different perfect shake (see example 1).
Constraints
-
n will be between 2 and 50, inclusive.
-
n will be even.
Examples
0)
 
   
2
Returns: 1
Two businessmen have only one possibility - just to shake each other's hand.
1)
 
   
4
Returns: 2
Two out of three possible shakes are perfect.

     
2)
 
   
8
Returns: 14
 
 
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.

원탁에 사람들이 앉아있고 동시에 악수를 하는데 각각의 팔이 cross 되지 않아야 한다.
악수를 할 수 있는 경우의 수 구하기..

http://acm.uva.es/p/v9/991.html 
이문제와 똑같다.. -_-;;
위의 문제를 미리 풀어본 나는 덕분에 거져먹었다..

그런데 이 문제는 Catalan Number를 구하면 된다고 하더라.. 음.. 왜일까..
코드는 생략..

Catalan Number에 관한 글..
http://apnetwork.tistory.com/25


[1000] CrazyComponents

Problem Statement
     
We are building an application using different types of components. Each time we want to install a new component, we choose one randomly (yes, it is crazy). Each of the n types of components has an equal probability 1/n of being chosen. There is an infinite number of each type.  Each time we choose a component instance, we first determine if it can be installed. Some components may require one or more other types of components to already be installed. If all the required components are not currently installed, we cannot install the chosen component.  If the chosen component can be installed, we then decide whether or not to actually install it. Each component has an associated income and expense. The expense is the amount of money we must spend to install the component, and the income is the amount of money the installed component is expected to give us. Our goal is to maximize the expected total profit (all our income minus all our expenses). If we decide to install a chosen component, we must install it immediately (i.e., we can't put it aside and use it later).  Multiple instances of the same component type can be installed in the application. Each instance costs the same amount of money and has the same expected income. Note that once all the requirements for a component have been met, we may install multiple instances of that component type. For example, consider the case where component type 5 requires component type 3, and a single instance of component type 3 is currently installed. Every time we choose component type 5 from now on, we are allowed to install an instance of it. We do not require an instance of component type 3 for each instance of component type 5.  You are given an int k, the number of times we randomly choose a new component. You are also given a String[] components, where the i-th element (0-indexed) contains the requirements for component type i. Each element is a single space separated list of the component's required component types. You are given int[]s income and expense, where the i-th elements are the income and expense, respectively, associated with component type i. We will use an optimal strategy and always try to maximize our expected total profit when deciding whether or not to install chosen components (so, if installing a component lowers our expected total profit, we don't install it). Return our expected total profit.
Definition
   
Class:
CrazyComponents
Method:
expectedProfit
Parameters:
int, String[], int[], int[]
Returns:
double
Method signature:
double expectedProfit(int k, String[] components, int[] income, int[] expense)
(be sure your method is public)
   
 
Notes
-
A return value with either an absolute or relative error of less than 1.0E-9 is considered correct.
Constraints
-
k will be between 1 and 50, inclusive.
-
components will contain between 1 and 15 elements, inclusive.
-
components, income and expense will each contain the same number of elements.
-
Each element of components will be a single space separated list of integers, without leading or trailing spaces.
-
Each integer in each element of components will be between 0 and n-1, inclusive, with no extra leading zeroes, where n is the number of elements in components.
-
The list described by element i of components will not contain i.
-
In each element of components, integers will be distinct.
-
Each element of income will be between 0 and 1000000, inclusive.
-
Each element of expense will be between 0 and 1000000, inclusive.
Examples
0)
 
   
1
{ "", "" }
{ 1, 2 }
{ 0, 0 }
Returns: 1.5
Here, we choose a component only once. If we choose component type 0, our profit is 1 - 0 = 1. If we choose component type 1, our profit is 2 - 0 = 2. Since each type is equally likely to be chosen, the expected profit is 0.5 * 1 + 0.5 * 2.
1)
 
   
2
{ "1", "" }
{ 10, 0 }
{ 0, 2 }
Returns: 1.5
If we pick component 0 in the first turn (1/2 probability), we won't be able to install it. Whichever component we pick after that, it's better not to install it and settle for 0 profit. On the other hand, if we pick component 1 in the first turn (1/2 probability), we should install it even though the net is -2. If on the second try we pick component 1 again (1/4 total probability), we don't install it and end up losing the 2 we already spent. However, if we pick component 0 on the second try (1/4 total probability), we can install it and earn 10 for a total profit of 8. The expected profit is 1/4 * (-2) + 1/4 * 8 = 1.5.
2)
 
   
3
{ "1 2", "", "" }
{ 100, 0, 0 }
{ 0, 0, 0 }
Returns: 7.407407407407408
Component 0 (the only one that makes a profit) requires components 1 and 2 to be already installed, so if we draw it in the first or in the second turn, we won't be able to install it. It is only possible to install it in the 3rd turn, supposing that in the 1st and 2nd turns we drew components 1 and 2. The probability that we will have components 1 and 2 installed after the 2nd turn is 2/3 * 1/3 = 2/9. The probability of then picking component 0 is 1/3, so our expected profit equals 2/9 * 1/3 * 100 = 7.407... .
3)
 
   
5
{ "1", "2", "0", "" }
{ 4, 5, 6, 7 }
{ 0, 0, 0, 8 }
Returns: 0.0
 
4)
 
   
10
{ "", "", "", "", "", "", "", "", "", "" }
{ 142352, 2342, 34534, 2344, 12346, 7589, 79872, 973453, 96233, 34567 }
{ 12432, 2345, 3678, 456, 345, 457, 56758, 4564, 774, 34567 }
Returns: 1269258.9999999998
 
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.

component들을 골라서 application을 만든다.. component를 선택하는것은 랜덤이고(-_-) 각 component끼리는 서로 dependency가 존재한다.. 그리고 각 component를 설치했을때의 설치비용과 수익이 주어진다..
최대 얻을수있는 수익을 구하는 문제..

첫번째 파라미터 k는 k개의 component를 선택
두번째 파라미터는 각 component간의 dependency
세번째 파라미터는 수익
네번째 파라미터는 설치비용..

어떻게 풀어야하나.. ㅠ_ㅠ


다른 사람들 소스를 보고나서야 겨우 이해했다..
역시 고수들은 다르군..
소스를 보니 pure dp로 푼사람도 있었지만.. 대체로 recursion + memorization으로 구현했다..

k번째 단계에서 i번째 component를 선택하는경우와 선택하지않는경우중 더 이익이 남는쪽을 선택한다..
어느쪽이 더 이익인지 알기 위해서는 k-1단계에서 i번째를 선택했을때와 선택하지않았을때를 비교해서 알 수 있다..
즉, 이러한 방법으로 recursive로 계산을 해야한다..
단, 같은상태에대해서 여러번 계산하지 않기위해 memorization을 해야한다..

아.. 어렵다.. ㅠ_ㅠ

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 using namespace std;
      6 #define max(x, y) ((x) > (y) ? (x) : (y))
      7
      8 class CrazyComponents {
      9 public:
     10
     11 int n;
     12 int pro[15];
     13 int need[15];
     14 char check[51][1<<15];
     15 double dp[51][1<<15];
     16
     17 double recur(int k, int mask)
     18 {
     19     int i;
     20     double res;
     21     if (check[k][mask])
     22         return dp[k][mask];
     23     check[k][mask] = 1;
     24     if (k == 0) {
     25         dp[k][mask] = 0.0;
     26         return 0.0;
     27     }
     28     res = 0.0;
     29     for (i = 0; i < n; i++) {
     30         if ((need[i] & mask) == need[i]) {
     31             res += max(recur(k-1, mask), (double)pro[i]+recur(k-1, mask|(1<<i)));
     32         }
     33         else {
     34             res += recur(k-1, mask);
     35         }
     36     }
     37     res /= n;
     38     dp[k][mask] = res;
     39     return res;
     40 }
     41
     42 double expectedProfit(int k, vector<string> components, vector<int> income, vector<int> expense) {
     43     int i;
     44     char buf[1000];
     45     char* p;
     46     n = components.size();
     47     memset(need, 0, sizeof(need));
     48     for (i = 0; i < n; i++) {
     49         strcpy(buf, components[i].c_str());
     50         p = strtok(buf, " ");
     51         while (p != NULL) {
     52             need[i] |= (1 << atoi(p));
     53             p = strtok(NULL, " ");
     54         }
     55         pro[i] = income[i]-expense[i];
     56     }
     57     memset(dp, 0, sizeof(dp));
     58     memset(check, 0, sizeof(check));
     59     return recur(k, 0);
     60 }
     61
     62 };