Connection Status:
Competition Arena > Quipu

Quipu

SRM 155 · 2003-07-17 · by vorthys

SRM 155 · 2003-07-17 · by vorthys · String Parsing
Class Name: Quipu
Return Type: int
Method Name: readKnots
Arg Types: (string)
Problem Statement

Problem Statement

The Incas used a sophisticated system of record keeping consisting of bundles of knotted cords. Such a bundle of cords is called a quipu. Each individual cord represents a single number. Surprisingly, the Incas used a base-10 positional system, just like we do today. Each digit of a number is represented by a cluster of adjacent knots, with spaces between neighboring clusters. The digit is determined by the number of knots in the cluster. For example, the number 243 would be represented by a cord with knots tied in the following pattern 

     -XX-XXXX-XXX-
where each uppercase 'X' represents a knot and each '-' represents an unknotted segment of cord (all quotes for clarity only).

Unlike many ancient civilizations, the Incas were aware of the concept of zero, and used it in their quipus. A zero is represented by a cluster containing no knots. For example, the number 204003 would be represented by a cord with knots tied in the following pattern 

     -XX--XXXX---XXX-
        ^^    ^^^
        ^^    ^^^
        ^^    two zeros between these three segments
        ^^
        one zero between these two segments
Notice how adjacent dashes signal the presence of a zero.

Your task is to translate a single quipu cord into an integer. The cord will be given as a String knots containing only the characters 'X' and '-'. There will be a single '-' between each cluster of 'X's, as well as a leading '-' and a trailing '-'. The first cluster will not be empty.

Constraints

  • knots contains between 3 and 50 characters, inclusive.
  • knots contains only the characters 'X' and '-'. Note that 'X' is uppercase.
  • The first and last characters of knots are '-'s. The second character is 'X'.
  • knots does not contain 10 consecutive 'X's.
  • knots will represent a number between 1 and 1000000, inclusive.
Examples
0)
"-XX-XXXX-XXX-"
Returns: 243

The first example above.

1)
"-XX--XXXX---XXX-"
Returns: 204003

The second example above.

2)
"-X-"
Returns: 1
3)
"-XX-"
Returns: 2
4)
"-XXX-"
Returns: 3

Submissions are judged against all 38 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Quipu with a public method int readKnots(string knots) · 38 test cases · 2 s / 256 MB per case

Submitting as anonymous