Cerinta completa

Meera teaches a class of students, and every day in her classroom is an adventure. Today is drawing day!

The students are sitting around a round table, and they are numbered from to in the clockwise direction. This means that the students are numbered , and students and are sitting next to each other.

After letting the students draw for a certain period of time, Meera starts collecting their work to ensure she has time to review all the drawings before the end of the day. However, some of her students aren’t finished drawing! Each student needs extra minutes to complete their drawing.

Meera collects the drawings sequentially in the clockwise direction, starting with student ID , and it takes her exactly minute to review each drawing. This means that student gets extra minutes to complete their drawing, student gets extra minute, student gets extra minutes, and so on. Note that Meera will still spend minute for each student even if the drawing isn’t ready.

Given the values of , help Meera choose the best possible to start collecting drawings from, such that the number of students able to complete their drawings is maximal. Then print on a new line. If there are multiple such IDs, select the smallest one.

Input Format

The first line contains a single positive integer, , denoting the number of students in the class.
The second line contains space-separated integers describing the respective amounts of time that each student needs to finish their drawings (i.e., ).

Constraints

Subtasks

  • for of the maximum score.

Output Format

Print an integer denoting the ID number, , where Meera should start collecting the drawings such that a maximal number of students can complete their drawings. If there are multiple such IDs, select the smallest one.

Limbajul de programare folosit: cpp14

Cod:

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

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i = 0; i < N; i++) {
        cin >> A[i];
    }

    int start = 0;

    vector<int> D(N+1, 0);
    for(int i = 0; i < N; i++) {
        if(A[i] <= i) {
            start++;
            D[i-A[i]]--;
            D[i]++;
        } else {
            D[i-A[i]+N]--;
            D[i]++;
        }
    }

    int best = start;
    int bi = 0;
    int cur = start;
    for(int i = 0; i < N; i++) {
        if(cur > best) {
            best = cur;
            bi = i;
        }
        cur += D[i];
    }

    cout << (bi+1) << endl;
}

Scor obtinut: 1.0

Submission ID: 464653319

Link challenge: https://www.hackerrank.com/challenges/kindergarten-adventures/problem

Kindergarten Adventures