TokenGrid
TCO05 Sponsor 4 · 2005-08-16 · by AdminBrett
TCO05 Sponsor 4 · 2005-08-16 · by AdminBrett · Brute Force
Problem Statement
Problem Statement
There is an n by n grid of network nodes. Each node is either standard, or a token consumer. Element i of setup, which corresponds to row i of the grid, will contain a single space delimited list of n values. A consumer will be denoted by an 'X' character. A standard node is denoted by a nonnegative integer with no extra leading zeros, which represents how many tokens it possesses. An unknown will be denoted by a '_' character (there will be exactly 1 unknown).
Suppose a particular standard node is adjacent to d nodes (upward, downward, leftward, or rightward with no wrap-around), and has at least d tokens. Then that node can send 1 token to each adjacent node leaving it with d fewer tokens. For example, a node in the corner with at least 2 tokens could send. Token consumers accept tokens but never send them. finish, which is formatted like setup but with the '_' character replaced by a number, should describe the state of the network after all possible tokens have been sent, and no more can be sent. Return the smallest possible nonnegative value of the unknown, or -1 if no value will work. If finish does not describe a network where tokens cannot be sent (a standard node has too many tokens), also return -1.
Suppose a particular standard node is adjacent to d nodes (upward, downward, leftward, or rightward with no wrap-around), and has at least d tokens. Then that node can send 1 token to each adjacent node leaving it with d fewer tokens. For example, a node in the corner with at least 2 tokens could send. Token consumers accept tokens but never send them. finish, which is formatted like setup but with the '_' character replaced by a number, should describe the state of the network after all possible tokens have been sent, and no more can be sent. Return the smallest possible nonnegative value of the unknown, or -1 if no value will work. If finish does not describe a network where tokens cannot be sent (a standard node has too many tokens), also return -1.
Notes
- The order in which nodes send their tokens is irrelevant.
Constraints
- setup and finish will be formatted as described in the problem statement.
- setup will contain between 2 and 4 elements inclusive.
- setup and finish will agree on the placement of consumer nodes.
- setup and finish will contain the same number of elements.
- Each integer in setup and finish will be between 0 and 50 inclusive.
- setup will contain at least 1 consumer node.
Examples
0)
{"X X",
"X _"}
{"X X",
"X 0"}
Returns: 0
0 works quite easily.
1)
{"X X",
"X _"}
{"X X",
"X 1"}
Returns: 1
2)
{"X X",
"X _"}
{"X X",
"X 2"}
Returns: -1
The lower right node in finish can send its tokens, so we immediately return -1.
3)
{"X 1",
"X _"}
{"X 1",
"X 1"}
Returns: 1
4)
{"X 2",
"X _"}
{"X 1",
"X 0"}
Returns: 1
If the unknown node begins with 1 token, the following sequence of scenarios occurs: X 2 ---> X 0 ---> X 1 X 1 X 2 X 0
47)
{"50 50 50 X",
"X 50 50 50",
"50 50 50 50",
"X 50 50 _"
}
{"1 1 2 X",
"X 1 3 2",
"2 2 2 2",
"X 2 2 1"
}
Returns: 563
Big inputs.
Submissions are judged against all 64 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TokenGrid with a public method int getUnknown(vector<string> setup, vector<string> finish) · 64 test cases · 2 s / 256 MB per case