Problem solving with programming: Standing Ovation: Google codejam 2015 Qualification round problem

Problem solving with programming: Standing Ovation: Google codejam 2015 Qualification round problem
https://code.google.com/codejam/contest/6224486/dashboard#s=p0
There are a group of N people in a stadium with their shyness levels represented by a String S of digits(0-9). The digit at each index represents the number of persons with shyness level equal to the index.

For example S[0] represents the number persons with shyness '0'.
S[1] represent the number of persons with shyness '1' and so on.

Persons with shyness level 'L' will not standup and clap until 'L' other people standup and clap before them. For example, in order for a person with shyness level 3 to standup and clap, 3 other people must do that before him. 

Now the problem is to find whether the all the people in the given group gives a standing ovation on its own? or What is the minimum number of people to add to the group to ensure that they give a standing ovation.

Let us consider a couple of simple examples.

1. [1, 1, 2]: There is one person with shyness level 0 who will clap first. After seeing him, the second person with shyness 1 will also clap. Then the last two people with shyness 2 will also clap. So there is no need to add any people to give a standing ovation.
2. [1, 0, 1]: In this case, we need one person with shyness 0 or 1 to be added to the group because the last person will not standup until 2 other people clap.

T test cases follow. Each consists of one line with S_max, the maximum shyness level of the shyest person in the audience, followed by a string of S_max + 1 single digits. The kth digit of this string (counting starting from 0) represents how many people in the audience have shyness level k. For example, the string "409" would mean that there were four audience members with S_i = 0 and nine audience members with S_i = 2 (and none with S_i = 1 or any other value). Note that there will initially always be between 0 and 9 people with each shyness level.

The string will never end in a 0. Note that this implies that there will always be at least one person in the audience.

 int t;


 cin >> t;


 int i,j;


 for( i = 0; i < t; i++ )


 {


  int smax;


  cin >> smax;


  string input;


  cin >> input;


  int standing = 0;


  int need = 0;


  for( j = 0; j < smax+1; j++ )


  {


   if( input[j] != '0' )


   {


    if( standing < j )


    {


     need += j-standing;


     standing += j-standing;


    }


    standing += input[j]-'0';


   }


  }


 


  cout << "Case #" << (i+1) << ": " << need << endl;  


 }

Read full article from Problem solving with programming: Standing Ovation: Google codejam 2015 Qualification round problem