Problem Description

N aircraft are preparing to land at an airport with only one runway. The i-th aircraft arrives above the airport at time Ti and has enough remaining fuel to continue circling for Di units of time. This means it can begin landing at the earleist at time Ti, and at the latest at time Ti + Di. The landing process itself requires Li units of time.

One aircraft can begin landing immediately after another completes its landing, but cannot begin before the preceding aircraft has finished.

Determine whether all N aircraft can land safely.

Input Format

The input contains multiple test cases. The first line contains an integer T, representing the number of test cases. For each test case:

• The first line contains an integer N.
• The following N lines each contain three integers: Ti, Di, and Li.

Output Format

For each test case, output YES or NO indicating whether all aircraft can land safely.

Sample Input

2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20

Sample Output

YES
NO

Explanation

For the first test case:

• Aircraft 3 can land starting at time 0, finishing at time 20.
• Aircraft 2 can land starting at time 20, finishing at time 30.
• Aircraft 1 can land starting at time 30, finishing at time 40. This sequence is possible.

For the second test case, no arrangement allows all aircraft to land within their constraints.

Constraints

• 30% of test cases: N ≤ 2.
• 100% of test cases: 1 ≤ T ≤ 10, 1 ≤ N ≤ 10, 0 ≤ Ti, Di, Li ≤ 10^5.

Solution Approach

The problem requires checking all possible lending orders (permutations) because N ≤ 10, making a brute-force depth-first search (DFS) feasible.

Key logic for each permutation check:

1. Track the next_available_time when the runway becomes free.
2. For the current aircraft in the sequence, calculate its actual start time: max(aircraft.arrival_time, next_available_time).
3. Verify this start time is within its allowed window: start_time ≤ aircraft.arrival_time + aircraft.max_delay.
4. If valid, update next_available_time = start_time + aircraft.landing_duration and proceed to the next aircraft.
5. If any aircraft cannot be scheduled, backtrack and try a different sequence.

If a valid sequence is found for all aricraft, output YES; otherwise, NO.

C++ Implementation

#include <iostream>
#include <cstring>
using namespace std;

const int MAX_AIRCRAFT = 15;
struct Aircraft {
    int arrival_time;
    int max_delay;
    int landing_duration;
};

Aircraft planes[MAX_AIRCRAFT];
bool visited[MAX_AIRCRAFT];
int total_planes;
bool solution_found;

void explore_sequences(int count, int runway_free_time) {
    if (count > total_planes) {
        solution_found = true;
        return;
    }

    for (int i = 1; i <= total_planes; i++) {
        if (!visited[i]) {
            visited[i] = true;
            int earliest_start = planes[i].arrival_time;
            int latest_start = planes[i].arrival_time + planes[i].max_delay;
            int actual_start = max(earliest_start, runway_free_time);
            
            if (actual_start > latest_start) {
                visited[i] = false;
                continue;
            }
            
            int new_free_time = actual_start + planes[i].landing_duration;
            explore_sequences(count + 1, new_free_time);
            visited[i] = false;
            
            if (solution_found) return;
        }
    }
}

void process_test_case() {
    scanf("%d", &total_planes);
    solution_found = false;
    
    for (int i = 1; i <= total_planes; i++) {
        scanf("%d %d %d", &planes[i].arrival_time, &planes[i].max_delay, &planes[i].landing_duration);
        visited[i] = false;
    }
    
    explore_sequences(1, 0);
    
    if (solution_found) printf("YES\n");
    else printf("NO\n");
}

int main() {
    int test_cases;
    scanf("%d", &test_cases);
    while (test_cases--) {
        process_test_case();
    }
    return 0;
}