오늘 새벽 1시에 열렸던 매치..
매우 피곤한 상태임에도 불고하고 지난번 SRM 445 의 복수전을 벼르고있었는데..
이상한 난이도의 문제들 덕분에 결국 삽질끝에 또다시 참패했다..
rating이 10점은 올랐으니.. 뭐 참패까지는 아니지만.. 이거 참 맘에 안드네..
250은 매우 쉬운문제가 나왔으나.. 나의 코딩 스피드 부족으로 남들에 비해 순위가 많이 쳐졌다..
500은 너무 어려운 문제가 나오고.. 흐미..
이런경우 챌 하나 성공하면 순위를 많이 끌어올릴수 있으나.. 오늘은 정말 챌 할수있는게 없었다..
우리 방에서 500점 하나 빼놓고 모든 코드가 패스해버렸다.. 챌을 시도했으면 그야말로 X 되는 매치..
물론 챌을 시도한사람도 없었다..
Level1 - CubeWalking
Problem Statement
Consider the 3x3x3 cube shown above. There are nine squares on each of its six faces, and each face is colored using the following pattern:
The four corner squares are red.
The center square is green.
The remaining four squares are blue.
There is a robot standing in the green square of the top face of the cube, facing one of the blue squares. It receives a sequence of commands. Each command is one of the following:
'L': Stay in the current square and turn left 90 degrees.
'R': Stay in the current square and turn right 90 degrees.
'W': Walk forward in the current direction to the next square.
Note that the robot can cross an edge of the cube into another face. When that happens, the cube will rotate automatically to keep the robot on the top face.
You are given a string movement containing the sequence of commands received by the robot. The robot will execute all of the commands in order. Return the color of the robot's final landing square - "RED", "GREEN" or "BLUE" (all quotes for clarity).
Definition
Class:
CubeWalking
Method:
finalPosition
Parameters:
string
Returns:
string
Method signature:
string finalPosition(string movement)
(be sure your method is public)
Notes
-
The answer does not depend on the initial direction of the robot.
Constraints
-
movement will contain between 1 and 50 characters, inclusive.
-
Each character in movement will be 'L', 'R' or 'W'.
Examples
0)
"LLRR"
Returns: "GREEN"
In this example, the robot only turns left or right without ever moving to a different square.
1)
"WWWWWWWWWWWW"
Returns: "GREEN"
Walking 12 squares forward in the same direction will lead the robot back to its original position.
2)
"WLWRW"
Returns: "RED"
3)
"WWLLWRWLWLLRWW"
Returns: "BLUE"
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.
그림과 같은 cube의 중앙에 로봇이 서있다.. L (turn left), R (turn right), W (move forward) 명령을 여러번 수행했을때 로봇이 위치한 cell의 color 구하기
9개의 cell을 0~8 까지 번호를 매겨서 관리하고 인풋에 대해 현재의 방향과 위치에따른 처리를 if 문으로 몽땅 해결했다.. 덕분에 시간좀 걸렸다..~
x 좌표와 y 좌표를 따로 관리하면서 하면 훨씬 짧은 코드가 되었을텐데..
그러고보니.. 내가 서밋한 코드중에 140줄이 넘는 코드가 있었나.. -_-??
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
11 class CubeWalking {
12 public:
13
14 string finalPosition(string move)
15 {
16 int len;
17 int dir, pos;
18 int i;
19 char ch;
20 string res;
21 dir = 0;
22 pos = 4;
23 len = move.size();
24 for (i = 0; i < len; i++) {
25 ch = move[i];
26 if (ch == 'L') {
27 dir = dir - 1;
28 if (dir < 0)
29 dir = 3;
30 continue;
31 }
32 else if (ch == 'R') {
33 dir = (dir + 1) % 4;
34 continue;
35 }
36 if (pos == 0) {
37 if (dir == 0) {
38 pos = 6;
39 }
40 else if (dir == 1) {
41 pos = 1;
42 }
43 else if (dir == 2) {
44 pos = 3;
45 }
46 else {
47 pos = 2;
48 }
49 }
50 else if (pos == 1) {
51 if (dir == 0)
52 pos = 7;
53 else if (dir == 1)
54 pos = 2;
55 else if (dir == 2)
56 pos = 4;
57 else if (dir == 3)
58 pos = 0;
59 }
60 else if (pos == 2) {
61 if (dir == 0)
62 pos = 8;
63 else if (dir == 1)
64 pos = 0;
65 else if (dir == 2)
66 pos = 5;
67 else if (dir == 3)
68 pos = 1;
69 }
70 else if (pos == 3) {
71 if (dir == 0)
72 pos = 0;
73 else if (dir == 1)
74 pos = 4;
75 else if (dir == 2)
76 pos = 6;
77 else if (dir == 3)
78 pos = 5;
79 }
80 else if (pos == 4) {
81 if (dir == 0)
82 pos = 1;
83 else if (dir == 1)
84 pos = 5;
85 else if (dir == 2)
86 pos = 7;
87 else if (dir == 3)
88 pos = 3;
89 }
90 else if (pos == 5) {
91 if (dir == 0)
92 pos = 2;
93 else if (dir == 1)
94 pos = 3;
95 else if (dir == 2)
96 pos = 8;
97 else if (dir == 3)
98 pos = 4;
99 }
100 else if (pos == 6) {
101 if (dir == 0)
102 pos = 3;
103 else if (dir == 1)
104 pos = 7;
105 else if (dir == 2)
106 pos = 0;
107 else if (dir == 3)
108 pos = 8;
109 }
110 else if (pos == 7) {
111 if (dir == 0)
112 pos = 4;
113 else if (dir == 1)
114 pos = 8;
115 else if (dir == 2)
116 pos = 1;
117 else if (dir == 3)
118 pos = 6;
119 }
120 else if (pos == 8) {
121 if (dir == 0)
122 pos = 5;
123 else if (dir == 1)
124 pos = 6;
125 else if (dir == 2)
126 pos = 2;
127 else if (dir == 3)
128 pos = 7;
129 }
130 }
131 if (pos == 0 || pos == 2 || pos == 6 || pos == 8)
132 res = "RED";
133 else if (pos == 4)
134 res = "GREEN";
135 else
136 res = "BLUE";
137 return res;
138 }
139
140 };
Level2 - AntOnGraph
Problem Statement
You are given a directed graph with n vertices, labeled 0 to n-1. The edges of the graph contain values, and each time you traverse an edge, the value of that edge gets added to your total score. If the same edge is traversed multiple times, its value gets added every time. Values can be any number between -499 and 499, inclusive. There are no edges that connect a vertex to itself.
There's an ant at vertex 0 and it wants to get to vertex 1. It must do this in an integer number of seconds between 1 and timeLimit, inclusive. The ant must make exactly stepsPerSecond steps each second, where each step consists of moving from its current vertex V to an adjacent vertex W (W is adjacent to V if there's a directed edge from V to W in the graph). The ant's goal is to get the highest score possible.
The graph is given as three String[]s p0, p1 and p2. Concatenate the j-th characters of the i-th elements of p0, p1 and p2 (in that order) to get a 3-digit String S. If S is "000", then there is no edge from vertex i to vertex j. Otherwise, there is an edge from vertex i to vertex j, and its value is A - 500, where A is the integer value of S. For example, if S is "100", then the value is -400, and if S is "999", the value is 499. Return the decimal representation of the highest possible score as a String with no extra leading zeroes. If it is impossible to reach vertex 1 under the given constraints, return "IMPOSSIBLE" (quotes for clarity) instead.
Definition
Class:
AntOnGraph
Method:
maximumBonus
Parameters:
String[], String[], String[], int, int
Returns:
String
Method signature:
String maximumBonus(String[] p0, String[] p1, String[] p2, int stepsPerSecond, int timeLimit)
(be sure your method is public)
Constraints
-
p0 will contain between 2 and 50 elements, inclusive.
-
p1 and p2 will each contain the same number of elements as p0.
-
Each element in p0, p1 and p2 will contain exactly n characters, where n is the number of elements in p0.
-
Each character in p0, p1 and p2 will be a digit ('0'-'9').
-
The i-th character of the i-th element of p0, p1 and p2 will be '0'.
-
stepsPerSecond will be between 1 and 100, inclusive.
-
timeLimit will be between 1 and 1000000000 (10^9), inclusive.
Examples
0)
{"05","50"}
{"00","00"}
{"01","10"}
3
2
Returns: "3"
Here, there are two vertices. There's an edge from vertex 0 to vertex 1 and an edge from vertex 1 to vertex 0. Both edges have a value of 1. The ant must make exactly 3 steps per second, so during the first second, it will make the following moves: 0->1, 1->0, 0->1. The time limit is 2, so there's time for 3 more moves. However, that would place the ant back at vertex 0, so the ant should stop after the first second.
1)
{"05","50"}
{"00","00"}
{"01","10"}
2
3
Returns: "IMPOSSIBLE"
This is the same graph as the previous example, but this time, the ant must make exactly 2 steps per second. The ant can therefore never reach vertex 1 because it will always return to vertex 0 after each second.
2)
{"0550","0000","0005","5000"}
{"0000","0000","0000","0000"}
{"0110","0000","0001","1000"}
7
9
Returns: "49"
In this case the ant can traverse cycle 0->2->3->0 and earn 3 points. The ant will keep moving along this cycle and finally go to vertex 1 and earn another point. Thus the number of points modulo 3 is 1. Among all multiple of 7 less than or equal to 63, 49 is the biggest one that satisfies the constraints.
3)
{"0540","0000","0004","4000"}
{"0090","0000","0009","9000"}
{"0190","0000","0009","9000"}
7
9
Returns: "-5"
This is the same as the previous example, but this time, the score for the cycle is -3.
4)
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.
graph 가 주어지고 각 edge 에는 score 가 주어져있다.. 0번에서 1번으로 갈때 score를 최대 많이 먹기..
단 제한이 있는데 한번 move 에 1초가 걸리는데 반드시 step 만큼 홉을 건너야한다.. 또한 limit 초 안에 1번 vertex 에 도착해야한다..
to be updated..
Level3 - CubePainting
Problem Statement
You are given a 3x3x3 cube. Each face of the cube contains a 3x3 grid of nine squares. Some of the squares are painted and the rest are unpainted. Your task is to calculate the number of ways you can cover all the unpainted squares with "cube-cycles".
A cube-cycle is a sequence of 3 or more squares, where each square is "cube-adjacent" to the next square, and the last square is "cube-adjacent" to the first square. All squares in a cube-cycle must be distinct. Two squares are cube-adjacent if they share a common edge. That common edge can be on a face or on an edge of the cube. Each square in the cube has exactly four cube-adjacent squares.
Note that two cube-cycles might be distinct even if they contain the same set of squares. See example 0.
You are given the cube as a vector <string> containing 54 characters, where each character represents a single square. The vector <string> will be formatted as a net of the cube, as shown below:
+---+
| |
+---+---+---+---+
| | | | |
+---+---+---+---+
| |
+---+
Painted squares are represented by '*' characters and unpainted squares are represented by '.' characters. You are only allowed to cover unpainted squares with cube-cycles. You are not allowed to cover painted squares. All unpainted squares must be covered, and no two cube-cycles can overlap each other. Return the number of ways you can cover the cube modulo 1,000,000,007.
Definition
Class:
CubePainting
Method:
count
Parameters:
vector <string>
Returns:
int
Method signature:
int count(vector <string> cube)
(be sure your method is public)
Constraints
-
cube will contain exactly 9 elements.
-
Elements 0, 1, 2, 6, 7 and 8 of cube will each contain exactly 3 characters.
-
Elements 3, 4 and 5 of cube will each contain exactly 12 characters.
-
All characters in cube will be either '*' or '.'.
Examples
0)
{"***",
"***",
"***",
"**....******",
"**....******",
"**....******",
"***",
"***",
"***"}
Returns: 3
There are two ways to cover it with one cycle and one way with two cycles.
1)
{"***",
"***",
"***",
"************",
"............",
"************",
"***",
"***",
"***"}
Returns: 1
There is only one way to cover a strip.
2)
{".*.",
"***",
".*.",
".*..*..*..*.",
"************",
".*..*..*..*.",
".*.",
"***",
".*."}
Returns: 1
All squares in the corners should be covered. There are eight independent cycles.
3)
{"***",
"***",
"***",
"************",
"************",
"************",
"***",
"***",
"***"}
Returns: 1
All squares are painted in this case.
4)
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.
