с такой задачей. Третий день бьюсь. Собрать многоугольник
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 2 секунды
Ограничение по памяти: 512 мебибайт
У вас есть n палок целой длины. Требуется выбрать из них наименьшее возможное количество палок так, чтобы из выбранных палок можно было составить строго выпуклый
многоугольник, либо определить, что из имеющихся палок составить строго выпуклый многоугольник невозможно.
Формат входных данных
В первой строке дано целое число n — количество палок (3 <= n <= 10^5). Во второй строке даны n целых чисел a1, a2, . . . , an, разделённые пробелами — длины палок (1 <= ai <= 10^9).
Формат выходных данных
Выведите наименьшее количество сторон в строго выпуклом многоугольнике, который можно составить из имеющихся палок. Ecли составить строго выпуклый многоугольник невозможно, выведите «-1» (без кавычек).
Система оценки
Тесты к этой задаче состоят из трёх групп. за каждую группу ставятся только при прохождении всех тестов, подходящих под ограничения этой группы. Во всех тестах первой группы 3 <= n <= 4. За прохождение первой группы можно получить
В тестах второй группы 3 <= n <= 15. За вторую группу можно получить ещё На тесты третьей группы не накладывается никаких дополнительных ограничений, то есть в ней 3 <= n <= 10^5. За неё можно получить оставшиеся
Примеры
стандартный ввод стандартный вывод
4. . . . . . . . . . . . . . . . 4
1 2 4 6
4. . . . . . . . . . . . . . . . -1
7 4 1 2
4. . . . . . . . . . . . . . . . 3
4 2 5 1
3. . . . . . . . . . . . . . . . -1
1 2 1
4. . . . . . . . . . . . . . . . 3
1 1 1 100
Пояснения к примерам
В первом примере строго выпуклый многоугольник можно составить, только если использовать все имеющиеся палки.
Во втором примере строго выпуклый многоугольник составить невозможно. В третьем примере можно составить строго выпуклый многоугольник из всех четырёх палок, но он не наименьший, так как из палок с длинами 4, 2 и 5 можно составить невырожденный треугольник. Поэтому ответ для третьего примера равен 3.
В четвёртом примере всего три палки, и они не образуют невырожденный треугольник, поэтому ответ равен -1. В пятом примере нельзя построить строго выпуклый многоугольник из всех четырёх палок, но можно из трёх палок длины 1, поэтому ответ равен 3.
Вот моё решение:
n=int(input())
m=sorted(input().split())
b=0
b2=0
c=0
d=0
q1=1
q2=1
p=[]
for i in range (0, n-1):
b += int(m[i])
b2+= 1
for i in range(0,len(m)-1):
p.append(m[i])
if int(max(m))>=b and b2<=n-1:
p=[]
p.extend(m)
b=-1
print(b)
if q1==1 and (b!=-1 or b2>2):
while c<=int(max(p)):
c+=int(m[d])
d+=1
q1+=1
if q2==1 and (b!=-1 or b2>2):
c=0
if len(p)
d=2
else:
d=1
while c<=int(max(m)):
c+=int(m[-d])
d+=1
q2+=1
if q1n-1):
print(q1)
elif q1>=q2 and (b!=-1 or b2>n-1):
print(q2)
print(q1, q2, m, c, b2, b, p)
(последняя строка нужна для того, чтобы видеть, как изменяются переменные, в решении она не участвует)
По какой-то причине у меня то 4. . . 1 2 4 7 выдаёт 3 вместо -1, то 4. . . 1 1 1 100 пишет -1 вместо 3. (Указанный выше вариант - это второй случай) Проблема в том, что у меня неправильный ответ пишется либо когда b равен наибольшему элементу, либо когда b меньше него (это зависит от варианта, собственно поэтому там есть p, но он не используется)
Пояснения:
n - даётся по условию, кол-во палок
m - даётся по условию, длины палок, поступает отсортированным по увеличению для удобства
b - от его состояния зависит, будет выведен -1 или решение пойдёт дальше
b2 - нужен, чтобы расчёт q1 и q2 нормально считались, я пробовал без b2, получался бред полный
с - нужен для расчёта ответа, после расчёта q1 переходит в изначальное состояние
d - нужен для расчёта с, означает индекс прибавляемого элемента
q1 и q2 - два варианта ответа, q1 считается с начала списка, q2 с конца, в ответ идёт меньший из них
p - дополнительный список (тот же m, только без самого большого элемента)
это процесс распределения всех элементов массива в определенном порядке. Очень часто это бывает полезным. Например, в вашем почтовом ящике электронные письма отображаются в зависимости от времени получения; новые письма считаются более релевантными, чем те, которые вы получили полчаса, час, два или день назад; когда вы переходите в свой список контактов, имена обычно находятся в алфавитном порядке, потому что так легче что-то найти. Все эти случаи включают в себя сортировку данных перед их фактическим выводом
Объяснение:
Как работает сортировка?
Сортировка данных может сделать поиск внутри массива более эффективным не только для людей, но и для компьютеров. Например, рассмотрим случай, когда нам нужно узнать, отображается ли определенное имя в списке имен. Чтобы это узнать, нужно проверить каждый элемент массива на соответствие нашему значению. Поиск в массиве с множеством элементов может оказаться слишком неэффективным (затратным).
Однако, предположим, что наш массив с именами отсортирован в алфавитном порядке. Тогда наш поиск начинается с первой буквы нашего значения и заканчивается буквой, которая идет следующей по алфавиту. В таком случае, если мы дошли до этой буквы и не нашли имя, то точно знаем, что оно не находится в остальной части массива, так как в алфавитном порядке нашу букву мы уже !
Не секрет, что есть алгоритмы поиска внутри отсортированных массивов и получше. Применяя простой алгоритм, мы можем искать определенный элемент в отсортированном массиве, содержащем 1 000 000 элементов, используя всего лишь 20 сравнений! Недостатком, конечно же, является то, что сортировка массива с таким огромным количеством элементов — дело сравнительно затратное, и оно точно не выполняется ради одного поискового запроса.
В некоторых случаях сортировка массива делает поиск ненужным. Например, мы ищем наилучший результат прохождения теста среди студентов. Если массив не отсортирован, то нам придется просмотреть каждый элемент массива, чтобы найти наивысшую оценку. Если же массив отсортирован, то наивысшая оценка будет находиться либо на первой позиции, либо на последней (в зависимости от метода сортировки массива: в порядке возрастания или в порядке убывания), поэтому нам не нужно искать вообще!
Сортировка обычно выполняется путем повторного сравнения пар элементов массива и замены значений, если они отвечают заданным критериям. Порядок, в котором эти элементы сравниваются, зависит от того, какой алгоритм сортировки используется. Критерии определяют, как будет сортироваться массив (например, в порядке возрастания или в порядке убывания).
Чтобы поменять два элемента местами, мы можем использовать функцию std::swap() из Стандартной библиотеки C++, которая определена в заголовочном файле algorithm. В C++11 функция std::swap() была перенесена в заголовочный файл utility:
#include <iostream>
#include <algorithm> // для std::swap. В C++11 используйте заголовок <utility>
int main()
{
int a = 3;
int b = 5;
std::cout << "Before swap: a = " << a << ", b = " << b << '\n';
std::swap(a, b); // меняем местами значения переменных a и b
std::cout << "After swap: a = " << a << ", b = " << b << '\n';
}
1
2
3
4
5
6
7
8
9
10
11
#include <iostream>
#include <algorithm> // для std::swap. В C++11 используйте заголовок <utility>
int main()
{
int a = 3;
int b = 5;
std::cout << "Before swap: a = " << a << ", b = " << b << '\n';
std::swap(a, b); // меняем местами значения переменных a и b
std::cout << "After swap: a = " << a << ", b = " << b << '\n';
}
Результат выполнения программы:
Before swap: a = 3, b = 5
After swap: a = 5, b = 3
После выполнения операции замены значения переменных a и b поменялись местами.
import turtle
from math import tan, sqrt, pi
def prepare(x, y, color):
turtle.penup()
turtle.goto(x, y)
turtle.pendown()
turtle.color(color)
turtle.begin_fill()
def draw_polygon(num_sides, side_length):
angle = 360.0 / num_sides
for i in range(num_sides):
turtle.forward(side_length)
turtle.right(angle)
turtle.end_fill()
def calc_s(num_sides, side_length):
return num_sides * side_length ** 2 / (4 * tan(pi/num_sides))
def calc_side(square):
return sqrt(4 * square * tan(pi/num_sides) / num_sides)
turtle.hideturtle()
turtle.speed(10)
colors = ['red', 'green', 'blue', 'cyan', 'magenta', 'black', 'yellow', 'pink', 'brown']
xcoords = [0, 150, -150, 150, -150, 270, -270, 270, -270]
ycoords = [0, 150, -150, -150, 150, 270, -270, -270, 270]
squares = []
numsides = []
for i in range(9):
num_sides = i + 3
square = round(calc_s(num_sides, 100), 2)
side_length = round(calc_side(10000), 3)
squares.append(square)
numsides.append(num_sides)
print("Углов:", num_sides, "была площадь:", square, "стала длина грани:", side_length,
"изменение в", round(side_length/100, 2), "раз")
prepare(xcoords[i], ycoords[i], colors[i])
draw_polygon(num_sides, side_length)
turtle.exitonclick()
print("Список количество углов:", numsides, end="")
print("Список площади:", squares)
Объяснение: