PROG0328 - Thue-Morse sequence
The Thue-Morse sequence is a binary sequence - an infinite sequence of zeroes and ones. The sequence is obtained by starting from the string 0, and constantly expanding it with the Boolean complement of the obtained string so far. The Boolean complement of a binary string is obtained by replacing all zeroes with ones and all ones with zeroes. This procedure therefore starts with the string 0, and successively delivers the strings 01, 0110, 01101001, 0110100110010110, and so on.
The Thue-Morse sequence has many stunning features. For example, the binary sequence is cube-free: it does not contain 000,111,010101, or more generally bbb in which b represents a random binary string. The sequence is also self-similar: if you remove every other bit from the series, you again obtain a Thue-Morse sequence. This sequence has many applications in mathematics, and is also used in chess, graphic design, weaving patterns and composing music.
Input
The first line of the input contains an integer $t \in \mathbb{N}$ indicating the number of test cases. This is followed by $t$ lines that each describe a test case. Each of these lines consists of two integers $s$ and $l$, separated by a space.
Output
For each test case, print the substring of the Thue-Morse sequence, starting at position $s$ and is $l$ binary digits long. We index the positions of the binary digits from zero.
Example
Input:
5
7645 37
8956 28
4724 26
8829 17
6051 12
Output:
0011001011001101001011010011001011001
0110100101100110100101101001
01100110100110010110011010
00110010110011010
010011001011
De Thue-Morse reeks is een binaire reeks — een oneindige reeks van nullen en eentjes. De reeks wordt bekomen door te vertrekken van de string 0, en die steeds uit te breiden met het Booleaanse complement van de string die men tot dusver heeft bekomen. Het Booleaanse complement van een binaire string bekomt men door alle nullen te vervangen door eentjes en alle eentjes door nullen. Deze procedure start dus bij de string 0, en levert achtereenvolgens de strings 01, 0110, 01101001, 0110100110010110, enzoverder op.
De Thue-Morse reeks heeft heel wat verbluffende eigenschappen. Zo is het bijvoorbeeld een binaire reeks die kubus-vrij is: ze bevat geen 000, 111, 010101 of meer algemeen bbb waarbij b zelf een willekeurige binaire string voorstelt. De reeks is ook zelf-gelijkend: als je om het andere bit verwijdert uit de reeks, dan bekom je opnieuw een Thue-Morse reeks. Deze reeks heeft heel wat toepassingen in de wiskunde, en wordt ook gebruikt bij schaken, grafisch ontwerpen, weefpatronen en het componeren van muziek.
Invoer
De eerste regel van de invoer bevat een getal $t \in \mathbb{N}$ dat het aantal testgevallen aangeeft. Daarna volgen $t$ regels die elk een testgeval omschrijven. Elk van deze regels bestaan uit twee natuurlijke getallen $s$ en $l$ die door een spatie van elkaar gescheiden worden.
Uitvoer
Schrijf voor elk testgeval de substring van de Thue-Morse reeks uit die start op positie $s$ en $l$ binaire cijfers lang is. We indexeren hierbij de posities van de binaire cijfers vanaf nul.
Voorbeeld
Invoer:
5
7645 37
8956 28
4724 26
8829 17
6051 12
Uitvoer:
0011001011001101001011010011001011001
0110100101100110100101101001
01100110100110010110011010
00110010110011010
010011001011
| Added by: | Peter Dawyndt |
| Date: | 2013-02-16 |
| Time limit: | 10s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | PY_NBC |
| Resource: | None |
RSS