TopCoder SRM 384 Div2 (완료)

오늘 아침 11시에 있었던 매치.. 역시.. 이번에도 고전했다.. ㅠ_ㅠ 이번에도 두문제를 풀기는했는데.. rating은 오히려 떨어졌다.. 헐.. 이제는 두문제를 풀어도 못올라가는것인가.. ㅠ_ㅠ;; Div2에 참여했던 한국사람들은 다들 선전했다.. 와.. 다들 대단..~! 내가 거의 최하위권.. ;; 이번셋은 별로 tricky하지 않고 떡밥도 별로 없어서 챌린지도 많지 않았다.. 문제를 얼마나 빨리 푸느냐에 따라서 대체로 승부가 갈렸다..

흠.. 중간에 내 개인 코딩서버가 맛탱이가 가는바람에.. 문제풀던 도중 다른 서버로 갈아타는 불상사가.. ㅠ_ㅠ 덕분에 코딩시간이 좀더 길어졌다.. ㅠ

근데 dma_timer_expiry (??) 는 또 뭔 에러지.. 드디어 나의 서버가 맛탱이가 갔구나.. ㅠ_ㅠ

방 8등 전체 161등

250점 resubmit..  500점은 문제이해하는데 오래걸리고.. ㅠ_ㅠ;;

두문제 풀고도 떨어지다니.. 젱장..



[250] Prank

Problem Statement
     
Jane tries her best to stay fit. Knowing this, her sister decided to play a prank on Jane: after Jane's old scale broke down, her sister got her a new scale that shows the square of a person's weight, instead of the real weight.
Not noticing the change, Jane has been using the scale for a while. One morning she screamed "Oh no! I gained apparentGain pounds!". Given an int apparentGain (the difference between the square of Jane's current weight and the square of her previous weight), return a vector <int> containing Jane's possible real weights after the latest measurement, sorted in ascending order.
All weights (displayed and real, previous and current) are positive integers.
Definition
   
Class:
Prank
Method:
realWeight
Parameters:
int
Returns:
vector <int>
Method signature:
vector <int> realWeight(int apparentGain)
(be sure your method is public)
   
 
Constraints
-
apparentGain will be between 1 and 100000, inclusive.
Examples
0)
 
   
233
Returns: {117 }
If Jane had previously weighed 116 pounds, the scale would have shown 116^2 = 13456. If she gained 1 pound, the scale would show 117^2 = 13689, for an apparent gain of 13689 - 13456 = 233.
1)
 
   
15
Returns: {4, 8 }
Assuming in this example Jane is actually a small animal, she could have gone from 1 to 4 or from 7 to 8.
2)
 
   
1440
Returns: {38, 39, 42, 46, 49, 53, 66, 77, 94, 123, 182, 361 }
 
3)
 
   
100000
Returns: {325, 350, 550, 665, 1025, 1270, 2510, 3133, 5005, 6254, 12502, 25001 }
This is the largest input.
4)
 
   
93301
Returns: {3595, 46651 }
Watch out for overflow!
5)
 
   
16
Returns: {5 }
 
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으로 apparentGain 이 주어지고.. x^2 - y^2 = apparentGain 을 만족하는 양의정수 x를 구하기..

y를 1에서부터 다 돌렸다.. upper bound를 어디에 두어야할지 몰라서 대충 50000이라고 했는데.. 다풀고나서 한참 후에 왠지 불안해서 1000000으로 고치고 resubmit 했다.. 흠.. 나중에 테스트를 해보니 y가 50000이 넘는 경우가 없는것같다.. 젠장.. 괜히 resubmit했다.. ㅠ_ㅠ

      1 #include <iostream>
      2 #include <cstdio>
      3 #include <algorithm>
      4 #include <vector>
      5 #include <string>
      6 #include <cmath>
      7 using namespace std;
      8
      9 class Prank{
     10 public:
     11
     12 vector<int> realWeight(int g)
     13 {
     14     long long prev, cur, temp;
     15     vector<int> res;
     16     for (prev = 1; prev <= 1000000; prev++) {
     17         temp = g+prev*prev;
     18         cur = (long long)sqrt((double)temp);
     19         if (cur*cur == temp) {
     20 printf("prev = %lld, cur = %lld..\n", prev, cur);
     21             res.push_back(cur);
     22         }
     23     }
     24 printf("\n");
     25     return res;
     26 }
     27
     28 };

[500] Library

Problem Statement
     
Mr. Agent has entered a government library where secret documents are stored. Documents are stored in different rooms, and each document has a list of user groups that can access it. In order to access a document, a person must have access to the room in which the document is stored and also be a member of at least one user group with access to the document. Your task is to determine the number of documents Mr. Agent can access.  You are given a vector <string> userGroups, each element of which is the name of a user group in which Mr. Agent is a member. You are also given a String[] roomRights, each element of which is the name of a room to which Mr. Agent has access. The documents are given in the vector <string> records. Each element of records is formatted "document_name room user_group" (quotes for clarity), where document_name is the name of a document, room is the name of the room where the document is located, and user_group is the name of a user group that has access to the document. If multiple user groups have access to a document, there will be an entry in records for each group. All documents have distinct names, all rooms have distinct names, and all user groups have distinct names. Return the number of documents Mr. Agent can access.
Definition
   
Class:
Library
Method:
documentAccess
Parameters:
vector <string>, vector <string>, vector <string>
Returns:
int
Method signature:
int documentAccess(vector <string> records, vector <string> userGroups, vector <string> roomRights)
(be sure your method is public)
   
 
Constraints
-
records, userGroups and roomRights will each contain between 0 and 50 elements, inclusive.
-
Each element of userGroups and roomRights will contain between 1 and 15 lowercase letters ('a'-'z').
-
Each element of records will be formatted as "document_name room user_group" (quotes for clarity), where document_name, room and user_group each contain between 1 and 15 lowercase letters ('a'-'z').
-
All elements of records with the same document_name will contain the same room.
-
All elements of records will be distinct.
-
All elements of userGroups will be distinct.
-
All elements of roomRights will be distinct.
Examples
0)
 
   
{"diary computers editor","fairytale gardening editor","comix cars author","comix cars librarian"}
{"employee","editor","author"}
{"history","cars","computers"}
Returns: 2
Mr. Agent only has access to the documents "diary" and "comix".
1)
 
   
{"diary computers editor","fairytale gardening editor","comix cars author","comix cars librarian"}
{"employee","editor","author","librarian"}
{"history","cars","computers"}
Returns: 2
Three elements of records satisfy the conditions, but two of them are for the same document (comix).
2)
 
   
{"diary computers editor","fairytale gardening editor","comix cars author","comix cars librarian"}
{"employee","editor","author","librarian"}
{}
Returns: 0
Mr. Agent can not access any rooms.
3)
 
   
{"a b c","a b d","b b c","b b d","e c d","e c b","e c c","t d e"}
{"c","d","x"}
{"a","b","c"}
Returns: 3
 
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.

도서관에 document들이 있는데 이 document를 접근할 수 있는 group과 document가 있는 room에 접근할 수 있는 권한이 주어진다.. 사용자의 group 권한과 room 권한이 주어질때 접근할 수 있는 document의 개수 구하기..

문제를 이해하는데 오래걸린 문제.. 각 document에 대해서 사용자가 가지고있는 group권한, room 권한인지를 체크한다.. 나같은경우 set을 이용하여 비교하였고.. linear search를 해도 된다.. 매우 쉬운문제..

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 #include <map>
  7 #include <set>
  8 using namespace std;
  9
 10 class Library {
 11 public:
 12
 13 int documentAccess(vector <string> records, vector<string> userGroups, vector<string> roomRights)
 14 {
 15     int i;
 16     char buf[10000], doc[100], group[100], room[100];
 17     set<string> g, r, res;
 18     for (i = 0; i < userGroups.size(); i++) {
 19         g.insert(userGroups[i]);
 20     }
 21     for (i = 0; i < roomRights.size(); i++) {
 22         r.insert(roomRights[i]);
 23     }
 24     for (i = 0; i < records.size(); i++) {
 25         strcpy(buf, records[i].c_str());
 26         sscanf(buf, "%s%s%s", doc, room, group);
 27         if (r.find(room) == r.end())
 28             continue;
 29         if (g.find(group) == g.end())
 30             continue;
 31         res.insert(doc);
 32     }
 33     return res.size();
 34 }
 35
 36 };

[1000] PowerGame

Problem Statement
     
Alan and Bob are playing a game with two piles of sticks. The two players alternate turns, and Alan gets the first turn. During each turn, the player must remove exactly n^2 sticks from each pile, where n is some positive integer. The value of n does not have to be the same for each pile. For example, he can remove 1^2 = 1 stick from the first pile and 3^2 = 9 sticks from the second pile. The first player who cannot make a valid move is declared the loser.  The first pile initially contains size0 sticks and the second pile contains size1 sticks. Suppose both players play optimally. One of them has a winning strategy (no matter how his opponent plays he can always win) and he wants to win as fast as possible. The other player wants to lose as slowly as possible.  Return a String formatted as "<WINNER> will win after <NUMBER> moves" (quotes for clarity), where <WINNER> is the name of the winner and <NUMBER> is the total number of turns in the game. The total number of turns is the sum of all the successful turns taken by Alan and Bob.
Definition
   
Class:
PowerGame
Method:
winner
Parameters:
int, int
Returns:
String
Method signature:
String winner(int size0, int size1)
(be sure your method is public)
   
 
Constraints
-
size0 and size1 will each be between 1 and 10000, inclusive.
Examples
0)
 
   
4
9
Returns: "Alan will win after 1 moves"
A player can take 1, 4, 9, 16, 25, ... sticks. Alan can make all the piles empty in his first move, leaving Bob with no valid moves. He will win the game after 1 turn.
1)
 
   
4
3
Returns: "Alan will win after 1 moves"
Alan can remove all the sticks from the first pile in his first turn, leaving Bob with no valid moves.
2)
 
   
2
3
Returns: "Bob will win after 2 moves"
The only possible move for both players is removing one stick during each turn.
3)
 
   
7
13
Returns: "Bob will win after 4 moves"
 
4)
 
   
2136
1244
Returns: "Alan will win after 7 moves"
 
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^2 꼴의 수를 뺄 수 있다.. 뺄수 없으면 지는겨우.. 두 사람이 각각 최적의 전략(최대한 빨리이기거나 이길수없으면 최대한 늦게 지거나)으로 play할때 처음 시작하는 사람이 몇번만에 이길지.. 이길수없다면 몇번만에 지는지.. 구하는 문제..

그동안 게임이론에 관한 포스팅만 실컷 해놓고.. 정작 게임이론 문제가 나왔는데 못풀었다.. ㅠ_ㅠ
역시.. 게임은 어려워.. ㅠ_ㅠ;;;

아.. 드디어 해결..~! 다른사람 코드를 참조해서 풀었다.. 기본적인 nim game의 이론을 적용해서 풀고.. 몇번만에 이기는지(지는지)를 따로 기억해둔다.. 구현은 깔끔하게.. recursion + memorization으로..

참고자료:  Game Theory

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <vector>
  5 #include <string>
  6 using namespace std;
  7 #define INF 99999999
  8 #define min(x, y) ((x) > (y) ? (y) : (x))
  9 #define max(x, y) ((x) > (y) ? (x) : (y))
 10
 11 char is_sq[10001];
 12 int state[10001];
 13 int cnt[10001];
 14
 15 int recur(int u)
 16 {
 17     int i;
 18     int temp, fl;
 19     int max1, min1;
 20
 21     if (state[u] != 0)
 22         return state[u];
 23     if (u == 0) {
 24         cnt[u] = 0;
 25         return -1;
 26     }
 27     if (is_sq[u]) {
 28         cnt[u] = 1;
 29         return 1;
 30     }
 31     min1 = INF;
 32     max1 = 0;
 33     fl = 0;
 34     for (i = 1; i*i <= u; i++) {
 35         temp = recur(u-i*i);
 36         if (temp == -1) {
 37             fl = 1;
 38             min1 = min(min1, cnt[u-i*i]+1);
 39         }
 40         else if (temp == 1) {
 41             max1 = max(max1, cnt[u-i*i]+1);
 42         }
 43     }
 44     if (fl) {
 45         cnt[u] = min1;
 46         return 1;
 47     }
 48     cnt[u] = max1;
 49     return -1;
 50 }
 51
 52 class PowerGame {
 53 public:
 54
 55 string winner(int size0, int size1)
 56 {
 57     int i;
 58     char ret[100];
 59     memset(is_sq, 0, sizeof(is_sq));
 60     for (i = 1; i <= 100; i++) {
 61         is_sq[i*i] = 1;
 62     }
 63     memset(state, 0, sizeof(state));
 64     for (i = 0; i <= 10000; i++) {
 65         state[i] = recur(i);
 66     }
 67
 68     if (cnt[size0] < cnt[size1]) {
 69         if (state[size0] == 1)
 70             sprintf(ret, "Alan will win after %d moves", cnt[size0]);
 71         else
 72             sprintf(ret, "Bob will win after %d moves", cnt[size0]);
 73     }
 74     else if (cnt[size0] > cnt[size1]) {
 75         if (state[size1] == 1)
 76             sprintf(ret, "Alan will win after %d moves", cnt[size1]);
 77         else
 78             sprintf(ret, "Bob will win after %d moves", cnt[size1]);
 79     }
 80     else {
 81         if (state[size0] == 1 && state[size1] == 1)
 82             sprintf(ret, "Alan will win after %d moves", cnt[size1]);
 83         else
 84             sprintf(ret, "Bob will win after %d moves", cnt[size1]);
 85     }
 86     return ret;
 87 }
 88
 89 };