## 10183 - How Many Fibs?

Moderator: Board moderators

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

### Re: 10183 - How many Fibs?

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) {
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

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

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));
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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10183 - How many Fibs?

Try it with BigInteger instead of BigDecimal.
Check input and AC output for thousands of problems on uDebug!

sith
Learning poster
Posts: 72
Joined: Sat May 19, 2012 7:46 pm

### Re: 10183 - How many Fibs?

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) {
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

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

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));
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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10183 - How many Fibs?

Input 4 5, output should be 1.
Check input and AC output for thousands of problems on uDebug!

uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

### Re: 10183 - How many Fibs?

Ghust_omega,

Thanks for the test cases.
Check input and AC output for over 7,500 problems on uDebug!

TryCatchMe
New poster
Posts: 15
Joined: Fri May 30, 2014 12:09 am

### Re: 10183 - How Many Fibs?

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
New poster
Posts: 1
Joined: Thu Oct 01, 2015 5:34 am

### 10183 - How Many Fibs? Runtime Error

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;
}``````
Last edited by brianfry713 on Sat Oct 10, 2015 5:23 am, edited 1 time in total.