The Problems

double getProbability(int waitTime, int walkTime, int lateTime, int bestArrival, int worstArrival)
    {
        int lateEnd = walkTime - lateTime;
        int t = waitTime;
        if( worstArrival > bestArrival) {
            int s = 0;
	        while( t<worstArrival) {
	            for (int i=0; i<lateEnd; i++) {
	                if( t+i >= bestArrival && t+i < worstArrival ) {
	                    s++;
	                }
	            }
	            t = t + walkTime + waitTime; //move to the next instance of the cycle.
	        }
	        return s / (double)(worstArrival - bestArrival );

	    } else {

	        while( t<=worstArrival) {
	            for (int i=1; i<=lateEnd; i++) {
	                if( t+i == bestArrival ) {
	                    return 1.0;
	                }
	            }
	            t = t + walkTime + waitTime; //move to the next instance of the cycle.
	        }
	        return 0.0;
	        
	    }
    }

final int INF  = 10000; //A large value.
final int[] dx = new int[]{0,0,1,-1};
final int[] dy = new int[]{1,-1,0,0};

public int maximumTurns(String[] maze) {
    int w = maze.length, h = maze[0].length(), sx=0,sy=0;
    int [][] fireTime = new int[w][h];
    int [][] arrivalTime = new int[w][h];
    
    //The first BFS, fill fireTime, the array that specifies the
    //turn number at which the cell gets set on fire. Find 'F'
    // cells and push them to the queue so that they become
    // starting points. Also find the initial character's cell (x,y).
    //
    // A single queue is used to store both coordinates, first
    // x is pushed to the queue, then y.
    //
    Queue<Integer> Q = new LinkedList<Integer>();
    for (int i=0; i<w; i++) {
        for (int j=0; j<h; j++) {
            arrivalTime[i][j] = INF;
            if(maze[i].charAt(j) == 'F' ) {
                fireTime[i][j] = 0;
                Q.offer(i);
                Q.offer(j);
            } else {
                if(maze[i].charAt(j) == '$') {
                    arrivalTime[i][j] = 0;
                    sx = i;
                    sy = j;
                }
                fireTime[i][j] = INF;
            }
        }
    }
    
    while( Q.peek() != null ) {
        int x = Q.remove();
        int y = Q.remove();
        for (int t=0; t<4; t++) {
            int nx=x+dx[t], ny=y+dy[t];
            if( (nx>=0) && (nx<w) && (ny>=0) && (ny<h)
                && (maze[nx].charAt(ny) != '#')
                && (fireTime[nx][ny] > fireTime[x][y]+1)
              ) {
                Q.offer(nx);
                Q.offer(ny);
                fireTime[nx][ny]=fireTime[x][y]+1;
            }
        }
    }
    //If the fire can never reach the starting point (sx,sy), then
    //the character can stay in there indifinitely.
    if( fireTime[sx][sy] >= INF ) {
        return -1;
    }
    
    // The second BFS, moves the character around the map. 
    // Make sure the character does not goes through cells that would
    // be on fire during the turn number. The character must also
    // stop moving if the cell in which it is located becomes on fire
    // exactly at that turn. It fills the arrivalTime array which
    // is the minimum distance between (sx,sy) and the cell.
    int best = 0;
    Q.offer(sx);
    Q.offer(sy);
    while ( Q.peek() != null ) {
        int x = Q.remove();
        int y = Q.remove();

        if( arrivalTime[x][y] <= fireTime[x][y] ) {
            // the result is the maximum of the fireTime values of
            // all the cells that can be reached before they are set on fire.
            best = Math.max(best, fireTime[x][y] );
        }
        if( arrivalTime[x][y] < fireTime[x][y] ) {
        // can move to another cell:
            for (int t=0; t<4; t++) {
                int nx=x+dx[t], ny=y+dy[t];
                if( (nx>=0) && (nx<w) && (ny>=0) && (ny<h)
                    && (maze[nx].charAt(ny) != '#')
                    && (arrivalTime[nx][ny] > arrivalTime[x][y]+1)
                  ) {
                    Q.offer(nx);
                    Q.offer(ny);
                    arrivalTime[nx][ny]=arrivalTime[x][y]+1;
                }
            }
        }
        
    }
    return best;
}

int dx[4] = {-1, 0, 1, 0};
int dy[4] = { 0, 1, 0,-1};
bool valid(int i, int j , int n, int m) {
    return i >= 0 && i < n && j >= 0 && j < m;
}
class MazeOnFire {
public:
    int maximumTurns(vector <string> maze) {
        int h, w, res, nx, ny;
        bool solved, fire;
        vector<string> next;
        res = 0;
        h = maze.size();
        w = maze[0].size();
        next = maze;
        solved = false;
        while(!solved) {
            //this turn is counted because the character is alive.
            ++res;
            //the positions reachable by the character in next turn are marked here.
            for(int y = 0; y < h; ++y) {
                for(int x = 0; x < w; ++x) {
                    if(maze[y][x] == '$') {
                        for(int i = 0; i < 4; ++i) {
                            nx = x + dx[i];
                            ny = y + dy[i];
                            if(valid(ny,nx,h,w) && maze[ny][nx] == '.') {
                                next[ny][nx] = '$';
                            }
                        }
                    }
                }
            }
            //the positions reachable by the fire are marked here
            fire = false;
            for(int y = 0; y < h; ++y) {
                for(int x = 0; x < w; ++x) {
                    if(maze[y][x] == 'F') {
                        for(int i = 0; i < 4; ++i) {
                            nx = x + dx[i];
                            ny = y + dy[i];
                            if(valid(ny,nx,h,w) && maze[ny][nx] != '#' && maze[ny][nx] != 'F') {
                                next[ny][nx] = 'F';
                                fire = true;
                            }
                        }
                    }
                }
            }
            //if the fire didn't reach any new cell of the grid
            //the character will survive indefinitely
            if(fire == false)
                return -1;
            maze = next;
            //the flag solved is used to check if the character has survived this turn
            //if not the main loop ends
            solved = true;
            for(int y = 0; y < h && solved; ++y) {
                for(int x = 0; x < w && solved; ++x) {
                    if(maze[y][x] == '$') {
                        solved = false;
                    }
                }
            }
        }
        return res;
    }
};

public class MazeOnFire{
	public int maximumTurns(String[] Maze){
		int[] dx = new int[]{0,-1,0,1,0};
		int[] dy = new int[]{0,0,-1,0,1};
	
		int r=Maze.length, c=Maze[0].length();
		boolean[][][] reachable = new boolean[2][r][c];
		boolean[][][] fire = new boolean[2][r][c];
		char[][] m = new char[r][0];
		for(int i=0; i<r; i++) m[i] = Maze[i].toCharArray();
		
		
		for(int i=0; i<r; i++)
			for(int j=0; j<c; j++)
				if(m[i][j]=='$') reachable[0][i][j]=true;
				else if(m[i][j]=='F') for(int t=0; t<2; t++) fire[t][i][j]=true;
		
		//At first I'd used t<1275 but that proved to be wrong, so I used t<2500.
		//Note: 2500 is a safe bet but not the optimum.
		for(int t=1; t<2500; t++){
			int num = 0;
			for(int i=0; i<r; i++)
				for(int j=0; j<c; j++)
					if(reachable[(t-1)%2][i][j])
						for(int a=0; a<5; a++)
							try{
								int nx = i+dx[a], ny = j+dy[a];
								if(!fire[(t-1)%2][nx][dy] && isfree(m[nx][dy])){
									reachable[t%2][nx][dy] = true;
									num++;
								}
							}catch(Exception e){};
			//If no cell was reachable in t moves
			//then the game ended in t-1 moves.
			if(num==0) return (t-1);
			for(int i=0; i<r; i++)
				for(int j=0; j<c; j++)
					if(fire[(t-1)%2][i][j])
						for(int a=0; a<5; a++)
							try{
								int nx = i+dx[a], ny = j+dy[a];
								if(isfree(m[nx][dy])){
									fire[t%2][nx][dy] = true;
									reachable[t%2][nx][dy] = false;
								}
							}catch(Exception e){};
			
		}
		//After 2500 turns and there're still cells that are reachable
		//we can safely assume it will never end.
		return -1;
	}
	boolean isfree(char c){
		return (c=='.')||(c=='$');
	}
	
}

// Use 64 bits integers to avoid overflow errors during multiplication.
long modPow(long a, long x, long p) {
    //calculates a^x mod p in logarithmic time.
    long res = 1;
    while(x > 0) {
        if( x % 2 != 0) {
            res = (res * a) % p;
        }
        a = (a * a) % p;
        x /= 2;
    }
    return res;
}

long modInverse(long a, long p) {
    //calculates the modular multiplicative of a mod m.
    //(assuming p is prime).
    return modPow(a, p-2, p);
}
long modBinomial(long n, long k, long p) {
// calculates C(n,k) mod p (assuming p is prime).

    long numerator = 1; // n * (n-1) * ... * (n-k+1)
    for (int i=0; i<k; i++) {
        numerator = (numerator * (n-i) ) % p;
    }
    
    long denominator = 1; // k!
    for (int i=1; i<=k; i++) {
        denominator = (denominator * i) % p;
    }
    
    // numerator / denominator mod p.
    return ( numerator* modInverse(denominator,p) ) % p;
}

public int calculate(int k, int n) {
    return (int)( modBinomial(n+k,k+1, 1000000007) );
}

String getKth(int n, long k) {
    // Get the k-th valid string of length n.
    // Requires a function countWithPrefix(String) that counts
    // the number of valid strings that begin with a prefix.
    //
        String s = "";
        for (int i=0; i<len; i++) {
            char ch = 'a';
            while(ch <= 'z' ) {
                String prefix = s + ch;
                long x  = countWithPrefix(prefix);
                // if the count is <= k, then we need to subtract it from
                // k so that we worry only about the (k-x)-th string that comes
                // after the current prefix.
                if( x <= k) {
                    k -= x;
                } else {
                    // if the count is > k, then ch must be the character to
                    // pick for this index.
                    break;
                }
                ch ++;
            }
            if( ch > 'z') {
                return ""; //The total number of strings is <= k
            }
            s = s + ch;
        }
        return s;
    }

public class NextHomogeneousStrings
{
    final int TOTAL_CHARS = 26;
    long INF = 1000000000000000001L;
    int    n,d;
    long[]   pow10;
    long[]   mem2;
    int      len;
    String   seed;
    ArrayList< HashMap<Long, Long> > mem;
    
    // Counts the number of strings that begin with
    // a given prefix , assuming that letters are indistinguishable 
    // from each other.
    long countGreater(int p, long prefix) {
        if(p==len) {
            return 1;
        }
        //memoization from hash table:
        if( mem.get(p).containsKey(prefix) ) {
            return mem.get(p).get(prefix);
        }
        long res = 0;
        int  mx = -1;
        int t = Math.min(n-1,p);
        for (int i=t-1 ; i>=0; i--) {
            mx = Math.max(mx, (int)( (prefix/pow10[i])%10 ) );
        }
        long c = 0;
        long tm = 0;
        long[] buff = new long[10];
        Arrays.fill(buff, -1);
        for (int i= ( (t<n-1) ? 0 : 1) ; i<t; i++) {
            int x = (int)( (prefix/pow10[i])%10 );
            if( buff[x] == -1) {
                buff[x] = c++;
            }
            if( t >= n-1 ) {
                tm += buff[x]*pow10[i-1];
            } else {
                tm += buff[x]*pow10[i];
            }
            
        }
        t = Math.min(n-1,p+1);
        for (int j=Math.min(mx+1, d-1); j>=0; j--) {
            long newprefix = 0;
            if( t!=0 ) {
                if ( buff[j] == -1 ) {
                    newprefix = tm + c * pow10[t-1];
                } else {
                    newprefix = tm + buff[j] * pow10[t-1];
                }
            }
            long fc = 1;
            if( j==mx+1) { // a new one:
                fc = ( TOTAL_CHARS - (mx+1) );  
            } else { //a known one:
                fc = 1;
            }
            long x = countGreater(p+1, newprefix);
            if ( x > INF/fc ) {
                x = INF;
            } else {
                x = x*fc;
            }
            //Avoid returning a result larger than INF:
            if ( x + res > INF ) {
                res = INF;
            } else {
                res += x;
            }
            
        }
        //save in hash table:
        mem.get(p).put(prefix,res);
        return res;
    }
    // Encodes a prefix for the last n-1 characters of a string, returns -1 if
    // the string is not homogeneus.
    // i.e: when n=4 reads "xaxaxxa",
    // converts to "100" (in decimal, which describes (0 0 1) ).
    long encodePrefix(String s) {
        long[] buf = new long[26];
        Arrays.fill(buf,-1);
        long m = 0;
        int c=0, j=0;
        for (int i=Math.max(0,s.length()-(n-1) ); i<s.length(); i++) {
            int x = (int)(s.charAt(i)-'a');
            if( buf[x] == -1 ) {
                buf[x] = c++;
            }
            m = m + pow10[j++]*buf[x];
        }
        if( (s.length() >= n) &&  (buf[ s.charAt(s.length()-n)-'a'  ] == -1 ) ) {
            c ++;
        }
        if( c > d) {
            return -1;
        }
        return m;
    }
    
    // Count the number of strings that begin with a given
    // prefix that is equal to the first p characters of seed:
    long countWithEqualPrefix(int p) {
        if(p==len) {
            //how many strings equal to seed are valid?
            // 1 if and only if seed is a valid string.
            return (encodePrefix(seed) != -1) ? 1 : 0;
        }
        if( mem2[p] != -1) {
            return mem2[p];
        }
        long res = 0;
        String s = seed.substring(0,p);
        for (char ch=seed.charAt(p); ch<='z';ch++) {
            String ns = s + ch;
            // Verify that the current prefix is valid:
            if( encodePrefix(ns) == -1) {
                continue;
            }
            long x = countWithPrefix(ns);
            if ( res > INF-x ) {
                res = INF;
            } else {
                res += x;
            }
        }
        return (mem2[p]=res);
    }
    
    // Count the number of valid strings that begin with a given
    // prefix:
    long countWithPrefix(String pref)
    {
        boolean greater = false;
        long ms = encodePrefix(pref);
        if( ms == -1) {
            return 0;
        }
        for (int i=0; i<pref.length(); i++) {
            if( ! greater ) {
	            if(seed.charAt(i) > pref.charAt(i) ) {
	                //Case 1, the prefix is lexicographically earlier, no
	                // valid strings begin with it.
	                return 0;
	            } else if ( seed.charAt(i) < pref.charAt(i) ) {
	                greater = true;
	            }
            }
        }
        if( greater ) {
            //case 2
            return countGreater(pref.length() , ms);
        } else {
            //case 3
            return countWithEqualPrefix(pref.length() );
        }

    }
    
    String getKth(int n, long k) {
    // Get the k-th valid string of length n.
    // Requires a function countWithPrefix(String) that counts
    // the number of valid strings that begin with a prefix.
    //
        String s = "";
        for (int i=0; i<len; i++) {
            char ch = 'a';
            while(ch <= 'z' ) {
                String prefix = s + ch;
                long x  = countWithPrefix(prefix);
                // if the count is <= k, then we need to subtract it from
                // k so that we worry only about the (k-x)-th string that comes
                // after the current prefix.
                if( x <= k) {
                    k -= x;
                } else {
                    // if the count is > k, then ch must be the character to
                    // pick for this index.
                    break;
                }
                ch ++;
            }
            if( ch > 'z') {
                return ""; //The total number of strings is <= k
            }
            s = s + ch;
        }
        return s;
    }
    
    public String getNext(int d, int n, String seed, long k)
    {
        //initialize many variables that are needed by the other methods.
        
        //An array of powers of ten to encode/decode prefixes easily.
        pow10 = new long[18];
        pow10[0] = 1;
        for (int i=1; i< pow10.length; i++) {
            pow10[i] = pow10[i-1]*10;
        }
        //copy the arguments to member variables.
        this.d = d;
        this.n = n;
        this.seed = seed;
        
        len = seed.length();
        //initialize the memoization arrays/hash tables.
        mem = new ArrayList<HashMap<Long, Long> >(len);
        for (int i=0; i<len; i++) {
            mem.add(i, new HashMap<Long, Long> () );
        }
        mem2 = new long[50];
        Arrays.fill(mem2,-1);
        return getKth(n,k); 
    }
}