fork(3) download
copy 
  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
comments (?)
stdin
copy 
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
copy 
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
https://ideone.com/Fn9qM
Facebook 2012 SquishedStatus
language:
C# (gmcs 5.20.1)
created:
12 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!