2009年6月11日 星期四

ACM Q10079



import java.util.Scanner;
public class Q10079 {
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
while(cin.hasNextLong()){
long n = cin.nextLong();
if(n<0)
break;
System.out.println(n*(n+1)/2+1);
}
}
}

1 則留言:

  1. 這一題可視為平面分割問題:
    一條直線可以將平面分成2部分.假設(n-1)條直線最多可以將平面分成a部分,假使平面上再加一條直線,這條直線最多可以與原來的每一條直線都相交(其他 n-1 條直線相交, 産生(n-1)個交點,該直線被分成n部分,而每一部分將所在區域一分爲二,使得平面多出了n個部分. 平面可以被分為共a+n個部分. 歸納推得切n刀可將平面分成
    n * ((n+1)/2) +1 部分. Solved!!!

    回覆刪除