#UVa:10079-Pizza Cutting

灆洢 2012-03-25 20:10:32

題目其實就是要問幾條線最多能切出幾塊平面的意思。

我們可以知道1條線最多可以切2塊平面,2條線最多可以切4塊平面。假設n-1條線已經切了k塊平面,現在要問n條線可以切出幾塊平面,那麼就好像是n-1條線又要再加上一條線,這條線怎麼切會增加最多的平面呢?

答案是和前n-1條線都有交到會最多,那麼這條線從邊緣~第一條線的交點地方可以多切出一塊平面,第一條線的交點~第二條線的交點的地方也可以多切出一塊平面……以此類推,一直到第n-2條線的交點~第n-1條線的交點又可以多切出一塊平面,第n-1條線到另外一邊的邊緣又會多切出一塊平面,總共就比n-1條線的情況多切出了n個平面,那麼公式就呼之欲出了。

C++(0.008)

/*******************************************************/
/* UVa 10079 Pizza Cutting                             */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2012/03/25                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
using namespace std;

int main(){
  long long N;
  while( scanf( "%lld", &N ) != EOF && N >= 0 )
    printf( "%lld\n", (N+1)*N/2+1 );
  return 0;
}

發表迴響

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料