Wednesday 15 April 2015

Google code jam :Standing Ovation

Problem
It's opening night at the opera, and your friend is the prima donna (the lead female singer). You will not be in the audience, but you want to make sure she receives a standing ovation -- with every audience member standing up and clapping their hands for her.

Initially, the entire audience is seated. Everyone in the audience has a shyness level. An audience member with shyness level Si will wait until at least Si other audience members have already stood up to clap, and if so, she will immediately stand up and clap. If Si = 0, then the audience member will always stand up and clap immediately, regardless of what anyone else does. For example, an audience member with Si = 2 will be seated at the beginning, but will stand up to clap later after she sees at least two other people standing and clapping.

You know the shyness level of everyone in the audience, and you are prepared to invite additional friends of the prima donna to be in the audience to ensure that everyone in the crowd stands up and claps in the end. Each of these friends may have any shyness value that you wish, not necessarily the same. What is the minimum number of friends that you need to invite to guarantee a standing ovation?
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with Smax, the maximum shyness level of the shyest person in the audience, followed by a string of Smax + 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 Si = 0 and nine audience members with Si = 2 (and none with Si = 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.

----->Source link for further understanding



package standingOvation;

public class StandingOvation {
 private int members[];
 int slevel;
 int n = 0;

 public StandingOvation(char[] members, int slevel) {
  super();
  this.members = new int[slevel + 1];
  this.slevel = slevel;
  for (int i = 0; i < slevel + 1; i++) {
   this.members[i] = (int) members[i] - '0';
  }
 }

 void print() {
  for (int i : members)
   System.out.print(i);
  System.out.println();
 }

 int test() {
  int temp = members[0];
  for (int i = 1; i < members.length; i++) {
   if (temp >= i) {
    temp += members[i];

   } else {
    members[0]++;
    n++;
    return test();
   }
  }
  return n;
 }

}
package standingOvation;

import java.io.File;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Scanner;

public class standingOvationManager {
 private static Scanner s;
 static File f1;// This class is used for creation of files and directories,
 static File f2; // file searching, file deletion etc.
 static int cases;
 static int slevel;
 static String str;
 static char members[];
 private static PrintWriter pw;
 static int num = 1;

 public static void main(String[] args) {
  f1 = new File("A-large.in");
  f2 = new File("A-large-practice.out");
  try {
   s = new Scanner(f1);
   pw = new PrintWriter(f2);
   cases = s.nextInt();
   while (cases != 0) {
    slevel = s.nextInt();
    str = s.next();
    members = new char[str.length()];
    members = str.trim().toCharArray();
    int d = new StandingOvation(members, slevel).test();
    System.out.println(d);
    pw.println("Case #" + num++ + ": " + d);
    cases--;
   }
   s.close();
   pw.close();
  } catch (FileNotFoundException e) {
   System.out.println("FileNotFoundException ");
  }
 }
}