2015多校联合训练赛 hdu 5308 I Wanna Become A 24-Point Master 2015 Multi-University Training Contest 2 构造题 I Wanna Become A 24-Point Master

106 阅读 0 评论 70 点赞

我是靠谱客的博主懦弱蜻蜓，这篇文章主要介绍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 .

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

Sample Input

Sample Output

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;
}