1199 - Walaweh
Time Limit : 8 Second
Memory Limit : 128 MB
Submission: 11
Solved: 9
- Description
Walaweh number is a numbering sequence that is so troublesome (that's exactly where it gets its name, "Walaweh!").
Walaweh number is similar to binary number (only consist of zeros and ones)
except that the length of the number is important (thus leading zeros are preserved).
Note that the "length" of Walaweh numbers means the number of digits in the Walaweh numbers.
To simplify the wording, Walaweh numbers of length L will be written as WL,
which denotes all Walaweh numbers with exactly L digits.
Walaweh numbers (of any length) is an ordered list of numbers.
The most basic (smallest) Walaweh numbers is W1 which are "0" and "1" in that order.
WL can be generated from WL-1 except for W1 which is fixed.
This is done by creating two clones (C1 and C2) of WL-1 then apply some operations (see below)
on C1 and C2 to produce C1' and C2'. The combined list of numbers in C1' followed by the list of numbers in C2' (in that order) produces WL.
These are the 8 possible operations on C1 and C2:
- Append a digit zero to the end of all numbers in C1 and append a digit one to the end of all numbers in C2.
- Append a digit zero to the beginning of all numbers in C1 and append a digit one to the beginning of all numbers in C2.
- Append a digit one to the end of all numbers in C1 and append a digit zero to the end of all numbers in C2.
- Append a digit one to the beginning of all numbers in C1 and append a digit zero to the beginning of all numbers in C2.
- Reverse the order of the list of numbers in C2 and do operation 1 above.
- Reverse the order of the list of numbers in C2 and do operation 2 above.
- Reverse the order of the list of numbers in C2 and do operation 3 above.
- Reverse the order of the list of numbers in C2 and do operation 4 above.
W1 is fixed. W2 is generated by applying the first operation on W1.
W3 is generated by applying the second operation on W2 and so on...
and it will go back to the first operation again after the eighth operation.
So, W9 is generated by applying the eighth operation on W8.
W10 is generated by applying the first operation on W9 and so on... Walaweh!
Below is the list of W1, W2, W3, and W4 :
Walaweh Length Sequence Number Walaweh Numbers
1 1. 0
1 2. 1
2 1. 00
2 2. 10
2 3. 01
2 4. 11
3 1. 000
3 2. 010
3 3. 001
3 4. 011
3 5. 100
3 6. 110
3 7. 101
3 8. 111
Walaweh Length Sequence Number Walaweh Numbers
4 1. 0001
4 2. 0101
4 3. 0011
4 4. 0111
4 5. 1001
4 6. 1101
4 7. 1011
4 8. 1111
4 9. 0000
4 10. 0100
4 11. 0010
4 12. 0110
4 13. 1000
4 14. 1100
4 15. 1010
4 16. 1110
To give you an idea of "reverse the order of the list of numbers in C2" for the fifth to eighth operations,
we give the last 5 numbers of W6 :
Walaweh Length Sequence Number Walaweh Numbers
6 60. 110011
6 61. 101111
6 62. 100111
6 63. 101011
6 64. 100011
Your job is to convert from Walaweh Length + Sequence Number into Walaweh Number and vice versa.
- Append a digit zero to the end of all numbers in C1 and append a digit one to the end of all numbers in C2.
- Input
- There are multiple input, each on a line by itself. The line will either begin with the word "Walaweh" then followed by an integer number L < 64 and N < 2L or begin with the word "Sequence" then followed by a binary representation of the Walaweh number with length < 64.
- Output
- For input line that begins with "Walaweh" you have to output the N'th Walaweh number of length L. For those lines that begins with "Sequence" you have to output the Sequence number of the given Walaweh number (The length of the Walaweh number is already obvious from the input).
- sample input
-
Walaweh 1 1 Walaweh 3 6 Walaweh 4 13 Sequence 1100 Walaweh 5 14 Sequence 1110 Sequence 01010 Walaweh 6 1 Walaweh 6 20 Walaweh 6 32 Sequence 100101 Walaweh 6 40 Walaweh 6 64 Walaweh 7 29 Sequence 0000001 Walaweh 7 100 Walaweh 15 1984 Sequence 00100101010001 Sequence 100101010001001001001001 Walaweh 20 38299 Walaweh 40 38294828288 Sequence 10100010001001001001 Walaweh 63 78487827863828368 Sequence 000011100010101010010100010010010101001001001011001010001001001
- sample output
-
0 110 1000 14 11100 16 31 100010 001110 011100 54 000001 100011 0010000 40 1010000 011011000111110 10018 6619354 01101010001001010001 0101001011111100010001001010000001000001 350619 010000110001110011110100010111111001000111000100111100101100010 2769960758748826002
- hint
- source