fork(1) download
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4.  
  5. namespace Protsyk.Puzzles.SquishedStatus {
  6. class Program {
  7. static void Main(string[] args) {
  8. ConsoleReader reader = new ConsoleReader();
  9.  
  10. /// Read test cases count
  11. reader.MoveNext();
  12. int N = int.Parse(reader.Current);
  13.  
  14. for (int j = 0; j < N; j++) {
  15.  
  16. /// Read Max value
  17. reader.MoveNext();
  18. int M = int.Parse(reader.Current);
  19.  
  20. List<int> parsedNumbers = new List<int>();
  21.  
  22. reader.MoveNext();
  23. string squished_status = reader.Current;
  24.  
  25. /// Split squished_status into the smallest valid numbers
  26. /// Example: M = 5, squished_status = 141 => parsedNumbers = { 1, 4, 1 }
  27. /// Example: M = 12, squished_status = 101 => parsedNumbers = { 10, 1 }
  28. /// Example: M = 2, squished_status = 101 => Error
  29. int number = 0;
  30. foreach (char c in squished_status) {
  31. if (c == '0') {
  32. if (number == 0) {
  33. parsedNumbers.Clear();
  34. break;
  35. } else {
  36. number *= 10;
  37. if (number > M) {
  38. number = 0;
  39. parsedNumbers.Clear();
  40. break;
  41. }
  42. }
  43. } else {
  44. if (number != 0) {
  45. parsedNumbers.Add(number);
  46. }
  47. number = c - '0';
  48. }
  49. }
  50. if (number > 0) {
  51. parsedNumbers.Add(number);
  52. }
  53.  
  54. if (parsedNumbers.Count == 0) {
  55. Console.WriteLine(string.Format("Case #{0}: {1}", j + 1, 0));
  56. } else {
  57.  
  58. List<int> numbers = new List<int>();
  59. List<uint> sequenceCounts = new List<uint>();
  60. sequenceCounts.Add(1);
  61.  
  62. /// Count numbers using recursive formula
  63. for (int i = parsedNumbers.Count - 1; i >= 0; i--) {
  64. SolveCounting(M, parsedNumbers[i], numbers, sequenceCounts);
  65. }
  66.  
  67. /// For small inputs use exhaustive search for verification
  68. if (parsedNumbers.Count < 15) {
  69. LinkedList<int> input = new LinkedList<int>(parsedNumbers);
  70. if (sequenceCounts.Last() != (1 + SolveEnumerating(M, input.First, input)) % 0xfaceb00c) {
  71. Console.WriteLine(string.Format("Case #{0}: {1}", j + 1, "Error"));
  72. }
  73. }
  74.  
  75. Console.WriteLine(string.Format("Case #{0}: {1}", j + 1, sequenceCounts.Last()));
  76. }
  77. }
  78. }
  79.  
  80. private static int Combine(int next, int previous) {
  81. if (previous < 10) previous += next * 10;
  82. else if (previous < 100) previous += next * 100;
  83. else { return int.MaxValue; }
  84. return previous;
  85. }
  86.  
  87. private static void SolveCounting(int max, int i, List<int> numbers, List<uint> sequenceCounts) {
  88. ulong newCount = sequenceCounts.Last();
  89.  
  90. // Combine two digits
  91. if (numbers.Count > 0) {
  92. int combine1 = Combine(i, numbers[0]);
  93. if (combine1 <= max) {
  94. checked {
  95. newCount += sequenceCounts[sequenceCounts.Count - 2];
  96. }
  97.  
  98. // Combine three digits
  99. if (numbers.Count > 1) {
  100. int combine2 = Combine(combine1, numbers[1]);
  101. if (combine2 <= max) {
  102. checked {
  103. newCount += sequenceCounts[sequenceCounts.Count - 3];
  104. }
  105. }
  106. }
  107. }
  108. }
  109.  
  110. sequenceCounts.Add((uint)(newCount % 0xfaceb00c));
  111. numbers.Insert(0, i);
  112. }
  113.  
  114. private static int SolveEnumerating(int max, LinkedListNode<int> current, LinkedList<int> input) {
  115. int solutions = 0;
  116. while (current.Next != null) {
  117.  
  118. if (current.Value < max) {
  119.  
  120. /// Try to combine consecutive input numbers
  121. int combine = Combine(current.Value, current.Next.Value);
  122. if (combine > max) {
  123. current = current.Next;
  124. continue;
  125. }
  126.  
  127. int currentValue = current.Value;
  128. int nextValue = current.Next.Value;
  129.  
  130. /// Replace number with combined value
  131. current.Value = combine;
  132. input.Remove(current.Next);
  133.  
  134. /// Recursively call solve method on reduced input
  135. solutions += 1 + SolveEnumerating(max, current, input);
  136.  
  137. /// Restore original values
  138. current.Value = currentValue;
  139. input.AddAfter(current, nextValue);
  140. }
  141.  
  142. current = current.Next;
  143. }
  144.  
  145. return solutions;
  146. }
  147.  
  148. /// <summary>
  149. /// Helper class for parsing input
  150. /// </summary>
  151. class ConsoleReader : IEnumerable<string>, IEnumerator<string> {
  152. public IEnumerator<string> GetEnumerator() {
  153. return this;
  154. }
  155.  
  156. System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() {
  157. return this;
  158. }
  159.  
  160. public void Dispose() {
  161. }
  162.  
  163. public string Current {
  164. get { return strings[position]; }
  165. }
  166.  
  167. object System.Collections.IEnumerator.Current {
  168. get { return strings[position]; }
  169. }
  170.  
  171. public bool MoveNext() {
  172. position++;
  173. if (strings != null && position < strings.Length) {
  174. return true;
  175. }
  176.  
  177. strings = Console.ReadLine().Split(new char[] { '\r', '\n', '\t', ' ' }, StringSplitOptions.RemoveEmptyEntries).ToArray();
  178. position = 0;
  179. return strings.Length > 0;
  180. }
  181.  
  182. public void Reset() {
  183. position = 0;
  184. strings = null;
  185. }
  186.  
  187. private int position;
  188. private string[] strings;
  189. }
  190.  
  191. }
  192. }
Success #stdin #stdout 0.05s 37296KB
stdin
20
190 9529102074196543040963325
255
219
92 87425153970967993390831896675153851510854781083794529288118964576857047283178102891855976962574675710971584027
40 9188174
70 8675309
204 335498212
203 687737220877470653784446097316072785470
56 070999427563706517458243835585840290099051637074025394195594348586510834073090163948736588183957349602833959886681418618106557443908727133367714791349473784783516431847035942668366755350157283760764531248617211483790180304621672055750617302943116131142903069883759519683748609377968256054437899455604836182222294525031294343713833201869042441444846948174771572377238024369781
2
101
180 71135853797525154801574664429928955385969111492458546393108368
144 403420455286144733012394352796117676232438993658729712221550931250841303194844906324788136156913626810108948602023083594977223986502041169240216642530162552975968233385427485675131472718018964836808453936722129133940950121976774689537233792725857619706585846714131638551181612253217
12
12
25 646522
134 2406258858721918774208848120315517208323779940599828715494389738665554681038314446893101871003518703575496336511449627393919132748479928913340144555418397315103310973766058610954180421686012930554663239422912710632257959476189261669997676809989671567278292632886370402049069985046878555076392720791616383499884307075233764956906527854413716114792441649375534077153257152101247222135886802040538230547674927916381416649052144975585897241738727151911864406075
116 972759570129420701017343026504780735238724865028026190998930433648895154524191409145141283939575313912329760551461452376912991044578
111 2636907296373399885646047517304031318176238406483770114869777782538642745151012568233889125626174631927487710326357830166987670817345199561837513121049890870755907
113 51304587103122063086234867477045723173180547403247145600300063966119431864569659559335776509576195196593245332640561449734900616851975700264874390248030968166
205 52266698626452
173 30112824594327595526379236283733863054755720634395622456658473382016537089827468578466186440548412571221610515303525092317381280436948960142601743842389999840805575879010781899131467875
171 0087894675463649
stdout
Case #1: 1365
Case #2: 4
Case #3: 1051059688
Case #4: 4
Case #5: 2
Case #6: 55
Case #7: 371280
Case #8: 0
Case #9: 0
Case #10: 2173147248
Case #11: 1591622528
Case #12: 2
Case #13: 2
Case #14: 2229146040
Case #15: 2694707812
Case #16: 2725167472
Case #17: 0
Case #18: 610
Case #19: 1263721604
Case #20: 0