For the hardest problem of the large data set, you are looking at getting the integer part of (3+sqrt(5))^(2,000,000,000). The number of decimal places you need to make that calculation accurately is more than 1,000,000,000:
(3+sqrt(5)+x)^2,000,000,000 >= (3+sqrt(5))^2,000,000,000+2,000,000,000(3+sqrt(5))^1,999,999,999x Even if you were able to set this up, the calculation might be quite slow. On 8 Apr 2012, at 19:44, Sachin Gupta <[email protected]> wrote: > BigDecimal in java can store it. The statement > System.out.println(x.toString()); shows the value with 48 decimal places, do > we need more than that. > > On Sunday, April 8, 2012, Luke Pebody wrote: > The numeric types used by programming languages are not accurate enough to > keep the full decimal expansion of 3+sqrt(5). As such, numerical inaccuracies > will turn up. > On 8 Apr 2012 13:58, "Sachin Gupta" <[email protected]> wrote: > can anyone please check why this code is giving wrong answers. I've checked > the solutions each of them uses recursion to solve the problem. > http://code.google.com/codejam/contest/32016/dashboard#s=p2 > > import java.io.*; > import java.math.*; > import java.util.*; > > public class Main { > public static void main (String args[]) throws Exception > { BufferedReader in = new BufferedReader(new > FileReader("C:\\downloads\\c-small-practice.in")); > BufferedWriter out = new BufferedWriter(new > FileWriter("C:\\downloads\\c-output.in")); > int t = Integer.parseInt(in.readLine()); > BigDecimal x = new BigDecimal(Math.sqrt(5)); > x = x.add(BigDecimal.valueOf(3)); > System.out.println(x.toString()); > for (int i=1;i<=t;i++) > { int n = Integer.parseInt(in.readLine()); > BigDecimal bd ; > bd = x; > bd = bd.pow(n); > // System.out.println(bd); > // System.out.println(bd.toBigInteger()); > Formatter fmt = new Formatter(); > fmt.format("%03d",bd.toBigInteger()); > // System.out.println(fmt); > > StringBuilder sb = new StringBuilder(fmt.toString()); > // System.out.println(sb.substring(sb.length()-3,sb.length())); > out.write("Case #"+i+": "+sb.substring(sb.length()-3,sb.length())); > out.newLine(); > } > out.close(); > } > } > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/google-code?hl=en. -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/google-code?hl=en.
