어제 밤 12시에 열린 매치..~
Level1 - Islands
더보기
Problem Statement
The king is trying to find new ways to generate revenue, and he is currently exploring tourism as one potential avenue. The kingdom is a group of islands, and the amount of revenue that can be generated depends on the combined total length of beaches on all the islands. You are given a vector <string> kingdom consisting of '.' or '#' characters. '#' represents a land mass, whereas '.' represents water. kingdom[i][j] represents a regular-hexagon shaped area with each side of unit length. Since the cells are hexagonal in shape, the odd-numbered rows (0-based) are 'shifted' towards the right. A beach is a segment which has water on one side, and land on the other. An example vector <string> and the corresponding image are given below to illustrate. The beaches are marked in red.
{"..#.##",
".##.#.",
"#.#..."}
Return the combined total length of beaches on all the islands.
Definition
Class:
Islands
Method:
beachLength
Parameters:
vector <string>
Returns:
int
Method signature:
int beachLength(vector <string> kingdom)
(be sure your method is public)
Constraints
-
kingdom will contain between 1 and 50 elements, inclusive.
-
Each element of kingdom will contain between 1 and 50 characters, inclusive.
-
Each element of kingdom will contain the same number of characters.
-
Each character in kingdom will be either '.' or '#'.
Examples
0)
{".#...#.."}
Returns: 4
There are two small islands with water on two sides of each island.
1)
{"..#.##",
".##.#.",
"#.#..."}
Returns: 19
The example in the problem statement.
2)
{"#...#.....",
"##..#...#."}
Returns: 15
3)
{"....#.",
".#....",
"..#..#",
"####.."}
Returns: 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.
그림과같이 정육각형 모양으로 생긴 지도를 input 으로 나올때, 해변의 길이 구하기..
모든 '#' 에 대해서 주위가 '.' 인지 아닌지를 검사하면 된다..~
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 Islands {
13 public:
14
15 int beachLength(vector <string> kingdom)
16 {
17 int r, c;
18 int cnt;
19 int i, j;
20 r = kingdom.size();
21 c = kingdom[0].size();
22 cnt = 0;
23 for (i = 0; i < r; i++) {
24 for (j = 0; j < c; j++) {
25 if (kingdom[i][j] == '#') {
26 if (j-1 >= 0 && kingdom[i][j-1] == '.') {
27 cnt++;
28 }
29 if (j+1 < c && kingdom[i][j+1] == '.') {
30 cnt++;
31 }
32 if (i % 2 == 0) {
33 if (i+1 < r && j-1 >= 0 && kingdom[i+1][j-1] == '.') {
34 cnt++;
35 }
36 if (i+1 < r && j >= 0 && kingdom[i+1][j] == '.') {
37 cnt++;
38 }
39 if (i-1 >= 0 && j-1 >= 0 && kingdom[i-1][j-1] == '.') {
40 cnt++;
41 }
42 if (i-1 >= 0 && j >= 0 && kingdom[i-1][j] == '.') {
43 cnt++;
44 }
45 }
46 else {
47 if (i+1 < r && j+1 < c && kingdom[i+1][j+1] == '.') {
48 cnt++;
49 }
50 if (i+1 < r && j < c && kingdom[i+1][j] == '.') {
51 cnt++;
52 }
53 if (i-1 >= 0 && j+1 < c && kingdom[i-1][j+1] == '.') {
54 cnt++;
55 }
56 if (i-1 >= 0 && j < c && kingdom[i-1][j] == '.') {
57 cnt++;
58 }
59 }
60 }
61 }
62 }
63 printf("cnt = %d\n", cnt);
64 return cnt;
65 }
66
67 };
Level2 - PythTriplets
더보기
Problem Statement
The prince has just been introduced to primitive pythagorean triplets. A primitive pythagorean triplet (a, b, c) is a triplet satisfying the following properties:
a, b and c are integers
a^2 + b^2 = c^2
The greatest common divisor of a and b is 1
The prince is not very fond of mathematics. The king is trying to make mathematics fun for his son (the prince). So, the king decides to make as many toys as possible which are triangular in shape having sides (a, b, c) where (a, b, c) form a primitive pythogorean triplet. The wooden framework of the two shorter legs of the toy give the toy its shape and prevent it from breaking, hence each toy with sides of length (a, b, c) must have one wooden stick of length a and one of length b. The third side of length c is not made of wood, and therefore the king does not need a wooden stick for it. You are given a vector <string> stick. Concatenate the elements of stick to get a single-space separated list of the lengths of available sticks. The king is a very loving father and would like to make the toys with his own hands. However, he is not skilled enough to cut the sticks, so he must use them in the sizes they are available. Return the maximum possible number of toys the king can make using these sticks.
Definition
Class:
PythTriplets
Method:
findMax
Parameters:
vector <string>
Returns:
int
Method signature:
int findMax(vector <string> stick)
(be sure your method is public)
Notes
-
An integer may be listed multiple times in the string formed by the concatenation of stick . If an integer n is listed k times, then the king has exactly k sticks of length n available with him.
Constraints
-
stick will contain between 1 and 50 elements, inclusive.
-
Each element of stick will contain between 1 and 50 characters, inclusive.
-
When concatenated, stick will represent a single-space separated list of N integers, where N is between 1 and 200 inclusive.
-
Each listed integer will be between 1 and 999999, inclusive.
-
Listed integers will not have leading zeroes.
Examples
0)
{"3 4 4 3 11 5 12 9 4"}
Returns: 3
(3, 4, 5) and (5, 12, 13) are primitive pythagorean triplets. Hence, there are three disjoint pairs (a, b) - (3, 4), (3, 4) and (5, 12).
1)
{"20 21 3021 220"}
Returns: 2
Possible pairs (a, b) are (20, 21), (21, 220) and (220, 3021). The maximum number of disjoint pairs is 2. Namely, (20, 21) and (220, 3021).
2)
{"28 19", "5 1035 21412 37995"}
Returns: 2
Make sure you concatenate the elements of stick.
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 에서 x^2 + y^2 = z^2 을 만족하는 (x, y) pair 를 최대한 많이 찾기..~
to be updated..
Level3 - KingdomTour
더보기
Problem Statement
The king loves his queen a lot, and he wants to take her all over the kingdom, in just a single day. The kingdom has N cities in it. There are bi-directional roads connecting the cities such that there is a unique path from any city in the kingdom to any other city. Each road has an integral length. The king wants to take his queen on a tour in the kingdom which starts and ends at the kingdom's capital. Since the kingdom is really beautiful, the king wants the tour to cover each road in the kingdom at least once (it doesn't matter in which direction). However, he has been informed that this might take a really long time. Hence, he has decided to build at most K shortcuts. A shortcut can connect any two cities (even if they are directly connected by a road), and the length of a shortcut is L. Since the scenery around the newly constructed shortcuts might not be so beautiful, the king has demanded that any particular shortcut cannot be taken more than once during the tour. The cities in the kingdom are numbered 0 to N-1. City 0 is always the capital. The roads of the kingdom are described in vector <string> roads. Concatenate the elements of roads to get a single string. This string is a comma separated list of the roads in the kingdom in the form "A B C" (quotes for clarity), meaning that there is a road of length C connecting city A and city B. Return the length of the shortest tour satisfying the king's demands.
Definition
Class:
KingdomTour
Method:
minTime
Parameters:
int, vector <string>, int, int
Returns:
int
Method signature:
int minTime(int N, vector <string> roads, int K, int L)
(be sure your method is public)
Constraints
-
N will be between 2 and 200, inclusive.
-
K will be between 0 and 100, inclusive.
-
roads will contain between 1 and 50 elements, inclusive.
-
Each element of roads will contain between 1 and 50 characters, inclusive.
-
roads, when concatenated, will be a comma-separated list of roads, where each road is formatted "A B C" (quotes for clarity).
-
In each road "A B C", A and B will be distinct integers between 0 and N-1, inclusive, with no extra leading zeroes, and C will be an integer between 1 and 10000, inclusive, with no leading zeroes.
-
The roads will be such that the kingdom will satisfy the properties mentioned in the problem statement.
-
L will be between 1 and 10000, inclusive.
Examples
0)
3
{"2 1 9,0 1 3"}
8
4
Returns: 16
If a shortcut is constructed from city 0 to city 2, then the tour 0-->1-->2-->0 has a length of 16 units.
1)
2
{"0 1 4"}
2
3
Returns: 7
Construct a shortcut between the only two existing cities. Traverse the road once, and use the shortcut once.
2)
6
{"4 0 4,2 0 4,2 5 4,4 3 1",
"0,1 2 10"}
2
5
Returns: 41
Make sure you concatenate the elements of roads[].
3)
10
{"1 2 2,4 1 9,2 5 5,6 5 4,", "1 7 7,7 3 1,2 0 2", ",5 8 5,9 5 6"}
2
4
Returns: 59
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..
