13 days ago

Rohit • 40

Hyderabad

Question 1: Geeta's River Crossing (Log Jumps)

Problem Statement:

Geeta wants to cross a river which does not have a bridge across it. She found some logs floating on the water and decides to cross the river by jumping from one log to the next. She noticed something peculiar about these logs - they were all very slippery and someone had tied them together at the left end to hold them parallel to each other. Only the right end of the logs was good enough to get some grip. So she decided to cross the river by jumping from the right end of one log to the next. However all the logs were of different lengths, which meant in each jump she had to also go a certain distance left or right.

Geeta knew she could only jump a fixed distance to her right and to her left. So if the logs were more apart than that, she would have to turn back and reach her starting position. Her first priority was to reach the opposite bank, but if left with no choice she would return back to her starting position.

Write a program to print the number of jumps Geeta makes before reaching either the opposite end or her starting position.

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:

I) N≥1, the number of logs

II X,Y≥0; maximum distance Geeta can jump left and right respectively

III) Length of any log ≥1

Input Format:

The first line of input contains N, X and Y separated by a single white space.

Question 2: Large Hadron Collider (LHC) Pod Navigation

Problem Statement:

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 F or 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 buttons.

Write a program to help the engineers find the fewest button presses required to reach their destination station from their starting station. 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

3 minutes ago

admin 1.9k

Hyderabad

Problem 1 Solution:

 Geeta's River Crossing (Log Jumps)

Overview

Geeta jumps from the right end of one log to the next. The distance of the jump is determined by the difference in log lengths. She has a maximum capacity for jumping left (X) and right (Y). If she cannot make a jump, she must return to the start, effectively doubling the jumps she had already made.

Approach

1. Iterate and Compare: Loop through the logs and calculate the difference between the current log and the next one.
2. Constraint Check: If the difference is greater than Y (too far right) or the negative difference is greater than X (too far left), the jump fails.
3. Result Calculation: If a jump fails at index i, the total jumps are i (to get there) + i (to get back) = 2i. If she completes all jumps, the total is N-1.

Code Implementation

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, x, y;
    if (!(cin >> n >> x >> y)) return 0;

    vector<int> logs(n);
    for (int i = 0; i < n; i++) {
        cin >> logs[i];
    }

    int successfulJumps = 0;
    bool reachedEnd = true;

    for (int i = 0; i < n - 1; i++) {
        int diff = logs[i + 1] - logs[i];
        
        // Check if jump is possible within X (left) and Y (right)
        if (diff > y || (diff < 0 && -diff > x)) {
            reachedEnd = false;
            successfulJumps = i;
            break;
        }
    }

    if (reachedEnd) {
        cout << n - 1;
    } else {
        // Jumps taken to reach fail point + jumps to return
        cout << 2 * successfulJumps;
    }

    return 0;
}

3 minutes ago

admin 1.9k

Hyderabad

Problem 2 Solution

LHC Pod Navigation

Overview

This is a shortest-path problem on a circular track of N stations. You can move forward (F), backward (B), or use a number pad (Enter) to jump to a station. Since some digits are broken, the number pad is only available for specific "typeable" stations.

Approach

1. Identify Typeable Stations: Determine which station numbers (1 to N) can be formed using only the available digits.
2. Breadth-First Search (BFS): * Initialize a distance array with a high value.
   • The distance to the starting station is 0.
   • Any station that is "typeable" can be reached from the start by typing its digits and pressing Enter. The cost is (number of digits) + 1.
   • Queue these initial possibilities and perform a BFS to account for Forward and Backward moves.
3. Circular Logic: Ensure that moving forward from N leads to 1, and backward from 1 leads to N.

Code Implementation

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>

using namespace std;

// Helper to check if a station can be typed with available digits
bool isTypeable(int station, const vector<bool>& active) {
    string s = to_string(station);
    for (char c : s) {
        if (!active[c - '0']) return false;
    }
    return true;
}

int main() {
    int n, startNode, destNode;
    cin >> n >> startNode >> destNode;

    vector<bool> active(10, false);
    int digit;
    // Reading digits until EOF or end of line (Problem dependent input handling)
    while (cin >> digit) {
        active[digit] = true;
        if (cin.peek() == '\n' || cin.peek() == EOF) break;
    }

    vector<int> dist(n + 1, 1e9);
    queue<int> q;

    // Start position cost
    dist[startNode] = 0;
    q.push(startNode);

    // Any typeable station can be a starting point via the number pad
    for (int i = 1; i <= n; i++) {
        if (isTypeable(i, active)) {
            int cost = to_string(i).length() + 1;
            if (cost < dist[i]) {
                dist[i] = cost;
                q.push(i);
            }
        }
    }

    // BFS for Forward and Backward moves
    while (!q.empty()) {
        int curr = q.front();
        q.pop();

        // Forward Move
        int fwd = (curr == n) ? 1 : curr + 1;
        if (dist[curr] + 1 < dist[fwd]) {
            dist[fwd] = dist[curr] + 1;
            q.push(fwd);
        }

        // Backward Move
        int bwd = (curr == 1) ? n : curr - 1;
        if (dist[curr] + 1 < dist[bwd]) {
            dist[bwd] = dist[curr] + 1;
            q.push(bwd);
        }
    }

    cout << dist[destNode];

    return 0;
}