Привет, дорогие читатели. Мы вновь и вновь радуем Вас новой подборкой интересных вопросов и задачек с собеседований в ведущие IT-компании!

Кстати, ответы на задачки из прошлого выпуска уже опубликованы!



Выпуски будут появляться каждую неделю — следите за обновлениями! Рубрика выходит при поддержке рекрутингового агентства Spice IT.

На этой неделе мы собрали задачи с собеседований в индийскую компанию MakeMyTrip.

Вопросы


1. 10 Coins Puzzle
You are blindfolded and 10 coins are place in front of you on table. You are allowed to touch the coins, but can’t tell which way up they are by feel. You are told that there are 5 coins head up, and 5 coins tails up but not which ones are which.

Can you make two piles of coins each with the same number of heads up? You can flip the coins any number of times.

Перевод
Вам завязывают глаза и кладут 10 монет на стол перед вами. Вы можете трогать монеты, но на ощупь вы не можете определить, какой из сторон вверх лежат монеты. Вам говорят, что есть 5 монет, лежащих аверсом («решкой») вверх и 5 монет, лежащих реверсом («орлом») вверх, но какие именно — не сказано.

Можете ли вы сделать две кучки монет с одинаковым количеством монет, лежащих аверсом вверх? Вы можете перевернуть монеты любое количество раз.

2. Newspaper Puzzle
A newspaper made of 16 large sheets of paper folded in half. The newspaper has 64 pages altogether. The first sheet contains pages 1, 2, 63, 64.

If we pick up a sheet containing page number 45. What are the other pages that this sheet contains?

Перевод
Газета состоит из 16 больших листов бумаги, сложенных пополам. Всего в газете 64 страницы. Первый лист содержит страницы 1, 2, 63, 64.


* газета сложена пополам

Если мы возьмем лист, содержащий номер страницы 45. Какие еще страницы содержит этот лист?

Задачи


1. Transpose of Matrix
Write a program to find transpose of a square matrix mat[][] of size N*N. Transpose of a matrix is obtained by changing rows to columns and columns to rows.

Input:
The first line of input contains an integer T, denoting the number of testcases. Then T test cases follow. Each test case contains an integer N, denoting the size of the square matrix. Then in the next line are N*N space separated values of the matrix.

Output:
For each test case output will be the space separated values of the transpose of the matrix

Constraints:
1 <= T <= 15
1 <= N <= 20
-103 <= mat[i][j] <= 103


Example:
Input:

2
4
1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4
2
1 2 -9 -2


Output:
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1 -9 2 -2


Explanation:
Testcase 1: The matrix after rotation will be: 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4.

Перевод
Напишите программу, чтобы найти транспонирование квадратной матрицы mat[][] размера N*N. Транспонирование матрицы получается путем изменения строк на столбцы и столбцов на строки.

Ввод:
Первая строка входных данных содержит целое число T, обозначающее количество тестовых наборов. Затем следуют T тестовых наборов. Каждый тестовый набор содержит целое число N, обозначающее размер квадратной матрицы. Затем в следующей строке через пробел записываются N*N значений матрицы.

Выход:
Для каждого теста выходными данными будут разделенные пробелами значения транспонирования матрицы

Ограничения:
1 < = T <= 15
1 < = N <= 20
-103 < = mat[i] [j] < = 103


Пример:
Ввод:

2
4
1 1 1 1 2 2 2 2 3 3 3 3 4 4 4 4
2
1 2 -9 -2


Выход:
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
1 -9 2 -2


Объяснение:
Тест 1: матрица после транспонирования будет: 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4.

2. Trailing zeroes in factorial
For an integer n find number of trailing zeroes in n!.

Input:
The first line contains an integer 'T' denoting the total number of test cases. In each test cases, it contains an integer 'N'.

Output:
In each seperate line output the answer to the problem.

Constraints:
1 <= T <= 100
1 <= N <= 1000


Example:
Input:

1
9

Output:
1
Перевод
Для целого числа n найдите количество нулей на конце числа n!.

Ввод:
Первая строка содержит целое число 'T', обозначающее общее число тестов. В каждом тесте содержится целое число 'N'.

Выход:
В каждой отдельной строке выведите ответ на задачу.

Ограничения:
1 < = T <= 100
1 < = N < = 1000


Пример:
Ввод:

1
9

Выход:
1

3. Steps by Knight
Given a square chessboard of N x N size, the position of Knight and position of a target is given. We need to find out minimum steps a Knight will take to reach the target position.

Input:
The first line of input contains an integer T denoting the number of test cases. Then T test cases follow. Each test case contains an integer n denoting the size of the square chessboard. The next line contains the X-Y coordinates of the knight. The next line contains the X-Y coordinates of the target.

Output:
Print the minimum steps the Knight will take to reach the target position.

Constraints:
1<=T<=100
1<=N<=20
1<=knight_pos,targer_pos<=N


Example:
Input:

2
6
4 5
1 1
20
5 7
15 20


Output:
3
9

Перевод
На квадратной шахматной доске размером N x N задается положение коня и положение цели. Нам нужно выяснить, какие минимальные шаги сделает конь, чтобы достичь цели.

Ввод:
Первая строка входных данных содержит целое число T, обозначающее количество тестов. Затем следуют T тестов. Каждый тест содержит целое число n, обозначающее размер квадратной шахматной доски. Следующая строка содержит координаты X-Y коня. Следующая строка содержит координаты X-Y цели.

Выход:
Выведите минимальные шаги, которые конь сделает, чтобы достичь целевой позиции.

Ограничения:
1<=T<=100
1<=N<=20
1<=knight_pos,targer_pos<=N


Пример:
Ввод:

2
6
4 5
1 1
20
5 7
15 20


Выход:
3
9

Ответы на задачи будут даны в течение следующей недели — успейте решить. Удачи!