Count Black Cells

Description:

Imagine a white rectangular grid of n rows and m columns divided into two parts by a diagonal line running from the upper left to the lower right corner. Now let’s paint the grid in two colors according to the following rules:

  • A cell is painted black if it has at least one point in common with the diagonal;
  • Otherwise, a cell is painted white.

Count the number of cells painted black.

Example

  • For n = 3 and m = 4, the output should be
    countBlackCells(n, m) = 6.

    There are 6 cells that have at least one common point with the diagonal and therefore are painted black.

  • For n = 3 and m = 3, the output should be
    countBlackCells(n, m) = 7.

    7 cells have at least one common point with the diagonal and are painted black.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer n

    The number of rows.

    Constraints:
    1 ≤ n ≤ 105.

  • [input] integer m

    The number of columns.

    Constraints:
    1 ≤ m ≤ 105.

  • [output] integer

    The number of black cells.

Tests:
Solution:

int countBlackCells(int n, int m) {
    int answer = 0;
    for (int x = 1; x <= n; x++) {
        int L = (int) (m * 1L * (x - 1) / n);
        if (m * 1L * (x - 1) % n == 0) {
            L--;
        }
        int R = (int) (m * 1L * x / n);
        L = Math.Max(0, L);
        R = Math.Min(R, m - 1);
        answer += R - L + 1;
    }
    return answer;
}

Candles

Description:

When a candle finishes burning it leaves a leftover. makeNew leftovers can be combined to make a new candle, which, when burning down, will in turn leave another leftover.

You have several candles in your possession. What’s the total number of candles you can burn, assuming that you create new candles as soon as you have leftovers?

Example

For candles = 5 and makeNew = 2, the output should be
candles(candles, makeNew) = 9.

Here is what you can do to burn 9 candles:

  • burn 5 candles, obtain 5 leftovers;
  • create 2 more candles, using 4 leftovers (1 leftover remains);
  • burn 2 candles, end up with 3 leftovers;
  • create another candle using 2 leftovers (1 leftover remains);
  • burn the created candle, which gives another leftover (2 leftovers in total);
  • create a candle from the remaining leftovers;
  • burn the last candle.

Thus, you can burn 5 + 2 + 1 + 1 = 9 candles, which is the answer.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer candles

    Constraints:
    1 ≤ candles ≤ 15.

  • [input] integer makeNew

    Constraints:
    2 ≤ makeNew ≤ 5.

  • [output] integer

Tests:
Solution:

int candles(int A, int B) {
    int burned = 0;
    int leftowers = 0;
    while (A > 0) {
        burned += A;
        leftowers += A;
        A = leftowers / B;
        leftowers %= B;
    }
    return burned;
}

Rounders

Description:

We want to turn the given integer into a number that has only one non-zero digit using a tail rounding approach. This means that at each step we take the last non 0 digit of the number and round it to 0 or to 10. If it’s less than 5 we round it to 0 if it’s larger than or equal to 5 we round it to 10 (rounding to 10means increasing the next significant digit by 1).

Example

  • For value = 15, the output should be
    rounders(value) = 20;
  • For value = 1234, the output should be
    rounders(value) = 1000.

    1234 -> 1230 -> 1200 -> 1000.

  • For value = 1445, the output should be
    rounders(value) = 2000.

    1445 -> 1450 -> 1500 -> 2000.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer value

    A positive integer.

    Constraints:
    1 ≤ value ≤ 108.

  • [output] integer

    The rounded number.

Tests:
Solution:

int rounders(int n) {
    int p = 10;
    while (n > p) {
        if ((n % p) / (p / 10) < 5)
            n = (n / p) * p;
        else
            n =  (n/p+1)*p ;
        p *= 10;
    }
    return n;
}

Increase Number Roundness

Description:

Define an integer’s roundness as the number of trailing zeroes in it.

Given an integer n, check if it’s possible to increase n‘s roundness by swapping some pair of its digits.

Example

  • For n = 902200100, the output should be
    increaseNumberRoundness(n) = true.

    One of the possible ways to increase roundness of n is to swap digit 1with digit 0 preceding it: roundness of 902201000 is 3, and roundness of nis 2.

    For instance, one may swap the leftmost 0 with 1.

  • For n = 11000, the output should be
    increaseNumberRoundness(n) = false.

    Roundness of n is 3, and there is no way to increase it.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer n

    A positive integer.

    Constraints:
    100 ≤ n ≤ 109.

  • [output] boolean

    true if it’s possible to increase n‘s roundness, false otherwise.

Tests:
Solution:

bool increaseNumberRoundness(int n) {
    bool gotToSignificant = false;
    while (n > 0) {
        if (n % 10 == 0 && gotToSignificant) {
            return true;
        } else if (n % 10 != 0) {
            gotToSignificant = true;
        }
        n /=  10 ;
    }

    return false;    
}

Apple Boxes

Description:

There’re k square apple boxes full of apples. If a box is of size m, then it contains m × m apples. You noticed two interesting properties about the boxes:

  1. The smallest box is of size 1, the next one is of size 2,…, all the way up to size k.
  2. Boxes that have an odd size contain only yellow apples. Boxes that have an even size contain only red apples.

Your task is to calculate the difference between the number of red apples and the number of yellow apples.

Example

For k = 5, the output should be
appleBoxes(k) = -15.

There are 1 + 3 * 3 + 5 * 5 = 35 yellow apples and 2 * 2 + 4 * 4 = 20 red apples, thus the answer is 20 - 35 = -15.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer k

    A positive integer.

    Constraints:
    1 ≤ k ≤ 40.

  • [output] integer

    The difference between the two types of apples.

Tests:
Solution:

int appleBoxes(int k) {
    if(1 <=k && k <= 40) {
        int yellows=0;
        int reds=0;
        for(int index=1;index<=k;index++) {
            if(index%2==0) {
                reds+=index*index;
            }
            else {
                yellows+=index*index;
            }
        }
        return reds-yellows;
    }
    else {
        throw new ArgumentOutOfRangeException();
    }
}

Addition Without Carrying

Description:

A little boy is studying arithmetics. He has just learned how to add two integers, written one below another, column by column. But he always forgets about the important part – carrying.

Given two integers, find the result which the little boy will get.

Note: the boy used this site as the source of knowledge, feel free to check it out too if you are not familiar with column addition.

Example

For param1 = 456 and param2 = 1734, the output should be
additionWithoutCarrying(param1, param2) = 1180.

   456
  1734
+ ____
  1180

The little boy goes from right to left:

  • 6 + 4 = 10 but the little boy forgets about 1 and just writes down 0 in the last column
  • 5 + 3 = 8
  • 4 + 7 = 11 but the little boy forgets about the leading 1 and just writes down 1 under 4 and 7.
  • There is no digit in the first number corresponding to the leading digit of the second one, so the little boy imagines that 0 is written before 456. Thus, he gets 0 + 1 = 1.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer param1

    A non-negative integer.

    Constraints:
    0 ≤ param1 ≤ 99999.

  • [input] integer param2

    A non-negative integer.

    Constraints:
    0 ≤ param2 ≤ 59999.

  • [output] integer

    The result that the little boy will get.

Tests:
Solution:

int additionWithoutCarrying(int param1, int param2) {
    string p1 = param1.ToString(); 
    string p2 = param2.ToString();
    int sum=0;
    for(int index=0;index < Math.Max(p1.Length, p2.Length);index++) {
        int a1=0,a2=0;
        if(index < p1.Length) {
            string s1 = string.Empty;
            s1+= p1[p1.Length -1 - index];
            a1 = int.Parse(s1);
        }
        if(index < p2.Length) {
            string s2 = string.Empty;
            s2+=p2[p2.Length -1 - index];
            a2 = int.Parse(s2);
        }
        int total = (a1+a2);
        if(total>=10)
            total-=10;
        sum = sum + total*(int)Math.Pow(10, index);
    }
    return sum;
}

Lineup

Description:

To prepare his students for an upcoming game, the sports coach decides to try some new training drills. To begin with, he lines them up and starts with the following warm-up exercise: when the coach says 'L', he instructs the students to turn to the left. Alternatively, when he says 'R', they should turn to the right. Finally, when the coach says 'A', the students should turn around.

Unfortunately some students (not all of them, but at least one) can’t tell left from right, meaning they always turn right when they hear 'L' and left when they hear'R'. The coach wants to know how many times the students end up facing the same direction.

Given the list of commands the coach has given, count the number of such commands after which the students will be facing the same direction.

Example

For commands = "LLARL", the output should be
lineUp(commands) = 3.

Let’s say that there are 4 students, and the second one can’t tell left from right. In this case, only after the second, third and fifth commands will the students face the same direction.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] string commands

    String consisting of characters 'L', 'R' and 'A' only.

    Constraints:
    0 ≤ commands.length ≤ 35.

  • [output] integer

    The number of commands after which students face the same direction.

Tests:
Solution:

int lineUp(string commands) {
    int r = 0;
    bool pair = true;

    if (commands.Trim().Length == 0) {
        return 0;
    }
    commands = commands.ToUpper();
    for (int i = 0; i < commands.Length; i++) {
        char c = commands[i];
        if ((c == 'L' || c == 'R')) {
            if(!pair)
                r++;
            pair = !pair;
        } else{
            if(pair)
                r++;
        }
    }

    return r;
}