5/24團練結果-ACM10325及ACM10228

團練參考網址:
Inclusion-Exclusion Principle
http://www.csie.ntnu.edu.tw/~u91029/Inclusion-ExclusionPrinciple.html
Extremum
http://www.csie.ntnu.edu.tw/~u91029/Extremum.html

/*JW's AC Code in ACM 10325*/

#include<stdio.h>
#define MAX 16

long long n,m;
long long marray[MAX];

void init(long long array[MAX])
{
    long long i;
    for(i=0;i<MAX;i++)array[i] = 0;
}

long long gcd(long long a,long long b)
{
    return b?gcd(b,a%b):a;
}

long long lcm(long long a,long long b)
{
    return a/gcd(a,b)*b;
}

long long backtrack(long long c,long long w,long long d)
{
    if(c==m)return w*(n/d);
    return backtrack(c+1,w,d)+backtrack(c+1,-w,lcm(d,marray[c]));
}

int main()
{
    while(scanf("%d%d",&n,&m)==2)
    {
    init(marray);
    long long i;
    for(i=0;i<m;i++)scanf("%lld",&marray[i]);
    printf("%lld\n",backtrack(0,1,1));
    }
    return 0;
}

/*ApplerMan's AC code in ACM 10228*/

#include<stdio.h>
#include<math.h>

double countDistance(double x1,double y1,double x2,double y2){
    return pow((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2),0.5);
}
double totalDistance(int N,double point[100][2],double x,double y){
    int i;
    double total=0;
    for(i=0;i<N;i++){
        total+=countDistance(x,y,point[i][0],point[i][1]); 
    }
    return total;
}
double xbisection(int N,double point[100][2],double y,double a, double b){
    double fa,fb,c=(a+b)/2,fc=totalDistance(N,point,c,y),d;
    for(d=fabs(b-a)/4;d>1e-5;d/=2){
        a=c-d,b=c+d,fa=totalDistance(N,point,a,y),fb=totalDistance(N,point,b,y);
        if(fa<fc) c=a,fc=fa;
        else if(fb<fc) c=b,fc=fb;
    }
    return fc;
}
double ybisection(int N,double point[100][2],double a,double b){
    double fa,fb,c=(a+b)/2,fc=xbisection(N,point,c,0,10000),d;
    for(d=fabs(b-a)/4;d>1e-5;d/=2){
        a=c-d,b=c+d,fa=xbisection(N,point,a,0,10000),fb=xbisection(N,point,b,0,10000);
        if(fa<fc) c=a,fc=fa;
        else if(fb<fc) c=b,fc=fb;
    }
    return fc;
}
int main(){
    int M,N,i;
    double point[100][2];
    scanf("%d",&M);
    while(M--){
        scanf("%d",&N);
        for(i=0;i<N;i++) scanf("%lf %lf",&point[i][0],&point[i][1]);
        printf("%.lf\n",ybisection(N,point,0,10000));
        if(M>0) printf("\n");
    }
    return 0;
}

團練討論:

ACM10325:

須使用long long 避免WA
如以下測資
2000000000 14
1073741789 1073741783 1073741741 1073741723 1073741719 1073741717 1073741689 1073741671 1073741663 1073741651 1073741621 1073741567 1073741561 1073741527
答案是1999999986
long long 在dev c++使用%I64d；
在Linux下使用 %lld
上傳皆使用%lld

ACM10228:

這題除了演算法，還要用些數學概念
切割xy平面去找極小值，
這題無特定公式可以直接求解，
在xy平面上，每一點對應到一個f(x,y)
f(x,y)即為一個曲面函數
求曲面上極大極小值要用lagrange
所以這題直接用切割平面的方式找極小較為容易
這意這題f(x,y)只出現一個極值，故可以不必分段找極大極小
因為他只有一個極小。