SPREAD2 : Editorial

Link to the Contest:
https://www.codechef.com/CSPK2020

SPREAD2 : Editorial
Author: CodeChef Public Repository
Tester: easy3279
Editorialist : chaitanya_44
Difficulty : Easy
Problem:

There are N people numbered 1 through N. Initially, only person 1 knows about Snackdown. On each day, everyone who already knows about Snackdown tells other people about it. For each valid i, person i can tell up to Ai people per day. People spread the information among the people who don’t know about Snackdown in the ascending order of their indices; you may assume that no two people try to tell someone about Snackdown at the same moment. Each person is only allowed to start telling other people about Snackdown since the day after he/she gets to know about it (person 1 can start telling other people already on day 1). How many days does it take for all people to know about Snackdown?

Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N.
The second line contains N space-separated integers A1,A2,…,AN.

Constraints
1≤T≤1,000
2≤N≤105
the sum of N for all test cases does not exceed 106
0≤Ai≤N for each valid i
1≤A1

Solution:

CPP 14
#include<bits/stdc++.h>
#define ll long long
#define Ant ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define test ll t;cin>>t;while(t–)
#define min3(a,b,c) min(a,min(b,c))
using namespace std;
#define rep(i,n) for ( i=0 ; i<n ; i++ )
#define rep2(i,m) for ( i=0 ; i<m ; i++ )
#define rep1(i,n) for ( i=1 ; i<=n ; i++ )
#define yes cout<<“YES”<<endl
#define no cout<<“NO”<<endl
#define nn <<endl
#define sp <<’ ‘<<
#define MAX 10000009
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define print(v) for(auto it:v)cout<<it<<’ '; cout<<endl;
#define vll vector
///digit count log10(n)+1
/ll nCr(ll n, ll r)
{
/// p holds the value of n
(n-1)(n-2)…,
// k holds the value of r
(r-1)…
if(r > n)
return 0;
long long p = 1, k = 1;

// C(n, r) == C(n, n-r),
///choosing the smaller value
if (n - r < r)
r = n - r;
if (r != 0)
{
while (r)
{
p *= n;
k *= r;

       // gcd of p, k
        long long m = __gcd(p, k);
        p /= m;
        k /= m;
        n--;
        r--;
    }
}
else
    p = 1;

return p;

}*/

ll dp[100005];
int main()
{
Ant;

test
{
    ll i,n,a,b,c,k=0,m,y=1,x,l,cnt=0,j=1,mx=INT_MIN,mn=INT_MAX;
    cin>>n;
    set<ll>st;
    vll v1(n+1),v(n+1);
    v1[0]=0;
    v[0]=0;
    for(i=1;i<=n;i++)
    {
        cin>>v1[i];
        v[i]=(v[i-1]+v1[i]);
        // cout<<v[i] nn;
    }
    i=1;
       while(j<n)
       {
           j+=v[i];
           i+=v[i];
           k++;
       }

cout<<k nn;
}

}

PYTHON 3.6:
import sys
input=sys.stdin.readline
t=int(input())
for you in range(t):
n=int(input())
l=input().split()
li=[int(i) for i in l]
z=[]
for i in range(n):
z.append(li[i])
maxpref=[0 for i in range(n)]
maxa=0
for i in range(n):
maxa+=z[i]
maxpref[i]=maxa
curr=0
count=0
while(curr<n-1):
curr+=maxpref[curr]
count+=1
#print(curr)
print(count)