fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. class Mse4089130 {
  8. 	final int N; // 10
  9. 	final int M; // 7
  10. 	final int K; // 5 (sum must be less than K)
  11. 	final int S; // 2^(7-1) = 64
  12. 	final long[] st; // states (indexed from 0 to S-1
  13. 	int t = 0;
  14.  
  15. 	public Mse4089130(int n, int m, int k) {
  16. 		N = n;
  17. 		M = m;
  18. 		K = k;
  19. 		S = (int) Math.pow(2, M - 1);
  20. 		st = new long[S];
  21. 		st[0] = 1;
  22. 	}
  23.  
  24. 	public void compute() {
  25. 		for (int tt = 1; tt <= N; tt++) {
  26. 			t = tt;
  27. 			long[] stold = Arrays.copyOf(st, st.length);
  28. 			Arrays.fill(st, 0);
  29. 			for (int x = 0; x < S; x++) {
  30. 				st[evolve(x, false)] += stold[x];
  31. 				if (weight(x) < K - 1)
  32. 					st[evolve(x, true)] += stold[x];
  33. 			}
  34. 		}
  35. 	}
  36.  
  37. 	long count() {
  38. 		long ac = 0; for (long x : st) ac += x;	return ac;
  39. 	}
  40.  
  41. 	int evolve(int x, boolean one) {
  42. 		return one ? x / 2 + S / 2 : x / 2;
  43. 	}
  44.  
  45. 	int weight(int n) {
  46. 		return Integer.bitCount(n);
  47. 	}
  48.  
  49. 	@Override
  50. 	public String toString() {
  51. 		return "[t=" + t + " count=" + count() + " N=" + N + ", M=" + M + ", K=" + K + ", S=" + S + "]";
  52. 	}
  53.  
  54. 	public static void main(String[] args) {
  55. 		Mse4089130 mse = new Mse4089130(10, 7, 5);
  56. 		System.out.println(mse.toString());
  57. 		mse.compute();
  58. 		System.out.println(mse.toString());
  59. 		System.out.println(mse.count());
  60. 	}
  61. }
  62.  
Success #stdin #stdout 0.18s 53788KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
[t=0 count=1 N=10, M=7, K=5, S=64]
[t=10 count=637 N=10, M=7, K=5, S=64]
637
https://ideone.com/IsNjy6
language:
Java (HotSpot 12)
created:
4 years ago
visibility:
public

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!