QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#308586#1837. Hamiltonianluyiming123AC ✓1ms3904kbC++141.5kb2024-01-20 10:49:082024-01-20 10:49:08

Judging History

This is the latest submission verdict.

  • [2024-01-20 10:49:08]
  • Judged
  • Verdict: AC
  • Time: 1ms
  • Memory: 3904kb
Show
  • [2024-01-20 10:49:08]
  • Submitted

answer

# include <bits/stdc++.h>
# define pii pair <int, int> 
using namespace std; 
using i64 = long long; 

void print(int n, int y)
{
    printf("%d %d\n", n + y, n * (n - 1) / 2 + y + 1); 
    // K_n
    for(int i = 1; i <= n; i++)
    {
        for(int j = i + 1; j <= n; j++) printf("%d %d\n", i, j); 
    }
    if(!y) return; 
    printf("1 %d\n", n + 1); 
    for(int i = 1; i < y; i++) 
    {
        printf("%d %d\n", n + i, n + i + 1); 
    }
    printf("%d %d\n", n + y, n); 
    return; 
}

int main(void)
{
    int k; scanf("%d", &k); 
    if(k <= 20) 
    {
        if(k == 1) 
        {
            printf("2 1\n1 2\n"); return 0;  
        }
        if(k == 2)
        {
            printf("4 4\n1 2\n1 3\n2 3\n3 4\n"); return 0; 
        }
        printf("%d %d\n", k, k); 
        for(int i = 1; i < k; i++) printf("%d %d\n", i, i + 1); 
        printf("%d %d\n", k, 1); 
        return 0; 
    }
    for(int n = 3; n <= 20; n++)
    {
        for(int y = 1; n + y <= 20; y++)
        {
            int cnt = n * (n - 1) / 2 - 1 + y - 1; 
            if(y == 1) cnt += n; 
            else if(y > 1) cnt += 2 * (n - 1); 
            if(cnt == k)
            {
                // printf("n = %d, y = %d\n", n, y); 
                print(n, y); return 0; 
            }
            // printf("n = %d, y = %d, cnt = %d\n", n, y, cnt); 
        }   
    }
    
    // for(int i = 21; i <= 60; i++)
    //     if(!vis[i]) { printf("Failed %d\n", i); return 0; }
    // printf("Yes\n"); 
    return 0; 
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3780kb

input:

1

output:

2 1
1 2

result:

ok correct

Test #2:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

2

output:

4 4
1 2
1 3
2 3
3 4

result:

ok correct

Test #3:

score: 0
Accepted
time: 0ms
memory: 3724kb

input:

3

output:

3 3
1 2
2 3
3 1

result:

ok correct

Test #4:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

4

output:

4 4
1 2
2 3
3 4
4 1

result:

ok correct

Test #5:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

5

output:

5 5
1 2
2 3
3 4
4 5
5 1

result:

ok correct

Test #6:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

6

output:

6 6
1 2
2 3
3 4
4 5
5 6
6 1

result:

ok correct

Test #7:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

7

output:

7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1

result:

ok correct

Test #8:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

8

output:

8 8
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 1

result:

ok correct

Test #9:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

9

output:

9 9
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 1

result:

ok correct

Test #10:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

10

output:

10 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 1

result:

ok correct

Test #11:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

11

output:

11 11
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 1

result:

ok correct

Test #12:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

12

output:

12 12
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 1

result:

ok correct

Test #13:

score: 0
Accepted
time: 0ms
memory: 3764kb

input:

13

output:

13 13
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 1

result:

ok correct

Test #14:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

14

output:

14 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 1

result:

ok correct

Test #15:

score: 0
Accepted
time: 0ms
memory: 3904kb

input:

15

output:

15 15
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 1

result:

ok correct

Test #16:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

16

output:

16 16
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 1

result:

ok correct

Test #17:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

17

output:

17 17
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 1

result:

ok correct

Test #18:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

18

output:

18 18
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 1

result:

ok correct

Test #19:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

19

output:

19 19
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 1

result:

ok correct

Test #20:

score: 0
Accepted
time: 1ms
memory: 3756kb

input:

20

output:

20 20
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 1

result:

ok correct

Test #21:

score: 0
Accepted
time: 1ms
memory: 3840kb

input:

21

output:

19 20
1 2
1 3
2 3
1 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 3

result:

ok correct

Test #22:

score: 0
Accepted
time: 1ms
memory: 3724kb

input:

22

output:

20 21
1 2
1 3
2 3
1 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 3

result:

ok correct

Test #23:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

23

output:

17 20
1 2
1 3
1 4
2 3
2 4
3 4
1 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 4

result:

ok correct

Test #24:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

24

output:

18 21
1 2
1 3
1 4
2 3
2 4
3 4
1 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 4

result:

ok correct

Test #25:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

25

output:

19 22
1 2
1 3
1 4
2 3
2 4
3 4
1 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 4

result:

ok correct

Test #26:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

26

output:

20 23
1 2
1 3
1 4
2 3
2 4
3 4
1 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 4

result:

ok correct

Test #27:

score: 0
Accepted
time: 1ms
memory: 3892kb

input:

27

output:

16 22
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
1 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 5

result:

ok correct

Test #28:

score: 0
Accepted
time: 0ms
memory: 3904kb

input:

28

output:

17 23
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
1 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 5

result:

ok correct

Test #29:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

29

output:

18 24
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
1 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 5

result:

ok correct

Test #30:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

30

output:

19 25
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
1 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 5

result:

ok correct

Test #31:

score: 0
Accepted
time: 1ms
memory: 3848kb

input:

31

output:

20 26
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
1 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 5

result:

ok correct

Test #32:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

32

output:

15 25
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
1 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 6

result:

ok correct

Test #33:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

33

output:

16 26
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
1 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 6

result:

ok correct

Test #34:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

34

output:

17 27
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
1 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 6

result:

ok correct

Test #35:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

35

output:

18 28
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
1 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 6

result:

ok correct

Test #36:

score: 0
Accepted
time: 0ms
memory: 3728kb

input:

36

output:

19 29
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
1 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 6

result:

ok correct

Test #37:

score: 0
Accepted
time: 1ms
memory: 3844kb

input:

37

output:

20 30
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6
1 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 6

result:

ok correct

Test #38:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

38

output:

14 29
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7
1 8
8 9
9 10
10 11
11 12
12 13
13 14
14 7

result:

ok correct

Test #39:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

39

output:

15 30
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7
1 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 7

result:

ok correct

Test #40:

score: 0
Accepted
time: 0ms
memory: 3820kb

input:

40

output:

16 31
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7
1 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 7

result:

ok correct

Test #41:

score: 0
Accepted
time: 0ms
memory: 3760kb

input:

41

output:

17 32
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7
1 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 7

result:

ok correct

Test #42:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

42

output:

18 33
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7
1 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 7

result:

ok correct

Test #43:

score: 0
Accepted
time: 0ms
memory: 3852kb

input:

43

output:

19 34
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7
1 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 7

result:

ok correct

Test #44:

score: 0
Accepted
time: 0ms
memory: 3836kb

input:

44

output:

20 35
1 2
1 3
1 4
1 5
1 6
1 7
2 3
2 4
2 5
2 6
2 7
3 4
3 5
3 6
3 7
4 5
4 6
4 7
5 6
5 7
6 7
1 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 7

result:

ok correct

Test #45:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

45

output:

13 34
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 8
7 8
1 9
9 10
10 11
11 12
12 13
13 8

result:

ok correct

Test #46:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

46

output:

14 35
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 8
7 8
1 9
9 10
10 11
11 12
12 13
13 14
14 8

result:

ok correct

Test #47:

score: 0
Accepted
time: 0ms
memory: 3756kb

input:

47

output:

15 36
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 8
7 8
1 9
9 10
10 11
11 12
12 13
13 14
14 15
15 8

result:

ok correct

Test #48:

score: 0
Accepted
time: 0ms
memory: 3832kb

input:

48

output:

16 37
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 8
7 8
1 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 8

result:

ok correct

Test #49:

score: 0
Accepted
time: 0ms
memory: 3828kb

input:

49

output:

17 38
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 8
7 8
1 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 8

result:

ok correct

Test #50:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

50

output:

18 39
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 8
7 8
1 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 8

result:

ok correct

Test #51:

score: 0
Accepted
time: 0ms
memory: 3720kb

input:

51

output:

19 40
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 8
7 8
1 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 8

result:

ok correct

Test #52:

score: 0
Accepted
time: 0ms
memory: 3896kb

input:

52

output:

20 41
1 2
1 3
1 4
1 5
1 6
1 7
1 8
2 3
2 4
2 5
2 6
2 7
2 8
3 4
3 5
3 6
3 7
3 8
4 5
4 6
4 7
4 8
5 6
5 7
5 8
6 7
6 8
7 8
1 9
9 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 8

result:

ok correct

Test #53:

score: 0
Accepted
time: 0ms
memory: 3844kb

input:

53

output:

12 40
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 3
2 4
2 5
2 6
2 7
2 8
2 9
3 4
3 5
3 6
3 7
3 8
3 9
4 5
4 6
4 7
4 8
4 9
5 6
5 7
5 8
5 9
6 7
6 8
6 9
7 8
7 9
8 9
1 10
10 11
11 12
12 9

result:

ok correct

Test #54:

score: 0
Accepted
time: 0ms
memory: 3900kb

input:

54

output:

13 41
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 3
2 4
2 5
2 6
2 7
2 8
2 9
3 4
3 5
3 6
3 7
3 8
3 9
4 5
4 6
4 7
4 8
4 9
5 6
5 7
5 8
5 9
6 7
6 8
6 9
7 8
7 9
8 9
1 10
10 11
11 12
12 13
13 9

result:

ok correct

Test #55:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

55

output:

14 42
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 3
2 4
2 5
2 6
2 7
2 8
2 9
3 4
3 5
3 6
3 7
3 8
3 9
4 5
4 6
4 7
4 8
4 9
5 6
5 7
5 8
5 9
6 7
6 8
6 9
7 8
7 9
8 9
1 10
10 11
11 12
12 13
13 14
14 9

result:

ok correct

Test #56:

score: 0
Accepted
time: 0ms
memory: 3840kb

input:

56

output:

15 43
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 3
2 4
2 5
2 6
2 7
2 8
2 9
3 4
3 5
3 6
3 7
3 8
3 9
4 5
4 6
4 7
4 8
4 9
5 6
5 7
5 8
5 9
6 7
6 8
6 9
7 8
7 9
8 9
1 10
10 11
11 12
12 13
13 14
14 15
15 9

result:

ok correct

Test #57:

score: 0
Accepted
time: 0ms
memory: 3892kb

input:

57

output:

16 44
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 3
2 4
2 5
2 6
2 7
2 8
2 9
3 4
3 5
3 6
3 7
3 8
3 9
4 5
4 6
4 7
4 8
4 9
5 6
5 7
5 8
5 9
6 7
6 8
6 9
7 8
7 9
8 9
1 10
10 11
11 12
12 13
13 14
14 15
15 16
16 9

result:

ok correct

Test #58:

score: 0
Accepted
time: 0ms
memory: 3752kb

input:

58

output:

17 45
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 3
2 4
2 5
2 6
2 7
2 8
2 9
3 4
3 5
3 6
3 7
3 8
3 9
4 5
4 6
4 7
4 8
4 9
5 6
5 7
5 8
5 9
6 7
6 8
6 9
7 8
7 9
8 9
1 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 9

result:

ok correct

Test #59:

score: 0
Accepted
time: 0ms
memory: 3848kb

input:

59

output:

18 46
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 3
2 4
2 5
2 6
2 7
2 8
2 9
3 4
3 5
3 6
3 7
3 8
3 9
4 5
4 6
4 7
4 8
4 9
5 6
5 7
5 8
5 9
6 7
6 8
6 9
7 8
7 9
8 9
1 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 9

result:

ok correct

Test #60:

score: 0
Accepted
time: 0ms
memory: 3704kb

input:

60

output:

19 47
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
2 3
2 4
2 5
2 6
2 7
2 8
2 9
3 4
3 5
3 6
3 7
3 8
3 9
4 5
4 6
4 7
4 8
4 9
5 6
5 7
5 8
5 9
6 7
6 8
6 9
7 8
7 9
8 9
1 10
10 11
11 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 9

result:

ok correct
English 繁體中文 简体中文

Server Time: 2025-02-18 18:23:07 | OpenSource Project