JOIN
Get Time
forums   
Search | Watch Thread  |  My Post History  |  My Watches  |  User Settings
View: Flat (newest first)  | Threaded  | Tree
Previous Thread  |  Next Thread
Wildcard problems | Reply
[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((x1-x2)^2 + (y1-y2)^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, y-1) 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.
Re: Wildcard problems (response to post by [[rng_58]]) | Reply
[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 K-1, 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.
Re: Wildcard problems (response to post by [[rng_58]]) | Reply
[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 non-empty 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 non-empty 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.
RSS