10070 | 2024. 03. 26 11:23:56 | Error42 | Kígyózó szavak | cpp17 | Elfogadva 100/100 | 52ms | 4644 KiB |
#include <climits>
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
ll h, n;
cin >> h >> n;
vector<vector<ll>> dp(h, vector<ll>(26, 0));
for (int j = 0; j < 26; j++)
dp[0][j] = 1;
for (int i = 1; i < h; i++) {
dp[i][0] = dp[i - 1][1] + 1;
for (int j = 1; j < 25; j++)
dp[i][j] = min((ll)INT_MAX, dp[i - 1][j - 1] + dp[i - 1][j + 1]) + 1;
dp[i][25] = dp[i - 1][24] + 1;
}
while (n--) {
ll k;
cin >> k;
string s = "";
// first character
int last = 0;
while (dp[h - 1][last] < k) {
k -= dp[h - 1][last];
last++;
}
s.push_back('a' + last);
for (int i = h - 2; i >= 0; i--) {
if (k == 1)
break;
k--;
vector<int> continuations;
if (last > 0)
continuations.push_back(last - 1);
if (last < 25)
continuations.push_back(last + 1);
for (int j : continuations) {
if (dp[i][j] >= k) {
s.push_back('a' + j);
last = j;
break;
}
k -= dp[i][j];
}
}
cout << s << "\n";
}
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
base | 100/100 | ||||||
1 | Elfogadva | 0/0 | 3ms | 1828 KiB | |||
2 | Elfogadva | 0/0 | 3ms | 2020 KiB | |||
3 | Elfogadva | 5/5 | 3ms | 2248 KiB | |||
4 | Elfogadva | 5/5 | 3ms | 2440 KiB | |||
5 | Elfogadva | 5/5 | 3ms | 2672 KiB | |||
6 | Elfogadva | 5/5 | 3ms | 2744 KiB | |||
7 | Elfogadva | 5/5 | 3ms | 3012 KiB | |||
8 | Elfogadva | 5/5 | 4ms | 3092 KiB | |||
9 | Elfogadva | 5/5 | 21ms | 3380 KiB | |||
10 | Elfogadva | 5/5 | 17ms | 3348 KiB | |||
11 | Elfogadva | 5/5 | 27ms | 3664 KiB | |||
12 | Elfogadva | 5/5 | 28ms | 3684 KiB | |||
13 | Elfogadva | 5/5 | 52ms | 4164 KiB | |||
14 | Elfogadva | 6/6 | 13ms | 4024 KiB | |||
15 | Elfogadva | 6/6 | 27ms | 4232 KiB | |||
16 | Elfogadva | 6/6 | 17ms | 4276 KiB | |||
17 | Elfogadva | 6/6 | 14ms | 4148 KiB | |||
18 | Elfogadva | 7/7 | 17ms | 4256 KiB | |||
19 | Elfogadva | 7/7 | 50ms | 4644 KiB | |||
20 | Elfogadva | 7/7 | 18ms | 4336 KiB |