fork(1) 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.4s 7432KB
stdin
30
210211202222222211222112102111220022202222210122222212220210
010222222120210221012002220212102220002222221122222220022212
111022212212022222222220111120022120122121022212211202022010
022121221020201212200211120100202222212222122222102220020212
112200102110212002122122011102201021222222120200211222002220
121102222220221210220212202012110201021201200010222200221002
022220200201222002020110122212211202112011102220212120221111
012220222200211200020022121202212222022012201201210222200212
210211221022122020011220202222010222011101220121102101200122
102220212200202121102122120000211221220222001202211220202222
020212122210101112211211220110222220002212212111212021220110
112021110100221101212212122122210022212122122222122020210001
221020211000222122101112212202221012201222122220202220202202
012020220002012222122122102122010101101222012121101202220222
020122110200210202001210102002120002022122001222221222022222
201101212222221002222100001112221221222212200012220222222222
210202012122012020102120201012201022222020020102012110021100
202212001121220002022222011211122022112121200222002022122222
122102212202221102022200121202010102210220000222010011220112
222212221022202012222110112020122102201222122212020021010220
220112222212020020112222100021010000222110001222022220022222
212220220201220222200002122221202222121000222220100221221000
222212122222210010220022120202212222020122112210212222220120
221021111202222222202122222221121020120011222221220220200001
222122202222022102202202211221220102100220112221200220222222
022220212102200202200102022222122202122022121222122222122001
002201022220221212202222222212222212201202101210112221000000
022222101222222102202220012222021000112010020122022112012111
201012200000222121022012202100120020210120120010022122201202
221211220121122021201212202100002120021022202212201202211020
200220120110022110120202222100121202011101122211002000202221
012021121220221122201002222020000011202002100102102212210111
022002222200220212202200202212222001011122002020020221202202
202012222211201121012221022210201022200222202202221120222022
201122122221002121202101020001110111202212112222112022102222
220020201212001222222022122210222122221101101202002200111221
210120220020222210222122222202220021120212212202201002002222
122202011012121000222022020112220011221120122212222222222020
020102211022021212101200222101110202211122110001102122220020
122112221122212221022211211020001121011222002020222222221222
021122122122120222200201222202220220222200221121022010211202
021202122022202000212110111212102222212220120120122022220022
102012210222001221222222111221222202121002010222212210011121
121201212212111120221022111200212201200022212212212122212000
221012212200121020020211120022122202121222210221210022021020
012221101120020102010222122101220020001201111222202202020122
110201012122221212222210002120220211221022212102002221221022
220212222121222000001200011100022220222222020120120200221220
202202221221200121200102022222120202112112102102101111010210
122222112202102122122220212202220011122212012212212222221222
022022122112112122222012212121211222020211022120202112211212
122211012011120222001221102121012022111221211222222010210212
221222221111010222022121221222100122212222122212202002122020
120120202002221222221211222202022002222122102210002221222121
122121212202202002222220202202210222222222001220022210202211
102002001122212021021122111100020221021202002121222021221122
011222012201100012122121222201122110122212112112201121121000
121122221222221000222102222001201012002212102222102102220221
201220202201112222202221222221010210022020112201010200102221
212101120022211222100021212022222202211021001222122110020011
122122221222212010111220022200022212120000201202002221111122
221200201212012210122200120100022021221120022202211222112122
222221101221102010211012212120021012212222112221112002121212
222122112212202122102022201112102112220212221021222212022120
121002020012020212122222002220202111222211001222122210210112
122122021022001222100222221100222010120222212120222201212020
201212022101211211122012112122120112122020202120220111111220
021201020012200100222000122221102020222222222010222210022021
022122001201221201111202101222112110221201221001211200102002
102011222211212021200220102100222220222220222222122000011120
121222021200122221000020012122211220021221221212202020010022
112102110222201221200201120220000212220122222121102020202201
201222121221122120012021211211211212222122220121222212200220
012102211002202021222202222212101220002221021211220121220000
002202102220222222021020222210011112101202222100000222112221
121100121212221122221111202202221200121222022010122112002220
222102121012101200222222012221222211012202012112022021222121
221222220200212222022222200211222120110002222200221110220022
202202020200220022220010221200002220122212121210000212212020
222010012221221000202212211021201212212022200112222121102210
012211222200222221221020222020002102202200111022000122120202
012021022211201121202120222122120210111220102102102202122222
001221210202001220211220222122011122210102010210010222002222
220212222100002221221000022220222021022212222212122000102222
222022121222212122022012200112012102222122212222020121212122
222212110220221101221122221221222202120202000220210220222122
021122212222010220200222111000202212112222120122120112112222
221212122220110212012221212122202102022020122221110122022200
122212112222022212220120211220001022211020222202202021111222
122212222021212022212020112220120200212002222222022202020222
220121011122002011210200000122122011012122221221220200112221
212000210121211122202222220200221222102202011210001122202021
212222020112102112012020211020022022211220110202222200112022
021111020201110212222220202221122002220201022021000110220220
102211122011122020122112122020012212111021220202222022122211
012021220021122022020001121022220201000112020020221122101022
020220002212021200110220210022210021210221222221222011001202
022210221221000201201220022210212122012221210220122210111221
002001101100202222221121222220221202222222201101121220210222
021120111001020002001000012122102020222221011010222102220012
122222200222022022222002122000222121212210122120012011002120
220121212022211012221221002212021221201222101212021220210122
202002221222210112010220102212201200021012212122011222210222
100221202221222202122011201021101222221212201212021222212100
220012122102221221220110012002122120020022020201222020102111
212101022222222120001202222212122210200220121222120222021122
020022111121012121220212220012212121120120122202202220122220
102002200200201122212202020221222222022222122022202222222012
221022021122220010000222111110222212100012222021200100100222
122222222222202121202212020120210211220121100101012222210000
222210022020220222122022002202122022120022212102201222002021
011222002201122220122222022121122222220012202001210222002121
202222212102122210202220000021012120122022202011202022100202
012212222122122102101020212222010222220222210012221122220220
210200011220000202001022122221212112202122222210110202022002
210210210112001002011021110022212210201212222221000021010020
011021202102210220002221202121222222120010222221200012221222
222110201100022120022221020202022120221120210120021122000201
010202021212111020012221222120001100202121100122202010112011
202202122121120001221202222022201212222220112122122020022021
221212002222220122002212212212022120202010202221220102220022
222120212101211120212022222122202200022110212021021002222101
000220020210222022012222201011220012222200201202022221122201
210121011210222112220211222212221222212002021022211000122121
012110012221220212222112102221122220112222021220222200222110
222122101211212110112122022022212212200022120000222212221002
022001222102220020122002212222020020202211220121120200200212
111000222202112101202222100000202000221222102220012210220220
220220021212221212012020222022220122111100202122012222202121
202211222100022021222022122001201100211012120202202020012102
200220202020202221222022210222200222022112121201012220222021
122212222202112222220012012000122212210222022200122222202222
121111020221212222120011222121120102000220012022202222000220
022020100010112101121020100120220222121220222120001102002212
202212021210210212110012202222121101022122022101222222112202
022222111212220220110222022212202222000212121002112112022021
221022220000220222111022112002120000201202220122102100200202
022112022100222022222222101100222222200121102122202212222021
212122120201200102022212220120111100122200102222212222121101
212102101220222202211111022022202101022022222112102121020222
120200112002022221221012110221200202222000012212001112012221
022200120221202221020200222220022100010222220221221201011110
001222120122222022202222212221222222202211222121201112212012
222122122201220001202122222212021212212022122122121220201200
212022021000202022221221002222212202210202012020212022000112
022122000211022220120121011022220222022121220201121220201122
010222202022121112121222201222010120122212212021002211220220
221020000022221110211002220100201011221101122201112022221220
210121112220000120222221112002222101202022112210020122122112
012012122200011222221212222220002122100222212210212212020110
010101222021001222122202011012022221102212212201221122222121
220211202000010022122220200122020001202202222121222022020100
010122112201220212222122110122100010201212220222202202202100
012022222022012000202111022012122012010202120212122102022210
012212022102022120201220200102122002211002120112222222210222
002220222121012220011221221001102222000222210222011221022011
001121220121122110202122222012201020022222121222012222121121
201121222001202220001202102110110200100100112222122010021222
220212222222222122022222112212020022210101222111210020221121
212112101222212121121201202122122021000212112102111122220211
111001211022120100120122122012122100220002122221001022221221
121212010202101122222012211022222221122020101222122210200220
222222202122201222102110121221202212220201121201202201002212
102210220101022210122022200200221021022212122202002212200220
212202221222120221202212220210122212221222211222212212201012
110211120112221001121011110222201022101020210021012210222122
001010002110000002122112100112211210220010010002112212222222
221222220201220120121222021210221002022222021210121022202012
100002112102112120102201200222022020020212002202210221122221
222222212202000111202222202112121222202200220022022212022000
220121211122211100002121212202121100002212220222212201210121
002220121002102001121220022122022211202221211122002202222001
122010110121120200202122012021221021000200221020111202222212
121122202000002112212220221120122010112102121210222211222222
222222212222012122211122200222212122210200012202020201201022
122002221000112210222222210202210100212212012022220212102122
222221200211120122201101100200021022212121121120201021212022
022122222222012202112221120120121222120110022212210222210212
020020221120200221101122222221200022222222202122002212201212
022212221112222220221201010112001212210201220122112002221221
220221220220021112222222202220020220212122211222211002001201
012021022211222022201211012121202010001010212210202002021221
022022222222010112021222020211012021222212002020021020212210
002220021221200121222221212200121200001222021022001121121100
211222212120002211112121221001012202121120012202212211220022
210020222221112202222111021022222020102022022210010120201112
202122010221121022222120220201121222022021200011222021122222
202120010201101212002222210022220220022201202122010212220100
202212021200222222212221221222212120022012000112222121002012
222212212022200222002110020211022221222022122220112200122202
020111002112010002220020100220222022202222222211221010012110
201100211112020220222021220111012222221010210100001022002022
212122111122201222122002222222012122122221112101110122211102
220200222220022221221020222220110202122021022220220122222002
221102200101222122212102212121202112002110022102022000020001
201202111200220212212212202122111000112220202022202212011220
220202102120022022212211122022202222202112212221002210212220
102222012200122122222012222222222212101110012220120212210002
021111001212010200220022100112121110102222222212120110020120
120210122211221121202121012222122000022220200220222221212122
stdout
number of matches: 298208861472
took 0.397459521 s