오랜만에 열린 SRM.. 또 망했다.. 연일 최저 rating을 갱신하고있다.. ㅠ_ㅠ 어쩌다 이지경이 됐는지.. 이번매치의 경우 블챌이 rating하락의 주범이다.. 앞으로 블챌은 자제하고 안정적으로 가야겠다.. 500점도 쉬운문제였는데 너무 안일하게 대처하다 틀렸다.. 흐미.. 확실히 맞았다고 생각했는데.. 학교가 정전되는바람에 학교서버에서 코딩을 못하고 .net에서 코딩했는데.. 완전 어색.. -_-; 탑코더가 쉽지않다는것을 다시한번 느꼈다.. 방 12등 전체 436등..
ㅠ_ㅠ
흐미.. 1군은 커녕.. green도 버거워보이는군..
[250] HockeyFault
Problem Statement
Last week, MyOwnBusiness Inc. received an urgent call from the IIHF (International Ice Hockey Federation) requesting a system to raise an alarm to the referee when there are too many players from the same team inside the rink. The system will be composed of three parts: A digital camera in the ceiling to take photos of the rink every second. A software module to extract the position of each player from the photo taken by the digital camera. A software module to count the number of players from the same team inside the hockey rink. The hockey rink consists of a width x height rectangle whose lower-left corner is at (x, y), and two circles with radius height / 2, one centered at (x, y + radius) and the other centered at (x + width, y + radius). See the image below for a graphic description. The players are specified by the vector <int>s px and py, where the k-th player's position is (px[k], py[k]).
You have been assigned the task of implementing the system's third module, following the specification given by the project leader: "Given the rink's specification and the players' positions, create a method numPlayers that returns the number of players on the boundary or inside the rink." Definition
Class: HockeyFault Method: numPlayers Parameters: int, int, int, int, vector <int>, vector <int> Returns: int Method signature: int numPlayers(int width, int height, int x, int y, vector <int> px, vector <int> py) (be sure your method is public)
Notes - For those who know about ice hockey, the rink described in this problem is different than a real hockey rink. Constraints - width will be between 1 and 100, inclusive. - height will be between 2 and 100, inclusive. - height will be an even number. - x will be between -100 and 100, inclusive. - y will be between -100 and 100, inclusive. - px will contain between 1 and 50 elements, inclusive. - Each element of px will be between -300 and 300, inclusive. - py will contain the same number of elements as px. - Each element of py will be between -300 and 300, inclusive. Examples 0)
20 10 5 0 {15, 1, 1} {5, 5, 1} Returns: 2 The first player is exactly in the middle of the rink, the second player is exactly at the left border of the left circle and the third player is outside the rink. 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.
아이스하키 링크가 주어지고 선수들의 좌표가 주어진다.. 아이스링크안에 몇명의 선수가 있는지 세는 문제..
좌표가 가운데 정사각형에 포함되는지 세고.. 그렇지 않을경우 좌우의 반원에 포함되는지 계산한다.. 쉬운문제..
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 HockeyFault { 10 public: 11 12 int numPlayers(int width, int height, int x, int y, vector <int> px, vector <int> py) 13 { 14 int cnt, i; 15 int n = px.size(); 16 double x1, y1; 17 double temp1, temp2, r; 18 cnt = 0; 19 r = 0.5 * height; 20 for (i = 0; i < n; i++) { 21 x1 = (double)px[i]; 22 y1 = (double)py[i]; 23 if (x1 >= x && x1 <= x+width && y1 >= y && y1 <= y+height) { 24 cnt++; 25 } 26 else { 27 temp1 = sqrt((x-x1)*(x-x1)+(y+r-y1)*(y+r-y1)); 28 temp2 = sqrt((x+width-x1)*(x+width-x1)+(y+r-y1)*(y+r-y1)); 29 if (temp1 <= r || temp2 <= r) 30 cnt++; 31 } 32 33 } 34 35 return cnt; 36 } 37 38 };
[500] SyllableSorting
Problem Statement
Syllable sorting is a method of sorting words based on their syllabic decompositions. The first step is to decompose each word into syllables. A syllable is defined as a maximal non-empty substring of consonants followed by a maximal non-empty substring of vowels. The only vowels are 'a', 'e', 'i', 'o' and 'u'. All other letters are considered consonants. All words will start with a consonant and end with a vowel.
To compare two words syllabically, first decompose them into sequences of syllables. For example, the words "zcdbadaerfe" and "foubsyudba" decompose as follows: "zcdbadaerfe" = {"zcdba", "dae", "rfe"} "foubsyudba" = {"fou", "bsyu", "dba"} Then, sort each sequence of syllables alphabetically. In the above example, the sequences become: {"dae", "rfe", "zcdba"} {"bsyu", "dba", "fou"} Then, compare these sorted sequences lexicographically. A sequence S1 comes before a sequence S2 lexicographically if S1 has an alphabetically earlier element at the first index at which they differ. In the above example, the second sequence comes earlier lexicographically because "bsyu" comes before "dae" alphabetically.
If two sorted sequences are equal, then compare their corresponding unsorted sequences instead. For example, the words "daba" and "bada" decompose into the same sorted sequence {"ba", "da"}. Compare the unsorted sequences {"da", "ba"} and {"ba", "da"} to determine that "bada" comes before "daba".
You are given a vector <string> words. Sort the words using the method above and return the resulting vector <string>.
Constraints - words will contain between 1 and 50 elements, inclusive. - Each element of words will contain between 2 and 50 characters, inclusive. - Each element of words will contain only lowercase letters ('a'-'z'). - The first character of each element of words will be a consonant. - The last character of each element of words will be a vowel. Examples 0)
{"xiaoxiao", "yamagawa", "gawayama"} Returns: {"gawayama", "yamagawa", "xiaoxiao" } After decomposing the words into sequences of syllables, we get the following unsorted and sorted sequences of syllables: WORD | UNSORTED SEQUENCES | SORTED SEQUENCES -----------+--------------------------+-------------------------- "xiaoxiao" | {"xiao", "xiao"} | {"xiao", "xiao"} "yamagawa" | {"ya", "ma", "ga", "wa"} | {"ga", "ma", "ya", "wa"} "gawayama" | {"ga", "wa", "ya", "ma"} | {"ga", "ma", "ya", "wa"} To compare "xiaoxiao" with the other two words, we use the sorted sequences of syllables. However, to compare "yamagawa" with "gawayama" we have to use the unsorted sequences because the sorted ones are equal. 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.
단어들이 들어오고.. 모음을 제외하고 재나열하여 정렬하기..
쉬운문제였는데.. 방심하다 틀렸다.. 조건에따라 정렬했을때 결과가 같으면 원래 소트하기전에 단어 마디를 비교했어야했는데 원래 문자열을 그냥 비교했다.. (그렇게하면 모든경우를 커버할줄 알았다.. 왜그랬지.. -_-) 흠.. 대충대충하는습관을 고쳐야겠다..
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 #include <string> 6 using namespace std; 7 8 typedef struct _s { 9 string ori; 10 vector<string> o; 11 vector<string> syl; 12 } DATA; 13 14 DATA data[1000]; 15 16 bool comp(const DATA& x, const DATA& y) 17 { 18 int i, k; 19 char str1[100], str2[100]; 20 for (i = 0; i < x.syl.size(); i++) { 21 if (y.syl.size() <= i) { 22 return false; 23 } 24 strcpy(str1, x.syl[i].c_str()); 25 strcpy(str2, y.syl[i].c_str()); 26 27 k = strcmp(str1, str2); 28 if (k == 0) 29 continue; 30 if (k < 0) 31 return true; 32 return false; 33 } 34 35 for (i = 0; i < x.o.size(); i++) { 36 if (y.o.size() <= i) { 37 return false; 38 } 39 strcpy(str1, x.o[i].c_str()); 40 strcpy(str2, y.o[i].c_str()); 41 42 k = strcmp(str1, str2); 43 if (k == 0) 44 continue; 45 if (k < 0) 46 return true; 47 return false; 48 } 49 strcpy(str1, x.ori.c_str()); 50 strcpy(str2, y.ori.c_str()); 51 k = strcmp(str1, str2); 52 if (k < 0) 53 return true; 54 return false; 55 } 56 57 int is_vow(char ch) 58 { 59 if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') 60 return 1; 61 return 0; 62 } 63 64 class SyllableSorting { 65 public: 66 67 vector <string> sortWords(vector <string> words) 68 { 69 int i, j, k; 70 int n, len; 71 char buf[1000]; 72 char w[1000]; 73 vector<string> res; 74 75 n = words.size(); 76 for (i = 0; i < n; i++) { 77 data[i].ori = words[i]; 78 79 strcpy(buf, words[i].c_str()); 80 len = strlen(buf); 81 82 j = k = 0; 83 84 while (j < len) { 85 while (!is_vow(buf[j]) && j < len) { 86 w[k++] = buf[j]; 87 j++; 88 } 89 while (is_vow(buf[j]) && j < len) { 90 w[k++] = buf[j]; 91 j++; 92 } 93 94 w[k] = 0; 95 k = 0; 96 //printf("w = %s\n", w); 97 data[i].syl.push_back(w); 98 data[i].o.push_back(w); 99 sort(data[i].syl.begin(), data[i].syl.end()); 100 } 101 102 } 103 104 sort(data, data+n, comp); 105 for (i = 0; i < n; i++) { 106 res.push_back(data[i].ori); 107 } 108 return res; 109 } 110 111 112 };
[1000] PlayerExtraction
Problem Statement
Three weeks ago, MyOwnBusiness Inc. received an urgent call from the IIHF (International Ice Hockey Federation) requesting a system to raise an alarm to the referee when there are too many players from the same team inside the rink. The system will be composed of three parts: A digital camera in the ceiling to take photos of the rink every second. A software module to extract the position of each player from the photo taken by the digital camera. A software module to count the number of players from the same team inside the hockey rink. The team has just finished the module to count the number of players inside the hockey rink, so now it is time to implement the module to extract the players' positions from the photo taken by the digital camera.
The photo taken by the camera is given as a vector <string>, where the x-th character of the y-th element is the color of the 2 x 2 square whose lower-left corner is at (2*x, 2*y). Colors are either uppercase letters ('A'-'Z') or digits ('0'-'9'). Uppercase letters represent terrain features (floor, chairs, spectators, etc.) and each digit X represents the color of the uniform used by the X-th team.
Two squares A and B belong to the same object if and only if there exists a chain of squares where the first square is A, the last square is B, each pair of consecutive squares in the chain shares a common edge and all the squares in the chain have the same color. The position of an object C is the center of its bounding box, where its bounding box is defined as the smallest axis-aligned box that contains all the object's squares. An object's area is defined as the sum of the areas of all the squares that compose the object. An object is a player from the i-th team if and only if it is colored with the digit i and its area is at least threshold.
Return a vector <string> containing all the players in the photo from the k-th team. Each element should represent a single player and be formatted "X Y" (quotes for clarity), where (X, Y) is the center of the player's bounding box, and X and Y have no extra leading zeroes. Sort the players in increasing order by x-coordinate. Sort players with the same x-coordinate in increasing order by y-coordinate.
Definition
Class: PlayerExtraction Method: extractPlayers Parameters: vector <string>, int, int Returns: vector <string> Method signature: vector <string> extractPlayers(vector <string> photo, int k, int threshold) (be sure your method is public)
Constraints - photo will contain between 1 and 50 elements, inclusive. - Each element of photo will contain between 1 and 50 elements, inclusive. - Each element of photo will contain the same number of characters. - Each element of photo will contain only uppercase letters ('A'-'Z') and digits ('0'-'9'). - k will be between 0 and 9, inclusive. - threshold will be between 1 and 10000, inclusive. Examples 0)
{"33JUBU33", "3U3O4433", "O33P44NB", "PO3NSDP3", "VNDSD333", "OIVNFD33"} 3 16 Returns: {"4 5", "13 9", "14 2" } There are four groups of adjacent pixels with color '3'. However, the first one is too small to be considered (its area is 12, which is smaller than the threshold). 1)
{"6VS", "D66"} 6 1 Returns: {"1 1", "4 3" } There are two players from the 6-th team in the image. Remember that diagonal pixels are not considered adjacent. 2)
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.
