Geocaching Coordinates
Time limit1sMemory limit1024 MB
Given a coordinate formula with lowercase letter slots and rules for each variable's allowed values, print every distinct resulting coordinate in lexicographic order.
- Level
Medium5 of 10
- Topics
- Brute force, Combinatorics, Implementation, String
- Solved
- No attempts yet
Problem
In geocaching, the coordinates of a hidden treasure are sometimes given as a formula in which some of the digits have been replaced by letters, for example N58 24.1ab E26 44.3c. Each lowercase Latin letter is a variable that stands for a single number.
Given the formula and the values each variable may take, write a program that prints every coordinate that can be obtained by substituting the variables.
Input
The first line contains the formula. It consists of a latitude and a longitude, each written as a compass letter (N, S, E, W) followed by degrees, minutes, and the fractional part of the minutes, in the format shown in the examples. Lowercase Latin letters in the formula mark variable slots. The formula is at most 25 characters long.
The second line contains the number of variables (). Each of the next lines describes one variable in the form name=list. A variable name is always a single lowercase Latin letter. The list is comma-separated, and each element is either a single value or a range lo..hi. Every value and range endpoint is a one- or two-digit integer, or the name of a previously described variable.
When an element is a variable name, it refers to the value assigned to that variable in the current combination, so a later variable may depend on an earlier one. If the same letter appears several times in the formula, it always takes the same value within one combination. You may assume that no variable's description ever produces duplicate values.
Output
Print every distinct coordinate that can be obtained by substituting the variables with their allowed values. Print the coordinates in ascending lexicographic (dictionary) order, one per line.