| Submit | All submissions | Best solutions | Back to list |
PROG0005 - Letter game |
Let us play a simple letter game in which the letters in a given string - consisting only of the letters a and b - are replaced at every turn. Every occurrence of the letter b is replaced by the letters ab, and every occurrence of the letter a is replaced by the letter b.
Suppose we start with "abba". After the first turn, this string has changed to "bababb", by replacing the a's by the letter b and by replacing the b's with ab. In this way, the string eventually becomes very long. How long is the string after n substitutions?
Input
The input consists of $t$ test cases ($t \leq 100$). The first line of the input contains a natural number $t$. This is followed by $t$ lines that describe the various test cases. Each case is defined by a string $s$ and a natural number $n$ ($0 < n \leq 50$). You may assume that $s$ consists only of the letters a and b, and counts no more than 100 characters .
Output
Write the length of the given string after $n$ replacements on a separate line for each test case.
Example
Input:
3 abba 1 abba 2 abbaabbababaabba 50
Output:
6 10 426530329384
Bij een eenvoudig letterspelletje wordt bij elke beurt in een gegeven string — die enkel bestaat uit de letters a en b — elk voorkomen van de letter b vervangen door de letters ab, en elk voorkomen van de letter a vervangen door de letter b.
Stel dat we bijvoorbeeld beginnen met "abba". Na de eerste beurt is deze string gewijzigd in "bababb", door de a's te vervangen door de letter b en de b's te vervangen door ab. Op deze manier wordt de string na verloop van tijd wel heel erg lang. Vraag is hoe lang de string wordt nadat n vervangingen zijn doorgevoerd?
Invoer
De invoer bestaan uit $t$ testgevallen ($t \leq 100$). De eerste regel van de invoer bevat een natuurlijk getal $t$. Daarna volgen $t$ regels die de verschillende testgevallen omschrijven. Elk geval wordt omschreven door een string $s$ en een natuurlijk getal $n$ ($0 < n \leq 50$). Je mag ervan uitgaan dat $s$ enkel bestaat uit de letters a en b, en niet meer dan 100 letters telt.
Uitvoer
Schrijf voor elk testgeval de lengte van de gegeven string na $n$ vervangingen uit op een afzonderlijke regel.
Voorbeeld
Invoer:
3 abba 1 abba 2 abbaabbababaabba 50
Uitvoer:
6 10 426530329384
| Added by: | Peter Dawyndt |
| Date: | 2011-07-09 |
| Time limit: | 10s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | |
| Resource: | None |
hide comments
|
2012-09-06 11:15:34 Brecht Embo
voor de eerste 2 invoer waarden heb ik het snel de uitkomt gevonden , maar voor abbaabbababaabba 50 duurt dit enorm lang. is er een manier om de loop functie in te korten ? |
RSS