PKU : 1840 - Eqs
問題概要
http://poj.org/problem?id=1840
問題文に書かれた式を満たすような, xの組み合わせ数を答えよ.
アルゴリズム
DPでやろうと思ったのですが, 値が大きすぎるため断念.
左2つと, 右3つに分割して計算し, 答えを併合しました.
C++では, mapではだめで, ハッシュを使わないといけないみたいです.
プログラム
public static void main(String[] args){ Scanner sc = new Scanner(System.in); int[] t = new int[5]; for(int i=0;i<5;i++){ t[i] = sc.nextInt(); } HashMap<Integer,Integer> left = new HashMap<Integer,Integer>(); for(int i=-50;i<=50;i++){ if(i == 0) continue; for(int j=-50;j<=50;j++){ if(j == 0) continue; int cal = t[0]*i*i*i + t[1]*j*j*j; Integer tmp = left.get(cal); if(tmp == null){ left.put(cal,1); } else{ left.put(cal,tmp+1); } } } int res = 0; for(int i=-50;i<=50;i++){ if(i == 0) continue; for(int j=-50;j<=50;j++){ if(j == 0) continue; for(int k=-50;k<=50;k++){ if(k == 0) continue; int cal = t[2]*i*i*i + t[3]*j*j*j + t[4]*k*k*k; Integer tmp = left.get(cal); if(tmp != null){ res += tmp; } } } } System.out.println(res); }