지난주 목요일 8시에 열렸던 매치.. 오랜만에 Div2에서 참여했다..
그런데 이번에도 역시 실망스런 결과.. ㅠ_ㅠ
그냥 두문제를 가볍게 풀었는데.. system test에서 fail했다..
젠장!! 거의 맞다고 생각했는데.. 뭐가 틀린것이지..
그래도 div2라서 raiting을 어느정도 유지했지 이번에 div1에서 했으면 완전 폭락할뻔했다..;;
그래도 오랜만에 챌 하나 성공했다.. 이것도 div2라서 가능한듯..
raiting은 눈꼽만큼 올랐는데.. 덕분에 다음에도 또 div2 다..;;
Level1 - MostCommonLetters
Problem Statement
It is commonly known that in a typical English text, some letters occur more frequently than others. For example, in a long text, approximately 12.31% of the letters will be 'e'. Your friend from the linguistics department has asked you to help him find the most common letters in a given text.
The text is given to you in the vector <string> text. Return the letter that occurs most frequently in text. If there are multiple letters that occur most frequently, return all of them in alphabetical order. See examples for further clarification.
Definition
Constraints
-
text will contain between 1 and 50 elements, inclusive.
-
Each element of text will contain between 0 and 50 characters, inclusive.
-
Each character of text will be either a space (' ') or a lowercase letter ('a' - 'z').
-
text will contain at least one letter.
Examples
0)
{"abc a"}
Returns: "a"
The letter 'a' is the most common letter here. It appears twice, while all other letters appear only once.
1)
{"abc", "ab"}
Returns: "ab"
Now letters 'a' and 'b' are most common: they appear twice, more than letter 'c' does.
2)
{"qwerty", "abc", "qwe", "a"}
Returns: "aeqw"
Don't forget to return letters in alphabetical order.
3)
{"english is a west germanic language originating",
"in england and is the first language for most",
"people in the united kingdom the united",
"states canada australia new zealand ireland",
"and the anglophone caribbean it is used",
"extensively as a second language and as an",
"official language throughout the world",
"especially in commonwealth countries and in",
"many international organizations"}
Returns: "a"
This is a short extract from wikipedia about the English language. All punctuations are omitted. This text is too short, so the letter 'e' is not the most common one. There are 41 occurrences of the letter 'a', 39 occurrences of 'n' and only 33 occurrences of 'e'.
4)
{"amanda forsaken bloomer meditated gauging knolls",
"betas neurons integrative expender commonalities",
"latins antidotes crutched bandwidths begetting",
"prompting dog association athenians christian ires",
"pompousness percolating figured bagatelles bursted",
"ninth boyfriends longingly muddlers prudence puns",
"groove deliberators charter collectively yorks",
"daringly antithesis inaptness aerosol carolinas",
"payoffs chumps chirps gentler inexpressive morales"}
Returns: "e"
Random words.
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.
문자열이 마구 주어지고, 가장 많이 나온 letter를 오름차순으로 출력하기
그냥 text를 쭉 읽으면서 나오는 letter들의 count를 1씩 증가시켰다.. 가장 많이 나오는 letter를 출력했다..
사실 이런 문제에서 시간을 낭비하면 안되는데.. 이정도 문제에 224점이면 케 안습이다.. 흠.. 요즘들어 코딩 속도가 안나온다.. 나이를 먹어서인지 순발력이 계속 떨어진다.. ㅠ_ㅠ
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <set>
7 using namespace std;
8 #define max(x, y) ((x) > (y) ? (x) : (y))
9
10 class MostCommonLetters {
11 public:
12
13 string listMostCommon(vector <string> text)
14 {
15 char buf[100][100];
16 int size, max1, len;
17 int i, j;
18 int ch_cnt[128];
19 string res;
20 size = text.size();
21 for (i = 0; i < size; i++) {
22 strcpy(buf[i], text[i].c_str());
23 }
24 memset(ch_cnt, 0, sizeof(ch_cnt));
25 max1 = 0;
26 for (i = 0; i < size; i++) {
27 len = strlen(buf[i]);
28 for (j = 0; j < len; j++) {
29 if (buf[i][j] == ' ')
30 continue;
31 ch_cnt[buf[i][j]]++;
32 max1 = max(max1, ch_cnt[buf[i][j]]);
33 }
34 }
35 res = "";
36 for (i = 'a'; i <= 'z'; i++) {
37 printf("ch_cnt[%c] = %d\n", i, ch_cnt[i]);
38 if (ch_cnt[i] == max1) {
39 res += (char)i;
40 }
41 }
42 return res;
43 }
44
45 };
Level2 - NextNumber
Problem Statement
The binary weight of a positive integer is the number of 1's in its binary representation. For example, the decimal number 1 has a binary weight of 1, and the decimal number 1717 (which is 11010110101 in binary) has a binary weight of 7.
Given a positive integer N, return the smallest integer greater than N that has the same binary weight as N.
Definition
Class:
NextNumber
Method:
getNextNumber
Parameters:
int
Returns:
int
Method signature:
int getNextNumber(int N)
(be sure your method is public)
Notes
-
The result is guaranteed to fit in a signed 32-bit integer.
Constraints
-
N will be between 1 and 1,000,000,000, inclusive.
Examples
0)
1717
Returns: 1718
Example from the problem statement.
1)
4
Returns: 8
4 is 100 in its binary representation and weighs 1. The next number is 1000(in binary) which represents 8.
2)
7
Returns: 11
The decimal 7 is binary 111, so it has binary weight of 3. The next number with the same binary weight is 11, which is 1011 in binary.
3)
12
Returns: 17
12 in decimal is 1100 in binary. The next number with the same binary weight is 10001 in binary, which is 17.
4)
555555
Returns: 555557
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으로 N이 주어지고, N보다 큰 수 중에서 이진수로 나타냈을 때 1의 개수가, N을 이진수로 나타냈을때의 1의 개수와 같은 가장 작은 수 구하기
이 문제는 N을 2진수 string으로 변환 후 next permutation을 구하면 된다.. 젠장!!
petr나 기타 많은 사람들은 pattern을 찾아서 구했다.. 뒤에서부터 읽어서 "01" pattern을 찾은 후
10으로 바꾸고.. 나머지는 어쩌고 저쩌고.. 나도 비스무리하게 했는데.. 생각을 잘못했다.. ㅠ_ㅠ
1 #include <iostream>
2 #include <cstdio>
3 #include <algorithm>
4 #include <vector>
5 #include <string>
6 #include <set>
7 using namespace std;
8 #define max(x, y) ((x) > (y) ? (x) : (y))
9
10 class NextNumber {
11 public:
12
13 int getNextNumber(int N)
14 {
15 int i, j;
16 int bit_cnt;
17 int bit[40], temp[40];
18 int res;
19 bit_cnt = 0;
20 while (N > 0) {
21 if (N % 2 == 0) {
22 temp[bit_cnt++] = 0;
23 }
24 else {
25 temp[bit_cnt++] = 1;
26 }
27 N /= 2;
28 }
29 temp[bit_cnt++] = 0;
30 for (i = 0, j = bit_cnt-1; i < bit_cnt; i++, j--) {
31 bit[i] = temp[j];
32 }
33 next_permutation(bit, bit+bit_cnt);
34 res = 0;
35 for (i = 0; i < bit_cnt; i++) {
36 res *= 2;
37 res += bit[i];
38 }
39 return res;
40 }
41
42 };
Level3 - DancingCouples
Problem Statement
There are N boys and M girls in a dance school. The teachers are organizing a performance and they need exactly K boy-girl couples for their show. Unfortunately, this is not a straightforward task since some children cannot be paired with each other (due to differences in height, skill, etc.). One of the teachers is a computer science graduate, and has decided to count the number of ways to select K couples.
You are given a vector <string> canDance containing exactly N elements, each with exactly M characters. The j-th character of the i-th element of canDance is 'Y' if boy i can be paired with girl j, and 'N' otherwise. Return the number of distinct valid ways to select exactly K boy-girl pairs.
Definition
Class:
DancingCouples
Method:
countPairs
Parameters:
vector <string>, int
Returns:
int
Method signature:
int countPairs(vector <string> canDance, int K)
(be sure your method is public)
Constraints
-
canDance will contain between 1 and 10 elements, inclusive.
-
Each element of canDance will contain between 1 and 10 characters, inclusive.
-
Each element of canDance will contain the same number of characters.
-
Each character in canDance will be either 'Y' or 'N'.
-
K will be between 1 and 10, inclusive.
Examples
0)
{"YYYY",
"YYYY",
"YYYY"}
3
Returns: 24
There are three boys and four girls. Every boy can dance with every girl. The first boy selects one of the four girls, the second boy selects one of the three remaining girls, and the third boy selects one of the two remaining girls. Thus, there are 4*3*2=24 ways to create three couples.
1)
{"YYNN",
"NYYN",
"NNYY"}
3
Returns: 4
There are 4 possible pairings: {boy1-girl1, boy2-girl2, boy3-girl3}, {boy1-girl1, boy2-girl2, boy3-girl4}, {boy1-girl1, boy2-girl3, boy3-girl4}, {boy1-girl2, boy2-girl3, boy3-girl4}
2)
{"YY",
"YY",
"YY"}
3
Returns: 0
There are 3 boys but only 2 girls, so it is impossible to select 3 pairs.
3)
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.
