All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.
Moderator: Board moderators
sith
Learning poster
Posts: 72 Joined: Sat May 19, 2012 7:46 pm
Post
by sith » Wed Jul 04, 2012 9:52 am
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
Guru
Posts: 5947 Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA
Post
by brianfry713 » Thu Jul 05, 2012 7:26 am
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
Post
by sith » Sat Jul 07, 2012 6:07 pm
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
Guru
Posts: 5947 Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA
Post
by brianfry713 » Tue Jul 17, 2012 3:06 am
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
Post
by uDebug » Wed Mar 12, 2014 2:51 pm
Ghust_omega,
Thanks for the test cases.
TryCatchMe
New poster
Posts: 15 Joined: Fri May 30, 2014 12:09 am
Post
by TryCatchMe » Sun Jan 04, 2015 10:23 pm
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
Post
by lilcoltsmith » Thu Oct 01, 2015 5:40 am
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.
Reason: Added code block