Problem z algorytmem

Dzień dobry !
Dostałem do wykonania następujące zadanie:
"Adek chce zbudować piaskownice z czterech równych desek. Niestety podczas kupowania nie zwrócił uwagi na długość desek. Na szczęście jeśli Adek potrzebuje może podzielić posiadane deski na mniejsze części. Na przykład : 15,5,2,4,7,8,4 wtedy może 15 podzielić na 3 części i uzyska 5,5,5,5,2,4,7,8. (ale też na 5 i uzyska pięć 3). Każda deska nie może być ułamkiem.
Napisz program który wczyta długości desek i określi największe pole piaskownicy jakie można uzyskać przy takich deskach"
**Wejście:
**
N (1<= N <= 1 000 000)
ciąg N liczb naturalnych określających długości desek zakupionych przez Antka.
**Wyjście:
**
Pole powierzchni piaskownicy gdy nie można jej zbudować z posiadanych desek należy wypisać 0

Przykład:
**Wejście:
**
7
4 10 3 4 2 1 2
**Wyjście:
**
16
**Wejście:
**
3
7 13 36
**Wyjście:
**
144

Bardzo proszę o pomoc ponieważ nie wiem jak zabrać się do tego zadania.
Z góry dziękuje. :)

Rozważmy ciąg s = [4, 10, 3, 4, 2, 1, 2]. Jego suma jest równa 26. Maksymalne pole jakie można uzyskać przy takim obwodzie uzyskamy z kwadratu o krawędzi równej 26/4 = 6.5. Iterujmy więc w dół od 6, za każdym razem sprawdzając czy z posiadanych desek można uzyskać 4 deski tej długości. Można to sprawdzić dzieląc wszystkie długości przez tę liczbę. Dla kodu

s = [4, 10, 3, 4, 2, 1, 2]
for i in range(sum(s)/4, 0, -1):
    print(i, [j/i for j in s])

Mamy

$ python test.py 
(6, [0, 1, 0, 0, 0, 0, 0])
(5, [0, 2, 0, 0, 0, 0, 0])
(4, [1, 2, 0, 1, 0, 0, 0])
(3, [1, 3, 1, 1, 0, 0, 0])
(2, [2, 5, 1, 2, 1, 0, 1])
(1, [4, 10, 3, 4, 2, 1, 2])

Widzimy, że długość 4 można uzyskać z deski pierwszej, czwartej i rozpiłowując drugą, matematycznie - suma takiej listy jest większa lub równa od cztery. Cały kod:

import sys

s = [4, 10, 3, 4, 2, 1, 2]
for i in range(sum(s)/4, 0, -1):
    if sum([j/i for j in s]) >= 4:
        print(i**2)
        sys.exit(0)
# nie znaleziono
print(0)

Spearhead napisał(a):

Rozważmy ciąg s = [4, 10, 3, 4, 2, 1, 2]. Jego suma jest równa 26. Maksymalne pole jakie można uzyskać przy takim obwodzie uzyskamy z kwadratu o krawędzi równej 26/4 = 6.5. Iterujmy więc w dół od 6, za każdym razem sprawdzając czy z posiadanych desek można uzyskać 4 deski tej długości. Można to sprawdzić dzieląc wszystkie długości przez tę liczbę. Dla kodu

Kopiuj

s = [4, 10, 3, 4, 2, 1, 2]
for i in range(sum(s)/4, 0, -1):
    print(i, [j/i for j in s])

Mamy

Kopiuj

$ python test.py 
(6, [0, 1, 0, 0, 0, 0, 0])
(5, [0, 2, 0, 0, 0, 0, 0])
(4, [1, 2, 0, 1, 0, 0, 0])
(3, [1, 3, 1, 1, 0, 0, 0])
(2, [2, 5, 1, 2, 1, 0, 1])
(1, [4, 10, 3, 4, 2, 1, 2])

Widzimy, że długość 4 można uzyskać z deski pierwszej, czwartej i rozpiłowując drugą, matematycznie - suma takiej listy jest większa lub równa od cztery. Cały kod:

Kopiuj

import sys

s = [4, 10, 3, 4, 2, 1, 2]
for i in range(sum(s)/4, 0, -1):
    if sum([j/i for j in s]) >= 4:
        print(i**2)
        sys.exit(0)
# nie znaleziono
print(0)

Bardzo dziękuje za algorytm przepisze na c++ i mam nadzieje że zadziała :)

Spearhead napisał(a):

Rozważmy ciąg s = [4, 10, 3, 4, 2, 1, 2]. Jego suma jest równa 26. Maksymalne pole jakie można uzyskać przy takim obwodzie uzyskamy z kwadratu o krawędzi równej 26/4 = 6.5. Iterujmy więc w dół od 6, za każdym razem sprawdzając czy z posiadanych desek można uzyskać 4 deski tej długości. Można to sprawdzić dzieląc wszystkie długości przez tę liczbę. Dla kodu

Kopiuj

s = [4, 10, 3, 4, 2, 1, 2]
for i in range(sum(s)/4, 0, -1):
    print(i, [j/i for j in s])

Mamy

Kopiuj

$ python test.py 
(6, [0, 1, 0, 0, 0, 0, 0])
(5, [0, 2, 0, 0, 0, 0, 0])
(4, [1, 2, 0, 1, 0, 0, 0])
(3, [1, 3, 1, 1, 0, 0, 0])
(2, [2, 5, 1, 2, 1, 0, 1])
(1, [4, 10, 3, 4, 2, 1, 2])

Widzimy, że długość 4 można uzyskać z deski pierwszej, czwartej i rozpiłowując drugą, matematycznie - suma takiej listy jest większa lub równa od cztery. Cały kod:

Kopiuj

import sys

s = [4, 10, 3, 4, 2, 1, 2]
for i in range(sum(s)/4, 0, -1):
    if sum([j/i for j in s]) >= 4:
        print(i**2)
        sys.exit(0)
# nie znaleziono
print(0)

Podczas kompilowania kodu w pythonie występuje błąd
Traceback (most recent call last): File "main.py", line 4, in <module> for i in range(sum(s)/4, 0, -1): TypeError: 'float' object cannot be interpreted as an integer

#include <iostream>
#include <algorithm>

using namespace std;

long long czydeskitejdlugosci(int tabsize,long long tab[],long long a)
{
    int suma = 0;
    for(int i = 0; i<tabsize ;i++)
    {
        suma += tab[i]/a;
    }
    //cout << "SUM :";
    return suma;
}

long long sum(int tabsize, long long tab[])
{
    int x = 0;
    for(int i = 0; i<tabsize; i++)
    {
        x = x+ tab[i];
    }
    return x;
}

int main(int argc, char** argv)
{

    int n;
    cin >> n;
    long long s[n];
    for(int i=0; i<n; i++)
    {
        cin >> s[i];
    }
   if(s[0] == s[1] && s[1] == s[2] && s[2] == s[3])
   {
       cout << s[0] * s[0];
        return 0;
   }
    for(long long i = sum(n,s) / 4; i>0; i--)
    {
        if (czydeskitejdlugosci(n,s,i) >= 4)
        {
            cout << i * i;
            return 0;
        }



    }
    cout << 0;
    return 0;

}

Proszę tutaj przepisany program na c++
,a i nie wiem jak zmienić tytuł wątku

if(s[0] == s[1] && s[1] == s[2] && s[2] == s[3]) po co to?
Popatrz na przykładowe wejście: 4, 4, 4, 4, 5, 5, 5, 5.

Delor napisał(a):

if(s[0] == s[1] && s[1] == s[2] && s[2] == s[3]) po co to?
Popatrz na przykładowe wejście: 4, 4, 4, 4, 5, 5, 5, 5.

Przy np
4
1000000000 1000000000 1000000000 1000000000
program zwraca 0 zamiast 1000000000000000000
i nie wiem jak sobie inaczej z tym poradzić
I jest jeszcze jeden problem bo przy dużych danych wejściowych program nic nie zwraca.
Bardzo proszę o pomoc i z góry dziękuje :)

Nie mieścisz się w zakresie int (patrz: linia 19).