QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#61385#4237. Word Ladder2pal1rak#AC ✓273ms3676kbC++142.1kb2022-11-12 19:09:152022-11-12 19:09:16

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-12 19:09:16]
  • 评测
  • 测评结果:AC
  • 用时:273ms
  • 内存:3676kb
  • [2022-11-12 19:09:15]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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