easy
1 views

Hare & Tortoise – 001

Determine the winner of a magical race between hare and tortoise based on power points and sleep mechanics

Understand the Problem

Problem Statement

Most of us would know the Hare & the Tortoise story. As the hare can run faster than the tortoise, god gives some magical power points X to the tortoise which never diminishes. But to be fair, god also gives an array of L magical power points to the Hare before each lap involved in the race.

When the hare acquires N or more magical power points due to laxity it goes to sleep and during sleep it loses exactly N magical power points. Then the hare wakes up and completes the remaining laps. If in the last lap the magical power points R remaining with the hare is more than X, Hare wins. Else tortoise wins. If R is equal to X, the match ends in a draw and the program must print -1. If the hare does not sleep, it will always win the race. The hare will sleep only once or not sleep at all.

Constraints

  • 1 ≤ N ≤ 10^9 (Hare's sleep threshold)
  • 1 ≤ X ≤ 10^9 (Tortoise's magical power points)
  • 1 ≤ L ≤ 100 (Number of laps in the race)
  • 1 ≤ a[i] ≤ 10^6 (Power points in each lap)
  • All values are positive integers

Examples

Example 1
Input
5 9
5
1 2 3 4 5
Output
HARE
Explanation

Total points R = 1+2+3+4+5 = 15. Since R ≥ 5, hare sleeps and loses 5 points, so R = 10. Since R (10) > X (9), hare wins.

Example 2
Input
5 11
5
1 2 3 4 5
Output
TORTOISE
Explanation

Total points R = 1+2+3+4+5 = 15. Since R ≥ 5, hare sleeps and loses 5 points, so R = 10. Since R (10) < X (11), tortoise wins.

Solution

#include <stdio.h>
#include <stdlib.h>

int main() {
    long int n, x, l, i, c = 0, r = 0;
    scanf("%li %li %li", &n, &x, &l);
    long int a[l];
    
    for (i = 0; i < l; i++)
        scanf("%li", &a[i]);
    
    // Sum all power points
    for (i = 0; i < l; i++)
        r = r + a[i];
    
    // Check if hare sleeps
    if (r >= n) {
        r = r - n;
        c++;
    }
    
    // Determine winner
    if (r > x || c == 0)
        printf("HARE");
    else if (r < x)
        printf("TORTOISE");
    else
        printf("-1");
    
    return 0;
}
Time:O(L) - We iterate through the array of L laps twice (once for input, once for summing)
Space:O(L) - We store the array of L power points
Approach:

C Solution Explanation:

  1. Declare variables for N (sleep threshold), X (tortoise points), L (laps), counter c, and total points r
  2. Read input values using scanf
  3. Read the array of power points for each lap
  4. Sum all power points from all laps into variable r
  5. Check if total points r ≥ N. If yes, hare sleeps once (c becomes 1) and loses N points
  6. Compare remaining points r with tortoise's points x:
    • If r > x OR hare didn't sleep (c == 0): print HARE
    • If r < x: print TORTOISE
    • If r == x: print -1

Visual Explanation

Loading diagram...
All Problems