Wednesday, September 9, 2015

project euler 320 problem

https://projecteuler.net/problem=230



1. A
2. B
3. AB
4. BAB
5. ABBAB
6. BABABBAB
.......

At first, I tired to find some repeated pattern.  between A And B.
Maybe I took one hour to find it.
but the result was failed. there is no pattern and had not to think about findind pattern.
Finally I thought this way.

A :
14159265358979323846264338327950288419716939937510
58209749445923078164062862089986280348253421170679

B:
82148086513282306647093844609550582231725359408128
48111745028410270193852110555964462294895493038196


Fibonaci (n) = Fibonaci(n-2) + Fibonaci(n-1);

so make array to put length of F(n);

arr[1] = 100;
arr[2] = 100;
arr[3] = 200;
arr[4] = 300;
arr[5] = 500;

if i want to find 320 I should find from arr[5]
because 500 covered 320 index word.
and find 20 position from arr[4];
arr[4] is made of arr[2] + arr[3]
next find 20 position of arr[2]

if the index of arr[] is 1 or 2, the answer is arr[1 Or to].charIndex(20);

My java code is below.
(Actually It is dirty code, need to be refactored)



import java.math.BigInteger;
import java.util.ArrayList;

/**
 * 처음에는 BB가 중복되서 나오는 숫자의 일정한 패턴이 있는줄 알았다.
 * 알고보니 일정한 패턴은 없네..
 * 
 * 그래서 접근하는 방법은 역 Search 방법이다.
 * @author ddavid
 *
 */
public class number230 {
 
 public static String first ="1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";
 public static String second ="8214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196";
 
 public static BigInteger total = BigInteger.ZERO;
 
 public static void main(String args[]){

  
  long start= System.currentTimeMillis();
  real();
  
  System.out.println(System.currentTimeMillis()-start);
  
 }
 
 public static void DAB(long num){
  String subFirst = "";
  String subSecond = "";
  subFirst = first;
  subSecond = second;
  long val =  num;
  System.out.println("val : " + val);
  
  
  for (int k = 0; k <15; k++) {
  
   String temp =subFirst+subSecond;
   
   subFirst = subSecond;
   subSecond = temp;
   
   if(subSecond.length() > val){
    System.out.println(subSecond.charAt((int)val-1));
    break;
   }
  }
 }
 
 public static void realDAB(long num){
  long val =  num;  // 81420679895522450
//  long val =  35;  // 81420679895522450
  
  System.out.println("val  : " + val);
  ArrayList<Long> cntList  = new ArrayList<Long>();
  cntList.add((long)first.length());
  cntList.add((long)first.length());
  while (true) {
   long two = cntList.get(cntList.size()-1);
   long one = cntList.get(cntList.size()-2);
   
   long sum = one+two;
   cntList.add(sum);
   if(sum > val){
    break;
   }
  }
  find(cntList.size()-1, val, cntList, 0);
 }
 
 public static void real(){
  for (int i = 0; i < 18; i++) {
   long val =  (long)(127+19*i)* (long)Math.pow(7, i);  // 81420679895522450
//   long val =  35;  // 81420679895522450
   
   System.out.println("val  : " + val);
   ArrayList<Long> cntList  = new ArrayList<Long>();
   cntList.add((long)first.length());
   cntList.add((long)first.length());
   while (true) {
    long two = cntList.get(cntList.size()-1);
    long one = cntList.get(cntList.size()-2);
    
    long sum = one+two;
    cntList.add(sum);
    if(sum > val){
     break;
    }
   }
   find(cntList.size()-1, val, cntList, i);
  }
  System.out.println(total.toString());
 }
 
 public static void find(int index, long position, ArrayList<Long> cntList, int i){
  if(index == 1 || index ==0){
   System.out.println("index : " + index + "  position : " + position );
   
   if(index == 0){
    System.out.println(first.charAt((int)position -1));
    total= total .add(BigInteger.valueOf((long)Math.pow(10, i)).multiply(BigInteger.valueOf(Long.valueOf(first.charAt((int)position -1) +""))) );
   }else{
    System.out.println(Long.valueOf(second.charAt((int)position -1) +""));
    total= total .add(BigInteger.valueOf((long)Math.pow(10, i)).multiply(BigInteger.valueOf(Long.valueOf(second.charAt((int)position -1) +""))) );
   }
   return;
  }
  if(position <= cntList.get(index -2)){   // one 위치인경우 
   find(index-2,  position  , cntList, i);
  }else{ // last 위치인경우
   find(index-1, position - cntList.get(index -2), cntList, i);
  }
 }
}

No comments:

Post a Comment