14.05.2020 14:35
Ac0olA 2 1200 Источник
Привет! Новая неделя — новый выпуск брейнтизиров. На этот раз, с собеседований в ИТ-компанию Accolite.

Кстати, ответы на задачки из прошлого выпуска уже опубликованы, проверяйте себя и свою смекалку.

Ну что, погнали!

Вопросы


1. Rich or Poor
A place has two kinds of residents, Poor, who always tell the truth, and their opposites, Rich, who always lie. You encounter two people A and B. What are A and B if A says “B is a Poor” and B says “The two of us are opposite types”?

Перевод
В одном из мест есть два вида жителей: бедные, которые всегда говорят правду, и богатые, которые всегда лгут. Вы сталкиваетесь с двумя людьми A и B. К какому из классов относится каждый из людей A и B, если A говорит «B — бедный», а B говорит: «Мы оба — противоположные типы»?

2. Boy with Marbles
A boy goes to 20 of his friend’s houses with ‘n’ number of newly purchased marbles in his hands. At every house he visits, he gives away half of marbles he have and take one of his friend’s marble’s and adds it with the one’s he is left with, he never had a problem of dividing an odd number of marbles left and finally after leaving the his 20th friends house, he is left with 2 marbles, can you guess the ‘n’ value?

Перевод
Мальчик идет в 20 домов своих друзей с «n» количеством недавно купленных шариков в руках. В каждом доме, который он посещает, он отдает половину шариков, которые у него есть, и берет один из шариков своего друга и добавляет его к тем, которые у него остались. У него никогда не было проблемы с разделением нечетного количества оставшихся шариков, и наконец, после того, как он покинул последний дом своих 20 друзей, у него осталось 2 шарика. Можете ли вы угадать значение «n»?

Задачи


1. Swap two nibbles in a byte
Given a byte, swap the two nibbles in it. For example 100 is be represented as 01100100 in a byte (or 8 bits). The two nibbles are (0110) and (0100). If we swap the two nibbles, we get 01000110 which is 70 in decimal.

Input:
The first line contains 'T' denoting the number of testcases. Each testcase contains a single positive integer X.

Output:
In each separate line print the result after swapping the nibbles.

Constraints:
1 ? T ? 70
1 ? X ? 255

Example:
Input:
2
100
129

Output:
70
24

Перевод
Дан байт, поменяйте местами две части в нем. Например, 100 можно представить как 01100100 в байте (или 8 битах). Две части — это (0110) и (0100). Если мы поменяем местами две части, то получим 01000110, что равно 70 в десятичной системе счисления.

Ввод:
Первая строка содержит букву «Т», обозначающую количество тестов. Каждый тест содержит одно положительное целое число X.

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

Ограничения:
1 ? T ? 70
1 ? X ? 255

Пример:
Ввод:
2
100
129

Вывод:
70
24

2. Count pairs with given sum
Given an array of integers, and an integer ‘K’, find the count of pairs of elements in the array whose sum is equal to 'K'.

Input:
First line of the input contains an integer T, denoting the number of test cases. Then T test cases follow. Each test case consists of two lines. First line of each test case contains 2 space separated integers N and K denoting the size of array and the sum respectively. Second line of each test case contains N space separated integers denoting the elements of the array.

Output:
Print the count of pairs of elements in the array whose sum is equal to the K.

Constraints:
1<=T<=50
1<=N<=50
1<=K<=50
1<=A[i]<=100

Example:
Input
2
4 6
1 5 7 1
4 2
1 1 1 1
Output
2
6

Перевод
Дан массив целых чисел и целое число «K», найдите количество пар элементов в массиве, сумма которых равна «K».

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

Вывод:
Выведите количество пар элементов в массиве, сумма которых равна К.

Ограничения:
1< = T< = 50
1< = N< = 50
1< = K< = 50
1<=A[i]< = 100

Пример:
Ввод
2
4 6
1 5 7 1
4 2
1 1 1 1
Вывод
2
6

3. Trie | (Insert and Search)
Trie is an efficient information retrieval data structure. Use this data structure to store Strings and search strings. Your task is to use TRIE data structure and search the given string A. If found print 1 else 0.

Input:
The first line of input contains a single integer T denoting the number of test cases. Then T test cases follow. Each test case consists of three lines.
First line of each test case consist of a integer N, denoting the number of element in a Trie to be stored.
Second line of each test case consists of N space separated strings denoting the elements to be stored in the trie.
Third line of each test case consists of a String A to be searched in the stored elements.

Output:
Print the respective output in the respective line.

Constraints:
1<=T<=20
1<=N<=20

Example:
Input:
1
8
the a there answer any by bye their
the
Output:
1

Перевод
Trie — это эффективная структура данных для поиска информации. Используйте эту структуру данных для хранения строк и поиска строк. Ваша задача состоит в том, чтобы использовать структуру данных TRIE и искать заданную строку A. Если она найдена, выведите 1, если нет — 0.

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

Вывод:
Выведите 1 или 0 в соответствующей строке.

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

Пример:
Ввод:
1
8
the a there answer any by bye their
the
Вывод:
1

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