soj1746大数贪心.java

来自「一些ACM题目的解答,主要是soj和poj的」· Java 代码 · 共 51 行

import java.util.*;
import java.math.BigInteger;
public class Main{
    public static void main(String[] args){
        int ncase=1;
        int n;
        Scanner an = new Scanner(System.in);
        while(an.hasNext())
        {
            n = an.nextInt();
            System.out.println("Case "+ ncase++ +":");
            if(n==3)
            {
                System.out.println("2\n1,2");
            }
            else if(n==4)
            {
                System.out.println("3\n1,3");
            }
            else
            {
                int a[] = new int[300];
                int k=(int)(Math.sqrt(2*(n+1)+1.0/4)-1.0/2);
                int i;
                for(i=0;i<=k-2;i++)
                {
                    a[i]=i+2;
                }
                n-=(k+2)*(k-1)/2;
                while(n>0)
                {
                    int j;
                    for(j=k-2;j>=0&&n>0;j--)
                    {
                        a[j]++;
                        n--;
                    }
                }
                BigInteger result = new BigInteger(""+a[0]);
                for(i=1;i<=k-2;i++)
                    result=result.multiply(new BigInteger(""+a[i]));
                System.out.println(result);
                System.out.print(a[0]);
                for(i=1;i<=k-2;i++)
                    System.out.print(","+a[i]);
                System.out.println();
            }
        }
    }
}