М
Молодежь
К
Компьютеры-и-электроника
Д
Дом-и-сад
С
Стиль-и-уход-за-собой
П
Праздники-и-традиции
Т
Транспорт
П
Путешествия
С
Семейная-жизнь
Ф
Философия-и-религия
Б
Без категории
М
Мир-работы
Х
Хобби-и-рукоделие
И
Искусство-и-развлечения
В
Взаимоотношения
З
Здоровье
К
Кулинария-и-гостеприимство
Ф
Финансы-и-бизнес
П
Питомцы-и-животные
О
Образование
О
Образование-и-коммуникации
mzhenyak1999
mzhenyak1999
18.10.2022 01:39 •  Информатика

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

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

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

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

👇
Открыть все ответы
Ответ:
topghalya228
topghalya228
18.10.2022
1) F=Av(¬A&B)
По закону дистрибутивности раскроем скобки
(Av¬A)&(AvB)
Av¬A = 1, значит остаётся AvB

2) F =A&(¬AvB)
По тому же закону раскрываем скобки
(A&¬A)v(A&B)
A&¬A = 0, значит остаётся A&B

3. (AvB)&(¬BvA)&(¬CvB)
По закону склеивания (AvB)&(¬BvA) = A , получается, что выражение принимает вид
A&(¬CvB)
Можно раскрыть скобки, получим
A&¬C v A&B

4) F =(1v(AvB))v((AC)&1) 
Скобка (1v(AvB)) = 1, так как 1 v ЧТОУГОДНО = 1
Получаем выражение
1v((AC)&1) = 1, так как 1 v ЧТОУГОДНО = 1
ответ 1
4,5(32 оценок)
Ответ:
vika2082
vika2082
18.10.2022
Program pr;
uses crt;

Var mas:array[1..1000, 1..1000] of integer;
N,M,i,j,k:integer;

Begin
Writeln('Введите размер матрицы N*M');
Write('N = ');
readln(N);
Write('M = ');
readln(M);

if (M>1000) or (N>1000) or (M<1) or (N<1)
then  
Writeln('Ошибка, указанные значения выходят за пределы матрицы')   else   
        Begin      
 Writeln('Введите элементы матрицы');      

k:=0; 
 for i:=1 to N do     
  for j:=1 to M do     
    Begin     
      readln(mas[i,j]);       
      if (mas[i,j] mod 2 = 0) then k:=k+1;     
    end; 
  
    Writeln();   
    Writeln('Исходная матрица');
   
   for i:=1 to N do   
     Begin     
       for j:=1 to M do     
          Begin     
             Write(mas[i,j], ' ')     
           end;     
      Writeln();   
     end;         

Writeln();   
Writeln('Количество четных элементов = ',k);      
 end;

readln;
end.
4,5(85 оценок)
Это интересно:
Новые ответы от MOGZ: Информатика
logo
Вход Регистрация
Что ты хочешь узнать?
Спроси Mozg
Открыть лучший ответ