3798-Abs Problem

3798-Abs Problem

时间: 1ms        内存:128M

描述:

Alice and Bob is playing a game, and this time the game is all about the absolute value! Alice has N different positive integers, and each number is not greater than N. Bob has a lot of blank paper, and he is responsible for the calculation things. The rule of game is pretty simple. First, Alice chooses a number a1 from the N integers, and Bob will write it down on the first paper, that's b1. Then in the following kth rounds, Alice will choose a number ak (2 ≤ k ≤ N), then Bob will write the number bk=|ak-bk-1| on the kth paper. |x| means the absolute value of x. Now Alice and Bob want to kown, what is the maximum and minimum value of bN. And you should tell them how to achieve that!

输入:

The input consists of multiple test cases; For each test case, the first line consists one integer N, the number of integers Alice have. (1 ≤ N ≤ 50000)

输出:

For each test case, firstly print one line containing two numbers, the first one is the minimum value, and the second is the maximum value. Then print one line containing N numbers, the order of integers that Alice should choose to achieve the minimum value. Then print one line containing N numbers, the order of integers that Alice should choose to achieve the maximum value. Attention: Alice won't choose a integer more than twice.

示例输入:

2

示例输出:

1 1
1 2
2 1

提示:

参考答案(内存最优[1032]):

#include<stdio.h>
#include<math.h>
int main()
{
    int N,i,j,max,min;
    while(scanf("%d",&N)!=EOF)
    {
        min=N%4;
        max=(N-1)%4;
        if(min==0||min==3)
            min=0;
        else min=1;
        if(max==0||max==3)
            max=0;
        else max=1;
        printf("%d %d\n",min,N-max);

        printf("%d",N);
        for(i=N-1; i>0; i--)
            printf(" %d",i);
        printf("\n");

        printf("%d",N-1);
        for(i=N-2; i>0; i--)
            printf(" %d",i);
        printf(" %d\n",N);
    }
    return 0;
}

参考答案(时间最优[9]):

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <queue>
#include <stack>
#include <map>
using namespace std;
#define up(i,x,y) for(i=x;i<=y;i++)
#define up2(i,x,y) for(i=x;y;i++)
#define down(i,x,y) for(i=x;i>=y;i--)
#define down2(i,x,y) for(i=x;y;i--)
#define pi acos(-1.0)
#define ll long long
#define s(a) scanf("%d",&a)
#define mem(a,b) memset(a,b,sizeof(a))
#define ads(a) (a<0?-a:a)
#define w(a) while(a)

void print(int l,int r,int m)
{
    int i=l,j=r;
    w(i<=j)//while(i<=j)
    {
        if(i==j)		//若两数相等,输出i
        {
            printf("%d ",i);
            break;
        }
        else if(i+1>=j)		//如果j与i相差不过1
        {
            printf("%d %d ",i,j);	//
            break;
        }
        else if(i+2>=j)		//如果j与i相差不过2
        {
            printf("%d %d %d ",i,j,i+1);		//
            break;
        }
        printf("%d %d ",i,i+1);			//其他情况
        i+=2;
        printf("%d %d ",j,j-1);
        j-=2;
    }
    printf("%d",m);
}

int main()
{
    int n,sum,i,j;
    w(~s(n))//while(scanf("%d",n)!=0)
    {
        sum=0;
        up(i,1,n)//for(i=1;i<=n;i++)
        sum+=i;		//把所有数都加起来
        printf("%d %d\n",sum%2,n-(sum-n)%2);		//输出
        if(n%2)										//如果n%2不为0
        {
            print(2,n,1);							//2 n 1传入上面函数
            printf("\n");
            print(1,n-1,n);							//把1 n-1 n传入上面函数
            printf("\n");
        }
        else
        {
            print(3,n,2);
            printf(" 1\n");
            print(2,n-1,1);
            printf(" %d\n",n);
        }
    }
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注