C - abc285_brutmhyhiizp Editorial by en_translator
First of all, notice that there are \(26^k\) IDs of length \(k\).
Also, there are \((26^1+26^2+\dots+26^k)\) IDs of length at most \(k\).
Now, let us find the index of the problem whose ID is a \(l\)-letter string \(S\).
In fact, it can be found as follows.
Initialize the answer with \(26^1 + 26^2 + \dots + 26^{l-1}\).
- Repeat the following for each \(i = 1,2,\dots,l\):
- add \((x-1) \times 26^{l-i}\) to the answer, if the \(i\)-th character of \(S\) is the \(x\)-th letter in the alphabet.
Print \(1\) to the answer and print it. (It shifts the \(0\)-based indexing to \(1\)-based.)
This solution can be interpreted in several ways.
For example, when the ID is QWERTY
, we can find the answer as follows.
Counting successively
- There are \((26^1 + 26^2 + \dots + 26^5)\) IDs of length at most \(5\).
- There are \(26^5\) IDs
A?????
of length \(6\) starting withA
. - There are \(26^5\) IDs
B?????
of length \(6\) starting withB
. - \(\vdots\)
- There are \(26^5\) IDs
P?????
of length \(6\) starting withP
. - There are \(26^4\) IDs
QA????
of length \(6\) starting withQA
. - There are \(26^4\) IDs
QB????
of length \(6\) starting withQB
. - \(\vdots\)
- There are \(26^3\) IDs
QWA???
of length \(6\) starting withQWA
. - \(\vdots\)
- There are \(26^2\) IDs
QWEA??
of length \(6\) starting withQWEA
. - \(\vdots\)
- There are \(26^1\) IDs
QWERA?
of length \(6\) starting withQWERA
. - \(\vdots\)
- There are \(26^0\) IDs
QWERTA
of length \(6\) starting withQWERTA
. - \(\vdots\)
Interpret it as base-\(26\) number
- There are \((26^1 + 26^2 + \dots + 26^5)\) IDs of length at most \(5\).
So far so good. Now let us interpret QWERTY
as a base-\(26\) number.
If we correspond AAAAAA
to \(0\), AAAAAB
to \(1\), \(\dots\), AAAAAZ
to \(25\), AAAABA
to \(26\), \(\dots\), we can treat the string just like a base-\(26\) integer by corresponding each uppercase English letter to \(0,1,\dots,25\). Thus, regard the input as a base-\(26\) number and reconstruct it to a decimal.
Sample code (C++):
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
cin >> s;
int l=s.size();
long long res=0,add=26;
for(int i=1;i<=l-1;i++){res+=add;add*=26;}
long long num=0;
for(int i=0;i<l;i++){
num*=26;
num+=(s[i]-'A');
}
cout << res+num+1 << "\n";
return 0;
}
posted:
last update: