// Notes: This solution works for small input only!
// Problem URL: https://code.google.com/codejam/contest/8224486/dashboard#s=p0&a=0
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
namespace GoogleCodeJam_Practice
{
class Program
{
long N;
long GetReversed ( long N )
{
char[] c = N.ToString ( ).ToCharArray ( );
Array.Reverse ( c );
long r = long.Parse ( new string ( c ) );
return r;
}
int[] rev;
int[] steps;
string ProcessCase ( )
{
long ans=steps[( int ) N];
return ans.ToString ( );
}
void Start ( )
{
string file1;
string file2;
file1 = @"e:\test_input.txt";
file1 = @"e:\A-small-practice.in";
StreamReader infile = new StreamReader ( file1 );
file2 = @"e:\ztest.out";
StreamWriter outfile = new StreamWriter ( file2 );
rev = new int[1000001];
for ( int i = 0; i < rev.Length; i++ )
{
rev[i] = ( int ) GetReversed ( i );
}
steps = new int[1000001];
for ( int i = 0; i < steps.Length; i++ )
steps[i] = int.MaxValue;
steps[1] = 1;
for ( int i = 2; i < steps.Length; i++ )
{
steps[i] = Math.Min ( steps[i], steps[i - 1] + 1 );
int r = rev[i];
steps[r] = Math.Min ( steps[r], steps[i] + 1 );
}
int nCases = int.Parse ( infile.ReadLine ( ) );
for ( int ncase=0; ncase < nCases; ncase++ )
{
string line = infile.ReadLine ( );
string[] inputs = line.Split ( new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries );
N = int.Parse ( inputs[0] );
// process case
string result = ProcessCase ( );
WriteOutput ( string.Format ( "Case #{0}: {1}", ncase + 1, result ), outfile );
}
infile.Close ( );
outfile.Close ( );
}
private void WriteOutput ( string text, StreamWriter outfile )
{
outfile.WriteLine ( text );
Console.WriteLine ( text );
}
static void Main ( string[] args )
{
Program p = new Program ( );
p.Start ( );
}
}
}
No comments:
Post a Comment