Spoj - Przekroczono limit czasu, Szachownica vs kwadraty

0

http://pl.spoj.com/problems/FR_07_06/ ---> link do zadania

https://ideone.com/7vUXWj ---> mój kod

Czy jeśli zrobie to jakoś rekurencją, jako funkcje jeszcze przed mainem, a w mainie tylko cout<<funkcja(n) (n to jakby ta dlugosc boku kwadratu), to będzie program szybszy?
Czy może jest na to zadanie jeszcze jakiś inny, prostszy sposób , którego nie zauważyłam?

0

1.Pisz po ludzku int i = 0 zamiast int i(0).
2.Nie składaj instrukcji w jedną linijkę - int n; cin>>n; rozbij na dwie, odrębne. Czytelność kodu ma ogromne znaczenie.
3.W jaki sposób rekurencja ma niby przyśpieszyć cokolwiek gdziekolwiek kiedykolwiek?
4.Tutaj jest obliczeń tyle, co kot napłakał, zatem bottleneck może siedzieć w prędkości, z jaką jesteś w stanie wczytywać dane, a nie w obliczeniach. Choć i obliczenia można w Twoim przypadku zoptymalizować.

0

Na temat odpowiadaj w postach.

cpp spoj fast input w Google.

0

q może być 10^6, n również, czyli Twój program może działać w czasie C * 10^12, co jest zdecydowanie za wolno. Wydaje mi się, że istnieje sprytny wzór, którego można używać zamiast lecieć w pętli od 1 do n, ale w tej chwili nie przychodzi mi do głowy.

1

Przypadłość SPOJ-a zadania gdzie operacje IO są wąskim gardłem.

#include <iostream>
using namespace std;

long long int f(int x)
{
    … … …
}

int main() {
    int t;
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> t;
    for(int i = 0; i < t; i++) {
       int x;
       cin >> x;
       cout << f(x) << '\n';
    }
   cout << flush;
   return 0;
}

Poza tym polecam skorzystać z http://www.wolframalpha.com/

0

i na dodatek maksymalny wynik to: 333333833333500000 (~3.3e17)

2

Proste.
f(n) = n*(n + 1)*(2*n + 1)/6

0

Szczerze mówiąc to nie bardzo rozumiem twój kod.
Przed mainem tam gdzie są kropki mam jednak napisać funkcję,a potem odwołać się do niej w programie, o to chodziło, tak?
ios::sync_with_stdio(false); ---> tutaj wyłączyłeś synchronizację wejścia i wyjścia? Widziałam coś bardzo podobnego ostatnio (ios_base::sync_with_stdio(0) ) gdy też miałam problem z szybkością programu, ale nie bardzo wiem jak to działa w praktyce, co się zmienia (oprócz tej szybkości właśnie) w programie gdy jest wyłączona synchronizacja?
cin.tie(NULL); do tego znalazłam nawet cokolwiek po polsku Wymuszanie wysokiej wydajności iostream ale (na razie ) i tak nic z tego nie rozumiem

0
  • ios::sync_with_stdio(false) - wyłącz synchronizację z API "C"
  • cin.tie(NULL) - rozłącza cout od cin. To połącznie powoduje, że każda operacja odczytania cin jest poprzedzona flush na cout. Generalnie chodzi o to, że jeśli masz interaktywną drugą stronę, to przed odczytem danych trzeba opróżnić bufory (by użytkownikowi pokazać co ma być wpisane, albo by serwer dostał pełen komunikat, na którą trzeba otrzymać odpowiedź).
  • każdy flush powoduje utratę na szybkości operacji zapisu, dlatego endl zastąpiłem '\n' oraz dlatego poprzedni punkt jest ważny.
0

Przeczytaj mój post, potem post @reptile333 lub @nalik i masz rozwiązanie.
W tym zadaniu wczytywanie miliona liczb nie powinno być problemem.

0

Dziękuję bardzo za pomoc :3

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