Zadanie Droga C++

Question

Witam, umiałby ktoś znaleźć wadę mojego programu (test, dla którego program nie działa poprawnie) lub powiedzieć, co zrobiłem źle?

Zadanie: link

Wyniki: link

Mój kod:

#include<bits/stdc++.h>
using namespace std;
long long sx=0,sy=0;
long long f(int n,int *tab){
	int i,j;
	sy*=(n-1);
	for(i=1; i<=n/2; i++){
		sx+=(tab[i]-tab[i-1])*(i*n-i*i);
		if(i!=n-i) sx+=(tab[n-i]-tab[n-i-1])*(i*n-i*i);
	}
	return sx+sy;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n,y; cin>>n;
	int *tab=new int [n];
	for(int j=0; j<n; j++){
		cin>>tab[j]>>y;
		sy+=y;
	}
	sort(tab,tab+n);
	cout<<f(n,tab);
	delete [] tab;
}

 

Comments

Nie dałeś żadnego komentarza, a zaprezentowanie rozwiązanie nie jest oczywiste. Dlaczego nie pamiętasz wszystkich danych a jedynie pozycje domków wzdłuż drogi, odległości od drogi po prostu sumujesz do zmiennej sy? Być może stojący za tym pomysł'jest dobry, ale jakoś go nie łapie...

 

Jedna z metod szukania błedów polega na znalezieniu sobie słuchacza (kolegi albo nawet zabawki) i wyjaśnieniu jemu jak dokładnie działa program. Zwykle pomaga, tj. opowiadający zwykle sam wpada na to co jest żle.

---

Rozumowanie jest w miarę dobre. W funkcji f suma tych y jest mnożona przez n-1, czyli policzone zostały odległości "pionowe" dla wszystkich spotkań. Ale kod rzeczywiście mógłby skorzystać na czytelniejszych nazwach

---

uzupełnienie: link

---

spróbuj może pozamieniać inty na long longi. Może jest jakiś overflow

---

niezły pomysł, teraz daje mi 57% zamiast wcześniejszych 28% (reszta testów, które nie działają to przekroczenie limitu czasu), ale to nadal nie 100, jakieś sugestie? może przebudowa algorytmu?

PS: zamiast cin,cout użyłem scanf,printf i niektóre testy, które nie działały, teraz działają, ale dają bardzo małą liczbę pkt:

wcześniej: link

teraz: link

---

możesz spróbować dać szybsze sortowanie. Np. jakiś counting sort

---

Zadam głupie pytanie - a w ogóle po co sortować?

---

załóżmy, że nie wykonam operacji sortowania, czyli usunę linię:

sort(tab,tab+n);

a w funkcji f operację odejnowania wrzucę do abs():

sx+=abs(tab[i]-tab[i-1])*(i*n-i*i);
if(i!=n-i) sx+=abs(tab[n-i]-tab[n-i-1])*(i*n-i*i);

Następnie sprawdź co się stanie dla przykładu:

3

2 2

3 3

1 1

z góry powiem, że powinno wypisać 16.

---

@polandonion, Możesz wrzucić linka do sprawdzarki?