download
1. # factorial table
2. FAC = [1]
3. def gen_fac(n)
4. n.times do |i|
5. FAC << FAC[i]*(i+1)
6. end
7. end
8.
9. # generates a mask such that it is matched by each string that matches m and n
10. def diff_mask(m,n)
11. q = m.dup
12. m.size.times do |i|
13. c1 = m[i]
14. c2 = n[i]
15. if c1=="0"&&c2=="1"||c1=="1"&&c2=="0"
16. return nil
17. elsif c1=='2'
18. q[i] = c2
19. elsif c2 == '2'
20. q[i] = c1
21. end
22. end
23. q
24. end
25.
26. # counts the number of possible balanced strings matching the mask
27. def count_mask(m)
28. n = m.size
29. c0 = n/2-m.count("0")
30. c1 = n/2-m.count("1")
31. c2 = c0+c1
32. if c0>n/2 || c1>n/2
33. 0
34. else
35. FAC[c2]/(FAC[c0]*FAC[c2-c0])
36. end
37. end
38.
39. # union masks of cn masks from m.size masks
40. def mask_diff_combinations(m,n=1,s=m.size,diff1='2'*m[0].size,j=-1,&b)
41. (j+1..s-1).each do |i|
42. diff2 = diff_mask(diff1,m[i])
43. next if !diff2
44. mask_diff_combinations(m,n+1,s,diff2,i,&b) if n<s
45. yield diff2,n
46. end
47. end
48.
49. # counts the number of balanced strings matched by at least one mask
50. def count_n_masks(m)
51. sum = 0
52. mask_diff_combinations(m) do |mask,i|
53. sum += i%2==1 ? count_mask(mask) : -count_mask(mask)
54. end
55. sum
56. end
57.
58.
59. time = Time.now
60.
61. # parse input
62. d = STDIN.each_line.map do |line|
63. line.chomp.strip
64. end
65. d.delete_if(&:empty?)
66. d.shift
67.
68. # generate factorial table
69. gen_fac([d.size,d[0].size].max+1)
70.
71. # count masks
72. puts "number of matches: #{count_n_masks(d)}"
73. puts "took #{Time.now-time} s"
Success #stdin #stdout 0.02s 7476KB
stdin
10
22222222222222222222
stdout
number of matches: 184756
took 0.000169685 s