CF #278 (Div. 2) B.(暴力枚举+推导公式+数学构造)

2024-09-07 19:58

本文主要是介绍CF #278 (Div. 2) B.(暴力枚举+推导公式+数学构造),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

B. Candy Boxes
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
题目链接: http://codeforces.com/contest/488/problem/B

There is an old tradition of keeping 4 boxes of candies in the house in Cyberland. The numbers of candies are special if their arithmetic mean, their median and their range are all equal. By definition, for a set {x1, x2, x3, x4} (x1 ≤ x2 ≤ x3 ≤ x4arithmetic mean is median is  and range is x4 - x1The arithmetic mean and median are not necessary integer. It is well-known that if those three numbers are same, boxes will create a "debugging field" and codes in the field will have no bugs.

For example, 1, 1, 3, 3 is the example of 4 numbers meeting the condition because their mean, median and range are all equal to 2.

Jeff has 4 special boxes of candies. However, something bad has happened! Some of the boxes could have been lost and now there are only n (0 ≤ n ≤ 4) boxes remaining. The i-th remaining box contains ai candies.

Now Jeff wants to know: is there a possible way to find the number of candies of the 4 - n missing boxes, meeting the condition above (the mean, median and range are equal)?

Input

The first line of input contains an only integer n (0 ≤ n ≤ 4).

The next n lines contain integers ai, denoting the number of candies in the i-th box (1 ≤ ai ≤ 500).

Output

In the first output line, print "YES" if a solution exists, or print "NO" if there is no solution.

If a solution exists, you should output 4 - n more lines, each line containing an integer b, denoting the number of candies in a missing box.

All your numbers b must satisfy inequality 1 ≤ b ≤ 106. It is guaranteed that if there exists a positive integer solution, you can always find such b's meeting the condition. If there are multiple answers, you are allowed to print any of them.

Given numbers ai may follow in any order in the input, not necessary in non-decreasing.

ai may have stood at any positions in the original set, not necessary on lowest n first positions.

Sample test(s)
input
2
1
1
output
YES
3
3
input
3
1
1
1
output
NO
input
4
1
2
2
3
output
YES
Note

For the first sample, the numbers of candies in 4 boxes can be 1, 1, 3, 3. The arithmetic mean, the median and the range of them are all2.

For the second sample, it's impossible to find the missing number of candies.

In the third example no box has been lost and numbers satisfy the condition.

You may output b in any order.



解题思路:

题目大意就是要构造四个数,要求这四个数的 平均数 == 中位数 == 极差。给你n个数,问你能否构造出这样的序列。

首先推导公式: (a + b + c + d) / 4 == (b + c) / 2 == d - a       ------------->>>>>>       d : a = 3 : 1 && a + d == b + c  -------->>>>>>>>  序列应该满足(x , y , 4 * x - y , 3 * x )。

由于题目给出a[ i ] 在[ 1 , 500 ]之间,所以对于x 在[ 1 , 500 ]内暴力枚举,相应的y在[ x , 3 * x ]内枚举,每次得出相应符合条件的四个数。然后判断给出的n个数是否和当前满足条件的数组进行匹配,如果发现匹配数正好等于n的话,说明可以构造出满足条件的序列。



完整代码:

#include <functional>
#include <algorithm>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <numeric>
#include <cstring>
#include <climits>
#include <cassert>
#include <complex>
#include <cstdio>
#include <string>
#include <vector>
#include <bitset>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <list>
#include <set>
#include <map>
using namespace std;#pragma comment(linker, "/STACK:102400000,102400000")typedef long long LL;
typedef double DB;
typedef unsigned uint;
typedef unsigned long long uLL;/** Constant List .. **/ //{const int MOD = int(1e9)+7;
const int INF = 0x3f3f3f3f;
const LL INFF = 0x3f3f3f3f3f3f3f3fLL;
const DB EPS = 1e-9;
const DB OO = 1e20;
const DB PI = acos(-1.0); //M_PI;
const int maxn = 10001;int a[maxn];
int res[maxn];
int c[5];
int vis[5];
int main()
{#ifdef DoubleQfreopen("in.txt","r",stdin);#endifint n;while(~scanf("%d",&n)){for(int i = 1; i <= n ; i ++)scanf("%d",&a[i]);int flag = 0;int s;for(int x = 1; x <= 500 ; x ++){for(int y = x ; y <= 3 * x ; y ++){c[1] = x;c[2] = y;c[3] = 4 * x - y;c[4] = 3 * x;int cnt = 0;memset(vis , 0 ,sizeof(vis));for(int i = 1 ; i <= n ; i ++){for(int j = 1 ; j <= 4 ; j ++){if(a[i] == c[j] && !vis[j]){vis[j] = 1;cnt ++;break;}}}if(cnt == n){s = 0;for(int i = 1 ; i <= 4 ; i ++){if(!vis[i]){res[s++] = c[i];}}flag = 1;break;}}if(flag)break;}if(flag){sort(res , res + s);printf("YES\n");for(int i = 0 ; i <  s ; i ++){printf("%d\n", res[i]);}}else{printf("NO\n");}}
}


这篇关于CF #278 (Div. 2) B.(暴力枚举+推导公式+数学构造)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/1146014

相关文章

Java 枚举的基本使用方法及实际使用场景

《Java枚举的基本使用方法及实际使用场景》枚举是Java中一种特殊的类,用于定义一组固定的常量,枚举类型提供了更好的类型安全性和可读性,适用于需要定义一组有限且固定的值的场景,本文给大家介绍Jav... 目录一、什么是枚举?二、枚举的基本使用方法定义枚举三、实际使用场景代替常量状态机四、更多用法1.实现接

使用Python开发Markdown兼容公式格式转换工具

《使用Python开发Markdown兼容公式格式转换工具》在技术写作中我们经常遇到公式格式问题,例如MathML无法显示,LaTeX格式错乱等,所以本文我们将使用Python开发Markdown兼容... 目录一、工具背景二、环境配置(Windows 10/11)1. 创建conda环境2. 获取XSLT

C 语言中enum枚举的定义和使用小结

《C语言中enum枚举的定义和使用小结》在C语言里,enum(枚举)是一种用户自定义的数据类型,它能够让你创建一组具名的整数常量,下面我会从定义、使用、特性等方面详细介绍enum,感兴趣的朋友一起看... 目录1、引言2、基本定义3、定义枚举变量4、自定义枚举常量的值5、枚举与switch语句结合使用6、枚

Java枚举类实现Key-Value映射的多种实现方式

《Java枚举类实现Key-Value映射的多种实现方式》在Java开发中,枚举(Enum)是一种特殊的类,本文将详细介绍Java枚举类实现key-value映射的多种方式,有需要的小伙伴可以根据需要... 目录前言一、基础实现方式1.1 为枚举添加属性和构造方法二、http://www.cppcns.co

利用Python实现添加或读取Excel公式

《利用Python实现添加或读取Excel公式》Excel公式是数据处理的核心工具,从简单的加减运算到复杂的逻辑判断,掌握基础语法是高效工作的起点,下面我们就来看看如何使用Python进行Excel公... 目录python Excel 库安装Python 在 Excel 中添加公式/函数Python 读取

C#实现获得某个枚举的所有名称

《C#实现获得某个枚举的所有名称》这篇文章主要为大家详细介绍了C#如何实现获得某个枚举的所有名称,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... C#中获得某个枚举的所有名称using System;using System.Collections.Generic;usi

使用C#代码计算数学表达式实例

《使用C#代码计算数学表达式实例》这段文字主要讲述了如何使用C#语言来计算数学表达式,该程序通过使用Dictionary保存变量,定义了运算符优先级,并实现了EvaluateExpression方法来... 目录C#代码计算数学表达式该方法很长,因此我将分段描述下面的代码片段显示了下一步以下代码显示该方法如

Java 枚举的常用技巧汇总

《Java枚举的常用技巧汇总》在Java中,枚举类型是一种特殊的数据类型,允许定义一组固定的常量,默认情况下,toString方法返回枚举常量的名称,本文提供了一个完整的代码示例,展示了如何在Jav... 目录一、枚举的基本概念1. 什么是枚举?2. 基本枚举示例3. 枚举的优势二、枚举的高级用法1. 枚举

Rust中的Option枚举快速入门教程

《Rust中的Option枚举快速入门教程》Rust中的Option枚举用于表示可能不存在的值,提供了多种方法来处理这些值,避免了空指针异常,文章介绍了Option的定义、常见方法、使用场景以及注意事... 目录引言Option介绍Option的常见方法Option使用场景场景一:函数返回可能不存在的值场景

uva 10014 Simple calculations(数学推导)

直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导,第二次没有继续下去。 代码: #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf