fork download
copy 
  1. import java.util.ArrayList;
  2. import java.util.Arrays;
  3. import java.util.Collections;
  4. import java.util.concurrent.TimeUnit;
  5. import java.util.function.Consumer;
  6.  
  7. class Q6_892
  8. {
  9.     // 1～MAX_BALL_NUMBERの数が書かれた球を使う
  10.     static final int MAX_BALL_NUMBER = 15;
  11.  
  12.     static boolean abort;
  13.  
  14.     public static void main(String[] args)
  15.     {
  16.         // 5個の球を使って21を作る
  17.         test(5, 21, false, true, false);
  18.  
  19.         // 6個～15個の球を使って21を作る
  20.         // 1個でも結果が見つかれば計算を打ち切る
  21.         for(int i = 6; i <= MAX_BALL_NUMBER; i++)
  22.         {
  23.             test(i, 21, false, true, true);
  24.         }
  25.     }
  26.  
  27.     static void test(int n, int m, boolean reduce, boolean view, boolean censoring)
  28.     {
  29.         abort = false;
  30.         ArrayList<int[]> list = new ArrayList<>();
  31.  
  32.         // 処理
  33.         long s = System.nanoTime();
  34.         forEach(reduce, n, (int[] p) -> {
  35.             if (test(m, p))
  36.             {
  37.                 if (reduce)
  38.                 {
  39.                     // 配列の要素を1個左に回転させる
  40.                     int[] is = new int[p.length];
  41.                     for(int i = 0; i < p.length - 1; i++)
  42.                     {
  43.                         is[i] = p[i + 1];
  44.                     }
  45.                     is[p.length - 1] = p[0];
  46.                     list.add(is);
  47.                 } else
  48.                 {
  49.                     list.add(Arrays.copyOf(p, p.length));
  50.                 }
  51.                 abort = censoring;
  52.             }
  53.         });
  54.         long e = System.nanoTime();
  55.  
  56.         if (reduce)
  57.         {
  58.             Collections.sort(list, (int[] a, int[] b) -> {
  59.                 int compare = 0;
  60.                 for(int i = 0; i < n && compare == 0; i++)
  61.                 {
  62.                     compare = Integer.compare(a[i], b[i]);
  63.                 }
  64.                 return compare;
  65.             });
  66.         }
  67.  
  68.         // 結果表示
  69.         System.out.printf(
  70.                 "N=%d,M=%d...%d個の結果が見つかりました　計算時間%,dms%n",
  71.                 n, m, list.size(), TimeUnit.NANOSECONDS.toMillis(e - s));
  72.  
  73.         if (view)
  74.         {
  75.             for (int[] is : list)
  76.             {
  77.                 System.out.println(Arrays.toString(is));
  78.             }
  79.         }
  80.         if (abort) System.out.println("計算を打ち切りました");
  81.         System.out.println();
  82.     }
  83.  
  84.  
  85.     /**
  86.      * ballsの配列を使って1~mの数値を作れるかどうかを調べる
  87.      */
  88.     static boolean test(int m, int[] balls)
  89.     {
  90.         boolean[] flags = new boolean[m + 1];
  91.  
  92.         int sum = 0;
  93.  
  94.         // ballsを全部足した合計値のフラグを立てる
  95.         for (int i = 0; i < balls.length; i++)
  96.         {
  97.             sum += balls[i];
  98.         }
  99.         if (sum <= m) flags[sum] = true;
  100.  
  101.         // 1~m-1個の連続した球の数の合計値のフラグを立てる
  102.         for (int i = 0; i < balls.length; i++)
  103.         {
  104.             sum = 0;
  105.             for (int j = 0; j < balls.length - 1; j++)
  106.             {
  107.                 sum += balls[(i + j) % balls.length];
  108.                 if (sum > m) break;
  109.                 flags[sum] = true;
  110.             }
  111.         }
  112.  
  113.         for (int i = 1; i <= m; i++)
  114.         {
  115.             if (!flags[i]) return false;
  116.         }
  117.         return true;
  118.     }
  119.  
  120.     /**
  121.      * 順列を生成してConsumerに処理を投げる
  122.      * @param reduce 計算量削減させるかどうか
  123.      * @param num 球の数
  124.      * @param c
  125.      */
  126.     static void forEach(boolean reduce, int num, Consumer<int[]> c)
  127.     {
  128.         if (num < 3 || num > MAX_BALL_NUMBER) throw new IllegalArgumentException();
  129.  
  130.         // 計算量削減のために最初3個をA,B,Cとした場合 B=1, C<Aとなるようにする。(基点の位置確定と反転の回避)
  131.         if (reduce)
  132.         {
  133.             int[] perm = new int[num];
  134.             boolean[] used = new boolean[MAX_BALL_NUMBER + 1];
  135.  
  136.             perm[1] = 1;
  137.             used[1] = true;
  138.             for (int i = 2; i <= MAX_BALL_NUMBER - 1; i++)
  139.             {
  140.                 perm[2] = i;
  141.                 used[i] = true;
  142.                 for (int j = i + 1; j <= MAX_BALL_NUMBER; j++)
  143.                 {
  144.                     perm[0] = j;
  145.                     used[j] = true;
  146.                     p(perm, used, 3, c);
  147.                     used[j] = false;
  148.                 }
  149.                 used[i] = false;
  150.             }
  151.         }
  152.         else
  153.         // 計算量削減せずに全パターン調べる
  154.         {
  155.             p(new int[num], new boolean[MAX_BALL_NUMBER + 1], 0, c);
  156.         }
  157.     }
  158.  
  159.     /**
  160.      * 再帰で順列生成
  161.      */
  162.     private static void p(int[] perm, boolean[] used, int p, Consumer<int[]> c)
  163.     {
  164.         if (perm.length == p)
  165.         {
  166.             c.accept(perm);
  167.             return;
  168.         }
  169.  
  170.         for (int i = 1; i <= MAX_BALL_NUMBER && !abort; i++)
  171.         {
  172.             if (used[i]) continue;
  173.             used[i] = true;
  174.             perm[p] = i;
  175.             p(perm, used, p + 1, c);
  176.             used[i] = false;
  177.         }
  178.     }
  179. }
Success #stdin #stdout 0.34s 320576KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
N=5,M=21...10個の結果が見つかりました　計算時間228ms
[1, 3, 10, 2, 5]
[1, 5, 2, 10, 3]
[2, 5, 1, 3, 10]
[2, 10, 3, 1, 5]
[3, 1, 5, 2, 10]
[3, 10, 2, 5, 1]
[5, 1, 3, 10, 2]
[5, 2, 10, 3, 1]
[10, 2, 5, 1, 3]
[10, 3, 1, 5, 2]

N=6,M=21...1個の結果が見つかりました　計算時間0ms
[1, 2, 3, 4, 5, 8]
計算を打ち切りました

N=7,M=21...1個の結果が見つかりました　計算時間0ms
[1, 2, 3, 4, 5, 6, 7]
計算を打ち切りました

N=8,M=21...1個の結果が見つかりました　計算時間0ms
[1, 2, 3, 4, 5, 6, 8, 7]
計算を打ち切りました

N=9,M=21...1個の結果が見つかりました　計算時間0ms
[1, 2, 3, 4, 5, 6, 8, 7, 10]
計算を打ち切りました

N=10,M=21...1個の結果が見つかりました　計算時間0ms
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
計算を打ち切りました

N=11,M=21...1個の結果が見つかりました　計算時間0ms
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 13]
計算を打ち切りました

N=12,M=21...1個の結果が見つかりました　計算時間0ms
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13]
計算を打ち切りました

N=13,M=21...1個の結果が見つかりました　計算時間0ms
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
計算を打ち切りました

N=14,M=21...1個の結果が見つかりました　計算時間0ms
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15]
計算を打ち切りました

N=15,M=21...1個の結果が見つかりました　計算時間0ms
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
計算を打ち切りました
https://ideone.com/VK7JC8
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!