【topcoder】Single Round Match 652 – Round 1 Div2



第一场只能打div 2 TAT


You are given a string s consisting of lower case letters. We assign the letters ‘a’ to ‘z’ values of 1 to 26, respectively. We will denote the value assigned to the letter X by val[X]. For example, val[‘a’] = 1 and val[‘e’] = 5. We define the value of the string s as follows. For each letter s[i], let k[i] be the number of letters in s that are less than or equal to s[i], including s[i] itself. Then, the value of s is defined to be the sum of k[i] * val[s[i]] for all valid i. Given the string, compute and return the value of the string.

裸模拟T T


Alice and Bob are playing a game called “The Permutation Game”. The game is parameterized with the int N. At the start of the game, Alice chooses a positive integer x, and Bob chooses a permutation of the first N positive integers. Let p be Bob’s permutation. Alice will start at 1, and apply the permutation to this value x times. More formally, let f(1) = p[1], and f(m) = p[f(m-1)] for all m >= 2. Alice’s final value will be f(x). Alice wants to choose the smallest x such that f(x) = 1 for any permutation Bob can provide. Compute and return the value of such x.



     Roger the Robot has been sent to explore a planet. The surface of the planet can be thought of as a two-dimensional plane. You are given two vector <int>s x and y. The planet has N interesting points described by these vector <int>s. The i-th interesting point has coordinates (x[i], y[i]). No three interesting points will be collinear. Roger will choose a permutation of {0,1,…,N-1}, and will visit the points in that order. Roger will travel in a straight line in between points. There are two conditions he must follow: He must never cross his own path (that is, if we look at the line segments formed by the path, no two segments strictly intersect). Due to rather unfortunate oversight, Roger is incapable of making any right turns. This means that for any three consecutive points that he visits, these three points constitute a counter-clockwise orientation. Your job is to find a path that Roger can take. If there is no valid path, return an empty vector <int>. Otherwise, return an vector <int> containing a permutation of 0,…,N-1, representing a valid path that Roger can take.



  • wulala2015年3月11日 下午9:48 回复