Przeczytałem, hmmm, nie widzę jakoś analogii 
Poza tym powtórzenia to ja sam zrobiłem kiedyś na ki.staszic.waw.pl/task.php?name=powtorzenia1 zupełnie innym sposobem niż oni tam podają w tej niebieskiej książeczce ;p
Anyway jeszcze pomyślę
9 months later
komentarz do rozwiązania linxaddict
nie wiem dlaczego daje błedne odpowiedzi, nie chciało mi się testować ani dokładnie analizować bo kod za długi
może warto dodać na końcu 'return 0;' ?
a kod zbyt długi bo:
po co wczytywać wszystkie testy do pamięci ?
wystarczy pojedyńczo
po co dynamicznie allokować tablicę ?
znamy maksymalny rozmiar
po co pisać własnego quicksorta ?
jest qsort, wystarczy napisać funkcję porównania
po co taka dziwna sekwencja:
for(int i = 0; i < t; ++i) {
for(int j = 0; j < n[i]; ++j)
quicksort(tab[i], 0, j);
wystarczy tylko jedna pętla (chyba że to nie jest quicksort)
po co używać po obu stronach porównania sqrt ?
tylko narzut na czas wykonania
po co używać pow
lepiej zwykłego mnożenia
po co wyliczać d w każdym porównaniu
przecież można policzyć raz w czasie czytania danych i zapamietać
rzeczywiście, pierwszy błąd (char name[10]
może dawać błędne wyniki,
drugi jest nieistotny, w tym przypadku & nie ma znaczenia.
prawdziwy problem jest w błednej implementacji quicksorta, daja całkowite bzdury, sprawdź dla danych:
1
100
A100 0 100
A99 0 99
A98 0 98
...
A01 0 1
Napisałem więc od nowa... i znów rozwiązanie nie jest akceptowane. Gdzie popełniam błąd? Oto kod:
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
struct Point {
char name[11];
int x;
int y;
};
int compare(const void *v1, const void *v2) {
Point *p1 = (Point*)(v1);
Point *p2 = (Point*)(v2);
if(sqrt(p1->x*p1->x + p1->y*p1->y) < sqrt(p2->x*p2->x + p2->x*p2->y)) return -1;
if(sqrt(p1->x*p1->x + p1->y*p1->y) > sqrt(p2->x*p2->x + p2->x*p2->y)) return 1;
else return 0;
}
int main() {
unsigned t;
cin >> t;
Point tab[1000];
unsigned n;
for(int i = 0; i < t; ++i) {
cin >> n;
for(int j = 0; j < n; ++j) {
cin >> tab[j].name;
if(strlen(tab[j].name) > 10) return 1;
cin >> tab[j].x;
if(tab[j].x < -1000 || tab[j].x > 1000) return 1;
cin >> tab[j].y;
if(tab[j].y < -1000 || tab[j].y > 1000) return 1;
}
qsort(tab, n, sizeof(Point), compare);
for(int j = 0; j < n; ++j)
cout << tab[j].name << " " << tab[j].x << " " << tab[j].y << endl;
cout << endl;
}
return 0;
}już prawie dobrze, choć było by lepiej zamiast:
int compare(const void *v1, const void *v2) {
Point *p1 = (Point*)(v1);
Point *p2 = (Point*)(v2);
if(sqrt(p1->x*p1->x + p1->y*p1->y) < sqrt(p2->x*p2->x + p2->x*p2->y)) return -1;
if(sqrt(p1->x*p1->x + p1->y*p1->y) > sqrt(p2->x*p2->x + p2->x*p2->y)) return 1;
else return 0;
}napisać znacznie prościej (bo sqrt jest niepotrzebny, a dwa razy liczyć też nie trzeba):
int compare(const void *v1, const void *v2) {
Point *p1 = (Point*)(v1);
Point *p2 = (Point*)(v2);
int d = (p1->x*p1->x + p1->y*p1->y) - (p2->x*p2->x + p2->y*p2->y);
return d;
}a jeszcze lepiej dodać do struktury d i wyliczać po wczytaniu x i y, wtedy funkcja porównująca jest jeszcze prostsza.
7 months later
Mógłby ktoś znaleźć błąd, bo dla wszystkich danych jakie spr wychodziło dobrze, a dostaję błędną odpowiedź.
#include <iostream>
#include <string>
using namespace std;
unsigned long long int odleglosc(long long int, long long int);
int main()
{
long long int t, n, x[100], y[100];
string nazwa[100];
cin >> t;
while(t--)
{
cin >> n;
for(int i=0; i<n; i++)
{
cin >> nazwa[i] >> x[i] >> y[i];
}
for(int i=0; i<n-1; i++)
{
for(int j=1; j<n; j++)
{
if(odleglosc(x[i],y[i])>odleglosc(x[j],y[j]))
{
swap(nazwa[i], nazwa[j]);
swap(x[i], x[j]);
swap(y[i], y[j]);
}
}
}
for(int i=0; i<n; i++) cout << nazwa[i] << " " << x[i] << " " << y[i] << "\n";
cout << "\n";
}
return 0;
}
unsigned long long int odleglosc(long long int x, long long int y)
{
unsigned long long int d;
d=x*x+y*y;
return d;
}11 months later
Mam problem, ponieważ rozwiązanie, które napisałem wygląda na poprawne (nie znalazłem danych przy których odpowiedz byłaby błędna), ale niestety tester nie chce go zaakceptować. Może ktoś spojrzeć na to i wskazać mi w czym tkwi problem?
#include <cstdlib>
#include <iostream>
using namespace std;
int main()
{
struct PKT
{
string nazwa; //nazwa pkt
long long x; //wsp. x
long long y; //wsp. y
long long o; //odleglosc od srodka ukladu
};
int t; //zmianna zawierająca ilość testów
cin >> t;
for(int x=0; x<t; x++) {
int a; //zmienna zawierająca ilość punktów
cin >> a;
PKT p[a]; // tablica pkt
for (int y=0; y<a; y++) {
cin >> p[y].nazwa >> p[y].x >> p[y].y;
p[y].o = (p[y].x*p[y].x) + (p[y].y*p[y].y);
}
if (a>1) {
int zmiany;
do {
zmiany = 0;
for (int y=0; y<a-1; y++) {
if (p[y].o > p[y+1].o) {
string stemp;
int temp, temp1, temp2;
stemp = p[y].nazwa;
temp = p[y].o;
temp1 = p[y].x;
temp2 = p[y].y;
p[y].nazwa = p[y+1].nazwa;
p[y].o = p[y+1].o;
p[y].x = p[y+1].x;
p[y].y = p[y+1].y;
p[y+1].nazwa = stemp;
p[y+1].o = temp;
p[y+1].x = temp1;
p[y+1].y = temp2;
zmiany++;
}
}
} while (zmiany>1);
}
for (int y=0; y<a; y++) {
cout << p[y].nazwa << ' ' << p[y].x << ' ' << p[y].y << endl;
}
cout << endl;
}
return 0;
}Z góry dzięki za pomoc.
2 months later
w ktorym miejscu ma byc ta pusat linia??
#include <cstdlib>
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;
int main(int argc, char *argv[])
{
string nazwa[10000];
long long int x[10000],y[10000],t,ile;
cin>>t;
for(int i=0;i<t;i++){
cin>>ile;
for(int j=0;j<ile;j++){
cin>>nazwa[j]>>x[j]>>y[j];
}
for(int j=0;j<ile*2;j++){
for(int z=0;z<ile-1;z++){
int x1 = (x[z]>0 ? x[z]: -x[z]);
int y1 = (y[z]>0 ? y[z]: -y[z]);
int x2 = (x[z+1]>0 ? x[z+1]: -x[z+1]);
int y2 = (y[z+1]>0 ? y[z+1]: -y[z+1]);
double l1 = sqrt(x1+y1);
double l2 = sqrt(x2+y2);
if(l1>l2){
int tmp1=x[z],tmp2=y[z];
x[z]=x[z+1];
y[z]=y[z+1];
x[z+1]=tmp1;
y[z+1]=tmp2;
string tmp=nazwa[z];
nazwa[z]=nazwa[z+1];
nazwa[z+1]=tmp;
}
}
}
for(int xd=0;xd<ile;xd++)
cout<<nazwa[xd]<<" "<<x[xd]<<" "<<y[xd]<<endl;
cout<<endl;
}
}19 days later
#include <iostream>
#include <string>
using namespace std;
struct pkt{
public:
string str;
int x,y,o,i;
};
int main()
{
int t,x,y,n;
string str;
cin >> t;
while(t--)
{
cin >> n;
pkt *p = new pkt [n];
for(int i=0;i<n;i++)
{
cin >>p[i].str >> p[i].x >> p[i].y;
p[i].o=(p[i].x*p[i].x+p[i].y*p[i].y);
}
int min=p[0].o, mini;
for(int i=0;i<n;i++)
{
mini=i;
for(int j=i;j<n;j++)
{
if(p[j].o<min)
{
min=p[j].o;
mini=j;
}
}
swap(p[i].str,p[mini].str);
swap(p[i].x,p[mini].x);
swap(p[i].y,p[mini].y);
swap(p[i].o,p[mini].o);
}
for(int i=0;i<n;i++)
{
cout << p[i].str << " " << p[i].x <<" "<< p[i].y <<" " << endl;
}
cout << endl;
}
//system("pause");
}czemu WA? kto odpowie mi ;]?
o.0 nie ma to jak robic kilka(nascie) rzeczy naraz... no ale kod dla potomnych, jak znajda blad niech maja;]
12 days later
Witam.
Mam problem z zadaniem z tematu które jakiś czas temu robiłem. Przykładowe dane wychodzą dokładnie tak samo, na innych także testowałem, wynik pozytywny mym skromnym zdaniem. Jednakże sędzią zwraca mi błędną odpowiedź. Kod który był poddawany testowi wygląda tak:
#include <iostream>
#include <string.h>
using namespace std;
int main()
{
int t,t2,i,asd;
float a;
char foo[15];
cin >> t;
while(t--)
{
cin >> t2;
i=0;
char nazwa[t2][15];
int ptk[t2][2];
float wynik[t2];
while(i<t2)
{
cin >> nazwa[i] >> ptk[i][0] >> ptk[i][1];
wynik[i] = (ptk[i][0]*ptk[i][0])+(ptk[i][1]*ptk[i][1]);
i++;
}
for(i=0;i<t2-1;i++)
{
for(int j=i;j<t2-1;j++)
{
if(wynik[j] > wynik[j+1])
{
strcpy(foo, nazwa[j+1]);
strcpy(nazwa[j+1], nazwa[j]);
strcpy(nazwa[j], foo);
a = wynik[j+1];
wynik[j+1] = wynik[j];
wynik[j] = a;
asd = ptk[j+1][0];
ptk[j+1][0] = ptk[j][0];
ptk[j][0] = asd;
asd = ptk[j+1][1];
ptk[j+1][1] = ptk[j][1];
ptk[j][1] = asd;
}
}
}
for(i=0;i<t2;i++)
{
cout << nazwa[i] << " "<< ptk[i][0] << " " << ptk[i][1] << endl;
}
if(t>0)cout << endl;
}
return 0;
}Proszę o pomoc
Z góry dzięki dla zainteresowanych.
No więc na przykład taki test:
1
10
A 7 7
B -7 -7
C -7 7
D 7 -7
E 5 5
F -5 -5
G -5 5
H 5 -5
I 7 5
J 5 7Odpowiedź mojego zaakceptowanego programu:
E 5 5
F -5 -5
G -5 5
H 5 -5
I 7 5
J 5 7
A 7 7
B -7 -7
C -7 7
D 7 -71 month later
Witam, próbuję rozwiązać to zadanie, ale otrzymuję status SE. Proszę o komentarz do mojego kodu, wskazówkę lub wyjaśnienie błędu w moim zrozumieniu treści zadania.
Kod:
tu był kod1 year later
1 year later
1 year later