Day: August 30, 2015

Cavity Map

Problem Statement

You are given a square map of size n×n. Each cell of the map has a value denoting its depth. We will call a cell of the map a cavity if and only if this cell is not on the border of the map and each cell adjacent to it has strictly smaller depth. Two cells are adjacent if they have a common side (edge).

You need to find all the cavities on the map and depict them with the uppercase character X.

Input Format

The first line contains an integer, n, denoting the size of the map. Each of the following n lines contains n positive digits without spaces. Each digit (1-9) denotes the depth of the appropriate area.

Constraints
1≤n≤100

Output Format

Output n lines, denoting the resulting map. Each cavity should be replaced with character X.

Sample Input

4
1112
1912
1892
1234

Sample Output

1112
1X12
18X2
1234

Solution

  
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner sc = new Scanner(System.in);
        String line;
        int n,i,j;
        n = sc.nextInt();
        char [][]CharArray = new char[n][n];
        for(i=0;i<n;i++){
            line = sc.next();
            CharArray[i]= line.toCharArray();
        }
        for(i=1;i<n-1;i++){
            for(j=1;j<n-1;j++){
                if(CharArray[i][j] > CharArray[i][j-1] & CharArray[i][j] > CharArray[i][j+1] & CharArray[i][j] > CharArray[i-1][j] & CharArray[i][j] > CharArray[i+1][j])
                    CharArray[i][j] = 'X';
            }
        }
        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                System.out.print(CharArray[i][j]);
            }
            System.out.println();
        }
    }
}

Chocolate Feast

Problem Statement

Little Bob loves chocolate, and he goes to a store with $N in his pocket. The price of each chocolate is $C. The store offers a discount: for every M wrappers he gives to the store, he gets one chocolate for free. How many chocolates does Bob get to eat?

Input Format:
The first line contains the number of test cases, T.
T lines follow, each of which contains three integers, N, C, and M.

Output Format:
Print the total number of chocolates Bob eats.

Constraints:
1≤T≤1000
2≤N≤105
1≤C≤N
2≤M≤N

Sample input

3
10 2 5
12 4 4
6 2 2

Sample Output

6
3
5

Explanation
In the first case, he can buy 5 chocolates with $10 and exchange the 5 wrappers to get one more chocolate. Thus, the total number of chocolates is 6.

In the second case, he can buy 3 chocolates for $12. However, it takes 4 wrappers to get one more chocolate. He can’t avail the offer and hence the total number of chocolates remains 3.

In the third case, he can buy 3 chocolates for $6. Now he can exchange 2 of the 3 wrappers and get 1 additional piece of chocolate. Now he can use his 1 unused wrapper and the 1 wrapper of the new piece of chocolate to get one more piece of chocolate. So the total is 5.

Solution

  
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;


int main() {
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */   
    int t,n,c,m,total,brought;
    cin>>t;
    while(t--){
        cin>>n>>c>>m;
        int ans=0;
        // Computer answer
        brought = n/c;
        total = brought +(brought-1)/(m-1);
        cout<<total<<endl;
    }
    return 0;
}