fork download 
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4.  
  5. /*
  6. プログラミングのお題スレ Part12 
  7. //mevius.5ch.net/test/read.cgi/tech/1538096947/755
  8.  
  9. 755 名前：デフォルトの名無しさん[sage] 投稿日：2018/12/03(月) 22:04:03.50 ID:cV13JBu4
  10. [お題]
  11. 整数A,B(1<=A<B<=50万)と P(1<=P<=10)が順に与えられる。
  12. A以上B以下の10進数の整数から異なる２つの整数を選ぶ。
  13. その2つの整数を表現するのに使われている(各桁の)数字の種類が
  14. ちょうどP種類である選び方は何通りできるか。
  15.  
  16. ※ 先頭ゼロ詰禁止、実行時間一問1.5秒以内(ideone等で)
  17.  
  18. 1) 8 11 2 --> 4
  19. 2) 10 1000 5 --> 207480
  20. 3) 44 44444 4 --> 33808313
  21. 4) 56785 113452 1 --> ?
  22. 5) 102345 480713 6 --> ?
  23. 6) 1 500000 7 --> 47440713600
  24.  
  25. 　例題1) の補足 "8 11 2" のとき
  26. 　　{8,9,10,11}から2整数を選ぶ。NCR(4,2)=6通りあるなかから
  27. 　　(8,9)(8,11)(9,11)(10,11) の4通りが答え。[]内を使用数字とすると、
  28. 　　例として、(8,11)は[8,1]の2種類, (10,11)は[1,0]の2種類からなる。
  29. 　　対象外は (8,10)は[8,1,0] (9,10)は[9,1,0]で ともに2種類ではない。
  30.  
  31. 　※解き方をパックて単純化した問題。
  32.  */
  33. class Ideone
  34. {
  35.     public static void main(String[] args) throws IOException
  36.     {
  37.         try (BufferedReader in = new BufferedReader(new InputStreamReader(System.in)))
  38.         {
  39.             while (true)
  40.             {
  41.                 String line = in.readLine();
  42.                 if (line == null) break;
  43.                 String[] split = line.split(" ");
  44.                 int a = Integer.parseInt(split[0]);
  45.                 int b = Integer.parseInt(split[1]);
  46.                 int p = Integer.parseInt(split[2]);
  47.                 System.out.printf("%d %d %d --> %d%n", a, b, p, count(a, b, p));
  48.             }
  49.         }
  50.     }
  51.  
  52.     static long count(int a, int b, int p)
  53.     {
  54.         int[] n = new int[1024];
  55.         for (int i = a; i <= b; i++)
  56.         {
  57.             int bit = 0;
  58.             for (int j = i; j > 0; j /= 10)
  59.             {
  60.                 bit |= 1 << j % 10;
  61.             }
  62.             n[bit]++;
  63.         }
  64.  
  65.         long count = 0;
  66. //      for (int x = 1; x < 1024; x++)
  67. //      {
  68. //          for (int y = x; y < 1024; y++)
  69. //          {
  70. //              if (Integer.bitCount(x | y) == p)
  71. //              {
  72. //                  count += x != y ? n[x] * n[y] : n[x] * (n[x] - 1) / 2;
  73. //              }
  74. //          }
  75. //      }
  76.         for (int x = 1; x < 1024; x++)
  77.         {
  78.             if (Integer.bitCount(x) == p)
  79.             {
  80.                 count += n[x] * (n[x] - 1) / 2;
  81.             }
  82.  
  83.             for (int y = x + 1; y < 1024; y++)
  84.             {
  85.                 if (Integer.bitCount(x | y) == p)
  86.                 {
  87.                     count += n[x] * n[y];
  88.                 }
  89.             }
  90.         }
  91.         return count;
  92.     }
  93. }
  94.  
Success #stdin #stdout 0.07s 2184192KB
comments (?)
stdin 
8 11 2
10 1000 5
44 44444 4
56785 113452 1
102345 480713 6
1 500000 7
stdout 
8 11 2 --> 4
10 1000 5 --> 207480
44 44444 4 --> 33808313
56785 113452 1 --> 0
102345 480713 6 --> 15250362566
1 500000 7 --> 47440713600
https://ideone.com/a1wOZ4
お題スレ12-755
language:
Java (HotSpot 12)
created:
5 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!