John and Gogo are playing Doors Game. This game is played in a building containing a single row of N+1 rooms, numbered 0 through N from left to right. One of the rooms is called the trophy room. There's a door between each pair of adjacent rooms. Each door has a color, and there are 16 possible colors (represented by uppercase letters 'A' through 'P'). All doors are initially closed. Initially, John is in room 0 and Gogo is in room N. The two players alternate turns, and John gets the first turn. On each turn, the current player chooses a color which hasn't yet been chosen from among the 16 possible colors. All doors, if any, with the chosen color are then opened. At this point, if one of the players can reach the trophy room by walking through only open doors, that player wins and the game ends. If both players can reach the trophy room, the game ends in a draw. If neither player can reach the trophy room, the game continues. Each player will play according to the following strategy: Each time a player needs to choose a color, he will make make his choice as follows:
If it's possible for him to choose a color in such a way that he will be able to win no matter what his opponent does, he will choose such a color. If there are several such colors, he will choose the one among them for which the game will end with the fewest total number of colors chosen, assuming that the opponent aims to maximize the number of colors chosen in the game.
Otherwise, if it's possible for him to choose a color in such a way that he will be able to end the game in a draw no matter what his opponent does, he will choose any such color.
Otherwise, he will choose a color for which the game will end with the largest total number of colors chosen, assuming that his opponent aims to win while minimizing the total number of colors chosen.
You are given the colors of the doors in the string doors. The i-th character in doors is the color of the door connecting rooms i and i+1. You are also given an int trophy, which denotes the number of the trophy room. If the game ends in a draw, return 0. Otherwise, let X be the number of colors chosen in the game. If John wins, return X. If Gogo wins, return -X.
Definition
Class:
DoorsGame
Method:
determineOutcome
Parameters:
string, int
Returns:
int
Method signature:
int determineOutcome(string doors, int trophy)
(be sure your method is public)
Constraints
-
doors will contain between 2 and 50 characters, inclusive.
-
Each character in doors will be an uppercase letter 'A'-'P'.
-
trophy will be between 1 and N-1, inclusive, where N is the number of characters in doors.
Examples
0)
"ABCD"
2
Returns: 3
There are five rooms, with the trophy room in the middle. John will win after he chooses color A and B.
1)
"ABCC"
2
Returns: -2
In this case, Gogo will win by just choosing color C.
2)
"ABABAB"
3
Returns: 0
When colors A and B have been chosen, both players will be able to reach the trophy room.
3)
"ABAPDCAA"
5
Returns: -4
4)
"MOCFDCE"
3
Returns: 5
5)
"ABCCDE"
3
Returns: 0
6)
"ABCCD"
3
Returns: 0
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.
0 번부터 n 번까지 n+1 개의 방이 있고 각 방은 door 로 연결되어있는데 door 마다 색깔이 있다
두사람이 서로 색깔 하나씩을 번갈아가면서 선택하는데 선택한 색깔의 door 가 open 된다
먼저 trophy 번째 방에 갈수 있는사람이 이기는 게임.. 둘다 동시에 간다면 draw
처음에 문제 보고 게임이론인줄 알고 황당해했지만.. 자세히 생각해보니 그냥 simulation 문제였다.
1. 두 player 는 각각 서로 자신만 필요로하는 색깔을 선택해야한다..
2. 그게 다 떨어졌을 경우 상대방이 필요로하더라도 내가 goal 에 도달하기 위한 색깔을 선택해야한다.
1번은 직관적이지만.. 2번은 직관적이지가 않았다..
틀릴걸 각오하고 서밋하고.. 반례를 찾아보려고했는데.. 반례 찾는데 실패..;;
왜 이 전략이 optimal 인지 더 생각해봐야겠다..~
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 DoorsGame {
13 public:
14
15 int determineOutcome(string doors, int trophy)
16 {
17 int i;
18 int s1, s2;
19 int cnt, fl;
20 s1 = s2 = 0;
21 for (i = 0; i < trophy; i++) {
22 s1 |= (1 << (doors[i]-'A'));
23 }
24 for (i = doors.size()-1; i >= trophy; i--) {
25 s2 |= (1 << (doors[i]-'A'));
26 }
27
28 fl = 1;
29 cnt = 0;
30 while (s1 && s2) {
31 if (fl) {
32 for (i = 0; i < 16; i++) {
33 if (s1 & (1 << i)) {
34 if (s2 & (1 << i))
35 continue;
36 break;
37 }
38 }
39 if (i < 16) {
40 s1 -= (1 << i);
41 cnt++;
42 }
43 else {
44 for (i = 0; i < 16; i++) {
45 if (s1 & (1 << i)) {
46 break;
47 }
48 }
49 s1 &= ~(1 << i);
50 s2 &= ~(1 << i);
51 cnt++;
52 }
53 }
54 else {
55 for (i = 0; i < 16; i++) {
56 if (s2 & (1 << i)) {
57 if (s1 & (1 << i))
58 continue;
59 break;
60 }
61 }
62 if (i < 16) {
63 s2 -= (1 << i);
64 cnt++;
65 }
66 else {
67 for (i = 0; i < 16; i++) {
68 if (s2 & (1 << i))
69 break;
70 }
71 s1 &= ~(1 << i);
72 s2 &= ~(1 << i);
73 cnt++;
74 }
75 }
76
77 fl = (fl+1) % 2;
78 }
79
80 if (s1 == 0 && s2 == 0)
81 return 0;
82 if (s1 == 0)
83 return cnt;
84 return -cnt;
85 }
86
87 };
Level2 - DrawingLines
Problem Statement
NOTE: This problem statement contains images that may not display properly if viewed outside of the applet. Little John has drawn a rectangle. On the top edge, he draws n dots at different places and numbers them 1 through n from left to right. On the bottom edge, he also draws n dots at different places and numbers them 1 through n from left to right. John will then draw n straight line segments. For each segment, he will first choose a dot on the top edge that has not been chosen earlier. Then, he will choose a dot on the bottom edge that has not been chosen earlier. Finally, he will connect those two dots to form a straight line segment. John has drawn several of the n segments so far. You are given vector <int>s startDot and endDot. startDot[i] is the number of the top dot chosen for the i-th segment which has already been drawn, and endDot[i] is the number of the bottom dot chosen for that segment. For each remaining segment, John will randomly choose an available top dot and an available bottom dot (each available top dot has an equal probability of being chosen, and each available bottom dot has an equal probability of being chosen). Return the expected number of distinct pairs of line segments that cross each other in the final drawing.
Definition
Class:
DrawingLines
Method:
countLineCrossings
Parameters:
int, vector <int>, vector <int>
Returns:
double
Method signature:
double countLineCrossings(int n, vector <int> startDot, vector <int> endDot)
(be sure your method is public)
Notes
-
The returned value must have an absolute or relative error less than 1e-9.
Constraints
-
n will be between 2 and 10000, inclusive.
-
startDot and endDot will each contain between 1 and 50 elements, inclusive.
-
startDot and endDot will contain the same number of elements.
-
startDot and endDot will each contain less than n elements.
-
Each element of startDot will be between 1 and n, inclusive.
-
Each element of endDot will be between 1 and n, inclusive.
-
All elements of startDot will be distinct.
-
All elements of endDot will be distinct.
Examples
0)
3
{2}
{3}
Returns: 1.5
There are four possible ways for Little John to pick the dots :
[Top 1]-[Bottom 1] [Top 3]-[Bottom 2]
[Top 1]-[Bottom 2] [Top 3]-[Bottom 1]
[Top 3]-[Bottom 1] [Top 1]-[Bottom 2]
[Top 3]-[Bottom 2] [Top 1]-[Bottom 1]
The first and the fourth ways correspond to the left picture, while the second and the third ways correspond to the right picture. The blue line is the line initially drawn by Little John. In the left configuration, there is 1 pair of segments that cross each other. In the right configuration, there are 2 pairs of segments that cross each other. Hence, the expected number of crossed pairs is 1.5.
1)
5
{1,4}
{3,1}
Returns: 5.5
2)
4
{4,1}
{4,1}
Returns: 0.5
3)
8
{1,4,3,6,7}
{1,3,2,4,5}
Returns: 7.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.
to be updated..
Level3 - BuildingRoads
Problem Statement
You are given the map of a country which is divided into a rectangular grid of cells. The country contains several cities, each of which occupies a single cell. Your goal is to connect certain pairs of cities with direct roads. However, there are several large rocks which might get in your way. Each rock potentially spans multiple cells, and costs some amount of money to destroy. You want to build your roads while spending as little money as possible destroying rocks. You are given the map in the vector <string> field. The j-th character of the i-th element of field represents the cell at row i, column j. Each cell is one of the following:
'.' - Empty space.
'!', '@', '#', or '$' - A city. For each of these characters, there can be either 0 or 2 cities denoted by it.
'a'-'z', 'A'-'Z', or '0'-'9' - A cell which is occupied entirely by a rock.
Cells containing rocks which are denoted by the same character are occupied by the same physical rock. Each pair of cells which is occupied by the same rock will be connected. This means that if you label the cells C1 and C2, at least one of the following will be true:
C1 and C2 share a side.
There exists another cell C3, where C1 and C3 share a side, and C3 is connected to C2.
The character used to denote a rock represents the cost required to destroy that entire rock. The costs are as follows:
'a' - 'z': 1 - 26
'A' - 'Z': 100 - 2,600 (each letter costs 100 more than the previous letter)
'1' - '9': 10,000 - 90,000 (each digit costs 10,000 more than the previous digit)
'0': 100,000
You must build a road between each pair of cities denoted by the same character. Each road must be a continuous (but not necessarily straight) line which starts in the middle of one city and ends in the middle of the other city. Roads cannot be built outside the boundaries of the map, and roads must not touch any cell which contains a rock (not even the sides or corners of such cells). Return the minimum cost required to destroy all the rocks necessary to build the roads.
Definition
Class:
BuildingRoads
Method:
destroyRocks
Parameters:
vector <string>
Returns:
int
Method signature:
int destroyRocks(vector <string> field)
(be sure your method is public)
Notes
-
The roads are assumed to be arbitrarily thin, and can intersect each other.
-
The roads may pass through any city.
Constraints
-
field will contain between 2 and 50 elements, inclusive.
-
Each element of field will contain between 1 and 50 characters, inclusive.
-
Each element of field will contain the same number of characters.
-
Each character in field will be '.', 'a'-'z', 'A'-'Z', '0'-'9', '!', '@', '#', or '$'.
-
field will contain either zero or two occurrences of '!'.
-
field will contain either zero or two occurrences of '@'.
-
field will contain either zero or two occurrences of '#'.
-
field will contain either zero or two occurrences of '$'.
-
There will be at least two cities in field.
-
Each pair of cells which is occupied by the same rock will be connected (as described in the problem statement).
Examples
0)
{"!1.!",
"aab2"}
Returns: 3
You must destroy the two rocks which cover the purple cells. The total cost is 3.
1)
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.
