Αποτελέσματα Β φάσης
-
- Δημοσιεύσεις: 65
- Εγγραφή: Δευ Δεκ 21, 2009 10:21 pm
- Επικοινωνία:
Re: Αποτελέσματα Β φάσης
μολις ειδα και εγω τα αποτελεσματα.
Περασα 9ος και να φανταστειτε οτι το πρωτο πρόγραμμα σε c που εγραψα ήταν φέτος για τη πρωτη φάση.
Ξερει κανεις πως γίνετε η τρίτη φαση γιατι εμένα με βολεύει να προγραμματίζω σε mac? Κάτι έχω ακούσει για linux.
Συγχαρητήρια σε όλους!!!
Περασα 9ος και να φανταστειτε οτι το πρωτο πρόγραμμα σε c που εγραψα ήταν φέτος για τη πρωτη φάση.
Ξερει κανεις πως γίνετε η τρίτη φαση γιατι εμένα με βολεύει να προγραμματίζω σε mac? Κάτι έχω ακούσει για linux.
Συγχαρητήρια σε όλους!!!
-
- Δημοσιεύσεις: 712
- Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Re: Αποτελέσματα Β φάσης
Συγχαρητήρια σε όλους! Μόλις πάω στον Desktop μου θα ποστάρω τη λύση μου για το θέμα του γυμνασίου. (Είμαι 12ος)
-----------------------
@kostassite: καλά έχεις ακούσει: http://pdp.gr/default.asp?pid=6&la=1&fid=3
Πέρισυ μας άφησαν αρκετό χρόνο για να εξοικιωθούμε με το περιβάλλον (Gnome + dev. applications (Anjuta, Kate etc) ) και μας είπαν πώς να σετάρουμε τις ρυθμίσεις που αφορούσαν την δικτύωση σωστά.
Δεν υπάρχει σύνδεση με WWW. Ωστόσο (αν δεν με απατάει η μνήμη μου) υπάρχει STL reference.
-----------------------
@kostassite: καλά έχεις ακούσει: http://pdp.gr/default.asp?pid=6&la=1&fid=3
Πέρισυ μας άφησαν αρκετό χρόνο για να εξοικιωθούμε με το περιβάλλον (Gnome + dev. applications (Anjuta, Kate etc) ) και μας είπαν πώς να σετάρουμε τις ρυθμίσεις που αφορούσαν την δικτύωση σωστά.
Δεν υπάρχει σύνδεση με WWW. Ωστόσο (αν δεν με απατάει η μνήμη μου) υπάρχει STL reference.
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
Re: Αποτελέσματα Β φάσης
Πέρασα 9ος στο γυμνάσιο , θα δώσω την λύση μου το μεσημέρι.
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
Re: Αποτελέσματα Β φάσης
Βγηκα 1ος! Θα ποστάρω την λύση μου και εγώ το μεσημέρι μιας και δεν την έχω σε αυτό το pc που κάθομαι. Η λύση που έκανα πάντως ήταν ΜΗ αναδρομική και σχετιζόταν με scan line fill. Οι περισσότεροι από εδώ αν όχι και όλοι, κάνατε ένα ήδους boundary fill αλγόριθμο http://www.siggraph.org/education/mater ... lygn6a.htm ο οποίος είναι πολύ πιο αργός από εναν scanline! Η scanline το λέει και η λέξη scannarei μία μια τις γραμμές και δεν κάνει push σε stack όλες τις τελείες(δέντρα) αλλά ώσες πρέπει να κάνει μόνο...
Το όλο σκηνικό του προβλήματος αποτελούσε array-fill αλγόριθμους. Γνωστός πολύ αλγόριθμος γι αυτή τη δουλειά είναι ο λεγόμενος Flood FIll http://en.wikipedia.org/wiki/Flood_fill . Προφανώς το πρόβλημα συσχετιζόταν με ένα ήδος ζωγραφικής... όποιος το πρόσεξε το πρόσεξε
Ωστόσο είχα κάνει και μια αναδρομική λύση scanline που αποδείχθεικε πως ήταν αρκετά γρήγορη αλλά όχι σε σχεσή με αυτή της μη αναδρομικής!
Συγχαρητήρια σε όλους... Θα δώσω την λύση μου όταν την βρω
Υ.Γ 1)Δείτε πως είναι το scanline fill -> http://upload.wikimedia.org/wikipedia/e ... y_fill.gif
Το όλο σκηνικό του προβλήματος αποτελούσε array-fill αλγόριθμους. Γνωστός πολύ αλγόριθμος γι αυτή τη δουλειά είναι ο λεγόμενος Flood FIll http://en.wikipedia.org/wiki/Flood_fill . Προφανώς το πρόβλημα συσχετιζόταν με ένα ήδος ζωγραφικής... όποιος το πρόσεξε το πρόσεξε
Ωστόσο είχα κάνει και μια αναδρομική λύση scanline που αποδείχθεικε πως ήταν αρκετά γρήγορη αλλά όχι σε σχεσή με αυτή της μη αναδρομικής!
Συγχαρητήρια σε όλους... Θα δώσω την λύση μου όταν την βρω
Υ.Γ 1)Δείτε πως είναι το scanline fill -> http://upload.wikimedia.org/wikipedia/e ... y_fill.gif
Τελευταία επεξεργασία από το μέλος thodoris την Πέμ Μαρ 18, 2010 12:34 pm, έχει επεξεργασθεί 1 φορά συνολικά.
- compileGuy
- Δημοσιεύσεις: 218
- Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm
Re: Αποτελέσματα Β φάσης
Συγχαριτήρια σε όλους
Πέρασα και εγω 10ος απο το γυμνάσιο. Πολύ ενδιαφέρον αλγόριθμος για το πρόβλημα του Λυκείου
Πέρασα και εγω 10ος απο το γυμνάσιο. Πολύ ενδιαφέρον αλγόριθμος για το πρόβλημα του Λυκείου
-
- Δημοσιεύσεις: 712
- Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Re: Αποτελέσματα Β φάσης
Ορίστε το προγραμματάκι μου για το θέμα του γυμνασίου. Δεν βασίζεται σε γνωστό αλγόριθμο (απ' όσο ξέρω τουλάχιστον) αν και θα είχα αναπτύξει κάποιον από τους γνωστούς αν δεν βαριόμουνα
αυτό βρήκα τώρα στο PC μου αν και νομίζω πριν να υποβάλλω τη λύση μου είχα αλλάξει το:
σε
Κώδικας: Επιλογή όλων
/* Loukas Xanthos, B Fasi PDP 2010.
* LANG: C++ */
#include <cstdio>
#include <queue>
using namespace std;
const unsigned int MAX_N=1024, MAX_M=65536;
char strSearch[MAX_N];
char strDisk[MAX_M];
char chStart, chEnd;
unsigned int N, M;
int main()
{
register unsigned int i=0, j=0;
queue<unsigned int> possible_beg;
queue<unsigned int> possible_end;
unsigned int beg_pos=0;
FILE *fin = fopen("matrix.in", "r");
FILE *fout= fopen("matrix.out","w");
fscanf(fin, "%u\n", &N);
fgets(strSearch, N+1, fin);
fscanf(fin, "%u\n", &M);
fgets(strDisk, M+1, fin);
chStart = strSearch[0];
chEnd = strSearch[N-1];
for(i=0; i < M; ++i) {
if(strDisk[i] == chStart) {
possible_beg.push(i);
}
if(strDisk[i] == chEnd) {
possible_end.push(i);
}
}
while(!possible_beg.empty() && !possible_end.empty())
{
if(possible_end.front() - possible_beg.front() == 0) {
possible_end.pop();
}
else if(possible_end.front() - (possible_beg.front() - 1) < N) {
possible_end.pop();
}
else if(possible_end.front() - (possible_beg.front() - 1) > N) {
possible_beg.pop();
}
else if(possible_end.front() - (possible_beg.front() - 1) == N) {
for(j=0; j<N; j++)
{
if( strSearch[j] == strDisk[ possible_beg.front() + j ] )
continue;
else
{
possible_beg.pop();
possible_end.pop();
break;
}
}
if(j == N) {
beg_pos = possible_beg.front() + 1;
break;
}
}
}
if(!beg_pos) {
fprintf(fout, "F\n");
}
else {
fprintf(fout, "%u\n", beg_pos);
}
fclose(fin);
fclose(fout);
return 0;
}
Κώδικας: Επιλογή όλων
if( strSearch[j] == strDisk[ possible_beg.front() + j ] )
continue;
else
{
Κώδικας: Επιλογή όλων
if( strSearch[j] != strDisk[ possible_beg.front() + j ] ) {
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
Re: Αποτελέσματα Β φάσης
Βασικά απ όσο ξέρω το πρόβλημα του γυμνασίου λύνεται με μια απλή strstr και strpos. Νομίζω ότι και μόνο με strpos(text,find) τελειώνεις. Και για να αυξήσεις λίγο την ταχύτητα δεν χρησιμοποιείς STL αλλά φιάχνεις δικιά σου. Η strpos βρίσκεται στην lib string.h . Αν δεν υπάρχει τότε αναγκαστικά την φιάχνεις μόνος σου
Re: Αποτελέσματα Β φάσης
Εκανα μια πολύ απλή λύση σε αυτή του γυμνασίου. Δεν ξέρω καν αν παίζει σωστά(με τα 2 testcases πάντως έπαιξε).
Κώδικας: Επιλογή όλων
#include <stdio.h>
int strpos(char *text, char *find)
{
char *p = strstr(find, text);
if (p)
return abs(p - find);
return -1; // Not found = -1.
}
int main()
{
int N,M,pos;
char strSearch[65536],strText[1024];
FILE *fin = fopen("matrix.in", "r");
FILE *fout= fopen("matrix.out","w");
fscanf(fin, "%d\n", &N);
fgets(strSearch, N+1, fin);
fscanf(fin, "%d\n", &M);
fgets(strText, M+1, fin);
fclose(fin);
if((pos = strpos(strSearch,strText)) != -1)
fprintf(fout,"%d\n",pos);
else
fprintf(fout,"F\n");
fclose(fout);
return 0;
}
-
- Δημοσιεύσεις: 65
- Εγγραφή: Δευ Δεκ 21, 2009 10:21 pm
- Επικοινωνία:
Re: Αποτελέσματα Β φάσης
Είμαι χρήστης ubuntu αρκετα χρόνια αλλα με βολεύει καλύτερα το xcode(mac).thetrojan01 έγραψε: @kostassite: καλά έχεις ακούσει: http://pdp.gr/default.asp?pid=6&la=1&fid=3
Πέρισυ μας άφησαν αρκετό χρόνο για να εξοικιωθούμε με το περιβάλλον (Gnome + dev. applications (Anjuta, Kate etc) ) και μας είπαν πώς να σετάρουμε τις ρυθμίσεις που αφορούσαν την δικτύωση σωστά.
Δεν υπάρχει σύνδεση με WWW. Ωστόσο (αν δεν με απατάει η μνήμη μου) υπάρχει STL reference.
Επίσης μπορούμε να έχουμε μαζί κάποια υποπρογράμματα δικά μας? Μαλλον δε γίνετε αλλα μια ερώτηση δε βλάπτει.
Σε ubuntu ποιο πρόγραμμα προτείνετε για c?
Re: Αποτελέσματα Β φάσης
Εγώ στα ubuntu έχω το Geany (sudo apt-get install geany)
Re: Αποτελέσματα Β φάσης
Εγώ βγήκα 4ος. .
- compileGuy
- Δημοσιεύσεις: 218
- Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm
Re: Αποτελέσματα Β φάσης
Το περιβάλλον εργασίας είναι σε linux οπως είπε και ο thetrojan01. Για C γίνεται να γράψει σε Kate και μετα με terminal να κανεις compile με gcc . Αλλιώς μπορείς να χρησιμοποιήσεις τον Anjuta .kostassite έγραψε:Είμαι χρήστης ubuntu αρκετα χρόνια αλλα με βολεύει καλύτερα το xcode(mac).thetrojan01 έγραψε: @kostassite: καλά έχεις ακούσει: http://pdp.gr/default.asp?pid=6&la=1&fid=3
Πέρισυ μας άφησαν αρκετό χρόνο για να εξοικιωθούμε με το περιβάλλον (Gnome + dev. applications (Anjuta, Kate etc) ) και μας είπαν πώς να σετάρουμε τις ρυθμίσεις που αφορούσαν την δικτύωση σωστά.
Δεν υπάρχει σύνδεση με WWW. Ωστόσο (αν δεν με απατάει η μνήμη μου) υπάρχει STL reference.
Επίσης μπορούμε να έχουμε μαζί κάποια υποπρογράμματα δικά μας? Μαλλον δε γίνετε αλλα μια ερώτηση δε βλάπτει.
Σε ubuntu ποιο πρόγραμμα προτείνετε για c?
-
- Δημοσιεύσεις: 65
- Εγγραφή: Δευ Δεκ 21, 2009 10:21 pm
- Επικοινωνία:
Re: Αποτελέσματα Β φάσης
Ευχαριστω θα τα δω και τα δυο το σαββατοκυριακο γιατι εχω και αοδε
Και τα δυο ειναι επιτρεπτα στη 3 φαση??
Και τα δυο ειναι επιτρεπτα στη 3 φαση??
Re: Αποτελέσματα Β φάσης
Έκανα τεράστια βελτίωση στην λύση του γυμνασίου: Και για τα 2 testcases βγάζω 0ms. Με του thetrojan έβγαζα 0.010.
Και εδώ η λύση του λυκείου που έκανα(νομίζω ότι αυτό είναι το τελευταίο):
Κώδικας: Επιλογή όλων
#include <stdio.h>
char *find_num(char * text,char * find)
{
char *cp = (char *) text;
char *s1, *s2;
while (*cp)
{
s1 = cp;
s2 = (char *) find;
while ( *s1 && *s2 && !(*s1-*s2) )
s1++, s2++;
if (!*s2)
return(cp);
cp++;
}
return (char *) 0;
}
int strpos(char *text, char *find)
{
char *p;
if ((p == find_num(find,text)))
return abs(p - find);
return -1; // Not found = -1.
}
int main()
{
int N,M,pos;
char strSearch[65536],strText[1024];
FILE *fin = fopen("matrix.in", "r");
FILE *fout= fopen("matrix.out","w");
fscanf(fin, "%d\n", &N);
fgets(strSearch, N+1, fin);
fscanf(fin, "%d\n", &M);
fgets(strText, M+1, fin);
fclose(fin);
if((pos = strpos(strSearch,strText)) != -1)
fprintf(fout,"%d\n",pos);
else
fprintf(fout,"F\n");
fclose(fout);
return 0;
}
Κώδικας: Επιλογή όλων
#include <iostream>
#include <fstream>
using namespace std;
char ektash[1000][1002]; //MAP
int sthles,grammes;
int count_foties=0;
int dots_x[1000000];
int dots_y[1000000];
int k = 0;
int pop()
{
if( k > 0)
{
k--;
return 1;
}
else
return -1;
}
void push(int x, int y)
{
dots_x[k] = x;
dots_y[k++] = y;
}
void fill_scan_line(int x, int y)
{
int y1,Left, Right;
push(x, y);
while(pop() != -1)
{
x = dots_x[k];
y1 = dots_y[k];
while(y1 >= 0 && ektash[x][y1] == '.') y1--;
y1++;
Left = Right = 0;
while(y1 < sthles && ektash[x][y1] == '.' )
{
ektash[x][y1] = '!';
count_foties++;
if(Left == 0 && x > 0 && ektash[x - 1][y1] == '.')
{
push(x - 1, y1);
Left = 1;
}
else if(Left == 1 && x > 0 && ektash[x - 1][y1] != '.')
{
Left = 0;
}
if(Right == 0 && x < grammes - 1 && ektash[x + 1][y1] == '.')
{
push(x + 1, y1);
Right = 1;
}
else if(Right == 1 && x < grammes - 1 && ektash[x + 1][y1] != '.')
{
Right = 0;
}
y1++;
}
}
}
int main()
{
int fire_x,fire_y,i;
ofstream out;
ifstream in;
in.open("fire.in");
out.open("fire.out");
in >> sthles >> grammes;
in >> fire_x >> fire_y;
for (i = 0; i < grammes; i++)
in >> ektash[i];
in.close();
fill_scan_line(fire_y-1,fire_x-1);
out << count_foties << endl;
out.close();
return 0;
}
Re: Αποτελέσματα Β φάσης
Οπα στην λυση του γυμνασιου το return abs(p - find); κάντε το return abs(p - find + 1); και είμαστε κομπλε
Re: Αποτελέσματα Β φάσης
Για text-editor/IDE:compileGuy έγραψε:Το περιβάλλον εργασίας είναι σε linux οπως είπε και ο thetrojan01. Για C γίνεται να γράψει σε Kate και μετα με terminal να κανεις compile με gcc . Αλλιώς μπορείς να χρησιμοποιήσεις τον Anjuta .kostassite έγραψε:Είμαι χρήστης ubuntu αρκετα χρόνια αλλα με βολεύει καλύτερα το xcode(mac).thetrojan01 έγραψε: @kostassite: καλά έχεις ακούσει: http://pdp.gr/default.asp?pid=6&la=1&fid=3
Πέρισυ μας άφησαν αρκετό χρόνο για να εξοικιωθούμε με το περιβάλλον (Gnome + dev. applications (Anjuta, Kate etc) ) και μας είπαν πώς να σετάρουμε τις ρυθμίσεις που αφορούσαν την δικτύωση σωστά.
Δεν υπάρχει σύνδεση με WWW. Ωστόσο (αν δεν με απατάει η μνήμη μου) υπάρχει STL reference.
Επίσης μπορούμε να έχουμε μαζί κάποια υποπρογράμματα δικά μας? Μαλλον δε γίνετε αλλα μια ερώτηση δε βλάπτει.
Σε ubuntu ποιο πρόγραμμα προτείνετε για c?
Το kate είναι βαρύ και δυσχρηστό χωρίς λόγο, anjuta ftw! Επίσης δες το emacs (αν είσαι μαζοχιστής ). Ακόμα και με gedit όμως γίνεται η δουλειά σου.
Compiler gcc κλασσικά.
Η λύση μου (νομίζω πως έστειλα αυτήν):
Κώδικας: Επιλογή όλων
#include <stdio.h>
int TimesFound[257], PosFound[257][1025], N;
long int M;
char str[65540],pat[1025];
int Allign(unsigned char c, int x)
{
long int f=TimesFound[c], t;
if(f<x) return -1;
t=PosFound[c][x-1];
return t;
}
int Compare(long int s, long int e)
{
long int i,j;
j=0;
for(i=s;i<e;i++)
{
if(pat[j++]!=str[i]) return -1;
}
return 0;
}
int main()
{
FILE *fin, *fout;
long int i,j,start,end,allign,found=-1;
unsigned char c;
for(i=0;i<256;i++) TimesFound[i]=0;
fin = fopen("matrix.in","r");
fout = fopen("matrix.out","w");
fscanf(fin,"%d\n",&N);
for(i=0;i<N;i++)
{
fscanf(fin,"%c",&c);
pat[i]=c;
PosFound[c][TimesFound[c]]=i;
TimesFound[c]++;
}
fscanf(fin,"%ld\n",&M);
for(i=0;i<M;i++)
{
fscanf(fin,"%c",&str[i]);
}
start=0;
end=N-1;
while(found==-1)
{
j=1;
allign=-2;
while(allign!=-1 && found==-1)
{
allign=Allign(str[end],j++);
if(allign!=-1) if(Compare(end-allign,end-allign+N)==0)
{
found=end-allign;
}
}
start+=N;
end+=N;
if(end>M && found<0) found=-2;
}
if(found<0) fprintf(fout,"F\n");
else fprintf(fout,"%ld\n",found+1);
fclose(fin);
fclose(fout);
return 0;
}
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
-
- Δημοσιεύσεις: 170
- Εγγραφή: Πέμ Νοέμ 26, 2009 9:59 pm
Re: Αποτελέσματα Β φάσης
Συγχαριτιρια σε ολους, εγω περασα 2ος στο γυμνασιο!!!!!!
Δεν το περιμενα, και ειμαι εντυπωσιασμενος!
Φανταζομαι πρεπει να μαθω πληροφοριες σχετικα με την 3η φαση.
δεν εχω χρονο ομως τωρα, μονο για να δω τα αποτελεσματα μπηκα...
φροντιστιρια...
Δεν το περιμενα, και ειμαι εντυπωσιασμενος!
Φανταζομαι πρεπει να μαθω πληροφοριες σχετικα με την 3η φαση.
δεν εχω χρονο ομως τωρα, μονο για να δω τα αποτελεσματα μπηκα...
φροντιστιρια...
DFS Hole:
- Spoiler: show
-
- Δημοσιεύσεις: 712
- Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Re: Αποτελέσματα Β φάσης
Πώς στο καλό μου ξέφυγε η strstr ??? Και να φανταστείς ψαχνόμουν με τις συναρτήσεις στην cstring όταν τέλειωσα το γράψιμο της λύσης μου!thodoris έγραψε:Βασικά απ όσο ξέρω το πρόβλημα του γυμνασίου λύνεται με μια απλή strstr και strpos. Νομίζω ότι και μόνο με strpos(text,find) τελειώνεις. Και για να αυξήσεις λίγο την ταχύτητα δεν χρησιμοποιείς STL αλλά φιάχνεις δικιά σου. Η strpos βρίσκεται στην lib string.h . Αν δεν υπάρχει τότε αναγκαστικά την φιάχνεις μόνος σου
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
Re: Αποτελέσματα Β φάσης
έλα μου ντε, υπήρχε έτοιμη συνάρτηση, 3 γραμμές πρόγραμμα... -_-
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
Re: Αποτελέσματα Β φάσης
Η strstr ωστόσο είναι η πιο γρηγόρη συνάρτηση για να κάνεις αναζήτηση σε string. Απλή η strstr επιστρέφει pointer οπότε πρέπει να συνοδευτεί και απο την strpos για να βρεις την θέση που βρέθηκε. Ναι είναι όντως ακριβώς 3 γραμμές κώδικα. Στην λύση που έδωσα παραπάνω απλά έγραψα δικιά μου strstr για ακόμη μεγαλύτερη ταχύτητα...
Νομίζω ότι θα βγαίνατε μέσα στην 3αδα πολύ χαλαρά.
Νομίζω ότι θα βγαίνατε μέσα στην 3αδα πολύ χαλαρά.