Advertisement
svetlai

Precision

Nov 13th, 2015
84
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 2.71 KB | None | 0 0
  1. namespace Precision
  2. {
  3.     using System;
  4.  
  5.     public class Program
  6.     {
  7.         public static void Main()
  8.         {
  9.             int maxDenominator = int.Parse(Console.ReadLine());
  10.             var fraction = Console.ReadLine().Split('.')[1];
  11.  
  12.             int bestNominator = 0;
  13.             int bestDenominator = 1;
  14.             int precision = 0;
  15.             for (int denominator = 1; denominator < maxDenominator; denominator++)
  16.             {
  17.                 int left = 0;
  18.                 int right = denominator;
  19.  
  20.                 while (left < right)
  21.                 {
  22.                     int middle = (left + right) / 2;
  23.                     if (Compare(fraction, middle, denominator))
  24.                     {
  25.                         right = middle;
  26.                     }
  27.                     else
  28.                     {
  29.                         left = middle + 1;
  30.                     }
  31.                 }
  32.  
  33.                 int current = Precision(fraction, left - 1, denominator);
  34.                 if (current > precision)
  35.                 {
  36.                     bestDenominator = denominator;
  37.                     bestNominator = left - 1;
  38.                     precision = current;
  39.                 }
  40.  
  41.                 current = Precision(fraction, left, denominator);
  42.                 if (current > precision)
  43.                 {
  44.                     bestDenominator = denominator;
  45.                     bestNominator = left;
  46.                     precision = current;
  47.                 }
  48.             }
  49.  
  50.             Console.WriteLine("{0}/{1}", bestNominator, bestDenominator);
  51.             Console.WriteLine(precision + 1);
  52.         }
  53.  
  54.         public static bool Compare(string fraction, int a, int b)
  55.         {
  56.             a *= 10;
  57.             int i;
  58.             for (i = 0; i < fraction.Length; i++)
  59.             {
  60.                 int digit = a / b;
  61.                 if (digit < fraction[i] - '0')
  62.                 {
  63.                     // our number is smaller - go right
  64.                     return false;
  65.                 }
  66.                 else if (digit > fraction[i] - '0')
  67.                 {
  68.                     // our number is bigger - go left
  69.                     return true;
  70.                 }
  71.  
  72.                 a = (a % b) * 10;
  73.             }
  74.  
  75.             return true;
  76.         }
  77.  
  78.         public static int Precision(string fraction, int a, int b)
  79.         {
  80.             a *= 10;
  81.             int i;
  82.             for (i = 0; i < fraction.Length; i++)
  83.             {
  84.                 int digit = a / b;
  85.                 if (digit != fraction[i] - '0')
  86.                 {
  87.                     break;
  88.                 }
  89.  
  90.                 a = (a % b) * 10;
  91.             }
  92.  
  93.             return i;
  94.         }
  95.     }
  96. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement