Cześć,
Rozwiązuję to zadanie:
https://szkopul.edu.pl/problemset/problem/plwJuavOqAD9XxBqllCwJRK3/site/?key=statement
Kompletnie nie mam pojęcia co mogę zrobić z moim rozwiązaniem, które dostaje 80% pkt, aby było szybsze i przeszło wszystkie testy. Wygląda ono tak:
https://4programmers.net/Pastebin/14743
Jaka jest złożoność mojego algorytmu? Nie potrafię tego ocenić.
Proszę o wskazówki.
Z podstawowych rzeczy:
- Używaj statycznych tablic w takich zadaniach, nie przejmuj się z reguły pamięcią. Statyczna alokacja jest zdecydowanie szybsza.
- Jeśli już musisz użyć dynamicznej alokacji (jak
std::vector
) to użyjreserve
jeśli znasz wynikowy rozmiar. Pojedyncza alokacja będzie zdecydowanie szybsza niż to co masz teraz, które co jakiś czas musi realokować tablicę i kopiować wszystkie elementy.
Z pozostałych:
- Podziel kod na funkcje, to nie lata 80te by to spowalniało kod, a będzie się go zdecydowanie łatwiej czytało.
Co do algorytmu, to nie wgłębiałem się mocno, ale zapewne zastosowanie będą tutaj miały liczby trójkątne.
Da się zrobić z kosztem pamięciowym O(1)
#include <iostream>
using namespace std;
int main()
{
int n,s;
cin>>n>>s;
int minmax=(n*n-n)>>1;
if((-minmax>s)||(s>minmax)||((minmax^s)&1)) cout<<"NIE"<<endl;
else
{
cout<<0<<endl;
for(int delta=(minmax-s)>>1,v=0;--n;cout<<v<<endl)
{
int dec=(delta>=n);
if(dec) delta-=n;
v+=1-(dec<<1);
}
}
return 0;
}
https://ideone.com/gJoyhR
Tylko mam jedno pytanie do tego zadania ...
W sumie rozwiązań może być wiele, na przykład dla 8 4
rozwiązań jest tyle na ile sposobów można dostać liczbę:
14
jako sumę elementów 1,2,3,4,5,6,7,8
, np 8+6
lub 6+4+3+1
lub 5+4+3+2
Więc w sumie zadanie niewystarczająco sprecyzowane.
@hauleth: Dzięki za rady.
@_13th_Dragon: W zadaniach OI zawsze jest tak, że jeśli istnieje wiele odpowiedzi do zadania to można wypisać dowolną (przynajmniej nigdy się nie spotkałem z odmiennym przypadkiem). Mógłbym Cię prosić o opisanie pokrótce tego algorytmu? Nie rozumiem jak on działa.
Maksymalna liczba kiedy cały czas idziemy w górę i jest to suma ciągu arytmetycznego: (n*n-n)/2
-> minmax
Zauważ że:
- jak zmienimy ostatnią liczbę na idącą w dół zamiast w górę to suma nam spadnie o
2
- jak zmienimy przedostatnią liczbę na idącą w dół zamiast w górę (oczywiście dalej też będzie wszystko pozmieniać) suma nam spadnie o
4
- jak zmienimy
k-tą
od końca to suma nam spadnie ok*2
Natomiast sumę musimy zmniejszyć o:(n*n-n)/2-s
ja to dziele przez 2 ->delta
aby zmniejszać ok
a nie o2*k
Toint dec=(delta>=n);
decyduje czy idziemy w dół.