TopCoder SRM 379 Div2 (완료)

일주일만에 참여한 SRM.. 역시.. 아침11시는 너무 힘들다.. ㅠ_ㅠ 집중력이 아무래도 저녁시간과 틀린것같아.. ㅠ_ㅠ 특히 250 문제읽는 중 연구실 모 선배님과의 면담으로인해 많은시간을 까먹고.. 결국 문제 포기상태에 이르렀다.. ㅠ_ㅠ rating은 아주 쬐금 올랐다.. 목표였던 r 1000은 실패.. ㅠ_ㅠ;; 250점은 남들 다 풀었는데.. 왜 나만 못푼것인가.. 그리고 역시.. 난 챌을 시도하면 안돼.. ㅠ_ㅠ;;;

방 5등 전체 167등..

그래도 사상 처음으로 세번 연속 올랐군..




[250] DownloadingFiles

Problem Statement
     
You are downloading some files from the Internet, and you want to know how long it will take until they are completely downloaded.  For each download, you are given its current speed (in KB/s) and remaining time based on that speed (in seconds). The sum of all the speeds is your total bandwidth, which remains constant and is utilized fully at all times during the downloads. This means that when files finish downloading, the newly available bandwidth is distributed among the remaining files. The way it's distributed does not affect the final answer.  For example, consider the following scenario where you are downloading two files. 1) Speed = 3 KB/s Remaining Time 57 seconds 2) Speed = 2 KB/s Remaining Time 22 seconds  After 22 seconds, the second file will finish downloading. The first file still has 35 seconds remaining, but that time is based on the original speed. The bandwidth freed up by the second file is now allocated to the first file, and its new speed is 3+2=5 KB/s. The new remaining time is: Old_Remaining_Time * Old_Speed / New_Speed = 35*3/5 = 21 seconds.  So the actual remaining time for all the files is 21+22=43 seconds.  You will be given a vector <string> tasks, each element of which represents a single file being downloaded. Each file is represented as two positive integers with no leading zeroes, separated by a single space. The first integer is the current download speed in KB/s and the second integer is the remaining time in seconds based on the current speed. Return a double representing the remaining time in seconds for all the downloads to finish.
Definition
   
Class:
DownloadingFiles
Method:
actualTime
Parameters:
vector <string>
Returns:
double
Method signature:
double actualTime(vector <string> tasks)
(be sure your method is public)
   
 
Constraints
-
tasks will contain between 1 and 50 elements, inclusive.
-
Each element of tasks will be formatted "<speed> <time>" (quotes for clarity), where <speed> is an integer between 1 and 100, inclusive, with no leading zeroes, and <time> is an integer between 1 and 10000, inclusive, with no leading zeroes.
Examples
0)
 
   
{"3 57","2 22"}
Returns: 43.0
The example from above.
1)
 
     
{"3 1057","2 1022"}
Returns: 1043.0
This is the same as the first example but all the files will take 1000 seconds more to completely download.
2)
 
   
{"25 1000","5 5000","10 5000"}
Returns: 2500.0
In this case, when the first file finishes downloading, we will have 25 KB/s of newly available bandwidth. We can share it between the remaining downloads however we want without affecting the final answer. Suppose that 15 KB/s goes to the second file and 10 KB/s goes to the third file. The new speeds and remaining times for those files will be: 20 KB/s and remaining time 2000 seconds 20 KB/s and remaining time 1000 seconds Those would take 1500 seconds to complete. So the answer is 1000 + 1500 = 2500.
3)
 
   
{"1 10","1 20","2 40"}
Returns: 27.5
For this example, suppose that all newly available bandwidth goes to the slowest task every time. When the first download finishes (after 10 seconds), the second task doubles its speed to 2, and thus halves its remaining time from (20-10=10) to 5. When the second download finishes, the third one doubles its speed, so its remaining time goes from (40-15=25) to 12.5. The total time is 10+5+12.5=27.5.
4)
 
   
{"6 88","39 7057","63 2502","45 2285","28 8749","62 3636","1 5546","49 5741"}
Returns: 4414.542662116041
And here is a nice random example for you.
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.

여러개의 task가 주어지고.. 각각의 task는 bandwidth와 걸리는시간의 쌍으로 주어진다.. 하나의 task가 끝나면 그동안 쓰고있던 bandwidth가 free가 되고.. 다음 작업에 더해서 쓸수있다.. 쉽게생각하면 여러개의 파일을 동시에 다운받을때.. 예상시간이나오고.. 하나 다운로드가 끝나면.. 다른파일들 예상시간이 팍 줄어드는.. 뭐 그런효과라 하겠다..

흠.. 꼭 풀었어야했는데 아쉽게 놓쳤다.. 초반에 문제 이해하는데도 오래걸렸고.. 중간에 인터럽트로인해 시간도 좀 까먹고.. 결국 시간에 쫒겨서 제대로 시도하지도 못했다..  안타깝다.. 나의 실력이 정말 이거밖에 안되는것인가.. ㅠ_ㅠ

있는 그대로 코딩하는 방법 말고.. 뭔가 꽁수가 반드시 존재할거라고 생각했는데.. 결국 찾는데 실패.. 나중에 다른사람 코드를 보고나서야 깨달았다.. 이런 제길 ㅠ_ㅠ;;; 어쨋든.. 좋은문제이다..

task를 동시에 실행하든 일렬로 실행하든 상관이 없다.. 따라서 총 bandwidth를 구하고 총 task의 크기를 구해서 그것을 한번에 계산하면 된다..

"거리 = 속력 * 시간" (이런 기초 공식을 알고도 못써먹다니..)

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 class DownloadingFiles {
      9 public:
     10
     11 double actualTime(vector <string> tasks)
     12 {
     13     int n, i;
     14     char buf[100];
     15     double size, sp, ti, sum;
     16     n = tasks.size();
     17     size = sum = 0;
     18     for (i = 0; i < n; i++) {
     19         strcpy(buf, tasks[i].c_str());
     20         sscanf(buf, "%lf %lf", &sp, &ti);
     21         size += sp * ti;
     22         sum += sp;
     23     }
     24     return size / sum;
     25 }
     26
     27 };

[500] SellingProducts

Problem Statement
     
You are planning to release a new product on the market and you want to find a strategy that will maximize your profit. That strategy will include fixing the optimal price for the product. You have made a customer list containing the maximum price each potential customer is willing to pay. You also know how much it costs to deliver the product to each of those customers. You are responsible for paying all the shipping costs, so if it's too expensive to deliver the product to a customer, you can choose not to sell to that customer.  You will be given vector <int>s price and cost, where price[i] is the maximum price customer i is willing to pay for the product and cost[i] is the cost of delivering the product to customer i. Return the price for the product that maximizes profit. If there are multiple such prices, return the smallest among them. If it's impossible to achieve a positive profit, return 0.
Definition
     
Class:
SellingProducts
Method:
optimalPrice
Parameters:
vector <int>, vector <int>
Returns:
int
Method signature:
int optimalPrice(vector <int> price, vector <int> cost)
(be sure your method is public)
   
 
Constraints
-
price will contain between 1 and 50 elements, inclusive.
-
Each element of price will be between 1 and 10^6, inclusive.
-
cost will contain the same number of elements as price.
-
Each element of cost will be between 0 and 10^6, inclusive.
Examples
0)
 
   
{13,22,35}
{0,0,0}
Returns: 22
If we sell the product at 13 then all three would buy it.(3x13=39) If we sell the product at 22 then only two would buy it. (2x22=44) If we sell the product at 35 then only one would buy it. (1x35=35) So, 22 is the optimal price for our product.
1)
 
     
{13,22,35}
{5,15,30}
Returns: 13
If we sell the product at 13 then all three would buy it, but we would only sell to the first one.(13-5=8) If we sell the product at 22 then only two would buy it, but we would only sell to the second one.(22-15=7). If we sell the product at 35 then only one would buy it. (35-30=5) So, 13 is the optimal price for our product.
2)
 
   
{13,22,35}
{15,30,40}
Returns: 0
Here it is too expensive to sell to anyone. So the optimal price is 0.
3)
 
   
{10,10,20,20,5}
{1,5,11,15,0}
Returns: 10
If we sell the product at 10 we gain 9 from the first customer and 5 from the second one(Total profit = 14). If we sell the product at 20 we gain 9 from the third customer and 5 from the fourth one(Total profit = 14). So both 10 and 20 are optimal prices but we must choose the smallest one.
4)
 
   
{13,17,14,30,19,17,55,16}
{12,1,5,10,3,2,40,19}
Returns: 17
 
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으로 price와 cost가 들어온다.. price는 소비자가 살수있는 가격.. cost는 그 소비자에게 팔때 드는 배송비용이다.. 소비자가 원하는가격보다 더 싸게 가격을 책정에도 물론 소비자는 산다.. 그러나 배송비용이 더 많이들어서 전혀 이득이 없으면 그 소비자에게는 안팔아도 된다.. 이때 최대의 이익을 내기위한 가격을 구하는문제..

비교적 쉬운문제이다.. 오히려 250보다 더 쉬운데.. 흠.. 사람들은 반대였던것같다..

처음에 가격순으로 정렬한 후 1차원 maximum sum을 돌릴까.. 생각하다가.. 다시보니 input size가 최대50이다.. 그래서 고민하지 않고 모든가격에대해 다 비교해보았다.. O(n^2)

챌 phase 막판에 뭔가 번뜩 떠올라 급조해서 테스트케이스를 만들었는데.. 2번시도해서 다 실패했다.. 알고보니 테스트케이스를 잘못만들었다.. ㅠ_ㅠ;;;

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 using namespace std;
      7
      8 class SellingProducts {
      9 public:
     10
     11 int optimalPrice(vector <int> price, vector <int> cost)
     12 {
     13     int i, j;
     14     int n;
     15     int max1, sum, sell;
     16     max1 = sell = 0;
     17     n = price.size();
     18     for (i = 0; i < n; i++) {
     19         sum = 0;
     20         for (j = 0; j < n; j++) {
     21             if (price[j] >= price[i]) {
     22                 if (price[i] - cost[j] > 0) {
     23                     sum += price[i]-cost[j];
     24                 }
     25             }
     26         }
     27 printf("i = %d, sum = %d\n", i, sum);
     28         if (sum > max1) {
     29             max1 = sum;
     30             sell = price[i];
     31         }
     32         else if (sum == max1) {
     33             if (sell > price[i]) {
     34                 sell = price[i];
     35             }
     36         }
     37     }
     38     return sell;
     39 }
     40
     41 };

[900] TVGameWinnings

Problem Statement
     
A domino is a rectangular tile with a number on each end.  On a TV game show, a player is presented with a NxN board containing N^2 dominoes. The domino in row i, column j (both 1-based indices) contains the numbers i and j. The player must choose exactly N dominoes from the board such that no two dominoes are from the same column and no two are from the same row. He is then required to join all pairs of dominoes that contain the same number. For example, if he picks (1,3), (3,2), (2,4) and (4,1), he must join them all together in a cycle.  At this point, there are one or more groups of connected dominoes (a single domino counts as a group). Because the player is not allowed to choose dominoes from the same column or row, there will always be a single way to join the dominoes together.  Each domino has a hidden number on its back. Compute the product of the hidden numbers of all the selected dominoes. If there is an even number of connected domino groups, multiply this product by -1. The final product is the outcome of the game, and if it is positive, the player wins money, and if it's negative, he loses money.  You are given a vector <string> board containing the hidden numbers of all the dominoes on the board. The j-th character of the i-th element of board is a character representing the hidden number of the domino in row i, column j. Digits '0' to '9' represent the numbers 0 to 9. Letters 'A' to 'I' represent the numbers -1 to -9. Return a vector <int> containing exactly two elements. The first element is the minimum possible outcome of the game, and the second element is the maximum possible outcome.
Definition
   
Class:
TVGameWinnings
Method:
getMinMax
Parameters:
vector <string>
Returns:
vector <int>
Method signature:
vector <int> getMinMax(vector <string> board)
(be sure your method is public)
   
 
Constraints
-
board will contain between 1 and 6 elements, inclusive.
-
Each element of board will contain exactly n characters, where n is the number of elements in board.
-
board will contain only digits '0'-'9' and uppercase letters 'A'-'I'.
Examples
0)
 
   
{"35",
 "44"}
Returns: {-12, 20 }
There are two possible ways to select the dominoes:  1) Select (1,1) and (2,2). You can't join them together, so you have two groups of dominoes (each containing a single domino). The product of their hidden numbers is 3x4 = 12. Since there's an even number of groups, you then multiply by -1 to get -12.  2) Select (1,2) and (2,1). You must join these two together, so you have one connected group of dominoes. The product of their hidden numbers is 4x5 = 20.  The minimum outcome is -12 and the maximum is 20.
1)
 
   
{"00200",
 "0B000",
 "00020",
 "10000",
 "00001"}
Returns: {-8, 0 }
Every choice leads to 0 earnings except (1,3), (2,2), (3,4), (4,1), (5,5). When we choose those, we get three groups of connected dominoes:
(1,3) - (3,4) - (4,1)
(2,2)
(5,5)
The outcome here is 2*(-2)*2*1*1 = -8.
2)
 
   
{"12A",
 "A12",
 "2A1"}
Returns: {-1, 8 }
There are 6 possible ways to select the dominoes, and their outcomes are: -1, 1, 2, 2, 2, 8.
3)
 
   
{"AAAA",
 "BBBB",
 "CCCC",
 "DDDD"}
Returns: {-24, 24 }
Here, no matter how we choose the dominoes, the outcome will always be either 24 or -24.
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 by n 보드가 주어지고 각 row당 & 각 col당 1개의 원소를 택한다.. 선택된 원소를 vertex라고 생각하고 (i, j)의 원소가 선택되었다고 하면, (i, j)는 (j, k) 원소와 edge로 연결된다.. 이런식으로 그래프를 구성하여 탐색할때 선택된 모든 vertex의 곱 * (-1)^(# of connected component % 2 + 1) 을 통해서 나올수 있는 값의 최소값과 최대값을 구하는 문제..

즉, 2 by 2 보드라고 생각하면
(0, 1) -> (1, 0) 이런 경우와
(0, 0), (1, 1) 이런 경우가 나올 수 있다..

문제 파악이 상당히 힘든 문제..;;


board size가 최대 6이므로 나올수 있는 모든 pair를 dfs을 통해서 다 찾는다..
찾은 pair에 대해서 graph를 구성하고 역시 dfs로 탐색하여 connected component의 개수를 구한다..
문제 파악이 가장 어려운 문제.. 해법은 그냥 brute force.. -_-;

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7
  8 int b[10][10], path[10];
  9 int n, c, sum;
 10 char check[10], check2[10];
 11 int min1, max1;
 12
 13 void dfs2(int u)
 14 {
 15     if (check2[path[u]] == 0) {
 16         check2[path[u]] = 1;
 17         sum *= b[u][path[u]];
 18         dfs2(path[u]);
 19     }
 20 }
 21
 22 void dfs(int u)
 23 {
 24     int i;
 25     if (u == n) {
 26         memset(check2, 0, sizeof(check2));
 27         c = 0;
 28         sum = 1;
 29         for (i = 0; i < n; i++) {
 30             if (check2[path[i]] == 0) {
 31                 c++;
 32                 check2[path[i]] = 1;
 33                 sum *= b[i][path[i]];
 34                 dfs2(path[i]);
 35             }
 36         }
 37         if (c % 2 == 0)
 38             sum *= -1;
 39         if (sum < min1)
 40             min1 = sum;
 41         if (sum > max1)
 42             max1 = sum;
 43         return ;
 44     }
 45     for (i = 0; i < n; i++) {
 46         if (!check[i]) {
 47             check[i] = 1;
 48             path[u] = i;
 49             dfs(u+1);
 50             check[i] = 0;
 51         }
 52     }
 53 }
 54
 55 class TVGameWinnings {
 56 public:
 57
 58 vector <int> getMinMax(vector <string> board)
 59 {
 60     int i, j;
 61     char buf[10];
 62     vector<int> res;
 63
 64     n = board.size();
 65     for (i = 0; i < n; i++) {
 66         strcpy(buf, board[i].c_str());
 67         for (j = 0; j < n; j++) {
 68             if (buf[j] >= '0' && buf[j] <= '9') {
 69                 b[i][j] = buf[j] - '0';
 70             }
 71             else {
 72                 b[i][j] = -1 * (buf[j]-'A'+1);
 73             }
 74         }
 75     }
 76
 77     memset(check, 0, sizeof(check));
 78     memset(path, -1, sizeof(path));
 79     max1 = -999999999;
 80     min1 = 999999999;
 81     dfs(0);
 82     res.push_back(min1);
 83     res.push_back(max1);
 84     return res;
 85 }
 86
 87 };