首页 > 代码库 > hdu 5312 Sequence(数学推导——三角形数)

hdu 5312 Sequence(数学推导——三角形数)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=5312

Sequence

Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1336    Accepted Submission(s): 410


Problem Description
Today, Soda has learned a sequence whose n技术分享-th(n1)技术分享 item is 3n(n?1)+1技术分享. Now he wants to know if an integer m技术分享 can be represented as the sum of some items of that sequence. If possible, what are the minimum items needed?



For example, 22=19+1+1+1=7+7+7+1技术分享.

 

Input
There are multiple test cases. The first line of input contains an integerT技术分享(1T10技术分享4技术分享)技术分享, indicating the number of test cases. For each test case:

There‘s a line containing an integer m技术分享(1m10技术分享9技术分享)技术分享.
 

Output
For each test case, output ?1技术分享 if m技术分享 cannot be represented as the sum of some items of that sequence, otherwise output the minimum items needed.
 

Sample Input
10 1 2 3 4 5 6 7 8 22 10
 

Sample Output
1 2 3 4 5 6 1 2 4 4
 

Source
BestCoder 1st Anniversary ($)
 
题目大意:给出一个序列3*n*(n-1)+1。再输入一个m,求构成给定n所需的最小个数。

(序列中的没一个数能够使用若干次)

解题思路:明白一下N*(N-1)/2为三角形数。性质:随意一个自然数都最多可由三个三角形数表示。 题目给的序列是3*n*(n-1)+1就能够转换为6*n*(n-1)/2+1。对于给定的值m,假如m须要k个数来表示。那么其一组解能够表示为m= 6*(K个三角形数的和)+K; 即随意由k个数组成的解 都有 (m-K)%6==0;那么仅仅要找到最小的k即为所求。
此外。对于序列的通式。当n=1或者n=2的时候,就会没有意义,所以对于1和2的时候须要特殊推断一下。
这是一道三角形数的推导及运用题目。

详见代码 。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

int a[100005];

bool check1(int m)
{
    for (int i=1; i<20010; i++)
    {
        if (a[i]==m)
            return 1;
    }
    return 0;
}

bool check2(int m)
{
    int j;
    for (int i=1,j=20010-1; i<20010&&a[i]<m; i++)
    {
        while (a[i]+a[j]>m)
            j--;
        if (a[i]+a[j]==m)
            return 1;
    }
    return 0;
}

int main()
{
    for (int i=0; i<20010; i++)
    {
        a[i]=3*i*(i-1)+1;
    }
    int t;
    scanf("%d",&t);
    while (t--)
    {
        int m;
        scanf("%d",&m);
        int flag=0;
        if (check1(m))
        {
            printf ("1\n");
            continue;
        }
        else if (check2(m))
        {
            printf ("2\n");
            continue;
        }
        else
        {
            for (int i=3; i<=8; i++) //循环到8的原因是由于模6的余数仅仅有0-5六个
            {
                if ((m-i)%6==0)
                {
                    printf ("%d\n",i);
                    flag=1;
                    break;
                }
            }
        }
        if (flag==0)
        {
            printf ("-1\n");

        }
    }
    return 0;
}



hdu 5312 Sequence(数学推导——三角形数)