저녁 8시에 열린 매치.. 평소에비해 한국사람도 무지 많았다.. 42명 참여.. 그중 중학생도 포함되어있었다..;; 근데 중학생들 실력이.. ㄷㄷㄷ 이제는 중학생들한테도 밀리는구나.. ㅠ_ㅠ
이번 매치는 무지 아쉬웠다.. 나름대로 문제셋이 쉬워서.. 처음으로 500점을 pass할 기회였는데.. 아쉽게도 시간이 모잘랐다.. 정말 1분만 더있었더라도 풀었을텐데.. 500점 pass했으면 난생처음 ACRush도 이겨보는건데 이런 좋은 기회를 놓치다니.. ㅠ_ㅠ;;;;
방 11등 전체 412등
[250] CountExpressions
Problem Statement
You are helping your brother with his homework assignment. His teacher gave him two distinct numbers x and y, and asked him to use those numbers to form as many different expressions as possible. Each expression must satisfy all of the following rules: The only allowed operators are '+', '-' and '*'. x and y must each appear exactly twice. No other numbers are allowed. The result of the expression must be equal to val.
In other words, each expression can be written in the form "a op1 b op2 c op3 d", where each of op1, op2 and op3 is '+', '-' or '*', and among the numbers a, b, c and d, exactly two are equal to x and the other two are equal to y. Please note that the unary minus is not allowed (see example 0). Expressions are calculated from left to right, and there is no operator precedence. For example, to calculate the result of "2 + 2 * 3 + 3", you would first calculate 2 + 2, then multiply the result by 3, and then add 3 to get 15.
Return the total number of different expressions that can be formed. Two expressions are considered different if their string notations (as described in the previous paragraph) are different. For example, the expressions "2 + 3 - 2 - 3", "2 - 2 + 3 - 3" and "2 - 3 - 2 + 3" are all different. Definition
Class: CountExpressions Method: calcExpressions Parameters: int, int, int Returns: int Method signature: int calcExpressions(int x, int y, int val) (be sure your method is public)
Constraints - x and y will each be between -100 and 100, inclusive. - x and y will be different. - val will be between -100000000 and 100000000, inclusive. Examples 0)
7 8 16 Returns: 9 The possible expressions are: 8 + 8 + 7 - 7 8 + 7 + 8 - 7 7 + 8 + 8 - 7 8 + 8 - 7 + 7 8 + 7 - 7 + 8 7 + 8 - 7 + 8 8 - 7 + 8 + 7 8 - 7 + 7 + 8 7 - 7 + 8 + 8 Please note that the unary minus is not allowed, so "-7 + 7 + 8 + 8" is not a valid expression. 1)
100 -100 -100000000 Returns: 0 There are no valid expressions. 5)
1 2 5 Returns: 17
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, y, val 이 주어지고 x 두개, y 두개 씩 사용하고 임의의 연산자 (+, -, *) 를 사용하여 수식을 만들때 수식의 결과가 val 이 되는 경우의 수 구하기..
우선 x, y를 두개씩 배열에 넣고 next_permutation을 이용하여 모든 operand의 sequence를 구한다.. 그리고 backtracking을 통하여 연산자를 대입..
이런 문제는 순식간에 풀어야되는데.. 흠..
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 #include <string> 6 using namespace std; 7 8 int num[10]; 9 char path[10]; 10 int val1, cnt; 11 12 int cal(int x, char ch, int y) 13 { 14 if (ch == '+') 15 return x+y; 16 else if (ch == '-') 17 return x-y; 18 return x*y; 19 } 20 21 void dfs(int u, char ch) 22 { 23 int k; 24 path[u] = ch; 25 if (u == 2) { 26 k = num[0]; 27 k = cal(k, path[0], num[1]); 28 k = cal(k, path[1], num[2]); 29 k = cal(k, path[2], num[3]); 30 if (k == val1) 31 cnt++; 32 return ; 33 } 34 dfs(u+1, '+'); 35 dfs(u+1, '-'); 36 dfs(u+1, '*'); 37 } 38 39 class CountExpressions { 40 public: 41 42 int calcExpressions(int x, int y, int val) 43 { 44 if (x < y) { 45 num[0] = num[1] = x; 46 num[2] = num[3] = y; 47 } 48 else { 49 num[0] = num[1] = y; 50 num[2] = num[3] = x; 51 } 52 val1 = val; 53 cnt = 0; 54 55 do { 56 dfs(0, '+'); 57 dfs(0, '-'); 58 dfs(0, '*'); 59 } while (next_permutation(num, num+4)); 60 printf("cnt = %d\n", cnt); 61 return cnt; 62 } 63 64 };
[500] CountPaths
Problem Statement
There is a rectangular table divided into r rows and c columns, for a total of r * c fields. The rows are numbered 1 to r, from bottom to top, and the columns are numbered 1 to c, from left to right. All coordinates in this problem will be given as (row, column).
You are given vector <int>s fieldrow and fieldcol containing a list of special fields in the table, where (fieldrow[i], fieldcol[i]) are the coordinates of the i-th field. For each number n, where 0 <= n <= the number of elements in fieldrow, you must count the number of different paths from field (1, 1) to field (r, c) that contain exactly n special fields. These paths are called paths of length n.
There are two rules you must follow. First, you are only allowed to make moves that are straight up or to the right. In other words, from each field (row, column), you can only move to field (row+1, column) or field (row, column+1). Second, in each path, all the special fields must appear in the same order that they appear in the input. In other words, if the path contains field a = (fieldrow[idxa], fieldcol[idxa]) and field b = (fieldrow[idxb], fieldcol[idxb]), and a appears before b in the path, then idxa must be less than idxb.
Return a vector <int> containing exactly k+1 elements, where k is the number of elements in fieldrow. The i-th element (0-indexed) must be the number of different paths of length i modulo 1000007. Definition
Constraints - r and c will each be between 1 and 50, inclusive. - fieldrow will contain between 0 and 50 elements, inclusive. - fieldcol and fieldrow will contain same number of elements. - Each element of fieldrow will be between 1 and r, inclusive. - Each element of fieldcol will be between 1 and c, inclusive. - For all i and j, where i < j, the pairs (fieldrow[i], fieldcol[i]) and (fieldrow[j], fieldcol[j]) will be different. Examples 0)
50 50 {50, 1} {50, 1} Returns: {0, 0, 0 } There is no path that passes through (50, 50) before (1, 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.
r by c 의 보드가 주어지고.. n개의 special field의 좌표가 주어진다.. (1, 1)에서 출발하여 (r, c)까지 가는데 0개의 SF를 지날때, 1개의 SF를 지날때, 2개의 SF를 지날때, ..., n개의 SF를 지날때 경우의 수를 각각 구하기.. 단 이동방향은 오른쪽 or 위쪽으로만 갈수있고 i > j 인 경우 i번째 SF를 지난 후 j번째 SF를 지날수 없다.. 즉, 반드시 input에 주어진 순서대로 지나야함..
이 문제는 대략 825 - Walking on the Safe Side 이런 류의 문제이다.. 여기에서 임의의 k개의 SF만 지날 경우와 번호가 높은 SF를 지난 후 번호가 낮은 SF를 지날 수 없다는 제약조건을 잘 생각해주면 된다..
결국 컴파일까지 해놓고 submit을 못했는데.. 그 코드에서 mod 연산만 추가하니 바로 pass해버렸다.. 무척 안타까운 문제. .ㅠ_ㅠ
4차원 DP로 풀었는데.. dp[i][j][k][l] = (i, j) 까지 갈때, k번째 SF까지 고려하여 l개의 SF를 지나는 경우의 수 라고 정의하고.. 대충 이리저리 시도해보니 답이 나왔다.. -_-;
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 #include <string> 6 using namespace std; 7 8 int n; 9 int x[51], y[51]; 10 int dp[51][51][51][51]; 11 12 int find_idx(int u, int v) 13 { 14 int i; 15 for (i = 1; i <= n; i++) { 16 if (x[i] == u && y[i] == v) 17 break; 18 } 19 return i; 20 } 21 22 class CountPaths { 23 public: 24 25 vector <int> difPaths(int r, int c, vector <int> fieldrow, vector <int> fieldcol) 26 { 27 int i, j, k, l, p; 28 vector<int> res; 29 n = fieldrow.size(); 30 memset(dp, 0, sizeof(dp)); 31 for (i = 0; i <= n; i++) { 32 dp[0][1][i][0] = 1; 33 } 34 for (i = 0; i < n; i++) { 35 x[i+1] = fieldrow[i]; 36 y[i+1] = fieldcol[i]; 37 } 38 for (i = 1; i <= r; i++) { 39 for (j = 1; j <= c; j++) { 40 p = find_idx(i, j); 41 if (p == n+1) { 42 for (k = 0; k <= n; k++) { 43 for (l = 0; l <= k; l++) { 44 dp[i][j][k][l] = dp[i-1][j][k][l] + dp[i][j-1][k][l]; 45 dp[i][j][k][l] %= 1000007; 46 } 47 } 48 } 49 else { 50 for (k = p; k <= n; k++) { 51 for (l = 1; l <= p; l++) { 52 dp[i][j][k][l] = dp[i][j-1][p-1][l-1] + dp[i-1][j][p-1][l-1]; 53 dp[i][j][k][l] %= 1000007; 54 } 55 } 56 } 57 } 58 } 59 60 for (i = 0; i <= n; i++) { 61 dp[r][c][n][i] %= 1000007; 62 res.push_back(dp[r][c][n][i]); 63 printf("len %d = %d\n", i, dp[r][c][n][i]); 64 } 65 return res; 66 } 67 68 };
[1000] MyFriends
Problem Statement
There is a group of n kids, numbered 0 through n-1, where n is an odd number. Each kid has some friends within the group, and each kid knows how many friends each of the other kids has. Friendship is symmetric, so if kid 0 is a friend of kid 1, then kid 1 is a friend of kid 0. Each kid i also supports exactly one other kid (i+k) % n, not necessarily a friend.
You ask each kid to answer the following question: Consider each kid in the group except yourself and the kid you support. What is the sum of the number of friends each of them has? For example, if you ask kid 0 this question, and kid 0 supports kid 1, he should tell you (the number of friends kid 2 has) + (the number of friends kid 3 has) + ... + (the number of friends kid n-1 has).
You are given a vector <int> sumFriends, where the i-th element (0-indexed) is the answer given to you by kid i. Some of the kids might not be telling the truth (they are just kids, forgive them). Return "IMPOSSIBLE" if it is impossible for all the given answers to be accurate. Otherwise, return "POSSIBLE" (all quotes for clarity). Definition
Class: MyFriends Method: calcFriends Parameters: vector <int>, int Returns: string Method signature: string calcFriends(vector <int> sumFriends, int k) (be sure your method is public)
Constraints - sumFriends will contain odd number of elements. - sumFriends will contain between 3 and 49 elements, inclusive. - Each element of sumFriends will be between 0 and 9999, inclusive. - k will be between 1 and (number of elements in sumFriends)-1, inclusive. Examples 0)
{8, 9, 8, 8, 9} 2 Returns: "POSSIBLE" We can get such sums only if kid 1 has 2 friends and all other kids have 3 friends. Such a situation is possible. For example: Kid His/her friends 0 1, 3, 4 1 0, 2 2 1, 3, 4 3 0, 2, 4 4 0, 2, 3 1)
{7, 6, 5, 4, 4} 2 Returns: "IMPOSSIBLE"
2)
{5, 6, 5, 4, 4} 1 Returns: "POSSIBLE"
3)
{1, 2, 3} 1 Returns: "IMPOSSIBLE" Here kid 2 supports kid 0, so he tells us the number of friends of kid 1. But it's obviously impossible for kid 1 to have 3 friends. 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.
