



[250]
Problem Statement You are a knight of the Integerland. You are located at (0, 0) and you want to go to (x, y). You move in a way that is similar to a chess knight. You can be described by a int d. In each step, you may move to any point such that both its coordinates are integers, and its Euclidean distance from your current point is precisely sqrt(d). You are given the ints d, x, and y. Return "YES" if you can arrive at (x, y) in a finite number of moves, and "NO" otherwise. Definition Class: KnightOfIntegerland Method: able Parameters: int, int, int Returns: String Method signature: String able(int d, int x, int y) (be sure your method is public)
Notes  In the problem statement, sqrt(d) denotes the square root of d.  The Euclidean distance between two points (x1, y1) and (x2, y2) is equal to sqrt((x1x2)^2 + (y1y2)^2).  There is no limit on the coordinates of points visited during your journey. In particular, they are allowed to be outside of the rectangle with corners (0, 0) and (x, y). Constraints  d will be between 1 and 1,000,000,000, inclusive.  x will be between 1,000,000,000 and 1,000,000,000, inclusive.  y will be between 1,000,000,000 and 1,000,000,000, inclusive. Examples 0)
25 1 0 Returns: "YES" The distance covered by each of your steps must be sqrt(25)=5. You can reach (1, 0) in this way: (0, 0) > (3, 4) > (6, 0) > (1, 0). 1)
25 2276 9059 Returns: "YES" From any point (x, y) we can reach (x+1, y) as shown in Example 0. Also, from any point (x, y) we can reach (x, y1) using a similar sequence of moves. Hence, it is possible to get from (0, 0) to (2276,9059) by repeating the first sequence of moves 2276 times and then the second sequence of moves 9059 times. 2)
5 58585858 85858585 Returns: "YES" For d=5 you move like a chess knight. It is well known that the chess knight can reach any cell on an infinite chessboard. 3)
4 47474747 74747474 Returns: "NO" It's easy to see that for any point (x, y) you can reach, x and y must be both even. 4)
169 2 0 Returns: "YES" One of the solutions is: (0, 0) > (13, 0) > (1, 5) > (14, 5) > (2, 0). 5)
3 1 1 Returns: "NO" In this case you can't achieve any integer point other than (0, 0). 6)
3 0 0 Returns: "YES"
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. 

[1000]
Problem Statement NOTE: This problem statement contains subscripts that may not display properly if viewed outside of the applet. Farmer John and Eel Brus are studying string theory at the university. One day John found a very interesting sequence of strings s1, s2, ..., sK and told Brus about it. Brus only remembers the following information: Each string in the sequence consists of lowercase letters only. The sequence starts with A. In other words, s1 = A. The sequence ends with B. In other words, sK = B. For each i between 1 and K1, inclusive, si+1 can be obtained by inserting one lowercase letter to si. For example, if s1 is "tco", valid options for s2 include "qtco", "trco", "tcso", and "tcot", but not "xco", "txoc", or "srm". Return the number of sequences that match Brus's information, modulo 1,000,000,007. Brus's memory is always correct, so it is guaranteed that at least one such sequence exists. Definition Class: StringSequences Method: countSequences Parameters: String, String Returns: int Method signature: int countSequences(String A, String B) (be sure your method is public)
Constraints  A will contain between 1 and 49 characters, inclusive.  Each character in A will be a lowercase letter ('a''z').  B will contain between N+1 and 50 characters, inclusive, where N is the number of characters in A.  Each character in B will be a lowercase letter ('a''z').  There will be at least one sequence that matches Brus's information in the problem statement. Examples 0)
"oxoxox" "foxfoxfox" Returns: 6 The following six sequences match Brus's information: "oxoxox", "foxoxox", "foxfoxox", "foxfoxfox" "oxoxox", "foxoxox", "foxoxfox", "foxfoxfox" "oxoxox", "oxfoxox", "foxfoxox", "foxfoxfox" "oxoxox", "oxfoxox", "oxfoxfox", "foxfoxfox" "oxoxox", "oxoxfox", "foxoxfox", "foxfoxfox" "oxoxox", "oxoxfox", "oxfoxfox", "foxfoxfox" 1)
"aaaaa" "aaaaaaaa" Returns: 1 Only the sequence "aaaaa", "aaaaaa", "aaaaaaa", "aaaaaaaa" matches Brus's information. 2)
"tco" "tcotco" Returns: 18
3)
"a" "alnfrlrealjnsliejsraijneroav" Returns: 135925750
4)
"ppmtmtttppmtmpppmtmtmp" "ppmmmpmtmpttmttptpmttptmtmppmppttpmtpppppmmtmmmptp" Returns: 856841145
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. 

[500]
Problem Statement In this problem, we consider 26 variables A, B, C, ..., Z, each of which represents a (possibly empty) string consisting of lowercase letters. You are given a String[] equations. Each element of equations is formatted as "VAR1 = VAR2 + VAL", where VAR1 and VAR2 will each be an uppercase letter representing a variable, and VAL is a nonempty string consisting of lowercase letters. This equation claims that variable VAR1 is equal to the concatenation of variable VAR2 and string VAL (in this order). If there is no (A, B, C, ..., Z) satisfying all given equations, return 1. Otherwise, return the minimum possible sum of the lengths of A, B, C, ..., Z. Definition Class: StringEquations Method: getMinimum Parameters: String[] Returns: int Method signature: int getMinimum(String[] equations) (be sure your method is public)
Constraints  equations will contain between 1 and 50 elements, inclusive.  Each element of equations will contain between 9 and 50 characters, inclusive.  Each element of equations will be formatted as "VAR1 = VAR2 + VAL", where VAR1 and VAR2 will each be an uppercase letter, and VAL will be a nonempty string consisting of lowercase letters. Examples 0)
{ "B = A + top", "C = B + coder", "C = A + topcoder" } Returns: 11 If we assign B = top, C = topcoder and the empty string to each of the other variables, these three equations are satisfied and the sum of the lengths is minimized. 1)
{ "B = A + coder", "C = B + top", "C = A + topcoder" } Returns: 1 The first two equations imply "C = A + codertop", which contradicts the third one. 2)
{ "A = B + p", "C = A + q", "D = F + r", "E = B + x", "G = A + y", "H = F + z" } Returns: 8
3)
{ "X = X + a" } Returns: 1
4)
{ "Y = X + a", "Y = X + b" } Returns: 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. 
