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);
}
}
}