Оффлайн
- Регистрация
- 12.04.17
- Сообщения
- 19.095
- Реакции
- 107
- Репутация
- 0
Приветы! Запилили новый выпуск с задачками, направленными на повышение нейропластичности мозга.
Вдохновлялись собеседованиями в американский Walmart. Ну что, готовы пошевелить извилинами?
Ответы на задачки из прошлого выпуска уже
Вопросы
1. Fill the Jug
Перевод
Есть два кувшина (изначально пустые) каждый по 4 и 3 литра соответственно, без каких-либо мерных знаков. Сколько минимум шагов требуется для того, чтобы налить 2 литра воды в 4-х литровый кувшин (кувшины можно наполнять водой и опустошать любое количество раз).
2. Geek and Cashier
Перевод
Гик просит кассира заплатить 200 рупий за классную программу, написанную им самим. Он просит кассира заплатить только следующим образом:
Как собирается расплачиваться кассир?
Задачи
1. Reverse words in a given string
Перевод
Дана строка длиной S. Переверните всю строку, не меняя местами отдельные слова в ней. Слова разделены точками.
Ввод:
Первая строка содержит T, обозначающее количество тестовых наборов. Каждый тест содержит строку S, содержащую символы.
Вывод:
Для каждого теста в новой строке выведите одну строку, содержащую перевернутую строку.
Ограничения:
1 1
Пример:
Ввод:
2
i.like.this.program.very.much
pqr.mno
Вывод:
much.very.program.this.like.i
mno.pqr
2. Kadane's Algorithm
Перевод
Дан массив arr из N целых чисел. Найдите смежный суб-массив с максимальной суммой.
Ввод:
Первая строка входных данных содержит целое число T, обозначающее количество тестов. Описание тестов t следующим образом. Первая строка каждого тестового набора содержит одно целое число N, обозначающее размер массива. Вторая строка содержит N целых чисел, разделенных пробелами A1, A2,..., Обозначающий элементы массива.
Вывод:
Выведите максимальную сумму смежного поддерева в отдельной строке для каждого теста.
Ограничения:
1 ≤ T ≤ 110
1 ≤ N ≤ 106
-107 ≤ A code>
Пример:
Ввод
2
5
1 2 3 -2 5
4
-1 -2 -3 -4
Вывод
9
-1
Объяснение:
Пример 1: максимальный подмассив — сумма 9 элементов (1, 2, 3, -2, 5) которая представляет собой непрерывный подмассив.
3. Ugly Numbers
Перевод
Уродливые числа — это числа, у которых единственными простыми множителями являются 2, 3 или 5. Последовательность: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,… показывает первые 11 уродливых чисел. По соглашению, единица включена. Напишите программу, чтобы найти N-е уродливое число.
Ввод:
Первая строка входных данных содержит целое число T, обозначающее количество тестов. Для каждого тестового набора существует одна строка ввода, содержащая число N.
Вывод:
Вывести N-нное по счёту «уродливое» число.
Ограничения:
1 ≤ T ≤ 104
1 ≤ N ≤ 104
Пример:
Ввод:
2
10
4
Вывод:
12
4
Ответы на задачи будут даны в течение следующей недели — успейте решить. Удачи!
Вдохновлялись собеседованиями в американский Walmart. Ну что, готовы пошевелить извилинами?
Ответы на задачки из прошлого выпуска уже
You must be registered for see links
. Сверяйтесь.Вопросы
1. Fill the Jug
There are two empty jugs each of 4 and 3 liters respectively, without any measuring marks. How many minimum steps are required to have 2 liters of water into the 4 litre jug (the jugs can be filled any number of times with water, and they can be emptied any number of times).
Перевод
Есть два кувшина (изначально пустые) каждый по 4 и 3 литра соответственно, без каких-либо мерных знаков. Сколько минимум шагов требуется для того, чтобы налить 2 литра воды в 4-х литровый кувшин (кувшины можно наполнять водой и опустошать любое количество раз).
2. Geek and Cashier
A Geek asks a cashier to pay Rs 200 for a cool program written by him. He asks the cashier to pay only in the following way:
How does the Geek’s Cashier plan to pay?
- Few 1 Rs Notes. Let x.
- Few 2 Rs Notes. Must ten times of 1 Rs Notes, i.e., 10x.
- Rest of the money as 5 Rs Notes(Minimum number Rs 5 notes should be used)
How does the Geek’s Cashier plan to pay?
Перевод
Гик просит кассира заплатить 200 рупий за классную программу, написанную им самим. Он просит кассира заплатить только следующим образом:
- Несколько банкнот по 1 Рупии. Пусть X.
- Несколько банкнот по 2 Рупии. Необходимо в десять раз больше, чем банкнот по 1 рупии, то есть 10х.
- Остальные деньги в виде банкнот по 5 рупий(минимальное количество банкнот по 5 рупий должно быть использовано)
Как собирается расплачиваться кассир?
Задачи
1. Reverse words in a given string
Given a String of length S, reverse the whole string without reversing the individual words in it. Words are separated by dots.
Input:
The first line contains T denoting the number of testcases. T testcases follow. Each case contains a string S containing characters.
Output:
For each test case, in a new line, output a single line containing the reversed String.
Constraints:
1 1
Example:
Input:
2
i.like.this.program.very.much
pqr.mno
Output:
much.very.program.this.like.i
mno.pqr
Input:
The first line contains T denoting the number of testcases. T testcases follow. Each case contains a string S containing characters.
Output:
For each test case, in a new line, output a single line containing the reversed String.
Constraints:
1 1
Example:
Input:
2
i.like.this.program.very.much
pqr.mno
Output:
much.very.program.this.like.i
mno.pqr
Перевод
Дана строка длиной S. Переверните всю строку, не меняя местами отдельные слова в ней. Слова разделены точками.
Ввод:
Первая строка содержит T, обозначающее количество тестовых наборов. Каждый тест содержит строку S, содержащую символы.
Вывод:
Для каждого теста в новой строке выведите одну строку, содержащую перевернутую строку.
Ограничения:
1 1
Пример:
Ввод:
2
i.like.this.program.very.much
pqr.mno
Вывод:
much.very.program.this.like.i
mno.pqr
2. Kadane's Algorithm
Given an array arr of N integers. Find the contiguous sub-array with maximum sum.
Input:
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the size of array. The second line contains N space-separated integers A1, A2, ..., AN denoting the elements of the array.
Output:
Print the maximum sum of the contiguous sub-array in a separate line for each test case.
Constraints:
1 ≤ T ≤ 110
1 ≤ N ≤ 106
-107 ≤ A code>
Example:
Input
2
5
1 2 3 -2 5
4
-1 -2 -3 -4
Output
9
-1
Explanation:
Testcase 1: Max subarray sum is 9 of elements (1, 2, 3, -2, 5) which is a contiguous subarray.
Input:
The first line of input contains an integer T denoting the number of test cases. The description of T test cases follows. The first line of each test case contains a single integer N denoting the size of array. The second line contains N space-separated integers A1, A2, ..., AN denoting the elements of the array.
Output:
Print the maximum sum of the contiguous sub-array in a separate line for each test case.
Constraints:
1 ≤ T ≤ 110
1 ≤ N ≤ 106
-107 ≤ A code>
Example:
Input
2
5
1 2 3 -2 5
4
-1 -2 -3 -4
Output
9
-1
Explanation:
Testcase 1: Max subarray sum is 9 of elements (1, 2, 3, -2, 5) which is a contiguous subarray.
Перевод
Дан массив arr из N целых чисел. Найдите смежный суб-массив с максимальной суммой.
Ввод:
Первая строка входных данных содержит целое число T, обозначающее количество тестов. Описание тестов t следующим образом. Первая строка каждого тестового набора содержит одно целое число N, обозначающее размер массива. Вторая строка содержит N целых чисел, разделенных пробелами A1, A2,..., Обозначающий элементы массива.
Вывод:
Выведите максимальную сумму смежного поддерева в отдельной строке для каждого теста.
Ограничения:
1 ≤ T ≤ 110
1 ≤ N ≤ 106
-107 ≤ A code>
Пример:
Ввод
2
5
1 2 3 -2 5
4
-1 -2 -3 -4
Вывод
9
-1
Объяснение:
Пример 1: максимальный подмассив — сумма 9 элементов (1, 2, 3, -2, 5) которая представляет собой непрерывный подмассив.
3. Ugly Numbers
Ugly numbers are numbers whose only prime factors are 2, 3 or 5. The sequence 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, … shows the first 11 ugly numbers. By convention, 1 is included. Write a program to find Nth Ugly Number.
Input:
The first line of input contains an integer T denoting the number of test cases. T testcases follow. For each testcase there is one line of input that contains the number N.
Output:
Print the Nth Ugly Number.
Constraints:
1 ≤ T ≤ 104
1 ≤ N ≤ 104
Example:
Input:
2
10
4
Output:
12
4
Input:
The first line of input contains an integer T denoting the number of test cases. T testcases follow. For each testcase there is one line of input that contains the number N.
Output:
Print the Nth Ugly Number.
Constraints:
1 ≤ T ≤ 104
1 ≤ N ≤ 104
Example:
Input:
2
10
4
Output:
12
4
Перевод
Уродливые числа — это числа, у которых единственными простыми множителями являются 2, 3 или 5. Последовательность: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15,… показывает первые 11 уродливых чисел. По соглашению, единица включена. Напишите программу, чтобы найти N-е уродливое число.
Ввод:
Первая строка входных данных содержит целое число T, обозначающее количество тестов. Для каждого тестового набора существует одна строка ввода, содержащая число N.
Вывод:
Вывести N-нное по счёту «уродливое» число.
Ограничения:
1 ≤ T ≤ 104
1 ≤ N ≤ 104
Пример:
Ввод:
2
10
4
Вывод:
12
4
Ответы на задачи будут даны в течение следующей недели — успейте решить. Удачи!