列表

详情

NC24777. Wormhole Construction

描述

Among the N planets somewhere in Galaxy, there’s no way to move from one to another initially. To make it convenient to travel between any two planets, you can arbitrarily build some one-way wormholes between any two of them. 
Pay attention that inverse wormholes will make the space unstable, which means you cannot build wormhole from u to v and wormhole from v to u at the same time. 
If for any two planets u,v there always exists at least one path from u to v consists of no more than d wormholes, we can call the wormhole system with inconvenience d. 
Obviously you can construct wormhole systems with different inconvenience values by building different sets of wormholes. Please give a solution to make d as small as possible.


Attention: Loops and multiple wormholes in your solution will also be treated as WRONG ANSWER.


输入描述

One integer N, the number of planets.

输出描述

Two numbers in the first line, d and m,indicate the minimum inconvenience and the number of wormholes in your solution.
Then m lines indicate your solution, oneline describing one wormhole from u to v .

示例1

输入: 

4

输出: 

3 4
1 2
2 3
3 4
4 1

说明:

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 484K, 提交时间: 2019-04-13 16:43:31 

#include<bits/stdc++.h>
using namespace std;
int n,num,m,d;
int main()
{
    scanf("%d",&n);
    if(n%2||n==4)
    {
        d=2;
        if(n==4) d=3;
        num=(n-1)/2;
        m=n*num;
        printf("%d %d\n",d,m);
        for(int i=1;i<=num;i++)
            for(int j=0;j<n;j++)
                printf("%d %d\n",j+1,(j+i)%n+1);
    }
    else
    {
        n-=2;
        num=(n-1)/2;
        m=n*num;
        printf("2 %d\n",m+2*n);
        for(int i=1;i<=num;i++)
            for(int j=0;j<n;j++)
                printf("%d %d\n",j+1,(j+i)%n+1);
        for(int i=2;i<=n;i+=2)
            printf("%d %d\n%d %d\n",i,n+1,n+1,i-1);
        printf("%d %d\n%d %d\n",1,n+2,n+2,n);
        for(int i=3;i<=n;i+=2)
            printf("%d %d\n%d %d\n",i,n+2,n+2,i-1);
    }
}

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 592K, 提交时间: 2019-04-13 13:59:31 

#include<cstdio>
using namespace std;
int main(){
	int n;
	scanf("%d",&n);
	if(n==4){
		puts("3 4\n1 2\n2 3\n3 4\n4 1");
		return 0;
	}
	if(n%2){
		printf("2 %d\n",n*(n-1)/2);
		for(int i=n;i>3;i-=2){
			for(int j=1;j<=i-2;j++)
				printf("%d %d\n%d %d\n",i,j,j,i-1);
			printf("%d %d\n",i-1,i);
		}
		printf("1 2\n2 3\n3 1");
		return 0;
	}
	printf("2 %d\n1 2\n1 3\n1 4\n2 3\n2 5\n3 4\n3 5\n3 6\n4 2\n4 5\n4 6\n5 1\n5 6\n6 1\n6 2\n",15+(n+5)*(n-6)/2);
	for(int i=8;i<=n;i+=2){
		for(int j=1;j<=i-2;j++)
			printf("%d %d\n%d %d\n",i,j,j,i-1);
		printf("%d %d\n",i-1,i);
	}
	return 0;
}

上一题

© 2024 nowcoder.com