Второй минимум
Последовательность состоит из натуральных чисел и завершается числом 0. Определите значение второго минимального по величине элемента в этой последовательности, то есть элемента, который будет наименьшим, если из последовательности удалить наименьший элемент.
Последнее число 0 не учитывается. Гарантируется, что в последовательности есть хотя бы два элемента (кроме завершающего числа 0).
Входные данные
На вход подаётся последовательность целых неотрицательных чисел, заканчивающаяся нулём. Все числа в последовательности неотрицательные, по значению не превосходящие 109.
Выходные данные
Выведите ответ на задачу.
Примеры
Ввод
1
7
9
0
3
2
2
1
1
0
Вывод
7
1
Вот мой код:
| Python | ||
|
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int idx;
Node *left, *right;
};
Node *createNode(int idx)
{
Node *t = new Node;
t->left = t->right = NULL;
t->idx = idx;
return t;
}
void traverseHeight(Node *root, int arr[], int &res)
{
if (root == NULL || (root->left == NULL &&
root->right == NULL))
return;
if (res > arr[root->left->idx] &&
root->left->idx != root->idx)
{
res = arr[root->left->idx];
traverseHeight(root->right, arr, res);
}
else if (res > arr[root->right->idx] &&
root->right->idx != root->idx)
{
res = arr[root->right->idx];
traverseHeight(root->left, arr, res);
}
}
void findSecondMin(int arr[], int n)
{
list<Node *> li;
Node *root = NULL;
for (int i = 0; i < n; i += 2)
{
Node *t1 = createNode(i);
Node *t2 = NULL;
if (i + 1 < n)
{
t2 = createNode(i + 1);
root = (arr[i] < arr[i + 1])? createNode(i) :
createNode(i + 1);
root->left = t1;
root->right = t2;
li.push_back(root);
}
else
li.push_back(t1);
}
int lsize = li.size();
while (lsize != 1)
{
int last = (lsize & 1)? (lsize - 2) : (lsize - 1);
for (int i = 0; i < last; i += 2)
{
Node *f1 = li.front();
li.pop_front();
Node *f2 = li.front();
li.pop_front();
root = (arr[f1->idx] < arr[f2->idx])?
createNode(f1->idx) : createNode(f2->idx);
root->left = f1;
root->right = f2;
li.push_back(root);
}
if (lsize & 1)
{
li.push_back(li.front());
li.pop_front();
}
lsize = li.size();
}
int res = INT_MAX;
traverseHeight(root, arr, res);
cout << "Minimum: " << arr[root->idx]
<< ", Second minimum: " << res << endl;
}
int main()
{
int arr[] = {61, 6, 100, 9, 10, 12, 17};
int n = sizeof(arr)/sizeof(arr[0]);
findSecondMin(arr, n);
return 0;
}
В массиве хранится информация о количестве людей, живущих на каждом из 15 этажей дома (на первом этаже — в нулевом элементе массива, на втором — в первом и т. д.). Определить два этажа, на которых проживает меньше всего людей. (Если минимальное количество жителей одинаково на 2х и более этажах, то вывести наименьшие этажи )
Входные данные: Элементы массива вводятся в одну строку через пробел
Выходные данные: Вывести два числа в одной строке через пробел, сначала этаж с самым маленьким числом людей. При одинаковом количестве жителей — сначала наименьший этаж.
Мой код, в котором я пузырьком сортирую и вывожу индексы 1 и 2
элемента отсортированного массива в изначальном, проходит 4 из 5
тестов => я что-то упустил, бьюсь уже несколько дней поэтому задаю
вопрос здесь
N = 15
a = input().split(' ')
a = [int(x) for x in a]
if a[0] > a[1]:
mn1 = 0
mn2 = 1
else:
mn1 = 1
mn2 = 0
for i in range(2,N):
if a[i] < a[mn1]:
b = mn1
mn1 = i
if a[b] < a[mn2]:
mn2 = b
elif a[i] < a[mn2]:
mn2 = i
if mn1 < mn2:
print(mn1+1, end = " ")
print(mn2+1)
else:
print(mn2+1,end=" ")
print(mn1 + 1)
Запрещенные операторы:sort;min;max;reverse;count
Функция действительно может быть изменена, чтобы найти вторую наименьшую:
def second_smallest(numbers):
m1, m2 = float('inf'), float('inf')
for x in numbers:
if x <= m1:
m1, m2 = x, m1
elif x < m2:
m2 = x
return m2
Старая версия основывалась на деталях реализации Python 2, которые None всегда сортируются перед чем-либо еще (поэтому он тестируется как «меньше» ); Я заменил это с помощью float('inf') как дозорного, так как бесконечность всегда проверяется как больше любого другого числа. В идеале исходная функция должна была использовать float('-inf') вместо None там, чтобы не привязываться к деталям реализации, другие реализации Python могут не делиться.
Демо:
>>> def second_smallest(numbers):
... m1, m2 = float('inf'), float('inf')
... for x in numbers:
... if x <= m1:
... m1, m2 = x, m1
... elif x < m2:
... m2 = x
... return m2
...
>>> print second_smallest([1, 2, 3, 4])
2
Вне функции, которую вы обнаружили, почти так же эффективно использовать функцию heapq.nsmallest(), чтобы вернуть два наименьших значения из iterable, и из этих двух выбрать второе (или последнее) значение:
from heapq import nsmallest
def second_smallest(numbers):
return nsmallest(2, numbers)[-1]
Как и вышеприведенная реализация, это решение O (N); сохраняя вариант кучи, каждый шаг принимает время logK, но K является константой здесь (2)! Что бы вы ни делали, не используйте сортировку; который принимает время O (NlogN).
Цикл while (“пока”) позволяет выполнить
одну и ту же последовательность действий, пока проверяемое условие истинно.
Условие записывается до тела цикла и проверяется до выполнения тела цикла.
Как правило, цикл while используется, когда невозможно
определить точное значение количества проходов исполнения цикла.
Синтаксис цикла while в простейшем случае выглядит так:
while условие:
блок инструкций
При выполнении цикла while сначала проверяется условие.
Если оно ложно, то выполнение цикла прекращается и управление
передается на следующую инструкцию после тела цикла while.
Если условие истинно, то выполняется инструкция, после чего условие
проверяется снова и снова выполняется инструкция.
Так продолжается до тех пор, пока условие будет истинно.
Как только условие станет ложно, работа цикла завершится и
управление передастся следующей инструкции после цикла.
Например, следующий фрагмент программы напечатает на экран
всех целые числа, не превосходящие n:
a = 1
while a <= n:
print(a)
a += 1
Общая схема цикла while в данном случае для перебора
всех всех подходящих значений такая:
a = начальное значение
while а является подходящим числом:
обработать a
перейти к следующему a
Небольшой модификацией цикла добъемся того, чтобы выводились
все степени двойки, не превосходящие числа n:
a = 1
while a <= n:
print(a)
a *= 2
Вот еще один пример использования цикла while
для определения количества цифр натурального числа n:
n = int(input())
length = 0
while n > 0:
length += 1
n //= 10
В этом цикле мы отбрасываем по одной цифре числа, начиная с конца,
что эквивалентно целочисленному делению на 10 (n //= 10),
при этом считаем в переменной length, сколько раз это было сделано.
В языке Питон есть и другой способ решения этой задачи:
length = len(str(i)).
Инструкции управления циклом
После тела цикла можно написать слово else:
и после него блок операций, который будет
выполнен один раз после окончания цикла, когда проверяемое
условие станет неверно:
i = 1
while i <= 10:
print(i)
i += 1
else:
print('Цикл окончен, i =', i)
Казалось бы, никакого смысла в этом нет, ведь эту же инструкцию можно
просто написать после окончания цикла. Смысл появляется только
вместе с инструкцией break, использование которой внутри цикла
приводит к немедленному прекращению цикла, и при этом не исполняется ветка
else. Разумеется, инструкцию break осмыленно
вызывать только из инструкции if, то есть она должна выполняться
только при выполнении какого-то особенного условия.
Другая инструкция управления циклом —
continue (продолжение цикла). Если эта инструкция
встречается где-то посередине цикла, то пропускаются все оставшиеся
инструкции до конца цикла, и исполнение цикла продолжается
со следующей итерации.
Инструкции break, continue и ветка
else: можно использовать и внутри цикла for.
Тем не менее, увлечение инструкциями break и continue
не поощряется, если можно обойтись без их использования. Вот типичный пример
плохого использования инструкции break.
while True:
length += 1
n //= 10
if n == 0:
break
Упражнения
A: Список квадратов
По данному целому числу N распечатайте все квадраты натуральных чисел,
не превосходящие N, в порядке возрастания.
| Ввод | Вывод |
|---|---|
50 |
1 4 9 16 25 36 49 |
B: Список факториалов
По данному числу N распечатайте все факториалы, не превосходящие N, в порядке возрастания.
| Ввод | Вывод |
|---|---|
24 |
1 2 6 24 |
С: Минимальный делитель
Дано целое число, не меньшее 2. Выведите его наименьший натуральный делитель, отличный от 1.
В этой задаче нельзя использовать инструкцию if.
| Ввод | Вывод |
|---|---|
15 |
3 |
D: Двоичный логарифм
По данному натуральному числу (N) выведите такое наименьшее целое
число (k), что (2^kge N).
В этой задаче нельзя использовать инструкцию if.
В этой задаче нельзя использовать операцию возведения в степень.
| Ввод | Вывод |
|---|---|
7 |
3 |
E: Точная степень двойки
Дано натуральное число N. Выведите слово YES, если число N является
точной степенью двойки, или слово NO в противном случае.
Операцией возведения в степень пользоваться нельзя!
Инструкция if должна быть после цикла.
| Ввод | Вывод |
|---|---|
8 |
YES |
3 |
NO |
F: Утренняя пробежка
В первый день спортсмен пробежал (x) километров,
а затем он каждый день увеличивал пробег на 10% от предыдущего значения.
По данному числу (y) определите номер дня, на который пробег спортсмена составит
не менее (y) километров.
Программа получает на вход действительные числа (x) и (y) и должна вывести одно натуральное
число.
Названия (x) и (y) используются здесь для удобства
обозначения. Называть переменные буквами (x) и (y) нельзя.
| Ввод | Вывод |
|---|---|
10 |
9 |
G: Банковские проценты
Вклад в банке составляет (x) рублей. Ежегодно он увеличивается на (p) процентов,
после чего дробная часть копеек отбрасывается. Определите, через сколько лет вклад составит не менее (y) рублей.
Программа получает на вход три натуральных числа: (x), (p), (y) и должна вывести одно целое число.
| Ввод | Вывод |
|---|---|
100 |
8 |
H: Длина последовательности
Программа получает на вход последовательность целых неотрицательных чисел,
каждое число записано в отдельной строке. Последовательность завершается числом
0, при считывании которого программа должна закончить свою работу и вывести
количество членов последовательности (не считая завершающего числа 0).
Числа, следующие за числом 0, считывать не нужно.
| Ввод | Вывод |
|---|---|
1 |
3 |
I: Сумма последовательности
Определите сумму всех элементов последовательности, завершающейся числом 0.
| Ввод | Вывод |
|---|---|
1 |
17 |
J: Среднее значение последовательности
Определите среднее значение всех элементов последовательности, завершающейся числом 0.
Гарантируется, что в последовательности есть хотя бы один элемент
(кроме завершающего числа 0).
| Ввод | Вывод |
|---|---|
1 |
5.666666666666667 |
K: Количество четных элементов последовательности
Определите количество четных элементов в последовательности, завершающейся числом 0.
| Ввод | Вывод |
|---|---|
2 |
2 |
L: Максимум последовательности
Последовательность состоит из натуральных чисел и завершается числом 0.
Определите значение наибольшего элемента последовательности.
Гарантируется, что в последовательности есть хотя бы один элемент
(кроме завершающего числа 0).
| Ввод | Вывод |
|---|---|
1 |
9 |
M: Количество элементов, которые больше предыдущего элемента последовательности
Последовательность состоит из натуральных чисел и завершается числом 0.
Определите, сколько элементов этой последовательности больше предыдущего элемента.
| Ввод | Вывод |
|---|---|
1 |
2 |
N: Второй максимум
Последовательность состоит из различных
натуральных чисел и завершается числом 0.
Определите значение второго по величине элемента в этой последовательности.
Гарантируется, что в последовательности есть хотя бы два элемента
(кроме завершающего числа 0).
| Ввод | Вывод |
|---|---|
1 |
7 |
O: Второй минимум
Последовательность состоит из
натуральных чисел не превосходящих (10^9) и завершается числом 0.
Определите значение второго минимального по величине элемента
в этой последовательности, то есть элемента,
который будет наименьшим, если из последовательности удалить наименьший элемент.
Последнее число 0 не учитывается. Гарантируется, что в последовательности есть хотя бы два элемента
(кроме завершающего числа 0).
Для удобства решения можно использовать тот факт, что все элементы
последовательности не превосходят (10^9).
| Ввод | Вывод |
|---|---|
1 |
7 |
1 |
1 |
P: Количество элементов, равных максимуму
Последовательность состоит из
натуральных чисел и завершается числом 0.
Определите, какое количество элементов этой последовательности,
равны ее наибольшему элементу.
Гарантируется, что в последовательности есть хотя бы один элемент
(кроме завершающего числа 0).
| Ввод | Вывод |
|---|---|
1 |
1 |
1 |
2 |
Q: Сумма последовательности — 2
Найдите сумму последовательности натуральных чисел, если признаком окончания конца последовательности
является два подряд идущих числа 0.
| Ввод | Вывод |
|---|---|
1 |
17 |
R: Числа Фибоначчи
Последовательность Фибоначчи определяется так:
[
varphi_0=0, varphi_1=1, …, varphi_{n}=varphi_{n-1}+varphi_{n-2}.
]
По данному числу (nge 1) определите (n)-е число Фибоначчи
(varphi_n).
| Ввод | Вывод |
|---|---|
6 |
8 |
S: Номер числа Фибоначчи
Дано натуральное число (Age 2). Определите, каким по счету числом Фибоначчи
оно является, то есть выведите такое число (n), что (varphi_n=A).
Если (А) не является числом Фибоначчи, выведите число -1.
| Ввод | Вывод |
|---|---|
8 |
6 |
10 |
-1 |
T: Исполнитель “Раздвоитель”
Исполнитель “Раздвоитель” преобразует натуральные числа.
У него есть две команды: “Вычесть 1” и “Разделить на 2”,
первая команда уменьшает число на 1, вторая команда уменьшает число в два раза, если оно чётное,
иначе происходит ошибка.
Дано два натуральных числа A и B (A>B). Напишите алгоритм для Развоителя, который преобразует
число A в число B и при этом содержит минимальное число команд. Команды алгоритма нужно выводить по
одной в строке, первая команда обозначается, как -1, вторая команда как :2.
| Ввод | Вывод |
|---|---|
179 |
-1 |
U: Контрольная работа
9Б2 класс написал контрольную работу. В результате ровно A% учащихся получили 5,
ровно B% — 4, ровно C% — 3, а остальные D% написали её на 2.
Какое минимальное количество школьников должно быть в классе для того, чтобы могли получиться такие результаты?
Вводятся 4 целых числа от 0 до 100 — (A), (B), (C), (D) ((A + B + C + D = 100)).
| Ввод | Вывод |
|---|---|
40 |
20 |
V: Максимальное число идущих подряд одинаковых элементов
Дана последовательность натуральных чисел, завершающаяся числом 0. Определите,
какое наибольшее число подряд идущих элементов этой последовательности
равны друг другу.
| Ввод | Вывод |
|---|---|
1 |
2 |
W: Максимальная длина монотонного фрагмента последовательности
Дана последовательность натуральных чисел, завершающаяся число 0.
Определите наибольшую длину монотонного фрагмента последовательности
(то есть такого фрагмента, где все элементы либо больше предыдущего,
либо меньше).
| Ввод | Вывод |
|---|---|
1 |
2 |
X: Количество локальных максимумов последовательности
Элемент последовательности называется локальным максимумом,
если он строго больше предыдущего и последующего элемента последовательности.
Первый и последний элемент последовательности не являются локальными максимумами.
Дана последовательность натуральных чисел, завершающаяся числом 0. Определите количество строгих
локальных максимумов в этой последовательности.
| Ввод | Вывод |
|---|---|
1 |
2 |
Y: Наименьшее расстояние между двумя строгими локальными максимумами
Определите наименьшее расстояние между двумя локальными максимумами
последовательности натуральных чисел, завершающейся числом 0. Если в последовательности
нет двух локальных максимумов, выведите число 0.
| Ввод | Вывод |
|---|---|
1 |
2 |
1 |
0 |
Z: Стандартное отклонение
Дана последовательность натуральных чисел (x_1), (x_2), …, (x_n).
Стандартным отклонением называется величина
[
sigma = sqrt{frac{(x_1-s)^2+(x_2-s)^2+ldots+(x_n-s)^2}{n-1}}
]
где (s=frac{x_1+x_2+ldots+x_n}{n}) — среднее арифметическое последовательности.
Определите стандартное отклонение для данной последовательности натуральных чисел,
завершающейся числом 0.
Гарантируется, что в последовательности есть хотя бы два элемента
(кроме завершающего числа 0).
| Ввод | Вывод |
|---|---|
1 |
4.16333199893 |
ZZ: Самое частое число в последовательности
Последовательность состоит из натуральных чисел, причем
какое-то из чисел составляет более половины от общего числа
членов последовательности. Найдите это число.
Программа должна использовать (O(1)) памяти, то есть нельзя
сохранять неограниченное количество элементов последовательности
в памяти.
| Ввод | Вывод |
|---|---|
4 |
6 |