Given a number n and a pattern that follows like:
(1 to 26): a,b,c,….z
(27 to 52): aa,ab,ac,…az
(52 to 78): ba,bb,bc,…bz
. . . za,zb,zc,…zz
aaa,aab,aac,…aaz
aba,abb,abc,… . . . find the nth pattern
# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3814 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3517 |
7 | Radewoosh | 3410 |
8 | hos.lyric | 3399 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 169 |
2 | maomao90 | 162 |
2 | Um_nik | 162 |
4 | atcoder_official | 161 |
5 | djm03178 | 158 |
6 | -is-this-fft- | 157 |
7 | adamant | 155 |
8 | awoo | 154 |
8 | Dominater069 | 154 |
10 | luogu_official | 150 |
Given a number n and a pattern that follows like:
(1 to 26): a,b,c,….z
(27 to 52): aa,ab,ac,…az
(52 to 78): ba,bb,bc,…bz
. . . za,zb,zc,…zz
aaa,aab,aac,…aaz
aba,abb,abc,… . . . find the nth pattern
Name |
---|
this is the link of problem , maybe it can helps you :) http://mirror.codeforces.com/gym/101372/attachments/download/5504/2017-russian-code-cup-rcc-17-3rd-qualification-round-en.pdf (problem A)
Actually I think this is what has been used in EXCEL...
One can find that the first 26 columns in EXCEL are denoted as A,B,...,Z while the next 26 ones are written as AA,AB,AC,....,AZ, and so on.
We can build a 26-ary tree to obtain an intuitive understanding of this problem. The root node is NULL, and it has 26 child nodes, denoted as A,B,...,Z. Next, node A has 26 child nodes A,B,....,Z, and node B has 26 child nodes A,B,...,Z, and node C has 26 child nodes A,B,...,Z, and so on. In a word, each node in the tree has exactly 26 child nodes, A,B,...,Z.
If we start from the root node and walk along the branches to some other node, all the nodes that have been visited just form the pattern A,B,...,Z,AA,AB,...,AZ,...
Moreover, if we assign index 0 to the root node, and increase the index from top to bottom and left to right, i.e., the child nodes of the root node are counted as 1,2,...,26, and so on, to calculate the n-th pattern is just to find out the route from root node to the node with index n.
For some node with index i, its child nodes have indices 26*i+1, 26*i+2,...,26*i+26. Thus, given node with index n, we can adopt this relationship to find out the route up to the root node, and output the letters that have been visited.
Similarly, given any pattern, like "AAC", we can also calculate its index.