Ustawieniem żołnierzy

0

Cześć, mam takie zadanie:
Żołnierze powinni ustawić się na planie kwadratu, tak, żeby każdych dwóch żołnierzy mieszkających w tym samym budynku stało na apelu obok siebie, czyli w tym samym rzędzie kwadratu.
Ponadto, żołnierze z poszczególnych budynków muszą stać po kolei, tzn. poczynając od pierwszego rzędu:
pierwszy budynek, drugi budynek, itd. znajdź najmniejszą długość boku takiego kwadratu.
Liczba całkowita n (1 ≤ n ≤ 500.000), oznacza liczbę budynków, w których mieszkają żołnierze, liczba żołnierzy w każdym budynku jest dodatnia i nie większa niż 10^9
Mój kod:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    long long n,maksk,mink,pom,i,j,D;
    cin>>n;
    long long t[n+1];
    long long s;
    bool dosc;
    maksk=0;
    s=0;
    for(i=1;i<=n;i++){
        cin>>t[i];
        if(maksk<t[i]) maksk=t[i];
        s+=t[i];
    }
    //wyznaczam min rzedow - pierwiastek z sumy lub max ilosc osob - zaokr.w gore
    pom=ceil(sqrt(s));
    if(pom>maksk)mink=pom;
    else mink=maksk;
    //wyznaczam max rzedow - pierwiastek z ilosci domow * max ilosc osob - zaokr.w gore
    pom=ceil(sqrt(n*maksk));
    if(pom>maksk) maksk=pom;
 
    if(maksk==mink) cout<<maksk;
    else //sprawdzam czy wszyscy sie zmieszcza w min ilosci rzedow a jak nie to mink++ az do maksk
       do{
          dosc=false;
          D=n;
          i=1;
          while(i<n && !dosc)
          {
              pom=mink-t[i];
              j=i+1;
              while(pom>=0 && !dosc && j<=n)
                 if(pom>=t[j]){
                    pom-=t[j];
                    D--;
                    j++;
                    if(D<=mink) dosc=true;
                 }
                 else{
                    i=j;
                    break;
                 }
          }
          if(dosc){
             cout<<mink;
             break;
          }
          else{
             mink++;
             if(mink==maksk){
                cout<<mink;
                break;
             }
          }
        }while(!dosc);
 
}

Program działa, sprawdzałem czy nie wywala się na maksymalnych liczbach w zadaniu ( wziąłem sumę =10^9 * 500.000), ale na kilku testach wychodzi mi błędny wynik...
1.jpg
Rozumiem przekroczenie limitu czasu, nad tym mogę popracować, ale nie ogarniam jakie dane można podać aby wyszła błędna odp.
Proszę o uwagi, ewentualnie może ktoś ma inny pomysł na rozwiązanie problemu, dzięki.

3

Kiedyś jak studenci nie mogli sobie poradzić z SPOJem to stawialo sie serwer http za pomoca np nc i do spoja wysylalo sie kod, ktory wysylal input na nasz serwer. Dostawalismy input z SPOJa i mozna bylo debugowac ;)

0

.

0
daniel1302 napisał(a):

Kiedyś jak studenci nie mogli sobie poradzić z SPOJem to stawialo sie serwer http za pomoca np nc i do spoja wysylalo sie kod, ktory wysylal input na nasz serwer. Dostawalismy input z SPOJa i mozna bylo debugowac ;)

możesz nieco więcej napisać na ten temat? netcat OK ale jak odpytać SPOJ szkolny?

0

To nie żaden SPOJ tylko kółko Staszica, to zadania mające na celu przygotowania do Olimpiady Informatycznej
https://ki.staszic.waw.pl/task.php?name=zol

0
Suchy702 napisał(a):

To nie żaden SPOJ tylko kółko Staszica, to zadania mające na celu przygotowania do Olimpiady Informatycznej
https://ki.staszic.waw.pl/task.php?name=zol

Generalnie treści zadań są w różnych miejscach w sieci, natomiast u nas to jest do zrobienia na ocenę semestralną wraz z innymi kilkoma zadaniami. Jest szkolny system do testowania i wyniki zamieściłem powyżej błąd WA + TLA
do żadnego kółka nie należę ;)

0

spróbuj rozwiązać to zadanie binary searchem

0
Suchy702 napisał(a):

spróbuj rozwiązać to zadanie binary searchem

a możesz rozwinąć czego mam szukać binary searchem? np dla n=3 i danych 4 1 1 będę mieć wynik =4 bo
A A A A
B * * *
C * * *


może to głupie pytanie ale nie bardzo wiem czego tu szukać binary searchem, chyba że źle rozumiem zadanie

1

binary search nie musi byc do posortwanych danych, w twoim przypadku byloby to

    min_sqr = maksymalna_wielkosc_domu;
    max_sqr = max(ilosc_domow, maksymalna_wielkosc_domu);
    while (min_sqr < max_sqr){
        int mid = (min_sqr + max_sqr) / 2;
        if (can_make_square(mid))
            max_sqr = mid;
        else 
            min_sqr = mid + 1;
    }

teraz musisz tylko napisac funkcje sprawdzajaca czy dla danej dlugosci kwadratu, mozna takowy kwadrat utworzyc

to twoje rozwiazanie tylko ze usprawnione

0

@Suchy702: Dzięki kolego, już poprawiłem, to była mała korekta bo i czasu dziś nie miałem ale błąd WA się nie pojawia, tylko w 4 testach program za wolny o 2s więc zrobię ten binary search i mam nadzieję że już będzie 100%
edit: gotowe, 100%, jeszcze raz dzięki za pomoc

1 użytkowników online, w tym zalogowanych: 0, gości: 1