QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#61385 | #4237. Word Ladder | 2pal1rak# | AC ✓ | 273ms | 3676kb | C++14 | 2.1kb | 2022-11-12 19:09:15 | 2022-11-12 19:09:16 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// mt19937 g(chrono::high_resolution_clock::now().time_since_epoch().count());
char s[5005][5];
int hamming(int A, int B) {
int x = 0;
int M = 4;
for(int i = 0; i < M; i++)
x += (s[A][i] != s[B][i]);
return x;
}
void solve_test() {
int N;
cin >> N;
int M = 4;
for(int i = 0; i < M; i++) s[0][i] = 'a';
s[0][M] = 0;
for(int i = 1; i < N; i++) {
for(int j = 0; j < M; j++)
s[i][j] = s[i - 1][j];
s[i][M] = 0;
bool added = false;
for(int p = 0; p < M && !added; p++) {
for(char c = s[i - 1][p] + 1; c <= 'z' && !added; c++) {
if(c == s[i - 1][p]) continue;
s[i][p] = c;
bool ok = true;
for(int j = 0; j < i - 1 && ok; j++) {
if(hamming(j, i) < 2) {
ok = false;
}
}
if(ok) {
added = true;
continue;
}
s[i][p] = s[i - 1][p];
}
for(char c = 'a'; c < s[i - 1][p] && !added; c++) {
if(c == s[i - 1][p]) continue;
s[i][p] = c;
bool ok = true;
for(int j = 0; j < i - 1 && ok; j++) {
if(hamming(j, i) < 2) {
ok = false;
}
}
if(ok) {
added = true;
continue;
}
s[i][p] = s[i - 1][p];
}
}
assert(added);
}
for(int i = 0; i < N; i++)
printf("%s\n", s[i]);
}
int main() {
#ifdef USEFOPEN
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
cin.sync_with_stdio(false); cin.tie(0);
int T = 1;
// scanf("%d", &T);
for(int t = 1; t <= T; t++) {
//printf("Case #%d: ", t);
solve_test();
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3448kb
input:
5
output:
aaaa baaa bbaa cbaa ccaa
result:
ok good solution
Test #2:
score: 0
Accepted
time: 3ms
memory: 3368kb
input:
3
output:
aaaa baaa bbaa
result:
ok good solution
Test #3:
score: 0
Accepted
time: 2ms
memory: 3580kb
input:
4
output:
aaaa baaa bbaa cbaa
result:
ok good solution
Test #4:
score: 0
Accepted
time: 2ms
memory: 3540kb
input:
6
output:
aaaa baaa bbaa cbaa ccaa dcaa
result:
ok good solution
Test #5:
score: 0
Accepted
time: 0ms
memory: 3428kb
input:
7
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa
result:
ok good solution
Test #6:
score: 0
Accepted
time: 0ms
memory: 3484kb
input:
8
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa
result:
ok good solution
Test #7:
score: 0
Accepted
time: 1ms
memory: 3460kb
input:
9
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa
result:
ok good solution
Test #8:
score: 0
Accepted
time: 2ms
memory: 3536kb
input:
10
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa
result:
ok good solution
Test #9:
score: 0
Accepted
time: 2ms
memory: 3540kb
input:
64
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba deba geba ghba jhba jkba ...
result:
ok good solution
Test #10:
score: 0
Accepted
time: 0ms
memory: 3392kb
input:
51
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa
result:
ok good solution
Test #11:
score: 0
Accepted
time: 0ms
memory: 3372kb
input:
97
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba deba geba ghba jhba jkba ...
result:
ok good solution
Test #12:
score: 0
Accepted
time: 2ms
memory: 3428kb
input:
100
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba deba geba ghba jhba jkba ...
result:
ok good solution
Test #13:
score: 0
Accepted
time: 8ms
memory: 3648kb
input:
1000
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba deba geba ghba jhba jkba ...
result:
ok good solution
Test #14:
score: 0
Accepted
time: 6ms
memory: 3428kb
input:
1001
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba deba geba ghba jhba jkba ...
result:
ok good solution
Test #15:
score: 0
Accepted
time: 12ms
memory: 3456kb
input:
1024
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba deba geba ghba jhba jkba ...
result:
ok good solution
Test #16:
score: 0
Accepted
time: 9ms
memory: 3548kb
input:
1025
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba deba geba ghba jhba jkba ...
result:
ok good solution
Test #17:
score: 0
Accepted
time: 260ms
memory: 3572kb
input:
5000
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba deba geba ghba jhba jkba ...
result:
ok good solution
Test #18:
score: 0
Accepted
time: 273ms
memory: 3676kb
input:
4999
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba deba geba ghba jhba jkba ...
result:
ok good solution
Test #19:
score: 0
Accepted
time: 178ms
memory: 3388kb
input:
4096
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba deba geba ghba jhba jkba ...
result:
ok good solution
Test #20:
score: 0
Accepted
time: 176ms
memory: 3452kb
input:
4097
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba deba geba ghba jhba jkba ...
result:
ok good solution
Test #21:
score: 0
Accepted
time: 181ms
memory: 3552kb
input:
4098
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba deba geba ghba jhba jkba ...
result:
ok good solution
Test #22:
score: 0
Accepted
time: 145ms
memory: 3508kb
input:
3751
output:
aaaa baaa bbaa cbaa ccaa dcaa ddaa edaa eeaa feaa ffaa gfaa ggaa hgaa hhaa ihaa iiaa jiaa jjaa kjaa kkaa lkaa llaa mlaa mmaa nmaa nnaa onaa ooaa poaa ppaa qpaa qqaa rqaa rraa sraa ssaa tsaa ttaa utaa uuaa vuaa vvaa wvaa wwaa xwaa xxaa yxaa yyaa zyaa zzaa zzba azba abba dbba deba geba ghba jhba jkba ...
result:
ok good solution