The a-b-c Calculator Filename: calc.java Standard Input, Standard Output You bou
ID: 3725379 • Letter: T
Question
The a-b-c Calculator Filename: calc.java Standard Input, Standard Output You bought a calculator at a garage sale for only 25 cents, thinking you got a steal. Unfortunately, the calculator has very limited functionality and a rather strange screen. The initial display always starts with 0 on it and there are three buttons you can press which perform the following operations on the current number on the screen: (1) Add a (2) Multiply by b (3) Integer Division by c where a, b, and c are given for each different calculator. The screen displays exactly 6 digits, and when you attempt a calculation with a result one million or greater, you realize that the display shows the last six digits of the actual correct response and uses this value instead for the next calculation. (For example, if the display showed 345678 and b 3, if we press the button to multiply by 3, the resulting value will be 037034, the last six digits of the actual result. If we then pressed the integer divide button by c 4, the new result would be 9258. Note that this is different than 1037034/4.) Given the constants a, b, and c, described above, and a target integer, t, determine the minimum number of button presses needed to obtain t on the calculator display Input The first line will contain a single positive integer, n, (n s 100), specifying the number of input cases. Each input case will be on a single line having four space-separated positive integers, a b, c and t, representing the additive constant, multiplicative constant, division constant and target value for the test case (1s a, b, cs 1000, 1s t s 999999) Output For each test case, on a line by itself, output the minimum number of button presses necessary to obtain the target for the case. If it's impossible to obtain the target, print out a -1 on a line by itself instead. Samples Input Output 1 3 2 197 10 30 1 5 1 7 2 123456 17Explanation / Answer
Java code:
import java.util.*;
class Ans {
public Integer value;
public Integer steps;
Ans(Integer v, Integer s) {
value = v;
steps = s;
}
@Override
public String toString() {
return "Ans [value=" + value + ", steps=" + steps + "]";
}
}
public class calc {
public static Integer a;
public static Integer b;
public static Integer c;
public static Integer t1;
static Integer BFS()
{
// As the targe value could not be greater than 10^6 we can have
// visited array of 10^6.
boolean visited[] = new boolean[1000000];
// Queue used in BFS.
LinkedList<Ans> queue = new LinkedList<Ans>();
visited[0]=true;
queue.add(new Ans(0,0));
while (queue.size() != 0)
{
Ans s1 = queue.poll();
// check if we have found the target value.
// if so return the number of steps. As in BFS we will reach in
// minimum number of steps.
if(s1.value.equals(calc.t1))
return s1.steps;
// Add element in queue based on the condition.
// Assuming next element to be current plus a
Integer add = (s1.value+calc.a)%1000000;
// Assuming next element to be current multiplied by b
Integer mult = (s1.value*calc.b)%1000000;
// Assuming next element to be current divided by c
Integer divide = (s1.value/calc.c)%1000000;
if(!visited[add]) {
visited[add] = true;
queue.add(new Ans(add,s1.steps+1));
}
if(!visited[mult]) {
visited[mult] = true;
queue.add(new Ans(mult,s1.steps+1));
}
if(!visited[divide]) {
visited[divide] = true;
queue.add(new Ans(divide,s1.steps+1));
}
// Add the element only if they are not visited.
// Re adding elements will cause redundancy in computation.
}
// Once queue is empty return -1 as the target element is unreachable.
return -1;
}
public static void main(String[] args) {
Scanner in= new Scanner(System.in);
// Take input from user.
int t = in.nextInt();
for(int i =0; i<t; i++) {
a = in.nextInt();
b = in.nextInt();
c = in.nextInt();
t1 = in.nextInt();
System.out.println(BFS());
}
in.close();
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.