fork(3) download
copy 
  1. // Program description: http://p...content-available-to-author-only...k.com/cms/?p=449
  2. // Puzzle origin: http://w...content-available-to-author-only...k.com/hackercup/problems.php?pid=191596157517194&round=225705397509134
  3.  
  4. using System;
  5. using System.Collections.Generic;
  6. using System.Linq;
  7. using System.Text;
  8.  
  9. namespace Protsyk.Puzzles.Checkpoint {
  10.     class Tuple<T1, T2>
  11.     {
  12.       public T1 Item1 {get; set;}
  13.       public T2 Item2 {get; set;}
  14.  
  15.       public Tuple(T1 item1, T2 item2) { Item1 = item1; Item2 = item2; }
  16.     }
  17.  
  18.     class Program {
  19.  
  20.         /// <summary>
  21.         /// Mapping from number N to list of points < (x1, y1), ... >
  22.         /// For each point (x1, y1) in the list of number N following property holds
  23.         /// G(x1, y1) = N, where G(x,y) - is the number of shortest paths from the origin
  24.         /// to (x,y) when only moving right and up is allowed.
  25.         /// </summary>
  26.         static Dictionary<int, List<Tuple<int, int>>> mapping = new Dictionary<int, List<Tuple<int, int>>>();
  27.  
  28.         static void Main(string[] args) {
  29.             BuildCache();
  30.  
  31.             int R = int.Parse(Console.ReadLine());
  32.             for (int testcase = 0; testcase < R; testcase++) {
  33.                 int S = int.Parse(Console.ReadLine());
  34.  
  35.                 if (S == 1) {
  36.                     Console.WriteLine(string.Format("Case #{0}: {1}", testcase + 1, 2));
  37.                     continue;
  38.                 }
  39.  
  40.                 int bestX = int.MaxValue / 2, bestY = int.MaxValue / 2;
  41.  
  42.                 // For each s1,s2 such that s1*s2 = S
  43.                 foreach (var factorization in Factorize(S)) {
  44.                     int s1 = factorization.Item1;
  45.                     int s2 = factorization.Item2;
  46.  
  47.                     // For each grid points for s1
  48.                     foreach (var point1 in GetPointsForNumber(s1)) {
  49.                         // For each grid points for s2
  50.                         foreach (var point2 in GetPointsForNumber(s2)) {
  51.  
  52.                             // Find best point (with shortest path)
  53.                             if (point1.Item1 + point2.Item1 + point1.Item2 + point2.Item2 < bestX + bestY) {
  54.                                 bestX = point1.Item1 + point2.Item1;
  55.                                 bestY = point1.Item2 + point2.Item2;
  56.                             }
  57.  
  58.                         }
  59.                     }
  60.                 }
  61.  
  62.                 Console.WriteLine(string.Format("Case #{0}: {1}", testcase + 1, bestX + bestY));
  63.             }
  64.         }
  65.  
  66.         /// <summary>
  67.         /// Factorize number into two multipliers
  68.         /// </summary>
  69.         static IEnumerable<Tuple<int, int>> Factorize(int s) {
  70.             int s1 = 1;
  71.             int threshold = (int)Math.Sqrt(s) + 1;
  72.  
  73.             while (s1 <= threshold) {
  74.                 int remainder = s % s1;
  75.  
  76.                 if (remainder == 0) {
  77.                     int s2 = s / s1;
  78.                     if (s2 < s1) yield break;
  79.                     yield return new Tuple<int, int>(s1, s2);
  80.                 }
  81.                 ++s1;
  82.             }
  83.         }
  84.  
  85.         static Dictionary<int, List<Tuple<int, int>>> BuildCache() {
  86.             List<int> prev = null;
  87.             List<int> next = new List<int>();
  88.  
  89.             // Start from the second row of the paths matrix G.
  90.             // No need to calculate first and second row, because:
  91.             // G(x,0)=G(0,x)=1
  92.             // G(x,1)=G(1,x)=x+1
  93.             int i = 2;
  94.             int j = 2;
  95.  
  96.             while (true) {
  97.                 while (true) {
  98.                     int number;
  99.                     if (i == j) {
  100.                         if (i == 2)
  101.                             number = 2 * (i + 1); // Use G(x,1)=x+1
  102.                         else
  103.                             number = 2 * prev[1]; // Use previous row
  104.                     } else {
  105.                         if (i == 2)
  106.                             number = next[j - i - 1] + (j + 1); // Use G(x,1)=x+1
  107.                         else
  108.                             number = next[j - i - 1] + prev[j - i + 1]; // Use previous row
  109.                     }
  110.  
  111.                     // Task threshold
  112.                     if (number > 10000000)
  113.                         break;
  114.  
  115.                     List<Tuple<int, int>> pointslist = new List<Tuple<int, int>>();
  116.                     if (!mapping.TryGetValue(number, out pointslist)) {
  117.                         pointslist = new List<Tuple<int, int>>();
  118.                         pointslist.Add(new Tuple<int, int>(number - 1, 1));
  119.                         mapping.Add(number, pointslist);
  120.                     }
  121.                     pointslist.Add(new Tuple<int, int>(i, j));
  122.  
  123.                     next.Add(number);
  124.                     ++j;
  125.                 }
  126.  
  127.                 if (next.Count < 2) {
  128.                     // Only one number, break
  129.                     break;
  130.                 } else {
  131.                     prev = next;
  132.                     next = new List<int>(next.Count + 1);
  133.                 }
  134.  
  135.                 ++i;
  136.                 j = i;
  137.             }
  138.             return mapping;
  139.         }
  140.  
  141.         /// <summary>
  142.         /// Get points from the cache
  143.         /// </summary>
  144.         static IEnumerable<Tuple<int, int>> GetPointsForNumber(int s) {
  145.             if (s == 1) {
  146.                 // Return point closest to origin
  147.                 yield return new Tuple<int, int>(1, 0);
  148.                 yield break;
  149.             }
  150.  
  151.             List<Tuple<int, int>> result;
  152.             if (mapping.TryGetValue(s, out result)) {
  153.                 foreach (Tuple<int, int> point in result)
  154.                     yield return point;
  155.             } else {
  156.                 // There is only one point for such number,
  157.                 // it is in the first row of the matrix
  158.                 yield return new Tuple<int, int>(s - 1, 1);
  159.             }
  160.         }
  161.  
  162.     }
  163. }
  164.  
Success #stdin #stdout 0.06s 38072KB
comments (?)
stdin
copy 
20
2
5
7312234
4457400
9763393
10000000
2128949
441362
846
6355041
1180
9407449
5097
298690
7180766
7635682
5700
9946273
7827820
9768443
stdout
copy 
Case #1: 3
Case #2: 6
Case #3: 5845
Case #4: 26
Case #5: 9763394
Case #6: 6325
Case #7: 4086
Case #8: 220683
Case #9: 65
Case #10: 130
Case #11: 65
Case #12: 17930
Case #13: 1702
Case #14: 537
Case #15: 211233
Case #16: 6307
Case #17: 25
Case #18: 9946274
Case #19: 60
Case #20: 9768444
https://ideone.com/8FVw5
Facebook 2012 Checkpoint
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!