Da li bi neko mogao da mi kaze zasto ovo resenje daje tle/wa?
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
int n;
long double m;
cin >> n >> m;
long double prev;
cin >> prev;
for(int i = 1; i < n; i++)
{
long double c;
cin >> c;
if(prev > c)prev=c;
else m *= c/prev,prev=c;
}
cout << m;
return 0;
}
Pozdrav,Aleksa Miljkovic.
Zdravo Aleksa,
WA na nekoliko test primera dobijaš zbog preciznosti, to može da se reši linijom cout << fixed << setprecision(6); (ovo vidim da si i sam shvatio).
TLE na ostatku dobijaš zbog korišćenja cin/cout. Sa printf/scanf tvoj kod dobija 100 poena. Tačno je da ios_base::sync_with_stdio(false); čini da cin/cout bude bliži printf/scanf po performansama, ali u zadacima koji imaju mnogo ulaznih podataka (kao što je Struja) razlika je i dalje primetna.
Pozdrav
Postovani, kod mene nije takav slucaj, prinf/scanf traje 0.89s na vecem test primeru, dok desyncovani cin/cout traje samo oko 0.3s na istom test primeru. Da li je ovo inace tako na petlja graderu?
Zanimljivo, izgleda da je desyncovani cin brži kad se učitavaju int-ovi, a sporiji kad se učitavaju long double-ovi (kao u rešenju @aleksami). Ovo su ~ vremena na poslednjem primeru:
Verovatno je u ovom slučaju bolji savet “ne učitavati stvari kao realne brojeve kada nema potrebe za tim” (učitavanje cena struje kao celih brojeva prolazi i sa cin i sa scanf).
Zašto su ovako nelogični odnosi brzina cin/scanf nisam siguran, možda @ivan100sic zna?
Evo malo detaljniji prikaz performansi uobičajenih metoda učitavanja na najčešćim tipovima podataka. Koristio sam GCC 7.2.0 gde je target x86_64-linux-gnu. Koliko znam, na Petlji je isti kompajler a target je 64-bitni Windows (ne bi trebalo da je ogromna razlika). Fajl iz kojeg sam učitavao je bio smešten na direktorijumu koji je mountovan kao tmpfs, dakle, efektivno, direktno iz RAM memorije (da bi eliminisao uticaj diska). Fajl sadrži broj 10.000.000 u prvoj liniji a u narednih 10M linija različite pozitivne devetocifrene brojeve. Na izlaz sam ispisivao jedan red - sumu učitanih brojeva. Utvrdio sam da ovo sumiranje i ispis ne utiče skoro uopšte na vreme izvršenja programa.
cin, desync, float = 3.71s
cin, desync, double = 3.33s
cin, desync, long double = 3.83s
cin, desync, int = 1.52s
cin, desync, unsigned int = 1.39s
cin, desync, long long = 1.49s
cin, desync, unsigned long long = 1.52s
cin, float = 8.11s
cin, double = 7.59s
cin, long double = 8.13s
cin, int = 5.51s
cin, unsigned int = 5.44s
cin, long long = 5.55s
cin, unsigned long long = 5.49s
scanf, float = 2.04s
scanf, double = 1.99s
scanf, long double = 2.45s
scanf, int = 1.54s
scanf, unsigned int = 1.51s
scanf, long long = 1.53s
scanf, unsigned long long = 1.54s
Kao što se može videti desyncovani cin je generalno sporiji od scanf za učitavanje floating-point brojeva a jednako je brz za učitavanje celih. Interesantno da je učitavanje unsigned celih brojeva za nijansu brže od signed brojeva.
Pod “desyncovanim cinom” mislim na:
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cerr.tie(nullptr);
Ova razlika se može objasniti različitim implementacijama iostream i stdio biblioteka, naime, dok je učitavanje celih brojeva algoritamski veoma prosto - treba učitati znak, ako ga ima, a zatim niz cifara i množiti ceo broj sa 10 - nema mnogo prostora za različite implementacije, što se vidi i na osnovu poređenja brzina učitavanja, učitavanje floating-point brojeva je skroz druga priča - mnogo je komplikovanije i može da se izvede na mnogo veći broj načina. Verovatno je C++ implementacija (cin) složenija, u smislu da na drugačiji način obrađuje izuzetne situacije, npr. postavljanjem internih flaggova u istream objektu.
Što se tiče velike razlike između cin i scanf na Petlji (koja kod mene na linuxu praktično i ne postoji), verovatno je “problem” to što Windows implementacija scanf funkcije nije jako efikasna. Verovatno desyncovani cin na pametniji način zove sistemske funkcije za dobavljanje podataka nego što to čini scanf. A možda i to što sam koristio tmpfs? Ko će ga znati…
Na kraju krajeva konačno objašnjenje možemo dobiti samo ako znamo implementacije ovih funkcija.
I ja sam imao isti problem, imao sam 50 poena na struji, zbog koriscenja syncovanog cina. Manje su mi bitni poeni koje sam izgubio, vise me zanima da li je moguce znati na takmicenjima koja nemaju full feedback koju vrstu inputa i outputa koristiti?
Onaj koji najbolje radi na Petlji, dakle scanf je najsigurnija varijanta. Za učitavanje nizova slova (tj. stringova) koji su odvojeni od ostalih tokena whitespace-om (tab, newline, razmak), koristiti scanf sa %s ili cin string, nikako getline ili gets.
Uvek imas i ovaj nacin input-a koji je, ja mislim, brzi od scanf-a :
< int read(){
char ch = ’ ';
while(ch < ‘0’ || ch > ‘9’) ch = getchar();
int res = 0;
while(ch >= ‘0’ && ch <= ‘9’){
res = res * 10 + ch - ‘0’;
ch = getchar();
}
return res;
} >
Poziva se kao int n = read();