NC215117. Interpretability
描述
小西和Antinomy在翻A+级比赛答辩的PPT时,发现PPT里列举的诸多指标之间都有相互支撑的关系,他们共同组织成了让评委看起来觉得很厉害同时也能站得住脚的观感。
说到站得住脚,众所周知三角形具有良好的稳定性,小西和Antinomy还发现,这一堆PPT列出的指标里,每个指标都有一个可信度。
如果任意三个指标的可信度,将其视为长度时能组成一个三角形的话,那么这三个指标就能相互支撑,从而看起来站得住脚。
经过整理之后发现,每个指标的可信度都是的正整数次幂,且可信度为的指标有个,只考虑三个指标相互支撑的情况,每个指标只能被用在一个相互支撑的三角形里。
现在Antinomy和小西想知道,给定一个数字,以及个数字,这些指标最多能形成多少个相互支撑的三角形体系?
输入描述
第一行输入一个数字
接下来一行有单个空格分隔的个数字,分别表示,即可信度为的指标有个,例如如果,那么表示有个长度为的指标。
输出描述
输出一行一个整数表示最多能形成多少个三角形体系。
示例1
输入:
3 1 1 1
输出:
0
示例2
输入:
5 1 2 2 2 2
输出:
3
示例3
输入:
3 3 3 3
输出:
3
C 解法, 执行用时: 50ms, 内存消耗: 316K, 提交时间: 2023-03-01 20:30:43
#include<stdio.h> int count=0; int main() { long long i,n,m,k,t,sum=0; scanf("%lld",&n); for(i=0;i<n;i++) { scanf("%lld",&k); sum+=k; } if(sum<=3) printf("0"); else{ printf("%lld",sum/3); } }
pypy3(pypy3.6.1) 解法, 执行用时: 170ms, 内存消耗: 44916K, 提交时间: 2020-12-19 13:56:05
n = int(input()) l = map(int, input().split()) lst, ans = 0, 0 for x in l: tmp = min(x // 2, lst) x -= tmp * 2 lst -= tmp ans += tmp ans += x // 3 x %= 3 lst += x print(ans)
Python3 解法, 执行用时: 535ms, 内存消耗: 39488K, 提交时间: 2021-12-12 09:52:56
n=input() m=list(map(int,input().split(' '))) a=0 b=0 for i in range(len(m)): if a+m[i]<3: a=m[i] else: b+=(a+m[i])//3 c=(a+m[i])//3 a=(a+m[i])%3 print(b)
C++(clang++11) 解法, 执行用时: 44ms, 内存消耗: 512K, 提交时间: 2020-12-20 13:02:13
#include<cstdio> int main(){ long long s,n,a; scanf("%lld",&n); while(n--) scanf("%lld",&a),s+=a; printf("%lld\n",s/3); }