The Large Hadron Collider (LHC) is the world's lar...

Question

The Large Hadron Collider (LHC) is the world's largest particle accelerator. It lies underground in a circular tunnel 27 kilometers in circumference. All of its components spread throughout the circumference, need to function optimally for the Collider to do its job. To quickly reach a component that needs repairs, a pod on rails has been built, which runs in the tunnel in a loop.

There are N stations (numbered 1 to N) in the tunnel where the pod can stop. Inside the pod, a number pad with digits 0 to 9, and an Enter button are given. One can enter the number of the station one wants to go to, press Enter, and the pod will go to that station. There are also two additional buttons: button F to move just one station forward (e.g. from station 34 to station 35), and button B to move one station backward (e.g. from station 38 to station 37). One need not press 'Enter' after pressing For B.

One morning, it was discovered that some digits on the number pad had stopped functioning, although buttons E (Enter), F, and B were working fine. Since the repair work cannot control, engineers are trying to figure out the fastest way to reach any station using only the functioning digits

Write a program to help the engineers find the fewest button presses required to reach their destination station from where they are. Print the number of button presses as the output.

Read the input from STDIN and print the output to STDOUT. Do not write arbitrary strings anywhere in the program, as these contribute to the standard output and testcases will fail.
Constraints:

N<10000

Input Format:

The first line of input contains N, the number of stations. The stations are numbered 1 to N.

The second line contains the count of functioning digits on the number pad. Buttons E F, and B are excluded from this count as they are always working

The third line contains the list of functioning digits, in random order, separated by single white spaces. Buttons E, F, and B are excluded as they are always working.

The fourth line contains the station where the pod is currently present. The fifth line contains the destination station where the pod needs to go

Output Format:

The output contains the minimum button presses required to reach the destination station.

Sample Input1:

650

4

1 8 0 4

475

485

Sample Output1:

5
Explanation:

There are 650 stations along the Collider's circumference, nurnbered 1 to 650.

Only four digits (0,1,4,8) are working on the number pad To reach 485, since the current position is 475, one way is to press F (forward) button 10 times, which is 10 button presses Another way is to press 481, Enter, and then the F button four times. The sequence would be 481EFFFF, which is 8 button presses. Another way is to press 488, Enter, then the B button thrice. The sequence would be 488EBBB, which is 7 button presses. Another way is to press 484, Enter, then F one time. The sequence would be 484EF, which is 5 button presses Since this is the fastest way to reach 485, 5 is printed as the output.

Sample Input2:

87
3
3 4 5
2
85

Sample Output2:

4

Explanation2:

The fastest way to reach station 85 is to press B four times, to go back four stations

code in java without comments and buffer reader such that it passes all the test cases

Answer 1

java
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int m = sc.nextInt();
        boolean[] ok = new boolean[10];
        for (int i = 0; i < m; i++) {
            ok[sc.nextInt()] = true;
        }
        int C = sc.nextInt();
        int T = sc.nextInt();
        int directForward = (T - C + N) % N;
        int directBackward = (C - T + N) % N;
        int ans = Math.min(directForward, directBackward);
        for (int k = 1; k <= N; k++) {
            String s = String.valueOf(k);
            boolean valid = true;
            for (char ch : s.toCharArray()) {
                if (!ok[ch - '0']) {
                    valid = false;
                    break;
                }
            }
            if (!valid) continue;
            int presses = s.length() + 1;
            int f = (T - k + N) % N;
            int b = (k - T + N) % N;
            presses += Math.min(f, b);
            if (presses < ans) {
                ans = presses;
            }
        }
        System.out.println(ans);
    }
}

Answer 2

cpp
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    int m;
    cin >> m;
    vector<bool> ok(10, false);
    for (int i = 0; i < m; i++) {
        int d;
        cin >> d;
        ok[d] = true;
    }
    int C, T;
    cin >> C >> T;

    int forwardMoves = (T - C + N) % N;
    int backwardMoves = (C - T + N) % N;
    int ans = min(forwardMoves, backwardMoves);

    for (int k = 1; k <= N; k++) {
        string s = to_string(k);
        bool valid = true;
        for (char ch : s) {
            if (!ok[ch - '0']) {
                valid = false;
                break;
            }
        }
        if (!valid) continue;
        int presses = s.length() + 1;
        int f = (T - k + N) % N;
        int b = (k - T + N) % N;
        presses += min(f, b);
        ans = min(ans, presses);
    }

    cout << ans;
    return 0;
}

The Large Hadron Collider (LHC) is the world's lar...

问题

思考

Considering Java algorithm design

Designing minimal button presses logic

Implementing button press algorithm

回答

问题

思考

回答

分享这个问答