Θέλω πιο γρήγορο κώδικα - C .

[ARIANAROS]

 

1) Καταρχήν, τονίζω ιδιαίτερα

"10 Do i=2,N // ξεκινάς από το δεύτερο διάστημα, δηλ. i=2]"

Εσύ ξεκινάς με i=1.

 

 

To πρόσεξα , απλά αφού ως πρώτο στοιχείο θεωρείται το 0 , ως δεύτερο πήρα το 1 , αλλά και με i = 2 που το δοκίμασα , πάλι με βγάζει λάθος απάντηση .

 

2) Εγώ έγραψα

"a1=a2 ; b1=b2".

Εσύ γράφεις

"a1=b1;

a2=b2;"

δηλ. το κάθε διάστημα δεν αντικαθιστά το προηγούμενό του.

 

Ναι , όντως , το διόρθωσα κι αυτό και πάλι τίποτα .

 

Διόρθωσε αυτά και θα δουλέψει.

Όσο για το "πώς ελέγχεις αν το παρών τμήμα επικαλύπτει κάποιο προηγούμενο( πολύ προηγούμενο δηλαδή )" είναι απλό.

Αρχικά θεωρείται ότι όλα τα τμήματα ότι επικαλύπτονται.

Αν κάποιο δεν επικαλύπτεται με το τρέχον τότε δεν επικαλύπτεται και με όλα τα προηγούμενα.

Ο έλεγχος απλώς το βρίσκει και το εξαιρεί. Τι σημαίνει αυτό ;

Ότι δεν πρέπει να φτάσει την γραμμή "a1=a2 ; b1=b2" και το επόμενο να συγκριθεί με αυτό.

Σκέψου το και θα το διαπιστώσεις μόνος σου.

 

Μου φαίνεται λογικό αυτό που λες αλλά τι να πω . Ακόμα το πρόβλημα βλακείες κάνει .

 

Με το "register" δεν κερδίζεις σχεδόν τίποτε στην περίπτωση αυτή. Αφού το πρόγραμμα είναι Ο(Ν) θα τρέχει αρκούντως γρήγορα.

Άντε καληνύχτα και χρόνια πολλά (Πασχα γαρ !!).

 

Χρόνια πολλά και σε εσένα φίλε μου !

Και σε ευχαριστώ πάρα πολύ για την βοήθεια !

ΥΓ : Ιδού ο κώδικας που έχω τώρα .

>
#include <stdio.h>

int main ( void ) {
FILE *in = fopen ( "crocodiles.in" , "r" ) , *out = fopen ( "crocodiles.out" , "w" ) ;
int N , crocs , a1 , a2 , b1 , b2 ;
register int i ;

fscanf ( in , "%d" , &N ) ;
crocs = N ;
fscanf ( in , "%d %d" , &a1 , &b1 ) ;
for ( i = 2 ; i <= N ; i++ ) {
	fscanf ( in , "%d %d" , &a2 , &b2 ) ;
	if ( b1 < a2 || a1 > b2) {
		crocs-- ;
		continue ;
	}
	a1 = a2 ;
	b1 = b2 ;
}
fprintf ( out , "%d\n" , crocs ) ;
fclose ( in ) ; fclose ( out ) ;
return ( 0 ) ;
}

[ARIANAROS]

Παιδιά , το πρόβλημα δεν λύθηκε , μην επαναπαύεστε !

[bnvdarklord]

Κατα την γνώμη μου παντως, δεν σημαινει τπτ το 1 δευτερόλεπτο που προσπαθείς και τα 4 που κάνει τωρα(ή οσο κανει μετα τις αλλαγες).... Αν το βάλεις να τρέξει σε καποιον πιο γρήγορο υπολογιστή πιθανόν κάνει λιγότερο από 1sec...

[ARIANAROS]

Όχι , στα ίδια έχω μείνει από χρόνο . Κι εγώ αυτή την άποψη έχω , αλλά στο site την μέτρηση την κάνουν σε δικό τους υπολογιστή και δεν μπορώ να αλλάξω κάτι , κι αν δεν περάσω δεν προχωράω παρακάτω .

[bnvdarklord]

Ποιο ειναι αυτό το site?

[ARIANAROS]

http://www.hellenico.gr/

 

Aλλά πρέπει να περάσεις τις προηγούμενες ενότητες για να φτάσεις εκεί που είμαι εγώ , στην 1.5 . Και αν δεν λύσω αυτό δεν προχωράω !

[bnvdarklord]

Ενδιαφέρον site.... θα ασχοληθω καποια στιγμή... Δεν σου δίνεται η δυνατότητα να κατεβάσεις το αρχείο in που εχουνε εκει?

[ARIANAROS]

Όχι τους άτιμους ! Σα δε ντρέπονται !

[javavall]

Χααχαχαχαχα , οι left και right ήταν παλιό τερτίπι μπας και μειώσω τον χρόνο και μετά ξέχασα να τις βγάλω ! Το site λέγεται hellenico ( είναι site προετοιμασίας για τον Πανελλήνιο Διαγωνισμό Πληροφορικής ( μην λιγουρεύεστε , είναι μόνο για μαθητές σαν και του λόγου μου ) ) αλλά πρέπει να περάσεις τις προηγούμενες ενότητες για να φτάσεις σε αυτό που σας λέω εγώ . Και το χειρότερο ξέρετε ποιο είναι ; Υπάρχουν άτομα που το έχουν περάσει !!!

Το HelleniCO (Hellenic Computing Olympiad) είναι ένας ιστότοπος που απευθύνεται κυρίως σε μαθητές Γυμνασίου και Λυκείου με βασικό στόχο την προετοιμασία τους για τη συμμετοχή στην Διεθνή και Βαλκανική Ολυμπιάδα Πληροφορικής. Παράλληλα όμως απευθύνεται και σε άτομα οποιασδήποτε ηλικίας που έχουν πάθος με τον προγραμματισμό και τους αλγορίθμους.

 

Οπότε μπορούμε να λιγουρευόμαστε

[ARIANAROS]

Φτου , όντως , δεν το είχα δει ( παλιολιγούρι ! ) . Άντε , καλή επιτυχία . Αλλά please , λύστε το πρόβλημά μου , επείγει !!!!!!

[bnvdarklord]

Φτιαξε δικό σου αρχείο in με αυτόν τον κώδικα

 

>
#include <stdio.h>
#include <time.h>
#define min(a, a<=b?a:b
#define max(a, a>=b?a:b
#define N 300000

int main(void)
{
FILE *in = fopen("crocodiles.in", "w");
int i;
srand((unsigned)time(0)); 

fprintf(in, "%d\n", N);

for(i = 1; i <= N; i++)
{
	int a = rand()%200000 - 100000;
	int b = rand()%200000 - 100000;
	fprintf(in, "%d %d\n", min(a,, max(a,);
}

fclose(in);

return 0;
}

 

Για να τεστάρεις πιο ανετα...

[ARIANAROS]

Ωραίος , αλλά το μόνο θέμα είναι με τον χρόνο , γιατί τα αποτελέσματα βγαίνουν σωστά !

[javavall]

Ωραίος , αλλά το μόνο θέμα είναι με τον χρόνο , γιατί τα αποτελέσματα βγαίνουν σωστά !

 

Καλύτερος αλγόριθμος αναζήτησης ίσως?

[ARIANAROS]

Δηλαδή ;

ασδφαφδσγκξφδσω

[bnvdarklord]

Κυρίως για μένα το εγραψα, αλλα ειπα να το ποστάρω αν θελει να τεστάρει και κάποιος αλλος

 

Διόρθωσα ενα λαθάκι στον κώδικα επρεπε να βαλω % στον υπολογισμό a,b...

 

edit: στο αρκετά παλιό pc μου o κώδικας σου με το αρχείο 300000 καταχωρίσεων που εφτιαξα με τον κώδικα μου, κάνει περίπου μισό δευτερόλεπτο

 

edit: απο περιέργεια δοκίμασα και τον πρώτο σου κώδικα που λες κανει 4 δευτερόλεπτα... guess what? Εκανε περίπου ενα λεπτό(!) και εβγαλε και λαθος αποτελεσμα(υποθέτοντας οτι το αποτέλεσμα του τελευταίου σου προγράμματος ειναι σωστό)... Οποτε μαλλον το εχεις φτιαξει, αλλα καποια μαλακια γινεται με το site ...