목요일 밤 12시에 열린 매치.. 이번에도 꽤 많은 사람이 참여했다.. 거의 1700명이 참여했고.. 한국사람도 40명 넘게 참여했다.. 한국사람중에도 최근에 탑코더를 시작한사람이 많아서.. 생소한 아이디들도 많다.. 흠.. 누가 누군지 모르겠다..
나는 이번에도 div2에서 했는데.. 간신히 두문제 풀고.. 1000점짜리 보다가 문제도 어렵고 너무 피곤해서 도저히 풀 엄두가 나지 않았다.. 결국 노가다문제 두개 풀고 그냥 포기했는데.. 음.. 1000점짜리 해법이 궁금하네..;;
이번에는 챌린지도 하지 못했다.. 250은 틀리는사람이 없을테고.. 500은 코드가 다들 넘 어려워서.. ㅠ_ㅠ 500도 생각보다 많이 맞았다.. 챌 했으면 큰일날뻔했다..
결과는 방 2등 전체 64등.. rating은 68점을 올려서 1196 -_- 아깝게 4점이 모자라서 다음에도 또 div2이다.. 젠장!! div1에서는 그냥 꼴등을 해도 별 부담이 없는데.. 이거 div2가 훨 부담스럽네..
Level1 - ReversedSum
Problem Statement
For a given positive integer X we can obtain the reversed positive integer Rev(X) by reversing the order of X's digits and removing leading zeroes. For example, if X = 123 then Rev(X) = 321; and if X = 100, then Rev(X) = 1.
You will be given two positive integers x and y. Return their reversed sum, which is defined as Rev(Rev(x) + Rev(y)).
Definition
Class:
ReversedSum
Method:
getReversedSum
Parameters:
int, int
Returns:
int
Method signature:
int getReversedSum(int x, int y)
(be sure your method is public)
Constraints
-
x and y will each be between 1 and 1000, inclusive.
Examples
0)
123
100
Returns: 223
As mentioned in the problem statement, Rev(123) = 321 and Rev(100) = 1. So, the reversed sum is equal to Rev(322) = 223.
1)
111
111
Returns: 222
2)
5
5
Returns: 1
3)
1000
1
Returns: 2
4)
456
789
Returns: 1461
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.
Rev()는 숫자를 거꾸로 뒤집은 연산이다.. (leading zero는 취급 X) 즉, Rev(321) = 123, Rev(100) = 1 이 된다.. input으로 x, y가 주어질때, Rev(Rev(x) + Rev(y)) 구하기
매우 쉬운문제.. 모처럼 240을 넘겼지만.. 그래도 순위에서 한참 밀렸다.. -_-
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7
8 int rev(char* buf)
9 {
10 int len;
11 int i, j;
12 char temp[100];
13 len = strlen(buf);
14 for (i = 0, j = len-1; i < len; i++, j--) {
15 temp[i] = buf[j];
16 }
17 temp[i] = 0;
18 return atoi(temp);
19 }
20
21 class ReversedSum {
22 public:
23
24 int getReversedSum(int x, int y)
25 {
26 int a, b;
27 char buf[100], buf2[100];
28 sprintf(buf, "%d", x);
29 sprintf(buf2, "%d", y);
30 a = rev(buf);
31 b = rev(buf2);
32 printf("a = %d, b = %d\n", a, b);
33 sprintf(buf, "%d", a+b);
34 return rev(buf);
35 }
36
37 };
Level2 - TemplateMatching
Problem Statement
In this problem you will be given a string text and you will need to find the substring of the text that matches a given template in the best way. The template will be represented by two strings: prefix and suffix. Consider a string S. The prefix match score of S with respect to a given template is the maximal n >= 0 such that the first n characters of S are equal to the last n characters of prefix and occur in the same exact order. Analogously, the suffix match score of S is the maximal m >= 0 such that the last m characters of S are equal to the first m characters of suffix and occur in the same exact order.
For example, if S = "something", prefix = "awesome", and suffix = "ingenious", than the prefix score of S is 4 (the matched characters are "some") and the suffix score is 3 (the matched characters are "ing").
The match score of a string S with respect to a given template is the sum of its prefix and suffix match scores. Find the non-empty substring of text with the maximal match score according to the template (prefix, suffix). In case of a tie, return the substring with the maximal prefix score. If there are still several candidates, return one that comes first lexicographically.
Definition
Notes
-
String A comes before string B lexicographically if A is a proper prefix of B, or if A has a smaller character at the first position where the strings differ. When comparing the characters, refer to the following list of characters in ascending order: ' ', 'a', 'b', ..., 'z'.
Constraints
-
text will contain between 1 and 50 characters, inclusive.
-
prefix will contain between 1 and 50 characters, inclusive.
-
suffix will contain between 1 and 50 characters, inclusive.
-
text, prefix and suffix will contain only lowercase letters ('a'-'z') and spaces (' ').
Examples
0)
"something"
"awesome"
"ingenious"
Returns: "something"
The example from the problem statement.
1)
"havka"
"eto"
"papstvo"
Returns: "a"
The return value must be non-empty string, so the correct answer is "a".
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.
input으로 text, prefix, suffix가 주어질때, text의 substring 중에서 앞에 prefix를 중첩시키고, 뒤에 suffix를 중첩시킬때 (당근 같은 letter여야만 중첩이 됨).. 그 중첩된 크기가 score이다. 이 score를 최대화하는 text의 substring 구하기.. 답이 여러개면 prefix가 많이 중첩되는거.. 그것도 여러개면 lexy-smallest를 구한다.
주어진 text에 대해 모든 substring을 다 구하고 각각에 대해 score를 구했다.. 단순 노가다 문제..
음.. 소스가 무지 복잡하군.. ㅠ_ㅠ
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 using namespace std;
7
8 char pre[100], suf[100], t[100];
9 int len, len1, len2;
10
11 void get_sub(int u, int l, char* sub)
12 {
13 int i, j;
14 for (i = 0, j = u; i < l; i++, j++) {
15 sub[i] = t[j];
16 }
17 sub[i] = 0;
18 }
19
20 int get_score1(char* sub, int len3)
21 {
22 char temp[100];
23 int i, j, k;
24 int max1, len4;
25 max1 = 0;
26 for (i = 0; i < len1; i++) {
27 strcpy(temp, &pre[i]);
28 if (strlen(temp) > len3)
29 continue;
30 len4 = strlen(temp);
31 for (j = 0, k = 0; j < len4; j++, k++) {
32 if (temp[j] != sub[k])
33 break;
34 }
35 if (j == len4 && max1 < len4) {
36 max1 = len4;
37 }
38 }
39 return max1;
40 }
41
42 int get_score2(char* sub, int len3)
43 {
44 char temp[100];
45 int i, j, k;
46 int max1, len4;
47 max1 = 0;
48 for (i = 0; i < len3; i++) {
49 strcpy(temp, &sub[i]);
50 len4 = strlen(temp);
51 if (len4 > len2)
52 continue;
53 for (j = 0, k = 0; j < len4; j++, k++) {
54 if (temp[j] != suf[k])
55 break;
56 }
57 if (j == len4 && max1 < len4) {
58 max1 = len4;
59 }
60 }
61 return max1;
62 }
63
64 class TemplateMatching {
65 public:
66
67 string bestMatch(string text, string prefix, string suffix)
68 {
69 char sub[100];
70 int a, b;
71 int i, j;
72 int max1, idx1, idx2;
73 char res[100];
74 strcpy(pre, prefix.c_str());
75 strcpy(suf, suffix.c_str());
76 strcpy(t, text.c_str());
77 len = strlen(t);
78 len1 = strlen(pre);
79 len2 = strlen(suf);
80 res[0] = 0;
81 max1 = -1;
82 idx1 = idx2 = -1;
83 for (i = 1; i <= len; i++) {
84 for (j = 0; j+i-1 < len; j++) {
85 get_sub(j, i, sub);
86 a = get_score1(sub, i);
87 b = get_score2(sub, i);
88 //printf("sub = %s, a = %d, b = %d\n", sub, a, b);
89 if (max1 < a+b) {
90 max1 = a+b;
91 idx1 = a;
92 idx2 = b;
93 strcpy(res, sub);
94 }
95 else if (max1 == a+b) {
96 if (idx1 < a) {
97 strcpy(res, sub);
98 idx1 = a;
99 idx2 = b;
100 }
101 else if (idx1 == a) {
102 if (strcmp(sub, res) < 0) {
103 strcpy(res, sub);
104 }
105 }
106 }
107 }
108 //printf("max1 = %d ----- sub = %s\n", max1, res);
109 }
110 printf("res = %s\n", res);
111 string ret = res;
112 return ret;
113 }
114
115 };
Level3 - TripleJump
Problem Statement
The triple jump works as follows. The athlete runs down a runway until he reaches a designated mark. He then makes three consecutive jumps and lands in a sand-filled box. The length of the triple jump is the sum of the lengths of the three consecutive jumps. The winner of the competition is the athlete with the longest triple jump.
You are taking part in the competition and jumping after all your opponents. Since you are the last to jump, you already know all your opponents' results. They are given in the vector <int> opponents, where opponents[i] is the length of the i-th opponent's triple jump in centimeters.
You have already made the first of your three jumps, and it was first centimeters long. You ask yourself a question: "What is the probability that I will take first place? Second place? And all the other places?". You know that each of your two remaining jumps will be between lower and upper centimeters, inclusive, in length. The lengths will not necessarily be integers, and all possible lengths between lower and upper will be equally likely. Return a vector <double> containing exactly N + 1 elements (N is the number of opponents you have) such that the i-th element (0-indexed) is the probability of you taking (i+1)-th place. Note that your place number is equal to one plus the number of opponents who had longer triple jumps than you.
Definition
Class:
TripleJump
Method:
getProbabilities
Parameters:
int, int, int, vector <int>
Returns:
vector <double>
Method signature:
vector <double> getProbabilities(int lower, int upper, int first, vector <int> opponents)
(be sure your method is public)
Notes
-
Each element of your return value must have an absolute or relative error less than 1e-9.
Constraints
-
lower will be between 1 and 1000, inclusive.
-
upper will be between lower and 1000, inclusive.
-
first will be between lower and upper, inclusive.
-
opponents will contain between 1 and 50 elements, inclusive.
-
Each element of opponents will be between 1 and 3000, inclusive.
Examples
0)
1
2
1
{1,2,3,4}
Returns: {0.5, 0.5, 0.0, 0.0, 0.0 }
Your first jump has length 1, and the two subsequent jumps - any lengths between 1 and 2. So your triple jump will have a total length between 3 and 5. This guarantees you at least the second place with an equal chance of getting the first one.
1)
3
7
5
{9,9,19,19,19}
Returns: {0.0, 0.0, 0.0, 1.0, 0.0, 0.0 }
Now the length of your triple jump will be between 11 and 19, and thus you are inevitably fourth. Note that the probability to have a triple jump with length exactly 19 in this case is zero.
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.
