0

Vikrant is at his college’s fest, and being a true foodie, he went straight away to the food corner in hope of getting his hands on some delicacies. There are N stalls in the food corner numbered 1 to N, and the ith stall has Ai people standing in front of it. Each stall takes a minute to serve one person. Vikrant will initially join the line for the first stall, but being an impatient guy, he will go on to join the line for the next stall after every minute if he is not served. (If he is in the line for the last stall, he will join the one for the first stall)

You have to tell the food stall from which Vikrant will be served. Output: For each testcase, in a new line, print the food-stall that will serve Vikrant.

Constraints: 1 ≤ T ≤ 100 1 ≤ N ≤ 105 0 ≤ Ai ≤ 106

Examples:
Input:
2
4
1 4 2 1
2
4 4
Output:
3
1

Explanation:
Testcase 1: At T = 0, he stands at stall 1, it is occupied till T=1 so he moves so stall 2, where he waits for 1 minute after which he moves to stall 3 at T = 2,
 which is empty at that point since the 2 people waiting at that stall are already serves by T = 2, so he gets serves at this stall.
Testcase 2: The progression is explained by the states given below.
4 4 T=0
3 3 T=1
2 2 T=2
1 1 T=3
0 0 T=4

#include<iostream>
using namespace std;
int main()
 {
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        int A[n];
        for(int i =0;i<n;i++)
            cin>>A[i];
        int T = 0;
        while(A[T] != 0)
        {
             for(int i = 0;i<n;i++)
                   A[i]--;
             T++;
             if(T>= n)
                T = T%n;

        }
        cout<<T+1<<endl;
    }
    return 0;
}
Megha98
  • 11
  • 3
  • I think you need to tell us what the code is supposed to do and what happens when you run it (error message /log) – Elemental Mar 19 '20 at 06:12
  • after submission it's just showing TLE (no other errors) – Megha98 Mar 19 '20 at 06:23
  • Is this from the same coding site as your other question? I don't really know the heirarchy of these sites, but since this one isn't giving you any helpful output when you fail a test case (what the test case was), I'd recommend finding a better one. Although I'm not sure if the other ones are much better in this regard. – JohnFilleau Mar 19 '20 at 06:28
  • Step through this code with your debugger and observe the values of `A[i]`. The answer should become apparent. – JohnFilleau Mar 19 '20 at 06:32
  • yes ! it is giving correct output for dummy test cases but after submission it is giving TLE error – Megha98 Mar 19 '20 at 06:34
  • 3
    Recommended read: [Why aren't variable-length arrays part of the C++ standard?](https://stackoverflow.com/q/1887097/9716597) [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/q/1452721/9716597) [C++: “std::endl” vs “\n”](https://stackoverflow.com/q/213907/9716597) – L. F. Mar 19 '20 at 06:34
  • The main problem is site is not disclosing test cases after submission and given test cases are small values so no idea how big input values can be – Megha98 Mar 19 '20 at 06:36
  • 1
    "so no idea how big input values can be" `Constraints: 1 ≤ T ≤ 100 1 ≤ N ≤ 105 0 ≤ Ai ≤ 106` – JohnFilleau Mar 19 '20 at 06:37
  • @Megha - this site you're using is bad. Why are you so attached to it? Is it a requirement for a job application? – JohnFilleau Mar 19 '20 at 06:38
  • 1
    Do you know how to use your debugger? – JohnFilleau Mar 19 '20 at 06:39
  • It was just a contest – Megha98 Mar 19 '20 at 06:55
  • 1
    Do you know how to use your debugger? – JohnFilleau Mar 19 '20 at 06:56
  • yes ! for sure (is there any error in logic ?) – Megha98 Mar 19 '20 at 07:14

1 Answers1

0

Basically, your algorithm is O(Amax x N), where Amax is the maximum A[.] value.

This can be avoided by decreasing each A value only when it is visited, not all the time. I provided an implementation of this idea behind. New complexity is O(Amax + N) in the worst case.

However, there is also a logical error in your code. This line:

while(A[T] != 0)

should be 

while(A[T] > 0)

The reason is that this value can became negative, simply meaning that no one is attending no longer at this place.

What was confusing is that this error has two effects: sometimes bad answers, and often a longer time spent. 

#include <iostream>
#include <vector>

int main() {
    int t;
    std::cin >> t;
    while (t--) {
        int n;
        std::cin >> n;
        std::vector<int> A(n);
        for (int i = 0; i < n ; ++i)
            std::cin >> A[i];
        int T = 0, i = 0;
        while (1) {
             if ((A[i] - T) <= 0) break;
             T++;
             i++;
             if (i == n) i = 0;
        }
        std::cout << i + 1 << "\n";
    }
    return 0;
}
Damien
  • 4,809
  • 4
  • 15
  • 20