Friday, May 8, 2015

Google Code Jam 2015 Round 1B Problem A. Counter Culture

// Google Code Jam 2015 Round 1B Problem A. Counter Culture
// 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