Aizu Online Judge 0106 Discounts of Buckwheat

■0106 Discounts of Buckwheat

入力の範囲が狭い(46通り)ので，全入力に対する解を予め全探索で求めておく．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  void run(){  
17.   int[] a=new int[51];  
18.   Arrays.fill(a, INF);  
19.   for(int k=0; toGramme(0, 0, k)<=50; k++){  
20.    for(int j=0; toGramme(0, j, k)<=50; j++){  
21.     for(int i=0; toGramme(i, j, k)<=50; i++){  
22.      int g=toGramme(i, j, k);  
23.      a[g]=Math.min(a[g], toMoney(i, j, k));  
24.     }  
25.    }  
26.   }  
27.   for(;;){  
28.    int g=sc.nextInt()/100;  
29.    if(g==0){  
30.     break;  
31.    }  
32.    println(a[g]+"");  
33.   }  
34.  }  
35.   
36.  int toGramme(int i, int j, int k){  
37.   return i*2+j*3+k*5;  
38.  }  
39.   
40.  int toMoney(int i, int j, int k){  
41.   int sum=0;  
42.   sum+=380*(i-i%5)*80/100+380*(i%5);  
43.   sum+=550*(j-j%4)*85/100+550*(j%4);  
44.   sum+=850*(k-k%3)*88/100+850*(k%3);  
45.   return sum;  
46.  }  
47.   
48.  void debug(Object... os){  
49.   System.err.println(Arrays.deepToString(os));  
50.  }  
51.   
52.  void print(String s){  
53.   System.out.print(s);  
54.  }  
55.   
56.  void println(String s){  
57.   System.out.println(s);  
58.  }  
59.   
60.  public static void main(String[] args){  
61.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
62.   new Main().run();  
63.  }  
64. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 void run(){
  int[] a=new int[51];
  Arrays.fill(a, INF);
  for(int k=0; toGramme(0, 0, k)<=50; k++){
   for(int j=0; toGramme(0, j, k)<=50; j++){
    for(int i=0; toGramme(i, j, k)<=50; i++){
     int g=toGramme(i, j, k);
     a[g]=Math.min(a[g], toMoney(i, j, k));
    }
   }
  }
  for(;;){
   int g=sc.nextInt()/100;
   if(g==0){
    break;
   }
   println(a[g]+"");
  }
 }

 int toGramme(int i, int j, int k){
  return i*2+j*3+k*5;
 }

 int toMoney(int i, int j, int k){
  int sum=0;
  sum+=380*(i-i%5)*80/100+380*(i%5);
  sum+=550*(j-j%4)*85/100+550*(j%4);
  sum+=850*(k-k%3)*88/100+850*(k%3);
  return sum;
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}