Using recursive procedure like topological sorting.

And how?

n=3000

6230944380615661730540866744905062220607354471963766287778397756065940
6962697903814082629320941801101660304581383981489487361062625347661816
5706321659264965023017203487210780255823880970691747085650866739360077
645709393425508719830393155473510779779930751

But I got wa too.

1322070819480806636890455259752144365965422032752148167664920368226828
5973467048995407783138506080619639097776968725823559509545821006189118
6534272525795367402762022519832080387801477422896484127439040011758861
8041128947815623094438061566173054086674490506178125480344405547054397
0388958174653682549161362208302685637785822902284163983078878969185564
0408489893760937324217184635993869

When n=3000 my AC program print:
1322070819480806636890455259752144365965422032752148167664920368226828597346704899540778313850608061963909777696872582355950954582100618911865342725257953674027620225198320803878014774228964841274390400117588618041128947815623094438061566173054086674490506178125480344405547054397038895817465368254916136220830268563778582290228416398307887896918556404084898937609373242171846359938695516765018940588109060426089671438864102814350385648747165832010614366132173102768902855220001

Because correct is:
1322070819480806636890455259752144365965422032752148167664920368226828597346704899540778313850608061963909777696872582355950954582100618911865342725257953674027620225198320803878014774228964841274390400117588618041128947815623094438061566173054086674490506178125480344405547054397038895817465368254916136220830268563778582290228416398307887896918556404084898937609373242171846359938695516765018940588109060426089671438864102814350385648747165832010614366132173102768902855220001

it is 3^1000

use extended

Use array friend, write your own multiply function.
Timus array max size = 64 K (or i may wrong)
which means you can create char array[64000]
store up to 64K digit

Edited by author 16.04.2007 20:37

Edited by author 16.04.2007 20:56

if in pascal
you can use extended

what is 'j'

int a[ 100000 ],
short b[ 1000 ];

It depends on the way use solve the problem. If you do all calculations in integers, any EPS from 1e-0 to 1e-15 will give right answer =)

100000 * 4 + 100000 * 2 = 600000 bytes + plus memory for your programm.
Memory limit can be 750000 bytes instead of 750 Kb.

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Reader;
import java.io.StreamTokenizer;
import java.io.Writer;
import java.util.Stack;
import java.util.LinkedList;

public class ACM1001 {

    Reader reader = null;
    Writer writer = null;
    StreamTokenizer in = null;
    PrintWriter out = null;
    boolean oj = System.getProperty("ONLINE_JUDGE") != null;
    Stack<Double> dInput = null;
    LinkedList<Double> dOuput = null;
    BufferedReader bufReader= null;

     public void run()
       {
           try{
               reader = oj ? new InputStreamReader(System.in) : new FileReader("input1001.txt");
               bufReader= new BufferedReader(reader);
               in = new StreamTokenizer(bufReader);
               writer = new OutputStreamWriter(System.out);
               out = new PrintWriter(writer);

               dInput = new Stack<Double>();
               dOuput = new LinkedList<Double>();
               int j = in.nextToken();
               while(j != StreamTokenizer.TT_EOF)
                {
                   if(j == StreamTokenizer.TT_NUMBER)
                   {
                       dInput.push(in.nval);
                   }
                   j = in.nextToken();
                }
           solve();
           out.flush();
           }
           catch (Exception e)
            {
                 e.printStackTrace();
            }
       }

     public void solve()
    {
        //long 类型的最大值的常量，该值为 2^63 -1 至  2^-63
        //double:(2-2-52)·2^1023 至 2^-1074
        while(!dInput.isEmpty()){
            double dva = dInput.pop();
            double x=Math.sqrt(dva);
            dOuput.add(x);
        }
        //BigDecimal 未不可变的、任意精度的有符号十进制数
        while(!dOuput.isEmpty()){
            System.out.printf("%.4f \n",dOuput.removeFirst());
        }
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        new ACM1001Solve2().run();
    }

}

class ACM1001Solve2 extends ACM1001
{
     public void run()
       {
           try{
               reader = oj ? new InputStreamReader(System.in) : new FileReader("input1001.txt");
               bufReader= new BufferedReader(reader);
               in = new StreamTokenizer(bufReader);
               writer = new OutputStreamWriter(System.out);
               out = new PrintWriter(writer);

               dInput = new Stack<Double>();
               int j = in.nextToken();
               while(j != StreamTokenizer.TT_EOF)
                {
                   if(j == StreamTokenizer.TT_NUMBER)
                   {
                       solve2(in.nval);
                   }
                   j = in.nextToken();
                }
               bufReader.close();
               bufReader = null;
               reader.close();
               reader = null;
               while(!dInput.isEmpty()){
                    System.out.printf("%.4f \n",dInput.pop());
                }
           out.flush();
           dInput.clear();
           dInput = null;
           out = null;
           writer.close();
           writer = null;
           }
           catch (Exception e)
            {
                 e.printStackTrace();
            }
           finally{
               reader = null;
               writer = null;
             }
       }

     private void solve2(double nn)
     {
        double x=Math.sqrt(nn);
        dInput.push(x);
     }
}//end class ACM1001Solve2

Mine solution have WA1 too...
It is very strange because test Nr1 must be the test from the sample...

Edited by author 28.03.2009 01:14

Edited by author 28.03.2009 01:14

By the way the correct answer is 0.38528021

Sorry it's my fault, there is an other problem in my program. I've got ac!

    Please help!

take N=29
p=0 q=28 i=14 L=1
p=15 q=28 i=21 L=2
p=22 q=28 i=25 L=3
this is cancelled since i value is not 10
NOW the other way
p=0 q=28 i=14 L=1
p=0 q=13 i=6 L=2
p=0 q=5 i=2 L=3
this is cancelled since i value is not 10
can any body explain me this??