列表

详情

NC25112. 121045 / 妈妈的考试

描述

又是 Grace Field House 日常的一天。
大家在紧张的氛围中做完了今天的考试题目。一如既往地，最年长的三个人得到了满分。
这一次的考试一共有 n 道题目，每道题目都是客观题，只有对或错两种结果，所以一份考卷的最终结果只有 种。我们用 s_i 表示一份考卷中第 i 道题的分数。假如这份考卷中该题答案正确，那么这题得 1 分；否则得 -1 分。即，如果第 i 题答案正确，那么 ；否则 。
妈妈对于每份考试有两个评分参数 w_0 和 w_1 。其计算方式为：
 

可爱的柯尼想要知道，对于一份 n 道题的考卷，在其全部的 种答题结果中，当 时， w_1 最小可以是多少？
而柯尼手里的可爱的小兔兔想要知道，对于一份 n 道题的考卷，在其全部的 种答题结果中，当 时， w_1 最大可以是多少？

输入描述

第一行一个正整数 T ，表示有 T 次询问。
接下去 T 行，每行一个正整数 n ，表示一次询问。

输出描述

输出共 T 行，每行两个整数，表示一组询问的答案。

对于每一组数据，先输出柯尼的询问的答案，然后用一个空格隔开，再输出小兔兔的询问的答案，之后换一行。

示例1

输入: 

3
3
4
10

输出: 

1 1
2 2
8 8

说明:

当 n=3 时：
- 对于第一个询问，一种可行的最优的答题结果为 [\checkmark, \checkmark, \checkmark] ，则分数为 [1, 1, 1] ，此时 w_0 = 3, w_1 = 1> 0 。
- 对于第二个询问，一种可行的最优的答题结果为 [✗, \checkmark, ✗] ，则分数为 [-1, 1, -1] ，此时 w_0 = -1 < 0, w_1 = 1 。

当 n=4 时：
- 对于第一个询问，一种可行的最优的答题结果为 [✗, ✗, \checkmark, ✗] ，则分数为 [-1, -1, 1, -1] ，此时 w_0=-2, w_1=2>0 。
- 对于第二个询问，一种可行的最优的答题结果为 [✗, \checkmark, ✗, ✗] ，则分数为 [-1, 1, -1, -1] ，此时 w_0=-2<0, w_1=2 。

原站题解

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

C++14(g++5.4) 解法, 执行用时: 700ms, 内存消耗: 5084K, 提交时间: 2019-08-23 09:56:30 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
ll  t,n,tt;
i128  mn,mx;
  
i128 js(ll x)
{
    i128 y=x;
    return (y*(y*y-3*(i128)n+2))/6;
}
  
i128 abss(i128 x)
{
    return x<0?-x:x;
}
  
  
void out(i128 x)
{
    int a[110],na=0;
    if(!x)cout<<0;
    else
    {
        while(x)a[++na]=x%10,x/=10;
        for(int i=na;i>=1;i--)cout<<a[i];
    }
}
  
int main()
{
    ll t;
    cin>>t;
    while(t--)
    {
        cin>>tt;
        n=tt;
        mn=2e18;
        if(n%2)mn=min(mn,-js(1));
        else mn=min(mn,-js(2));
        ll c1=sqrt(3.0*n-2.0);
        ll c2=sqrt((3.0*n-2)/3.0);
        //c1--;
        if((n%2)!=(c1%2))c1--;
        if(js(c1-2)!=0)mn=min(mn,abss(js(c1-2)));
        if(js(c1)!=0)mn=min(mn,abss(js(c1)));
        if(c1+2<=n&&js(c1+2)!=0)mn=min(mn,abss(js(c1+2)));
        if(c1+4<=n&&js(c1+4)!=0)mn=min(mn,abss(js(c1+4)));
          
        mx=0;
        if((n%2)!=(c2%2))c2--;
        if(js(c2-2)<0)mx=max(mx,-js(c2-2));
        if(js(c2)<0)mx=max(mx,-js(c2));
        if(c2+2<=n&&js(c2+2)<0)mx=max(mx,-js(c2+2));
        if(c2+4<=n&&js(c2+4)<0)mx=max(mx,-js(c2+4));
        //cout<<(ll)mn<<" "<<(ll)mx<<endl;
        out(mn);putchar(' ');out(mx);putchar('\n');
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 1053ms, 内存消耗: 6924K, 提交时间: 2019-05-20 10:14:05 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
ll  t,n,tt;
i128  mn,mx;

i128 js(ll x)
{
	i128 y=x;
	return (y*(y*y-3*(i128)n+2))/6;
}

i128 abss(i128 x)
{
	return x<0?-x:x;
}


void out(i128 x)
{
	int a[110],na=0;
	if(!x)cout<<0;
	else
	{
		while(x)a[++na]=x%10,x/=10;
		for(int i=na;i>=1;i--)cout<<a[i];
	}
}

int main()
{
    ll t;
    cin>>t;
	while(t--)
	{
		cin>>tt;
		n=tt;
		mn=2e18;
		if(n%2)mn=min(mn,-js(1));
		else mn=min(mn,-js(2));
		ll c1=sqrt(3.0*n-2.0);
		ll c2=sqrt((3.0*n-2)/3.0);
		//c1--;
		if((n%2)!=(c1%2))c1--;
		if(js(c1-2)!=0)mn=min(mn,abss(js(c1-2)));
		if(js(c1)!=0)mn=min(mn,abss(js(c1)));
		if(c1+2<=n&&js(c1+2)!=0)mn=min(mn,abss(js(c1+2)));
		if(c1+4<=n&&js(c1+4)!=0)mn=min(mn,abss(js(c1+4)));
		
		mx=0;
		if((n%2)!=(c2%2))c2--;
		if(js(c2-2)<0)mx=max(mx,-js(c2-2));
		if(js(c2)<0)mx=max(mx,-js(c2));
		if(c2+2<=n&&js(c2+2)<0)mx=max(mx,-js(c2+2));
		if(c2+4<=n&&js(c2+4)<0)mx=max(mx,-js(c2+4));
		//cout<<(ll)mn<<" "<<(ll)mx<<endl;
		out(mn);putchar(' ');out(mx);putchar('\n');
	}
	return 0;
}

Python3(3.5.2) 解法, 执行用时: 3911ms, 内存消耗: 8024K, 提交时间: 2019-05-10 20:59:25 

T=int(input())
while T>0:
    n=int(input())
    T-=1
    ans2=-n*n*n-1000000
    if (n%2==1):
        ans1=(n-1)//2
    else:
        ans1=n-2
    z=(3*n-2)**0.5
    for i in range(12):
        y=abs(int(z+i-6))
        if (y%2==n%2):
            t=(y*y*y-(3*n-2)*y)//6
            if (t<0):
                t=-t
            if (t>0 and t<ans1):
                ans1=t
    x=-int(((3*n-2)/3)**0.5)    
    for i in range(12):
        if (abs(x+i-6)%2==n%2):
            if (x+i-6>0):
                break
            y=x+i-6
            y=(y*y*y-(3*n-2)*y)//6
            if (y>ans2):
                ans2=y
    print(ans1,ans2)

上一题

© 2024 nowcoder.com