| Submit | All submissions | Best solutions | Back to list |
PROG0428 - Rondo |
A rondo (or its French part-equivalent rondeau) is a medieval poetical and musical form, that contains repetitions of a couplet separated by longer sections of poetry. The form has a principal theme (sometimes called the refrain) that alternates with one or more contrasting themes, generally called episodes or couplets. During the Classical period the succession of refrains and couplets usually was symmetric, with patterns like ABA or ABACABA.
This kind of symmetrical patterns can be constructed easily based on the following procedure. The procedure starts with the most simple form A of a symmetric pattern, representing the principal theme. Each time, the next pattern is obtained by appending the next letter of the alphabet to the previous pattern, followed by a second repetition of the previous pattern. As such we successively get the following series of patterns: A, ABA, ABACABA, ABACABADABACABA, ….
If we continue the above procedure long enough so that we get a symmetrical rondo pattern that has the form ABACABADABACABA…, then what is the subpattern that starts at position $p$ and has $l$ sections?
Input
The first line of the input contains an integer $t \in \mathbb{N}$ that indicates the number of cases that follow. This is followed by another $2t$ line, as each case is described by two integers $p, l \in \mathbb{N}$, each on a separate line. It always holds that $p \leq 5000$ and $l \leq 20$.
Output
For each case, write the subpattern of a sufficiently long symmetrical rondo pattern that starts at position $p$ and has $l$ sections. We agree upon the fact that the first refrain A of the symmetrical rondo pattern is on position 1.
Example
Input:
3 3 1 6 4 7 5
Output:
A BADA ADABA
Een rondo (ook: rondeau of rondeel) is een vers- en muziekvorm die ontstaan is tijdens de middeleeuwen, waarbij een hoofdthema — het zogenaamde rondothema — telkens als een soort refrein terugkeert. De tussenliggende delen, die andere thema's bespelen, worden dan de coupletten genoemd. Tijdens het classicisme was de opeenvolging van refreinen en coupletten vaak symmetrisch, en werden patronen gebruikt van de vorm ABA of ABACABA.
Dit soort symmetrische patronen kan makkelijk geconstrueerd worden op basis van de volgende procedure. De procedure start met de meest eenvoudige vorm A van een symmetrisch patroon, die het hoofdthema voorstelt. Het volgende patroon wordt steeds bekomen door de volgende letter van het alfabet aan het vorige patroon toe te voegen, en daarachter nogmaals het vorige patroon te herhalen. Op die manier krijgen we achtereenvolgens A, ABA, ABACABA, ABACABADABACABA, ….
Veronderstel dat we bovenstaande constructieprocedure lang genoeg blijven herhalen totdat we een symmetrisch rondopatroon krijgen van de vorm ABACABADABACABA…. Wat is dan het deelpatroon dat start op positie $p$ en $l$ delen lang is?
Invoer
De eerste regel van de invoer bevat een getal $t \in \mathbb{N}$ dat aangeeft hoeveel gevallen er volgen. Daarna volgen nog $2t$ regels, omdat elk geval omschreven wordt door twee getallen $p, l \in \mathbb{N}$ die elk op een afzonderlijke regel staan. Hierbij geldt dat $p \leq 5000$ en $l \leq 20$.
Uitvoer
Schrijf voor elk geval het deelpatroon uit van een voldoende lang symmetrisch rondopatroon dat start op positie $p$ en $l$ delen lang is. Hierbij spreken we af dat het eerste refrein A van het symmetrisch rondopatroon op positie 1 staat.
Voorbeeld
Invoer:
3 3 1 6 4 7 5
Uitvoer:
A BADA ADABA
| Added by: | Peter Dawyndt |
| Date: | 2013-09-11 |
| Time limit: | 10s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | PY_NBC |
| Resource: | None |
RSS