我是靠谱客的博主 懦弱蜻蜓,这篇文章主要介绍2015多校联合训练赛 hdu 5308 I Wanna Become A 24-Point Master 2015 Multi-University Training Contest 2 构造题 I Wanna Become A 24-Point Master,现在分享给大家,希望可以做个参考。
I Wanna Become A 24-Point Master
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 60 Accepted Submission(s): 16
Special Judge
Problem Description
Recently Rikka falls in love with an old but interesting game -- 24 points. She wants to become a master of this game, so she asks Yuta to give her some problems to practice.
Quickly, Rikka solved almost all of the problems but the remained one is really difficult:
In this problem, you need to write a program which can get 24 points with n numbers, which are all equal to n .
Quickly, Rikka solved almost all of the problems but the remained one is really difficult:
In this problem, you need to write a program which can get 24 points with n numbers, which are all equal to n .
Input
There are no more then 100 testcases and there are no more then 5 testcases with
n≥100
. Each testcase contains only one integer
n (1≤n≤105)
Output
For each testcase:
If there is not any way to get 24 points, print a single line with -1.
Otherwise, let A be an array with 2n−1 numbers and at firsrt Ai=n (1≤i≤n) . You need to print n−1 lines and the i th line contains one integer a , one char b and then one integer c, where 1≤a,c<n+i and b is "+","-","*" or "/". This line means that you let Aa and Ac do the operation b and store the answer into An+i .
If your answer satisfies the following rule, we think your answer is right:
1. A2n−1=24
2. Each position of the array A is used at most one tine.
3. The absolute value of the numerator and denominator of each element in array A is no more than 109
If there is not any way to get 24 points, print a single line with -1.
Otherwise, let A be an array with 2n−1 numbers and at firsrt Ai=n (1≤i≤n) . You need to print n−1 lines and the i th line contains one integer a , one char b and then one integer c, where 1≤a,c<n+i and b is "+","-","*" or "/". This line means that you let Aa and Ac do the operation b and store the answer into An+i .
If your answer satisfies the following rule, we think your answer is right:
1. A2n−1=24
2. Each position of the array A is used at most one tine.
3. The absolute value of the numerator and denominator of each element in array A is no more than 109
Sample Input
4
Sample Output
1 * 2 5 + 3 6 + 4
Source
2015 Multi-University Training Contest 2
题意:
输入N。用N个N通过加减乘除得到24.中间过程得到的数字可以用分数表示,不能截断小数。
分析:前几个数字打表吧。很容易写的。但是我队员(GMY)也是写的很辛苦啊。========(现在看到是修改过后的,所以打表的部分少了)
后面的数字这样处理:
选a个N相加 使得|a*N-24|最小,这样做的目的是为了减少用于构造24的N的使用量。
且令b = |24-a*N| (a*N+b = 24 或者a*N-b = 24)构造这个等式就可以了。
那么用b+1个N就能构造 b了 。方法: (N *b)/N = b
剩下left = N - a - b - 1个N。用left个N构造0即可。
显然left >= 2 (7特判了,就不怕有bug了)
如果left 为奇数
构造 (N*(left/2) - N(left/2))/N = 0
否则 构造 N*(left/2) - N(left/2) = 0
所以left个N一定可以构造出0的
最后看b > 0 那么用a*N - b
否则用a*N + b
当然要特别考虑b = 0,的情况。
因为保证left > 0 了。所以先构造出0.方便后面的运算。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
int n;
while(~scanf("%d",&n))
{
if( n == 1 || n == 2 || n == 3 ){
printf("-1n");
}
else if( n == 4 )
printf("1 * 2n5 + 3n6 + 4n");
else if( n == 5 )
printf("1 * 2n6 * 3n7 - 4n8 / 5n");
else if( n == 7 )
printf("1 + 2n8 + 3n4 + 5n10 + 6n11 / 7n9 + 12n"); //为了保证left > 1 n = 7 特判
else {
int i,j,k,q,p,left,need;
for(i = 0;;i++){
if(abs(i*n - 24) <= abs(i*n+n-24) )
break;
}
int a = i; //算出几个N相加会最接近于24
int fx = 24 - a*n; //算出 24 - a * N 关于0的大小
if( abs(24-a*n) > 0 )need = abs(24-a*n) + 1;
else need = 0; //算出需要need个N来构造 出|24 - a*N|
left = n - need - i; //用left个N构造出0
//用left个N构造0
printf("1 - 2n");
p = n + 1;
i = 3;
j = 0;
for(;i <= (left - left% 2); ){
if(j & 1 ){
printf("%d - %dn",p++,i++);
}
else printf("%d + %dn",p++,i++);
j ^= 1;
}
//left 为奇数,多计算一次 0 / N
if(left % 2 == 1){
printf("%d / %dn",p++,i++);
}
//构造a个N相加的和
q = i;
for(i = 0;i < a; i++){
printf("%d + %dn",p++,q++);
}
int xp;
if(need > 0){
//need = 2 直接做除法,否则先做加法,最后做除法
if(need != 2){
printf("%d + %dn",q,q+1);
q += 2;
xp = p + 1;
for(; q < n; ){
printf("%d + %dn",xp++,q++);
}
printf("%d / %dn",xp++,q++);
}
else {
printf("%d / %dn",q,q+i);
xp = p + 1;
}
//判断是加法还是减法
if(fx > 0)
printf("%d + %dn",p,xp);
else
printf("%d - %dn",p,xp);
}
}
}
return 0;
}
最后
以上就是懦弱蜻蜓最近收集整理的关于2015多校联合训练赛 hdu 5308 I Wanna Become A 24-Point Master 2015 Multi-University Training Contest 2 构造题 I Wanna Become A 24-Point Master的全部内容,更多相关2015多校联合训练赛内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复