저녁 8시에 열린 매치.. 예비군훈련 다녀오고나서 힘든몸을 이끌고 겨우 참여.. 시간대가 좋아서 한국사람이 무려 40명 넘게 참여했다.. 이번 매치가 SRM 404였는데.. 누가 센스있게 저런 메세지를 날리더군.. ㅎㅎㅎ
문제는 뭐.. 그럭저럭 삽질만하다가.. 결국 블챌 하나 성공에 힘입어 rating을 살짝 올렸다.. 드디어 1300 돌파~ 방 9등 전체 414등..
이번 매치는 한국인이 1등했다.. 우아.. 대단.. 얼마나 공부해야 우승을할수있는것인가..;; 그리고.. 천하무적 Petr는 68등으로.. 근래 보기드문 졸전(?)을 펼쳤다..
[250] RevealTriangle
Problem Statement
Suppose there is a triangle of digits like the following: 74932 1325 457 92 1 Each digit, with the exception of those in the top row, is equal to the last digit of the sum of its upper and upper-right neighboring digits. You will be given a vector <string> questionMarkTriangle containing a triangle where only one digit in each row is known and all others are represented by '?'s (see example 0 for clarification). Each element of questionMarkTriangle represents a row of the triangle, and the rows are given from top to bottom. Each element contains exactly one digit ('0'-'9') and the remaining characters are all '?'s. Restore the triangle and return it as a vector <string> without '?'s. Definition
Constraints - questionMarkTriangle will contain between 1 and 50 elements, inclusive. - Element i (0 indexed) of questionMarkTriangle will contain exactly n-i characters, where n is the number of elements in questionMarkTriangle. - Each element of questionMarkTriangle will contain exactly one digit ('0'-'9') and all others characters will be '?'s. Examples 0)
{"4??", "?2", "1"} Returns: {"457", "92", "1" } Let's substitute '?'s with unknown variables: 4ab c2 1 Having done that, we start solving for the variables from the bottom to the top. First, we know that the last digit of (c + 2) is 1. Therefore, c must be 9: 4ab 92 1 Now we know that the last digit of (4 + a) is 9, which means a is 5: 45b 92 1 And, finally, the last digit of (5 + b) is 2, so b is 7. 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.
input으로 숫자로 이루어진 역삼각형이 들어온다.. 아래 숫자는 위에 두 숫자의 합 % 10 이다.. 각 row마다 딱 하나의 숫자만 주어지고 나머지는 '?' 로 주어질때.. 이 '?'를 다 구하는 문제..
그냥 greedy하게 풀리는 문제.. 맨 밑에서부터 '?'를 하나씩 채우면서 올라오면 된다.. 밑에 row가 모두 채워지게되면 현재 row도 모두 채울 수 있는데.. '?' 가 연속으로 나오면 한번에 구할 수 없다.. 나같은 경우 앞에서부터 쭉 읽으면서 채울수 있으면 채우고 못채우면 넘어가고.. 를 다 채워질때까지 반복했다..
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <vector> 5 #include <string> 6 using namespace std; 7 8 class RevealTriangle { 9 public: 10 11 vector <string> calcTriangle(vector <string> questionMarkTriangle) 12 { 13 int i, j, k; 14 int size; 15 char tri[100][100]; 16 vector<string> res; 17 size = questionMarkTriangle.size(); 18 for (i = 0; i < size; i++) { 19 strcpy(tri[i], questionMarkTriangle[i].c_str()); 20 } 21 for (i = size-2; i >= 0; i--) { 22 for (k = 0; k < size; k++) { 23 for (j = 0; j < size-i; j++) { 24 if (tri[i][j] == '?') { 25 if (j > 0 && tri[i][j-1] != '?') { 26 tri[i][j] = (((tri[i+1][j-1]-'0') - (tri[i][j-1]-'0') + 10) % 10) + '0'; 27 } 28 else if (j+1 < size-i && tri[i][j+1] != '?') { 29 tri[i][j] = (((tri[i+1][j]-'0') - (tri[i][j+1]-'0') + 10) % 10) + '0'; 30 } 31 } 32 } 33 } 34 } 35 for (i = 0; i < size; i++) { 36 res.push_back(tri[i]); 37 printf("%s\n", tri[i]); 38 } 39 return res; 40 } 41 42 };
[500] KSubstring
Problem Statement
You are given numbers A0, X, Y, M and n. Generate a list A of length n using the following recursive definition: A[0] = A0 A[i] = (A[i - 1] * X + Y) MOD M (note that A[i - 1] * X + Y may overflow 32-bit integer) Let s(i, k) be a sum of k consecutive elements of the list A starting with the element at position i (0 indexed). More formally, s(i, k) = A[i] + A[i + 1] + ... + A[i + k - 1]. Your task is to find the smallest difference between s(i, k) and s(j, k) (where difference is defined as abs(s(i, k) - s(j, k))) such that i + k <= j. In other words, you must find the smallest difference between two subsequences of the same length that do not overlap. Call this smallest difference val, and return a vector <int> containing exactly two elements. The first element should be k, and the second element should be val. If there are multiple solutions with the same val, return the one among them with the highest k. Definition
Class: KSubstring Method: maxSubstring Parameters: int, int, int, int, int Returns: vector <int> Method signature: vector <int> maxSubstring(int A0, int X, int Y, int M, int n) (be sure your method is public)
Constraints - M will be between 1 and 1,000,000,000, inclusive. - A0 will be between 0 and M-1, inclusive. - X will be between 0 and M-1, inclusive. - Y will be between 0 and M-1, inclusive. - n will be between 2 and 3,000, inclusive. Examples 0)
5 3 4 25 5 Returns: {2, 1 } The elements of the list are {5, 19, 11, 12, 15}. There is no way to find two subsequences that have equal sums and do not overlap, so there is no way to obtain 0 as a difference. |s(0, 2) - s(2, 2)| = 1 and that is the minimal difference. Note that |s(2, 1) - s(3, 1)| is also 1, but we don't choose these subsequences because they have a lower value for k. 1)
8 19 17 2093 12 Returns: {5, 161 } The elements of the list are {8, 169, 1135, 652, 1940, 1296, 1618, 1457, 491, 974, 1779, 330}. The smallest difference is |s(1, 5) - s(7, 5)| = 161. 2)
53 13 9 65535 500 Returns: {244, 0 }
3)
12 34 55 7890 123 Returns: {35, 4 }
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.
임의의 수열이 주어진다.. 이 수열중에서 임의의 연속되면서 겹치지않는 길이가 k인 구간 두개를 고른다.. 각 구간의 합의 차이를 최소화하기.. 답이 여러개이면 k를 최대화..
to be updated..
[950] SoftwareCompanies
Problem Statement
There are several companies on the market, with each company processing some data in order to produce data in a new company-specific format. When a company gets a unit of input data, it produces a unit of new data. Unfortunately, each company can process only some limited amount of data, and each company can accept only some specific data formats. Of course, running each company costs the owner some money. The information about the companies will be given to you in a vector <string> names, a vector <string> process, a vector <int> cost and a vector <int> amount. names[i] is the name of the i-th company. process[i] is a single-space delimited list of companies which can process the data produced by the i-th company. cost[i] is the cost of running the i-th company, and amount[i] is the maximal amount of data that the i-th company can process. Also you will be given two companies - company1 and company2. The company company1 has an infinite amount of unprocessed data in its supply which can be processed. Your goal is to convert as much data as possible to the new format of company2, spending the least amount of money as possible. You are to select the companies you want to run, since only running companies can process the data. Return the names of those companies as a vector <string>, sorted in lexicographical order. If more than one answer is possible, return the lexicographically smallest one. If there is no way company2 can process any data at all, return an empty vector <string>. Definition
Notes - String A is lexicographically smaller than string B if it contains a smaller letter at the first position they differ or if A is a prefix of B. List A is lexicographically smaller than list B if it contains a lexicographically smaller string at the first position they differ or if it is a prefix of list B. Constraints - names will contain between 2 and 12 elements, inclusive. - Each element of names will contain between 1 and 50 lowercase letters ('a'-'z'), inclusive. - All elements of names will be distinct. - amount, cost, process and names will all contain same number of elements. - Each element of process will contain between 0 and 50 characters, inclusive. - Each element of process will contain a single-space separated names of companies without any leading or trailing spaces. - Each element of process will contain no duplicate names. - Each element of process will list only companies presented in names. - Element i of process will not contain the i-th company in names. - Each element of cost will be between 0 and 1000000, inclusive. - Each element of amount will be between 1 and 1000000, inclusive. - company1 and company2 will both be present in names. - company1 and company2 will be distinct. Examples 0)
{"topcoder", "doodle", "nasa", "ninny", "idm", "noname", "kintel"} {"doodle nasa noname", "idm ninny noname", "idm ninny noname", "kintel", "kintel", "", ""} {1, 2, 7, 4, 6, 1, 2} {50, 10, 11, 9, 14, 11, 23} "topcoder" "kintel" Returns: {"doodle", "idm", "kintel", "nasa", "ninny", "topcoder" } topcoder has an unlimited amount of data. We take 21 units of topcoder data, with 10 units going to doodle and 11 to nasa. When doodle processes all 10 units, all 10 units of the output go to idm, and, after being processed by idm, those 10 units continue to kintel. 11 units of data processed by nasa are split between ninny (9 units) and idm (2 units). Both those companies give their output to kintel, which has enough power to process all 21 units of data it gets. Therefore the optimal strategy is to run all the companies except "noname". 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.
