Rectangle Rotation

Description:

A rectangle with sides equal to even integers a and b is drawn on the Cartesian plane. Its center (the intersection point of its diagonals) coincides with the point (0, 0), but the sides of the rectangle are not parallel to the axes; instead, they are forming 45 degree angles with the axes.

How many points with integer coordinates are located inside the given rectangle (including on its sides)?

Example

For a = 6 and b = 4, the output should be
rectangleRotation(a, b) = 23.

The following picture illustrates the example, and the 23 points are marked green.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer aA positive even integer.

    Constraints:
    2 ≤ a ≤ 50.

  • [input] integer bA positive even integer.

    Constraints:
    2 ≤ b ≤ 50.

  • [output] integerThe number of inner points with integer coordinates.

Tests:

Explain:

a17b87ea843a52e8ce44a35109bca772af4ba2631

therefore 4 blue edges make 45 degrees angles so the 4 edges are corresponding 4 expressions:

  • f1(x,y) = x + y + u = 0
  • f2(x,y) = x + y – u = 0
  • f3(x,y) = x – y + v = 0
  • f4(x,y) = x – y – v = 0

therefore point O(0,0) is in the rectangle, So

  • f1(0,0) = u > 0
  • f2(0,0) = -u < 0
  • f3(0,0) = v > 0
  • f4(0,0) = -v < 0

If 1 point P(x,y) is in the rectangle then demands 4 conditions:

  • f1(x,y) = x + y + u > 0
  • f2(x,y) = x + y – u < 0
  • f3(x,y) = x – y + v > 0
  • f4(x,y) = x – y – v < 0

Mean: |x + y| < u and |x – y| < v

Now finding u, v:

Draws more 2 red lines perpendicular with 2 edges of the rectangle, we have right angled triangles, So u = a/sqrt(2), v = b/sqrt(2).
Solution(C#):


int rectangleRotation(int a, int b) {
   int r = 0;
	for (int x = -a - b; x &amp;amp;amp;amp;amp;lt;= a + b; x++) {
		for (int y = -a - b; y &amp;amp;amp;amp;amp;lt;= a + b; y++) {
			if (2 * (x - y) * (x - y) &amp;amp;amp;amp;amp;lt;= a * a &amp;amp;amp;amp;amp;amp;&amp;amp;amp;amp;amp;amp; 2 * (x + y) * (x + y) &amp;amp;amp;amp;amp;lt;= b * b)
                r++;
		}
	}
	return r;
}

Crossword Formation

Description:

You’re a crossword fanatic, and have finally decided to try and create your own. However, you also love symmetry and good design, so you come up with a set of rules they should follow:

  • the crossword must contain exactly four words;
  • these four words should form four pairwise intersections;
  • all words must be written either left-to-right or top-to-bottom;
  • the area of the rectangle formed by empty cells inside the intersections isn’t equal to zero.

Given 4 words, find the number of ways to make a crossword following the above-described rules. Note that two crosswords which differ by rotation are considered different.

Example

For words = ["crossword", "square", "formation", "something"], the output should be
crosswordFormation(words) = 6.

The six crosswords can be formed as shown below:

  f                         f                             f
  o                     c r o s s w o r d     c r o s s w o r d
c r o s s w o r d           r   o                   q     r
  m   q                     m   m                   u     m
  a   u            ;  s q u a r e          ;        a     a
  t   a                     t   t                   r     t
  i   r                     i   h             s o m e t h i n g
s o m e t h i n g           o   i                         o
  n                         n   n                         n
                                g                               
                                                              
    c         s               s                                      
f o r m a t i o n       c     q               c         s          
    o         m         r     u               r         o      
    s q u a r e       f o r m a t i o n       o         m            
    s         t    ;    s     r            ;  s q u a r e                  
    w         h         s o m e t i n g       s         t         
    o         i         w                     w         h     
    r         n         o                   f o r m a t i o n            
    d         g         r                     r         n         
                        d                     d         g             

Input/Output

  • [time limit] 20000ms (swift)
  • [input] array.string words

    An array of distinct strings, the words you need to use in your crossword.

    Constraints:
    words.length = 4,
    3 ≤ words[i].length < 15.

  • [output] integer

    The number of ways to make a correct crossword of the desired formation.

Tests:
Solution(Swift):

func crosswordFormation(words: [String]) -> Int {
    var count = 0
    for i in 0..<4 {
        let a = words[i].characters.map({String($0)})
        for a1 in 0..<(a.count - 1) {
            for j in 0..<4 {
                if j == i {
                    continue
                }
                let b = words[j].characters.map({String($0)})
                for b2 in 1..<b.count {
                    if b[b2] != a[a1] {
                        continue
                    }
                    for b1 in 0..<(b2 - 1) {
                        for k in 0..<4 {
                            if k == i || k == j {
                                continue
                            }
                            let c = words[k].characters.map({String($0)})
                            let d = words[6 - i - j - k].characters.map({String($0)})
                            if b2 - b1 >= d.count {
                                continue
                            }
                            for c1 in 0..<(c.count - 1) {
                                if c[c1] != b[b1] {
                                    continue
                                }
                                for c2 in (c1 + 2)..<c.count {
                                    let a2 = a1 + (c2 - c1)
                                    if a2 >= a.count {
                                        continue
                                    }
                                    for d1 in 0..<d.count {
                                        if d[d1] != c[c2] {
                                            continue
                                        }
                                        let d2 = d1 + (b2 - b1)
                                        if d2 >= d.count {
                                            break
                                        }
                                        if a[a2] != d[d2] {
                                            continue
                                        }
                                        count += 1
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    return count
}

Weak Numbers

Description:

We define the weakness of number x as the number of positive integers smaller than x that have more divisors than x.

It follows that the weaker the number, the greater overall weakness it has. For the given integer n, you need to answer two questions:

  • what is the weakness of the weakest numbers in the range [1, n]?
  • how many numbers in the range [1, n] have this weakness?

Return the answer as an array of two elements, where the first element is the answer to the first question, and the second element is the answer to the second question.

Example

For n = 9, the output should be
weakNumbers(n) = [2, 2].

Here are the number of divisors and the specific weakness of each number in range [1, 9]:

  • 1: d(1) = 1, weakness(1) = 0;
  • 2: d(2) = 2, weakness(2) = 0;
  • 3: d(3) = 2, weakness(3) = 0;
  • 4: d(4) = 3, weakness(4) = 0;
  • 5: d(5) = 2, weakness(5) = 1;
  • 6: d(6) = 4, weakness(6) = 0;
  • 7: d(7) = 2, weakness(7) = 2;
  • 8: d(8) = 4, weakness(8) = 0;
  • 9: d(9) = 3, weakness(9) = 2.

As you can see, the maximal weakness is 2, and there are 2 numbers with thatweakness level.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer nConstraints:
    1 ≤ n ≤ 1000.
  • [output] array.integerArray of two elements: the weakness of the weakest number, and the number of integers in range [1, n] with this weakness.

Tests:
Solution:

int[] weakNumbers(int n) {
    List<int> result=new List<int>();
    int weaknesses = 0, weaknest=0;
    for(int index=1;index<=n;index++) {
        int w = getWeakness(index);
        if(w>weaknest) {
            weaknest = w;
            weaknesses=1;
        }
        else if(w==weaknest)
            weaknesses++;
    }
    result.Add(weaknest);
    result.Add(weaknesses);
    return result.ToArray();
}
int getWeakness(int n) {
    int count=0;
    if(n==1)
        return 0;
    int dN = getD(n);
    for(int i=1;i<n;i++) {
        if(getD(i)>dN)
            count++;
    }
    return count;
}
int getD(int n) {
    if(n==1)
        return 1;
    if(n==2)
        return 2;
    int count=0;
    int halfN = n/2;
    for(int i=2;i<=halfN;i++) {
        if(n%i==0)
            count++;
    }
    return count+2;
}

Comfortable Numbers

Description:

Let’s say that number a feels comfortable with number b if a ≠ b and b lies in the segment [a - s(a), a + s(a)], where s(x) is the sum of x‘s digits.

How many pairs (a, b) are there, such that a < b, both a and b lie on the segment [L, R], and each number feels comfortable with the other?

Example

For L = 10 and R = 12, the output should be
comfortableNumbers(L, R) = 2.

Here are all values of s(x) to consider:

  • s(10) = 1, so 10 is comfortable with 9 and 11;
  • s(11) = 2, so 11 is comfortable with 9, 10, 12 and 13;
  • s(12) = 3, so 12 is comfortable with 9, 10, 11, 13, 14 and 15.

Thus, there are 2 pairs of numbers comfortable with each other within the segment [10; 12]: (10, 11) and (11, 12).

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer LConstraints:
    1 ≤ L ≤ R ≤ 1000.
  • [input] integer RConstraints:
    1 ≤ L ≤ R ≤ 1000.
  • [output] integerThe number of pairs satisfying all the above conditions.

Tests:
Solution:

int comfortableNumbers(int L, int R) {
    if(L==R)
        return 0;

    int a = L, b = a + 1, sumA = 0, pairs = 0;
    List<string> listPairs = new List<string>();
    while (a < R) {
        string aStr = a.ToString();
        int aX = 0;

        while (aX < aStr.Length) {
            sumA = sumA + int.Parse(aStr[aX]+"");
            aX = aX + 1;
        }
        while (b <= R) {
            string bStr = b.ToString();
            int bX = 0, sumB = 0;

            while (bX < bStr.Length) {
                sumB = sumB + int.Parse(bStr[bX]+"");
                bX = bX + 1;
            }

            if((b >= a - sumA) && (b <= a + sumA)&&
              (a >= b - sumB) && (a <= b + sumB)) {
                pairs = pairs + 1;
            }

            b = b + 1;
        }

        a = a + 1;
        b = a + 1;
        sumA = 0;
    }
    return pairs;
}

Pages Numbering With Ink

Description:

You work in a company that prints and publishes books. You are responsible for designing the page numbering mechanism in the printer. You know how many digits a printer can print with the leftover ink. Now you want to write a function to determine what the last page of the book is that you can number given thecurrent page and numberOfDigits left. A page is considered numbered if it has the full number printed on it (e.g. if we are working with page 102 but have ink only for two digits then this page will not be considered numbered).

It’s guaranteed that you can number the current page, and that you can’t number the last one in the book.

Example

  • For current = 1 and numberOfDigits = 5, the output should be
    pagesNumberingWithInk(current, numberOfDigits) = 5.The following numbers will be printed: 1, 2, 3, 4, 5.
  • For current = 21 and numberOfDigits = 5, the output should be
    pagesNumberingWithInk(current, numberOfDigits) = 22.The following numbers will be printed: 21, 22.
  • For current = 8 and numberOfDigits = 4, the output should be
    pagesNumberingWithInk(current, numberOfDigits) = 10.The following numbers will be printed: 8, 9, 10.

Input/Output

  • [time limit] 3000ms (cs)
  • [input] integer currentA positive integer, the number on the current page which is not yet printed.

    Constraints:
    1 ≤ current ≤ 1000.

  • [input] integer numberOfDigitsA positive integer, the number of digits which your printer can print.

    Constraints:
    1 ≤ numberOfDigits ≤ 1000.

  • [output] integerThe last printed page number.

Tests:
Solution:

int pagesNumberingWithInk(int current, int numberOfDigits) {
    int digitsInCurrent = countDigitsInNumber(current);
    while (numberOfDigits >= digitsInCurrent) {
        numberOfDigits -= digitsInCurrent;
        current++;
        digitsInCurrent = countDigitsInNumber(current);
    }
    return current - 1;
}
private static int countDigitsInNumber(int n) {
    int count = 0;
    while (n > 0) {
        count++;
        n /= 10;
    }
    return count;
}

 

Is Power?

Description:

Determine if the given number is a power of some non-negative integer.

Example

  • For n = 125, the output should be
    isPower(n) = true;
  • For n = 72, the output should be
    isPower(n) = false.

Input/Output

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

    A positive integer.

    Constraints:
    1 ≤ n ≤ 350.

  • [output] boolean

    true if n can be represented in the form ab (a to the power of b) wherea and b are some non-negative integers and b ≥ 2, false otherwise.

Tests:
Solution:

bool isPower(int n) {
    if(n==1)
        return true;
    for(int index=2;index<=Math.Sqrt(n);index++) {
        for(int power=2;power<=Math.Sqrt(n);power++) {
            if(Math.Pow(index,power)==n)
                return true;
        }
    }
    return false;
}

Square Digits Sequence

Description:

Consider a sequence of numbers a0, a1, …, an, in which an element is equal to the sum of squared digits of the previous element. The sequence ends once an element that has already been in the sequence appears again.

Given the first element a0, find the length of the sequence.

Example

  • For a0 = 16, the output should be
    squareDigitsSequence(a0) = 9.

    Here’s how elements of the sequence are constructed:

    • a0 = 16
    • a1 = 12 + 62 = 37
    • a2 = 32 + 72 = 58
    • a3 = 52 + 82 = 89
    • a4 = 82 + 92 = 145
    • a5 = 12 + 42 + 52 = 42
    • a6 = 42 + 22 = 20
    • a7 = 22 + 02 = 4
    • a8 = 42 = 16, which has already occurred before (a0)

    Thus, there are 9 elements in the sequence.

  • For a0 = 103, the output should be
    squareDigitsSequence(a0) = 4.

    The sequence goes as follows: 103 -> 10 -> 1 -> 1, 4 elements altogether.

Input/Output

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

    First element of a sequence, positive integer.

    Constraints:
    1 ≤ a0 ≤ 650.

  • [output] integer

Tests:
Solution:

int squareDigitsSequence(int a0) {
    int cur = a0;
    List<int> was = new List<int>();

    while (!was.Contains(cur)) {
        was.Add(cur);
        int next = 0;
        while (cur > 0) {
            next += (cur % 10) * (cur % 10);
            cur /= 10;
        }
        cur = next;
    }

    return was.Count + 1;
}