Overview

Find the number (1-based index) of the meat that finishes grilling the earliest. If multiple pieces of meat finish grilling at the same time, choose the one with the smallest number.

Analysis

Since all pieces of meat are placed on the grill at the same time, a piece of meat with a smaller \(A_i\) finishes grilling earlier.

In this solution, we use an approach where we advance the time by \(1\) second and check whether any piece of meat finishes grilling at that time. Since \(A_i \leq 1000\), it is sufficient to check times from \(1\) second to \(1000\) seconds.

Even with this naive approach, the number of checks is at most \(1000 \times 100 = 100000\), which runs fast enough.

However, care must be taken when multiple pieces of meat finish grilling at the same time. By checking the meat in ascending order of their numbers and terminating as soon as the first one is found, we can select the smallest number.

For example, when \(A = (4, 2, 2)\), the process is as follows:

• At \(1\) second: No meat finishes grilling.
• At \(2\) seconds: The \(2\)-nd and \(3\)-rd pieces of meat finish grilling. Checking in order of their numbers, the \(2\)-nd piece is found first, so the answer is \(2\).

Algorithm

1. Read \(N\) and the array \(A\).
2. Iterate through time \(t\) from \(1\) to \(1000\).
3. For each time, check the pieces of meat in order from the \(1\)-st to the \(N\)-th.
4. When a piece of meat satisfying \(A_i = t\) is found, output its number and terminate the program.

Since time is checked in increasing order, the first piece of meat found is the one that finishes grilling earliest. In addition, because the pieces are checked in ascending order of their numbers at each time step, the smallest number is chosen among those that finish grilling simultaneously.

Complexity

Let \(T = 1000\) be the upper bound on the time.

• Time Complexity: \(O(TN)\). For at most \(1000\) time steps, we check at most \(N\) pieces of meat each.
• Space Complexity: \(O(N)\). We store the seconds required to grill in an array.

Implementation Notes

• Since arrays in code are \(0\)-indexed, the \(1\)-based number of the meat at index \(i\) is \(i + 1\).

• Since some pieces of meat may finish grilling at \(1000\) seconds, the loop condition should be t <= 1000.

• Once the answer is found, immediately terminate with return 0;. This prevents accidentally outputting another piece of meat found later.

  Source Code

// 問題文から独立に実装: 時刻を 1 秒ずつ進め、最初に焼き上がる肉を探す
#include <iostream>
#include <vector>
int main() {
    int n; std::cin >> n;
    std::vector<int> a(n);
    for (int& x : a) std::cin >> x;
    for (int t = 1; t <= 1000; ++t)
        for (int i = 0; i < n; ++i)
            if (a[i] == t) { std::cout << i + 1 << std::endl; return 0; }
}

This editorial was generated by gpt-6-astra-medium.