1923 Fouriers Lines

1923 Fouriers Lines

問題

http://acm.pku.edu.cn/JudgeOnline/problem?id=1923

解答方針

交差点の数は，直線を平行な直線のグループに分けたときの各グループの直線数がわかれば計算できる．たとえば，問題文の図の状況は

(8,4,2,1,1,1)

という組で表現することができ，交点数は

0*8+8*4+(8+4)*2+(8+4+2)*1+(8+4+2+1)*1+(8+4+2+1+1)*1=101

と計算できる．

与えられた直線数nに対し，nを自然数の和として表す方法を列挙し，nの自然数の和への分割方法をn本の直線の平行な直線のグループへの分割方法と解釈して，交点数が与えられたものと等しくなるか調べていけばよい．なお，分割される領域数は「直線数+交点数+1」で求めることができる．問題文の「分割される領域数の最大値を求めよ」というのはダミーである．

解答例

import java.util.*;

public class Main{
    public static void main(String args[]){
        int m,n,c;
        boolean ans;
        Scanner sc = new Scanner(System.in);
        c=0;
        while(true){
            n = sc.nextInt();
            m = sc.nextInt();
            if(n==0) break;
            c++;
            Solver sol = new Solver(n,m);
            ans = sol.solve();
            if(ans){
                System.out.println("Case "+c+": "+n+" lines with exactly "+m+" crossings can cut the plane into "+(n+m+1)+" pieces at most.");
            }
            else{
                System.out.println("Case "+c+": "+n+" lines cannot make exactly "+m+" crossings.");
            }
        } 
    }
}

class Solver{
    int n,m;
    Solver(int n0,int m0){
        n = n0;
        m = m0;
    }
    public boolean solve(){
        return solveMain(n,m,0,n);
    }
    private boolean solveMain(int n,int m,int l,int a){
        if(n==0){
            if(m==0){
                return true;
            }
            else{
                return false;
            }
        }
    
        if(a==1){
            if(m==n*(2*l+n-1)/2){
                return true;
            }
            else{
                return false;
            }
        }
    
        //cut
        int q = n/a;
        if(l*n>m){
            return false;
        }
        if(n*(2*l+n-1)/2<m){
            return false;
        }
    
        //next
        boolean ans = false;
        for(int i=1;i<=a;i++){
            boolean tmp = solveMain(n-i,m-l*i,l+i,i);
            if(tmp){
                ans = true;
                break;
            }
        }
        return ans;
    }
}