首页 > ACM题库 > HDU-杭电 > hdu 2886 Lou 1 Zhuang待解决[解题报告]C++
2014
02-17

hdu 2886 Lou 1 Zhuang待解决[解题报告]C++

Lou 1 Zhuang

问题描述 :

All members of Hulafly love playing the famous network game called ‘Lou 1 Zhuang’ so much that Super Da Lord got mad with them. So he thought over and over and finally came up with a good idea to stop them. He consulted an ACM master and asked for the hardest problem ever in the world. Hulafly must solve this problem in order to get permission of playing ‘Lou 1 Zhuang’. They, however, are so eager to play ‘Lou 1 zhuang’ and have no interest in this problem at all, so they turn to you for help. You can do this only if you swear that you will never tell Da Lord that you have helped them.’Lou 1 Zhuang’ is a game with only one but a very tall buiding in it and everybody runs a shop in this buiding —- either a cake shop or a barbershop, each one occupies a whole floor. (Log in at www.xiaonei.com and check details at http://apps.xiaonei.com/soletower/tower.php?origin=2807) Super Da Lord asks that if the buiding is N stories high, how can we devided the floors(or the shops) and multiply the number of floors(or shops) in each part to make the product P as large as possible. Neverthless, Super Da Lord thought that it’s still too hard for them, so he gave them some hints, he said:”Go and find the solutoin in ‘Lou 1 Zhuang’!”

Given the buidings’ height N, you are to find the largest P.

输入:

The buidings’ height N. (1 <= N <= 10^9)

输出:

The buidings’ height N. (1 <= N <= 10^9)

样例输入:

1
2
3
4

样例输出:

1
2
3
4
Hint

Hint You can apply to be huhupao, flytosky and koala’s friends at xiaonei.com.

题目意思:若干个整数的和为n, 求它们的乘积的最大值。

参考思路:假设其中有一个整数k>=4, 则2 *(k – 2) – k = k – 4 >= 0,则2 * (k – 2) >= k, 我们把k替换为2、(k – 2),其它数字不变,则它们的和仍然是1976,而它们的乘积只有可能更大。所以我们可以假设,取到最大乘积时,只含有2,3两种正整数。

另一方面, 我们把其中的3个2更换为2个3,和仍然保持不变,但是3*3>2*2*2,所以要使乘积最大,最多只能有2个2。
CODE:

#include<iostream>
using namespace std;
int main()
{
    int n;
    while(~scanf("%d", &n))
    {
        if (n < 5)
        {
            printf("%d\n",n);
            continue;
        }
        int two=1;
        while(n%3)
            two*=2,n-=2;
        int a=3,b=n/3,k=1;
        while(b>1)
        {
            if(b&1)
                k=k*a%2009;
            a=a*a%2009;
            b>>=1;
        }
        printf("%d\n",two*a*k%2009);
    }
    return 0;
}

 


  1. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  2. #include <cstdio>
    #include <cstring>

    const int MAXSIZE=256;
    //char store[MAXSIZE];
    char str1[MAXSIZE];
    /*
    void init(char *store) {
    int i;
    store['A']=’V', store['B']=’W',store['C']=’X',store['D']=’Y',store['E']=’Z';
    for(i=’F';i<=’Z';++i) store =i-5;
    }
    */
    int main() {
    //freopen("input.txt","r",stdin);
    //init(store);
    char *p;
    while(fgets(str1,MAXSIZE,stdin) && strcmp(str1,"STARTn")==0) {
    if(p=fgets(str1,MAXSIZE,stdin)) {
    for(;*p;++p) {
    //*p=store[*p]
    if(*p<’A’ || *p>’Z') continue;
    if(*p>’E') *p=*p-5;
    else *p=*p+21;
    }
    printf("%s",str1);
    }
    fgets(str1,MAXSIZE,stdin);
    }
    return 0;
    }