Blog

  Input The first and the only line of the input contains tw…

  Input The first and the only line of the input contains two distinct integers n and m (1 ≤ n, m ≤ 10000), separated by a space .   Output Print a single number — the minimum number of times one needs to push a button required to get the number m out of number n.   Sample Input 1 4 6 Sample Output 1 (your program output) 2 Explanation: you need to push the BLACK button (-1) once, and then push the RED button (*2) once. Hence the answer is 2.   Sample Input 2 41 22 Sample Output 2 (your program output) 3 Explanation: You need to press WHITE, BLUE, BLUE to get 41-20-21-22. Hence the answer is 3. test data: test_data.zip These are the data sets the judge will “type” in the console to test your submission: 1.in  1.out  2.in 2.out   3.in  3.out  4.in  4.out  5.in  5.out  6.in  6.out  7.in  7.out  8.in  8.out  9.in  9.out  10.in  10.out  Note that you can also test the program on the Judge (http://69.209.30.21/problems/7006), but do submit your solution to Canvas. The judge only does console IO for simplicity (it does not do file I/O). Do not use any package, and name your class Main and your file Main.java (this is a convention used across all universities and companies for online testing).   Grading metric: some effort: 5 points reasonable effort: 10 points significant effort: 15 points almost working: 20 points Beyond this, each case you solve you score 1 points. Max score: 30 points.   Hint 1: solve it as a BFS problem. For example, you can use: (a) an int array where the subscript is the immediate number and the content is the number of steps to reach that number or (b) a State class (like in the Snakes and Ladder Facebook problem). This is a sufficient State class for you to use: class State { int number; int step; State(int number, int step) { this.number = number; this.step = step; } }  or (c) Any approach you think will solve this problem, including but not limited to building all the edges and running our textbook’s BFS algorithm.  Hint 2: Have you set a lower bound and an upper bound on the intermediate numbers reached? You can set 5*n as the upper bound.

When one runs bfs traversal on an unweighted graph, one gets…

When one runs bfs traversal on an unweighted graph, one gets a Search Tree (as discussed in class). Given such a search tree  in Java: and bfs implementation like this (in class): There are 6 vertices. If the graph edge data look like this:   Using 0 as the starting vertex, what is the search order? List the order in which the vertices are searched: [searchorder] parent of 1 is [p1] parent of 2 is [p2] parent of 3 is [p3] parent of 4 is [p4] parent of 5 is [p5]