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 withn 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
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, letA 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 arrayA is
used at most one tine.
3. The absolute value of the numerator and denominator of each element in arrayA is
no more than 109
If there is not any way to get 24 points, print a single line with -1.
Otherwise, let
If your answer satisfies the following rule, we think your answer is right:
1.
2. Each position of the array
3. The absolute value of the numerator and denominator of each element in array
Sample Input
4
Sample Output
1 * 2 5 + 3 6 + 4
Source
题意：
输入N。
用N个N通过加减乘除得到24.中间过程得到的数字能够用分数表示，不能截断小数。
分析：前几个数字打表吧。非常easy写的。可是我队员（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("-1
");
}
else if( n == 4 )
printf("1 * 2
5 + 3
6 + 4
");
else if( n == 5 )
printf("1 * 2
6 * 3
7 - 4
8 / 5
");
else if( n == 7 )
printf("1 + 2
8 + 3
4 + 5
10 + 6
11 / 7
9 + 12
"); //为了保证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 - 2
");
p = n + 1;
i = 3;
j = 0;
for(;i <= (left - left% 2); ){
if(j & 1 ){
printf("%d - %d
",p++,i++);
}
else printf("%d + %d
",p++,i++);
j ^= 1;
}
//left 为奇数。多计算一次 0 / N
if(left % 2 == 1){
printf("%d / %d
",p++,i++);
}
//构造a个N相加的和
q = i;
for(i = 0;i < a; i++){
printf("%d + %d
",p++,q++);
}
int xp;
if(need > 0){
//need = 2 直接做除法，否则先做加法，最后做除法
if(need != 2){
printf("%d + %d
",q,q+1);
q += 2;
xp = p + 1;
for(; q < n; ){
printf("%d + %d
",xp++,q++);
}
printf("%d / %d
",xp++,q++);
}
else {
printf("%d / %d
",q,q+i);
xp = p + 1;
}
//推断是加法还是减法
if(fx > 0)
printf("%d + %d
",p,xp);
else
printf("%d - %d
",p,xp);
}
}
}
return 0;
}