2009年6月2日 星期二

ACM Q11296



import java.util.Scanner;
public class Q11296 {
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
long n;
while(cin.hasNextInt() ){
n = cin.nextInt();
if(n > 1000001){
continue;
}
long count=0;
count = (n/2+1)*(n/2+2)/2;
System.out.println(count);
}

}
}



利用公式解!!!



import java.util.Scanner;
public class Q11296 {
public static void main(String args[]) {
Scanner cin = new Scanner(System.in);
int n;
while(cin.hasNextInt() ){
n = cin.nextInt();
if(n > 1000001){
continue;
}
long count=0;
for(int x=n%2; x<=n ;x=x+2){
count += (n-x)/2+1;
}
System.out.println(count);
}

}
}



不用公式解!!!

1 則留言:

  1. 公式解可想成 y+z = (n-x)/2

    所以y+z <= n/2

    利用排列組合可得 H(3, n/2) = C((n/2)+2 , n/2)

    C((n/2)+2 , n/2) 可得 ((n/2)+2) * ((n/2)+2) /2

    不過UVA 測得不用公式解跑的比較快 ?!!! 還快 38ms?

    不了解

    回覆刪除