79272197114

08.04.2020 16:08

Информатика

Есть ответ 👍

с такой задачей. Третий день бьюсь. Собрать многоугольник

Имя входного файла: стандартный ввод

Имя выходного файла: стандартный вывод

Ограничение по времени: 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, только без самого большого элемента)