250점은 좀 쉬운 문제가 나왔는데.. 아쉽게도 심한 삽질을 하고 말았다.. 한잠 후에 오류를 발견하고 resubmit.. ㅠ_ㅠ;; 그래도 resubmit해서 pass했으니 다행인건가.. 그래도 챌 하나 성공시켰다는데 상당히 만족한다.. 더군다나 이번에는 블챌도 아니었으니.. 500점짜리도 무려 30줄 짜리 테스트케이스를 만들었는데.. 결국 시도해보지는 못했다.. 잽싸게 한명 잡고 테스트케이스 한줄 입력하고있을때 이미 딴사람이 챌 해버렸다.. -_-;; 허무하군.. 의외로 많이 fail했는데.. 나머지한테도 시도해볼껄 그랬나.. red도 fail일줄은 몰랐네..
rating은 이번에도 소폭 상승..!! 세번 연속 올랐다.. 이것도 의왼데.. -_-; 방 16등이라서 rating 좀 떨어질 줄 알았는데.. 전체 700명중에 410등이면 비교적 선전한 모양이다.. 실력은 감퇴하고있는데.. rating은 오히려 오르고있으니.. 이거 왠지 불안해진다.. ㄷㄷㄷ
그건 그렇고.. 밀린 후기들.. 언제 다쓰지..?
방 16등 전체 410등
Level1 - RelativePath
Problem Statement
In a typical filesystem, there are files, representing complete units of data. These files are contained in directories, and these directories, in turn, may be contained in other directories, and so on. A path is a pointer to a specific file or directory in this stucture. Most Unix-like OSes have a single root directory, that has all other directories and files directly or indirectly (via other directories) inside it. Such OSes use the following structure for file paths: /<directory-name>/<directory-name>/.../<directory-name>/<file-name> and, correspondingly, the following structure for directory paths: /<directory-name>/<directory-name>/.../<directory-name> For example, "/etc/passwd" (all quotes here and below are for clarity only) points to a file named "passwd" inside a directory named "etc" inside the root directory. Other valid file names might be "/home/user/pictures/me" or just "/file". In this problem, we allow only nonempty sequences of lowercase letters ('a'-'z') as file and directory names. A special case is the root directory itself, which is referred to as just "/". When a user works with such an OS, one of the directories is chosen as 'current'. Such a designation allows her to refer to the files in that directory without specifying the full path to the current directory. For example, if the current directory is "/home/user/pictures", then one might refer to the file "/home/user/pictures/me" as just "me" (note that such a short form can be easily spotted by the absence of the starting '/' character). Moreover, the files in subdirectories of the current directory can also be referred to in a short manner: "/home/user/pictures/others/she" can be referred to as "others/she". And even more exciting is the ability to have short references for files outside the current folder. More specifically, ".." means "the directory one level above the current directory", "../.." means "the directory two levels above the current directory", and so on. For example, if the current directory is "/home/user/pictures", and you want to refer to "/home/top/data/file", you can express that as "../../top/data/file". Given a string path, indicating the complete path to the file that needs to be referred to, and a string currentDir, indicating the current directory, return a String that contains the relative path to that file according to the above rules. You should choose the shortest of all possible relative paths (for example, if the current directory is "/home/user/pictures", you should use "../movies/title" and not "../../user/movies/title" as a pointer to "/home/user/movies/title"). Some files and/or directories may have coinciding names, but it is impossible to have two files or two directories or a file and a directory with the same name inside the same directory, so file and directory paths are not ambiguous. It is guaranteed that the given data describes a valid file and directory according to the above rules. In particular, they will not contradict - for example, path="/home/user/some" and currentDir="/home/user/some/other" are a contradiction, since it implies that a file and a directory both named "some" exist inside the directory "/home/user". Definition
Notes - A file name never ends with the '/' character. A directory name never ends with the '/' character, with the exception of the root directory, which is specified as just "/". Constraints - path and currentDir will each contain between 1 and 50 characters, inclusive. - Each character of path and currentDir will be '/', or a lowercase letter ('a'-'z'). - path will contain a valid file path according to the above rules. - currentDir will contain a valid directory path according to the above rules. - path and currentDir will not contradict (see the last paragraph of the statement). Examples 0)
"/home/top/data/file" "/home/user/pictures" Returns: "../../top/data/file" The example from the problem statement. 1)
"/home/user/movies/title" "/home/user/pictures" Returns: "../movies/title" And another one from the statement. 2)
"/file" "/" Returns: "file" Remember about the root directory. 3)
"/a/b/a/b/a/b" "/a/b/a/a/b/a/b" Returns: "../../../../b/a/b" Some file and directory names may be the same. 4)
"/root/root/root" "/root" Returns: "root/root" Some files and/or directories can be named "root" - but that doesn't make them root directories. 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.
유닉스에서 두개의 절대경로가 주어진다.. 두번째 디렉토리에서 첫번째 디렉토리로 가기위한 상대경로 구하기..
음.. 문제가 열라 길었는데.. 이거 다 읽을필요도없는데.. 괜히 힘들게 다읽었다.. ㅠ_ㅠ 샘플만 봐도 파악할수있는 문제였는데..;;
아무리 level1 문제이지만.. 생각보다 쉬운문제가 나왔다.. 그냥 직관적으로 앞에서부터 쭉 읽으면서 서로 다른 디렉토리가 나올때까지 읽는다.. 그리고나서 두번째 경로를 그 지점까지 위치하기위해서 "../" 를 수행하고.. 그 지점부터 첫번째 경로의 남은 부분을 들어가면 된다..
음.. 나는 결과가 ".." 로 끝날경우 "/"를 반드시 붙여줘야된다고 생각했다.. (왜그랬지.. -_-) 나중에 잘못생각한것을 알고 리서밋.. 덕분에 점수가 와장창 날라갔다.. ㅠ_ㅠ
그래도 챌 하나 성공시킨것은 고무적이다.. 블챌이 아닌 코드분석후 챌 성공은 참 오랜만인것 같다.. 타겟도 못찾은 버그를 내가 찾다니..
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 #include <string> 6 using namespace std; 7 8 class RelativePath { 9 public: 10 11 string makeRelative(string path, string currentDir) 12 { 13 int n, m; 14 int i, j, k; 15 char path1[100][100], path2[100][100], buf[100]; 16 char res[100][100]; 17 char* ptr; 18 string ret; 19 n = m = 0; 20 strcpy(buf, path.c_str()); 21 ptr = strtok(buf, "/ "); 22 while (ptr != NULL) { 23 strcpy(path1[n], ptr); 24 n++; 25 ptr = strtok(NULL, "/ "); 26 } 27 strcpy(buf, currentDir.c_str()); 28 ptr = strtok(buf, "/ "); 29 while (ptr != NULL) { 30 strcpy(path2[m], ptr); 31 m++; 32 ptr = strtok(NULL, "/ "); 33 } 34 i = 0; 35 while (1) { 36 if (i < n && i < m) { 37 if (strcmp(path1[i], path2[i]) != 0) 38 break; 39 } 40 else 41 break; 42 i++; 43 } 44 if (i == n && i == m) 45 return ""; 46 k = 0; 47 for (j = m-1; j >= i; j--) { 48 strcpy(res[k], ".."); 49 k++; 50 } 51 for (j = i; j < n; j++) { 52 strcpy(res[k], path1[j]); 53 k++; 54 } 55 ret = res[0]; 56 for (i = 1; i < k; i++) { 57 ret += "/"; 58 ret += res[i]; 59 } 60 printf("ret = %s\n", ret.c_str()); 61 return ret; 62 } 63 };
Level2 - AllCycleLengths
Problem Statement
There are several cities in a country, and some pairs of those cities are connected by one-way roads (although it is possible that there are one-way roads both from A to B and from B to A). It is possible to get from any city to any other city using roads. A traveler starts from some city, and travels along one of the roads every day. A number x is called vacation-friendly if a traveler can have an x-day long vacation. That means he can start from some city, travel exactly x roads, and be back at the city where he started. A vacation string is an infinite string of '0' and '1' digits, which has a '1' in the x-th (1-based) position if and only if x is a vacation-friendly number.
For example, consider the country shown in the following picture. Its vacation string is "0011011111111...": 0->1->3->0 is a 3-day vacation, 0->1->2->3->0 is a 4-day vacation, 0->1->3->0->1->3->0 is a 6-day vacation, 0->1->2->3->0->1->3->0 is a 7-day vacation, and so on. It turns out that every vacation string becomes periodic at some point. We will enclose the period in parentheses to obtain a finite representation for a vacation string. For example, the above vacation string can be represented by "00110(1)" or "00110111(11)". We will call the shortest possible representation canonical. Given a description of a country as a vector <string> arcs, where the j-th character of the i-th element of arcs is 'Y' if there is a road from city i to city j, and 'N' otherwise, return the canonical representation of its vacation string. Definition
Constraints - arcs will contain between 2 and 30 elements, inclusive. - Each element of arcs will contain exactly n characters, where n is the number of elements in arcs. - Each character of each element of arcs will be either 'Y' or 'N'. - The i-th character of the i-th element of arcs will always be 'N'. - arcs will define a network of roads where it is possible to get from any city to any other city using the roads. Examples 0)
{"NYNN", "NNYY", "NNNY", "YNNN"} Returns: "00110(1)" The example from the problem statement. 1)
{"NY", "YN"} Returns: "(01)" Only even numbers are vacation-friendly here. 2)
{"NYYYY", "NNYYY", "NNNYY", "NNNNY", "YNNNN"} Returns: "0(1)" Every vacation length except 1 is possible here. 3)
{"NYNNN", "NNYNN", "NNNYN", "NNNNY", "YNNYN"} Returns: "010(1)" The vacation can start from any vertex. 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 - ReasonableOdds
Problem Statement
When it's impossible to determine a winner after normal soccer play between two teams, a penalty shoot-out is used. During a penalty shoot-out, each of the teams takes k shots (each of those can either result in scoring a goal or not), and the team who scores the most goals is declared the winner. If both teams score an equal number of goals, we will assume in this problem that the game ends in a draw. We will also assume that for each team there exists a number between 0 and 1, inclusive, denoting the skill level of that team, such that each penalty shot taken by that team results in a goal with probability equal to that number. You can assume that all shots are independent. Your friend, an eager sports better, tells you that he knows that team 1 will win with probability p1%, team 2 will win with probability p2%, and the probability of a draw is pDraw%. You need to check if such a probability distribution is possible. In other words, can there exist two teams with valid skill levels such that those three outcomes would happen with the given probabilities? Given ints p1, pDraw, p2 and k, return "YES" if such a distribution is possible, and "NO" otherwise (quotes for clarity only). Definition
Class: ReasonableOdds Method: check Parameters: int, int, int, int Returns: string Method signature: string check(int p1, int pDraw, int p2, int k) (be sure your method is public)
Constraints - p1, pDraw and p2 will be between 0 and 100, inclusive. - p1, pDraw and p2 will sum up to 100. - k will be between 1 and 5, inclusive. Examples 0)
0 100 0 1 Returns: "YES" When both teams have a skill level of 0, a draw is unavoidable. 1)
50 0 50 1 Returns: "NO" When both teams can win, a draw is also a possibility. 2)
30 0 70 5 Returns: "NO"
3)
30 10 60 2 Returns: "NO" Moreover, a draw is a significant possibility. 4)
30 40 30 2 Returns: "YES"
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.
