UVA 10079 - Pizza Cutting

￡神魔★判官ぃ 2022-08-09 13:47 2阅读 0赞

Time Limited: 8.333 Seconds

When someone calls Ivan lazy, he claimsthat it is his intelligence that helps him to be so. If his intelligence allowshim to do something at less physical effort, why should he exert more? He alsoclaims that he always uses his brain and tries to do some work at less effort;this is not his laziness, rather this is his intellectual smartness.

Once Ivan was asked to cut a pizza intoseven pieces to distribute it among his friends. (Size of the pieces may not bethe same. In fact, his piece will be larger than the others.) He thought a bit,and came to the conclusion that he can cut it into seven pieces by only threestraight cuts through the pizza with a pizza knife. Accordingly, he cut thepizza in the following way (guess which one is Ivan's piece):One of hisfriends, who never believed in Ivan’s smartness, wasstartled at this intelligence. He thought, if Ivan can do it, why can’t mycomputer? So he tried to do a similar (but not exactly as Ivan's, for Ivan willcriticize him for stealing his idea) job with his computer. He wrote a programthat took the number of straight cuts one makes through the pizza, and output anumber representing the maximum number of pizza pieces it will produce. Yourjob here is to write a similar program. It is ensured that Ivan’s friend won’t criticizeyou for doing the same job he did.

Input

The input file will contain a singleinteger N (0 <= N <= 210000000) in each line representing the number ofstraight line cuts one makes through the pizza. A negative number terminates theinput.

Output

Output the maximum number of pizza piecesthe given number of cuts can produce. Each line should contain only one outputinteger without any leading or trailing space.

Sample Input:

\-100

Sample Output:

题意：一块披萨切n刀，问最多能够切多少块！

思路：前n项和公式，以下是我的推理过程：

首先，题目关注的是一块馅饼能够切成几块，不是面积均分，也不涉及周长，所以只考虑块数即可，那么也就是说，这个馅饼多大根本无所谓，是什么形状也无所谓，只要能分成不同的块即可，那么我们就把他看成一个平面。

然后在平面内画一条线，能把该平面分成1+1个

在平面内画两条线，两条线最多有1个交点，能把该平面分成1+1+2个

在平面内画三条线，三条线最多有3个交点，能把该平面分成1+1+2+3个

……

这样分下去，每增加一条线，交点就会增加n-1个，就会增加n块

所以a\[n\]=a\[n-1\]+1;注意的是a\[0\]=1,那么s\[n\]=1+n\*(n+1)/2;

code:

#include <iostream>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    
    typedef unsigned long long ull;
    typedef long long ll;
    
    ull cal(ll n)   //实际上long long 已经够用
    {
         
        if (n%2) return (n+1)/2*n+1;
        else return n/2*(n+1)+1;
    }
    
    int main()
    {
         
        ll n;
        while (~scanf("%lld",&n))
        {
         
            if (n<0) break;
            //else if (n==0) cout<<0<<endl;
            else cout<<cal(n)<<endl;
        }
    }