HDU 5308 I Wanna Become A 24-Point Master
2024-10-01 07:25:25
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=5308
题面:
I Wanna Become A 24-Point Master
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 602 Accepted Submission(s): 249
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)
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 ith
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 ith
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
解题:
如此之大的数据量,搜索是肯定不行。但还是被题目那句大于100的数据不会超过5组给蒙了一下。队友之前想着能不能从24往前搜,实则也是不行的。
由于根本不知道前面到底有什么数。又该相应如何的操作。看了题解后,恍然大悟。就应该去构造。
枚举n比較小的情况,然后当n大于等于14时,能够去凑((4*n)/n)*((6*n)/n),尽管是12个n,可是仍要从14,開始,由于多余的n须要通过一次减法,多次乘法消去。最后再加上之前算出的24就可以。
代码:
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
int main()
{
int n,tmp;
while(~scanf("%d",&n))
{
// printf("%d:\n",n);
if(n<=3)
printf("-1\n");
else if(n==4)
printf("1 * 2\n5 + 3\n6 + 4\n");
else if(n==5)
printf("1 * 2\n3 / 6\n4 - 7\n5 * 8\n");
else if(n==6)
printf("1 + 2\n3 + 4\n5 - 6\n7 + 8\n10 - 9\n");
else if(n==7)
printf("1 + 2\n3 + 8\n9 / 4\n10 + 5\n11 + 6\n12 + 7\n");
else if(n==8)
printf("1 + 2\n3 + 9\n4 - 5\n11 * 6\n12 * 7\n13 * 8\n10 + 14\n");
else if(n==9)
printf("1 + 2\n3 + 10\n4 / 5\n6 / 7\n8 / 9\n11 - 12\n15 - 13\n 16 - 14\n");
else if(n==10)
printf("1 + 2\n3 / 4\n5 / 6\n7 / 8\n9 / 10\n11 + 12\n16 + 13\n17 + 14\n18 + 15\n");
else if(n==11)
printf("1 + 2\n3 / 4\n5 / 6\n7 - 8\n15 * 9\n16 * 10\n17 * 11\n12 + 13\n19 + 14\n20 + 18\n");
else if(n==12)
printf("1 + 2\n3 - 4\n5 * 14\n6 * 15\n7 * 16\n8 * 17\n9 * 18\n10 * 19\n11 * 20\n12 * 21\n13 + 22\n");
else if(n==13)
printf("1 + 2\n3 / 4\n5 / 6\n7 - 8\n17 * 9\n18 * 10\n19 * 11\n20 * 12\n21 * 13\n22 + 14\n23 - 15\n24 - 16\n");
else
{
printf("1 + 2\n3 + 4\n5 + 6\n7 + 8\n9 + 10\n");
printf("%d + %d\n%d + %d\n%d + %d\n",n+1,n+2,n+3,n+4,n+5,n+6);
printf("%d / 11\n%d / 12\n",n+7,n+8);
printf("%d * %d\n",n+9,n+10);
printf("13 - 14\n");
tmp=n-14;
int i;
for(i=0;i<tmp;i++)
{
printf("%d * %d\n",n+12+i,15+i);
}
printf("%d + %d\n",n+11,n+12+tmp);
}
// printf("\n");
}
return 0;
}
最新文章
- Java01
- 【编程题目】如何对n个数进行排序,要求时间复杂度O(n),空间复杂度O(1)
- 关于如何来构造一个String类
- sql server 导出数据到 Azure Hbase / Hive 详细步骤
- HALCON基础知识
- hibernate的id生成策略
- JavaScript代码性能优化总结
- Memcache的基本应用
- show_space/get_alert_log/get_trace_file
- requireJS配置选项
- haproxy path_beg
- 在Centos 5.4上安装Mysql5.5.10 (整理以前的工作文档)
- CKEditor上传插件
- IOS真机Profile时调用树中的对象只是显示地址,没有显示symbol name
- NoSession问题
- String的内存模型,为什么String被设计成不可变的
- bzoj 4826: [Hnoi2017]影魔 [主席树 单调栈]
- Leetcode_66_Plus One
- Web(二)
- 超实用教程,教你用墨刀做出小红书app原型
热门文章
- 二进制部署Kubernetes-v1.14.1集群
- BZOJ 4525 二分
- 2015 多校赛 第七场 1011 (hdu 5379)
- HDU 4474 Yet Another Multiple Problem BFS
- C - Fafa and his Company
- C#利用ICSharpCode将远程文件打包并下载
- CSS清除浮动_清除float浮——详解overflow:hidden 与clear:both属性
- 能够附加图片的标签控件iOS项目源码
- Morse理论:拓扑不变性特征匹配原理
- 使用NDK编译VTK