10183 - How Many Fibs?

[sith]

Thanks for your case.
I've updated my solution but sill get WA

Code: Select all

import java.io.*;
import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Main {


    public static void main(String[] args) {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        List<BigDecimal> fibonacciNumber = new ArrayList<BigDecimal>();

        fibonacciNumber.add(BigDecimal.ONE);
        fibonacciNumber.add(BigDecimal.valueOf(2));

        Scanner scanner = new Scanner(reader);

        BigDecimal maxValue = BigDecimal.valueOf(10).pow(100);
        int index = 2;
        BigDecimal newFib = BigDecimal.ZERO;
        while (newFib.compareTo(maxValue) <= 0) {
            newFib = fibonacciNumber.get(index - 1).add(fibonacciNumber.get(index - 2));
            fibonacciNumber.add(newFib);
            index++;
        }


        try {
            BigDecimal first;
            BigDecimal second;

            while (true) {
                first = new BigDecimal(scanner.next());
                second = new BigDecimal(scanner.next());
                if (first.equals(BigDecimal.ZERO) && second.equals(BigDecimal.ZERO)) {
                    break;
                }                

                if (first.equals(BigDecimal.ZERO)) {
                    first = BigDecimal.ONE;
                }

                int start = 0;
                int end = 0;

                for (int i = 0; i < fibonacciNumber.size(); i++) {
                    BigDecimal bigDecimal = fibonacciNumber.get(i);
                    if (first.compareTo(bigDecimal) <= 0) {
                        start = i;
                        break;
                    }
                }

                for (int i = start; i < fibonacciNumber.size(); i++) {
                    BigDecimal bigDecimal = fibonacciNumber.get(i);
                    if (second.compareTo(bigDecimal) <= 0) {
                        end = i;
                        break;
                    }
                }
                int result = end - start;
                if (fibonacciNumber.get(start).equals(first) && fibonacciNumber.get(end).equals(second)) {
                    result++;
                }
                writer.write(Integer.valueOf(result).toString());
                writer.write("\n");
            }
            writer.flush();
        } catch (IOException e) {
        }
    }
}

[brianfry713]

Try it with BigInteger instead of BigDecimal.

[sith]

Same result!!!

Code: Select all

import java.io.*;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Main {


    public static void main(String[] args) {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        List<BigInteger> fibonacciNumber = new ArrayList<BigInteger>();

        fibonacciNumber.add(BigInteger.ONE);
        fibonacciNumber.add(BigInteger.valueOf(2));

        Scanner scanner = new Scanner(reader);

        BigInteger maxValue = BigInteger.valueOf(10).pow(100);
        int index = 2;
        BigInteger newFib = BigInteger.ZERO;
        while (newFib.compareTo(maxValue) <= 0) {
            newFib = fibonacciNumber.get(index - 1).add(fibonacciNumber.get(index - 2));
            fibonacciNumber.add(newFib);
            index++;
        }


        try {
            BigInteger first;
            BigInteger second;

            while (true) {
                first = new BigInteger(scanner.next());
                second = new BigInteger(scanner.next());
                if (first.equals(BigInteger.ZERO) && second.equals(BigInteger.ZERO)) {
                    break;
                }

                if (first.equals(BigInteger.ZERO)) {
                    first = BigInteger.ONE;
                }

                int start = 0;
                int end = 0;

                for (int i = 0; i < fibonacciNumber.size(); i++) {
                    BigInteger BigInteger = fibonacciNumber.get(i);
                    if (first.compareTo(BigInteger) <= 0) {
                        start = i;
                        break;
                    }
                }

                for (int i = start; i < fibonacciNumber.size(); i++) {
                    BigInteger BigInteger = fibonacciNumber.get(i);
                    if (second.compareTo(BigInteger) <= 0) {
                        end = i;
                        break;
                    }
                }
                int result = end - start;
                if (fibonacciNumber.get(start).equals(first) && fibonacciNumber.get(end).equals(second)) {
                    result++;
                }
                writer.write(Integer.valueOf(result).toString());
                writer.write("\n");
            }
            writer.flush();
        } catch (IOException e) {
        }
    }
}

[brianfry713]

Input 4 5, output should be 1.

[uDebug]

Ghust_omega,

Thanks for the test cases.

[TryCatchMe]

Some valid ACC I/O:

Code: Select all

21 33
22 34
22 33
10 100
100 1000
5000 9000
1234000 123456000
5567 900000000
34556 10000000000000
43324234 85675676576575675675
8678678 345345345345345345353453453
235432435425 4364364653453646353643645656345646345
1 100000000000000000000000
234134 454765765674567457645
123421341234234 3465546345465634546564636 
453643644654656645 45645465645465564645465654465465645
1 2
1 5
5 5
6 7
4 5
1 1
334 45564645
4356 56765878768787678768657856785576
23545 6547657457665
234535 46765758908765432
12 500000000000
45 9000000000000000000000000000000000
2354 566546456456456746545765464564
1 10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
0 0

And my ACC Java program outputs:

Code: Select all

1
1
0
5
5
1
10
25
40
59
94
120
110
73
50
81
2
4
1
0
1
1
25
134
40
54
51
155
127
479

I was feeling lazy and used Java's BigInteger class.

[lilcoltsmith]

Hello all. When I run this program on my computer, with many test cases, I don't get any run time errors at all. It terminates with 0 status. Could someone help me identify the problem? Again, I am getting a Runtime Error when submitted. My code is attached and is written in C++ 11.

Code: Select all

// Colton Smith
// UVA 10183
// 9/28/2015

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(){
    vector<int> bigInt1;
    vector<int> bigInt2;
    vector<int> bigInt3;
    vector<string> Fibs = {"1", "1"};
    string str;
    int zero = 0;
    
    string low = "", high = "", line;
    
    while(getline(cin, line)){
        low = "";
        high = "";
        int c = 0;
        while(line[c] != ' '){
            low += line[c];
            ++c;
        }
        ++c;
        while(c < line.length()){
            high += line[c];
            ++c;
        }
        if(high == "0")
            break;
            
        bigInt1 = {1};
        bigInt2 = {1};
        
//            int count = 0;
            do{
                str = "";
                while(bigInt1.size() < bigInt2.size())
                    bigInt1.push_back(zero);
                while(bigInt3.size() < bigInt2.size())
                    bigInt3.push_back(0);    
                
                int carry = 0, sum = 0;
                for(int i = 0; i < bigInt2.size(); ++i){
                    sum = 0;
                    if(carry == 1){
                        sum = 1;
                        --carry;
                    }
                    
                    sum += bigInt1[i] + bigInt2[i];
                    if(sum > 9){
                        ++carry;
                    }
                    bigInt3[i] = sum % 10;
                }
                if(carry)
                    bigInt3.push_back(1);               
                    
                for(int k = 0; k < bigInt1.size(); ++k){
                    bigInt1[k] = bigInt2[k];
                }
                int m;
                for(m = 0; m < bigInt2.size(); ++m){
                    bigInt2[m] = bigInt3[m];
                }
                while(bigInt2.size() < bigInt3.size())
                    bigInt2.push_back(bigInt3[m]);
                for(int j = bigInt3.size() - 1; j >=0; --j){
                        str += bigInt3[j] + 48;
                }
                Fibs.push_back(str);
//                str = "";
//            ++count;
            }while(str.length() <= high.length());
            
            bigInt1.clear();
            bigInt2.clear();
            bigInt3.clear();
            
            int inRangeCount = 0;
            bool flag = true;
            int index = 1;
            string fib;
            
            while(flag){
                fib = "";
                fib += Fibs[index];
                if(fib.length() >= low.length()){
                    int i = 0;
                    while(fib[i] == low[i]){
                        ++i;
                        if(i == fib.length())
                            break;
                    }
                    if(i == fib.length())
                            break;
                    if(fib[i] >= low[i])
                        break;
                }
                ++index;
            }
            
            while(flag){
                fib = "";
                fib += Fibs[index++];
                if(fib.length() < high.length()){
                    ++inRangeCount;
                }
                else if(fib.length() == high.length()){
                    int j = 0;
                    while(fib[j] == high[j]){
                        ++j;
                        if(j == fib.length())
                            break;
                    }
                    if(j == fib.length()){
                        ++inRangeCount;
                        break;
                    }
                    if(fib[j] < high[j]){
                        ++inRangeCount;
                    }
                    else
                        break;
                }
                else
                    break;
            }

            cout << inRangeCount << endl;
        }
    
    return 0;
}