Connection Status:
Competition Arena > BinaryConway

BinaryConway

SRM 850 · 2023-10-25 · by misof

SRM 850 · 2023-10-25 · by misof · Brute Force, Simulation
Class Name: BinaryConway
Return Type: String
Method Name: say
Arg Types: (string)
Problem Statement

Problem Statement

You may have heard of the "look and say" sequence. It starts as follows: 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, 31131211131221, ...

This sequence starts with 1 and then each term describes the previous term using simple run-length encoding as follows:

  • 1 is "one 1", so we write 11 as the next term
  • 11 is "two 1s", so we write 21 as the next term
  • 21 is "one 2, one 1", so we write 1211 as the next term
  • 1211 is "one 1, one 2, two 1s", so we write 111221 as the next term
  • 111221 is "three 1s, two 2s, one 1", so the next term is 312211, and so on forever.

The above sequence uses base 10, but we can do the same in binary as well. In binary, the sequence starting 1 would continue with 11 (one 1), then we get 101 (two 1s, and we write the two in binary as 10), afterwards it's 111011 (one 1, one 0, one 1), and then the next term is 11110101 ("11" times 1, "1" times 0, "10" times 1).


You are given a binary string String term. Assume that the binary "look and say" sequence starts with the given first term. Find and return its second term.

Notes

  • Binary numbers in this problem cannot start with an unnecessary leading zero.

Constraints

  • term will have between 1 and 1000 characters, inclusive.
  • Each character in term will be '0' or '1'.
  • The first character in term will be '1'.
Examples
0)
"1"
Returns: "11"

The first few examples are the steps described in the statement.

1)
"11"
Returns: "101"
2)
"101"
Returns: "111011"
3)
"111011"
Returns: "11110101"
4)
"11110101"
Returns: "100110111011"

This is the next step after those shown in the statement. This sequence is "four 1s, one 0, one 1, one 0, one 1", and as four in binary is "100", we get "1001" + "10" + "11" + "10" + "11" = "100110111011".

5)
"1111111"
Returns: "1111"

Seven 1s. Note that sometimes the new string can be shorter than the old one.

6)
"1111111100000000"
Returns: "1000110000"

Eight 1s, eight 0s.

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

Coding Area

Language: C++17 · define a public class BinaryConway with a public method string say(string term) · 15 test cases · 2 s / 256 MB per case

Submitting as anonymous