fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Ideone
  6. {
  7.     static final int COIN_001_WEIGHT = 10;
  8.     static final int COIN_005_WEIGHT = 37;
  9.     static final int COIN_010_WEIGHT = 45;
  10.     static final int COIN_050_WEIGHT = 40;
  11.     static final int COIN_100_WEIGHT = 48;
  12.     static final int COIN_500_WEIGHT = 70;
  13.  
  14.     public static void main(String[] args)
  15.     {
  16.         try(Scanner in = new Scanner(System.in))
  17.         {
  18.             while(true)
  19.             {
  20.                 System.out.printf("Weight of Coins (gram) : ");
  21.                 if (!in.hasNextDouble()) break;
  22.                 search(in.nextDouble());
  23.             }
  24.         }
  25.     }
  26.  
  27.     static class CoinSet
  28.     {
  29.         int n001, n005, n010, n050, n100, n500;
  30.         int amount;
  31.  
  32.         CoinSet(int n001, int n005, int n010, int n050, int n100, int n500)
  33.         {
  34.             this.n001 = n001;
  35.             this.n005 = n005;
  36.             this.n010 = n010;
  37.             this.n050 = n050;
  38.             this.n100 = n100;
  39.             this.n500 = n500;
  40.             amount = n001 + 5 * n005 + 10 * n010 + 50 * n050 + 100 * n100 + 500 * n500;
  41.         }
  42.  
  43.         @Override
  44.         public String toString()
  45.         {
  46.             return String.format(" %10d : %6d %6d %6d %6d %6d %6d", amount, n001, n005, n010, n050, n100, n500);
  47.         }
  48.     }
  49.  
  50.     static void search(double g)
  51.     {
  52.         long s = System.nanoTime();
  53.         ArrayList<CoinSet> result = search1((int) (g * 10));
  54.         result.sort(Comparator.comparing(x -> x.amount));
  55.         long e = System.nanoTime();
  56.  
  57.         System.out.printf("%nCoin Weight    : %.1f g%n", g);
  58.         System.out.printf("Number of List : %d%n", result.size());
  59.         System.out.printf("Time           : %,dns%n", e - s);
  60.         if (result.size() < 1000)
  61.         {
  62.             System.out.printf("amount(yen) :   1yen   5yen  10yen  50yen 100yen 500yen%n");
  63.             System.out.printf("---------------------------------------------------------%n");
  64.             for(CoinSet set : result)
  65.             {
  66.                 System.out.println(set);
  67.             }
  68.         }
  69.         System.out.println();
  70.     }
  71.  
  72.     // 残りが1.0g単位になるように探索する
  73.     static ArrayList<CoinSet> search1(int remain)
  74.     {
  75.         ArrayList<CoinSet> result = new ArrayList<CoinSet>();
  76.         for(int n005 = 0; n005 <= 9; n005++)
  77.         {
  78.             remain -= n005 * COIN_005_WEIGHT;
  79.             for(int n100 = 0; n100 <= 4; n100++)
  80.             {
  81.                 remain -= n100 * COIN_100_WEIGHT;
  82.                 for(int n010 = 0; n010 <= 1; n010++)
  83.                 {
  84.                     remain -= n010 * COIN_010_WEIGHT;
  85.                     if (remain >= 0 && remain % 10 == 0)
  86.                     {
  87.                         search2(result, remain, n005, n010, n100);
  88.                     }
  89.                     remain += n010 * COIN_010_WEIGHT;
  90.                 }
  91.                 remain += n100 * COIN_100_WEIGHT;
  92.             }
  93.             remain += n005 * COIN_005_WEIGHT;
  94.         }
  95.         return result;
  96.     }
  97.  
  98.     // 1g単位で探索する…5重ループよくないｗｗｗｗｗｗｗｗ
  99.     static void search2(ArrayList<CoinSet> result, int remain, int _n005, int _n010, int _n100)
  100.     {
  101.         for (int n005 = 0; n005 * COIN_005_WEIGHT <= remain; n005 += 10)
  102.         {
  103.             remain -= n005 * COIN_005_WEIGHT;
  104.             for (int n100 = 0; n100 * COIN_100_WEIGHT <= remain; n100 += 5)
  105.             {
  106.                 remain -= n100 * COIN_100_WEIGHT;
  107.                 for (int n010 = 0; n010 * COIN_010_WEIGHT <= remain; n010 += 2)
  108.                 {
  109.                     remain -= n010 * COIN_010_WEIGHT;
  110.                     for (int n500 = 0; n500 * COIN_500_WEIGHT <= remain; n500++)
  111.                     {
  112.                         remain -= n500 * COIN_500_WEIGHT;
  113.                         for (int n050 = 0; n050 * COIN_050_WEIGHT <= remain; n050++)
  114.                         {
  115.                             remain -= n050 * COIN_050_WEIGHT;
  116.  
  117.                             // 1円はあまりで作る
  118.                             result.add(new CoinSet(remain / 10, n005 + _n005, n010 + _n010, n050, n100 + _n100, n500));
  119.  
  120.                             remain += n050 * COIN_050_WEIGHT;
  121.                         }
  122.                         remain += n500 * COIN_500_WEIGHT;
  123.                     }
  124.                     remain += n010 * COIN_010_WEIGHT;
  125.                 }
  126.                 remain += n100 * COIN_100_WEIGHT;
  127.             }
  128.             remain += n005 * COIN_005_WEIGHT;
  129.         }
  130.     }
  131. }
  132.  
Success #stdin #stdout 3.42s 321216KB
comments (?)
stdin
copy 
23.7
100
200
333.3
stdout
copy 
Weight of Coins (gram) : 
Coin Weight    : 23.7 g
Number of List : 23
Time           : 82,734,766ns
amount(yen) :   1yen   5yen  10yen  50yen 100yen 500yen
---------------------------------------------------------
         25 :     20      1      0      0      0      0
         36 :     11      1      2      0      0      0
         47 :      2      1      4      0      0      0
         71 :     16      1      0      1      0      0
         82 :      7      1      2      1      0      0
        117 :     12      1      0      2      0      0
        127 :      7      2      1      0      1      0
        128 :      3      1      2      2      0      0
        163 :      8      1      0      3      0      0
        173 :      3      2      1      1      1      0
        209 :      4      1      0      4      0      0
        218 :      3      3      0      0      2      0
        255 :      0      1      0      5      0      0
        410 :      0      0      1      0      4      0
        518 :     13      1      0      0      0      1
        529 :      4      1      2      0      0      1
        564 :      9      1      0      1      0      1
        575 :      0      1      2      1      0      1
        610 :      5      1      0      2      0      1
        620 :      0      2      1      0      1      1
        656 :      1      1      0      3      0      1
       1011 :      6      1      0      0      0      2
       1057 :      2      1      0      1      0      2

Weight of Coins (gram) : 
Coin Weight    : 100.0 g
Number of List : 7078
Time           : 28,066,646ns

Weight of Coins (gram) : 
Coin Weight    : 200.0 g
Number of List : 163831
Time           : 200,399,211ns

Weight of Coins (gram) : 
Coin Weight    : 333.3 g
Number of List : 1838203
Time           : 2,961,281,899ns

Weight of Coins (gram) :
https://ideone.com/p9TGWl
language:
Java (HotSpot 12)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!