1. Erste Version: JAVA, Gunaar Hage
/**
* ACM programming Contest WS 08/09 "944 - Happy Numbers"
* Time limit exceeded
* @author Gunnar Hage, AP5(IFB5A) Okt. 2008
*
* Aufgabe: http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&page=show_problem&problem=885
*/


import java.io.IOException;
import java.util.StringTokenizer;

/*
* AAAAAARGGG DIESE VERDAMMTE AUSGABE DAUERT ZU LANG! die Berechnug dauert laut dem
* System.CurrentTimeMillis() nur 0.031 Sekunden aber die Ausgabe dauert 5 Sekunden.
*/
public class Main {
    public static void main(String... args){
        int[] hn = new int[406]; //f(99999)=5*9*9=405
        int[] newDV = new int[]{0,1,3,5,7,9,11,13,15,17,-81};//enthält die Werde um die newZ bei Ziffernänderung verändert werden muss.
        int z =0; // Bleibt bis zum schreiben ins Array gleich.
        int newZ = 0; // wird für jeden Iterationsschrit neu berechnet
        int oldZ = 0; // Wird wärend der Quersummenberechnung zerlegt.
        int count = 0; // Zählt die anzahl der iterationsschritte
        double temp = System.currentTimeMillis();
       
        hn[1] = 1;   
        hn[4] = -1; // Value for sad numbers
//Vorbereitung evtl. in Methode auslagern.
//Schreibt die Anzahl der benötigten iterationsschritte in das Array wenn die Zahl eine "Happy Number" ist. Bei Sad Numbers -1
        for(z=2; z<hn.length; z++){
            count=1; oldZ = z; newZ = 0;
            while(oldZ != 1){
                newZ = 0;
                while(oldZ > 0){
                    newZ = newZ + (oldZ%10) * (oldZ%10);
                    oldZ = oldZ/10;
                }
                oldZ = newZ;
                if(hn[newZ] == -1){// Wenn der neue Iterationsschritt schon als sad number bekannt ist
                    hn[z] = -1;
                    oldZ = 1;
                }
                else if(hn[newZ] != 0){//Wenn die anzahl der Folgenden Iterationsschirtte bis zum erkennen der Happy Number schon bekannt ist.
                    hn[z] = hn[newZ] + count;
                    oldZ = 1;
                }
                count++;
            }
        }
        // Das Array ist mit allen Lösungen bis 405 gefüllt.
        //System.out.println(System.currentTimeMillis()-temp);

//Einlesen und Ausgeben.
        StringTokenizer st;
        String line = ReadLn(255);
        int low,high;
        String ausgabe = "";
        // Solange neue Zeilen gelesen werden.
        while(line != null){
            st = new StringTokenizer(line);
            low = Integer.parseInt(st.nextToken());
            high = Integer.parseInt(st.nextToken());
            //temp = System.currentTimeMillis();
            //die erste Zahl wird ausserhalb der schleife bearbeitet, weil ich in der Schleife NewZ brauche.
            if(low !=1){
                oldZ = low;
                while(oldZ > 9){
                    newZ = newZ + (oldZ%10) * (oldZ%10);
                    oldZ = oldZ/10;
                }
                newZ+=oldZ*oldZ;
                if(hn[newZ]!= -1)
                    ausgabe = ausgabe + low + " " + (hn[newZ]+1) + "\n";
            }
            else{
                newZ=1;
                ausgabe = ausgabe + "1 1\n";
            }
            //Ab der zweiten Zahl wird dann innerhalb der Schleife gerechnet.
            z = low + 1;
            //d1 bis d5 representieren die Ziffern von z.
            int d1=z/10000, d2=(z/1000)%10, d3=(z/100)%10, d4=(z/10)%10, d5 = z%10;
            if(d5==0)d5=10;
            while(z<=high){
                // Zu langsam! 5,1xx Sekunden für die Berechnung von 1 bis 99999
                // Die nächstes 5 Zeilen lassen sich durch die 5 unten auskommentierten ersetzen.
                newZ+= 2*d5-1;
                if(d5==10){ d5=0; newZ-=100; d4++; newZ+=2*d4-1;
                    if(d4==10){d4=0; newZ-=100; d3++; newZ+=2*d3-1;
                        if(d3==10){d3=0; newZ-=100; d2++; newZ+=2*d2-1;
                            if(d2==10){d2=0; newZ-=100; d1++; newZ+=2*d1-1;
                            }
                        }
                    }
                }
                /* Dachte es wäre zu langsam... desshalb die lösung oben ohne Arrayzugriff, statdessen 1 addition mehr
                newZ+=newDV[d5];
                if(d5==10){ d5=0; d4++; newZ+=newDV[d4];
                    if(d4==10){d4=0; d3++; newZ+=newDV[d3];
                        if(d3==10){d3=0; d2++; newZ+=newDV[d2];
                            if(d2==10){d2=0; d1++; newZ+=newDV[d1];*/
               
                if(hn[newZ]!= -1)
                    ausgabe = ausgabe + z + " " + (hn[newZ]+1) + "\n";
                   
                d5++;
                z++;
            }
            //System.out.println(System.currentTimeMillis()-temp);
            System.out.println(ausgabe);
            //System.out.println(ausgabe.length());
            ausgabe = "";
            line = ReadLn(255);
        }
        System.exit(0);
    }
   
     static String ReadLn (int maxLg)  // utility function to read from stdin
     {
         byte lin[] = new byte [maxLg];
         int lg = 0, car = -1;
         try
         {
             while (lg < maxLg)
             {
                 car = System.in.read();
                 if ((car < 0) || (car == '\n')) break;
                 lin [lg++] += car;
             }
         }
         catch (IOException e)
         {
             return (null);
         }
         if (car < 0 || lg < 2) return (null);  // eof
         return (new String (lin, 0, lg));
     }
     /* Der alte Algorytmus ist leider zu langsam. Möglicheriweise oder sogar wahrscheilich ist er in wirklichkeit
      *  doch schneller als der der jetzt drin ist.
             for(z=low;z<=high;z++){
                 oldZ = z; newZ = 0;
                while(oldZ > 9){
                    //digit = oldZ%10; newZ = newZ + digit*digit; // 1-99999 -> 4,4xx Sekunden
                    //newZ = newZ + (int)Math.pow(oldZ%10,2); // 1-99999 -> 4,6xx sekunden
                    newZ = newZ + (oldZ%10) * (oldZ%10); // 1-99999 -> 4,3xx Sekunden
                    oldZ = oldZ/10;
                }
                newZ = newZ + oldZ*oldZ;
                if(hn[newZ]!= -1)
                    ausgabe = ausgabe + z + " " + (hn[newZ]+1) + "\n";
             }
             System.out.println(ausgabe + "\n");
             ausgabe = "";
             System.out.println(System.currentTimeMillis()-temp);
             line = ReadLn(255);
         }
         */
}