Αποτελέσματα Β φάσης

[kostassite]

μολις ειδα και εγω τα αποτελεσματα.
Περασα 9ος και να φανταστειτε οτι το πρωτο πρόγραμμα σε c που εγραψα ήταν φέτος για τη πρωτη φάση.
Ξερει κανεις πως γίνετε η τρίτη φαση γιατι εμένα με βολεύει να προγραμματίζω σε mac? Κάτι έχω ακούσει για linux.
Συγχαρητήρια σε όλους!!!

[thetrojan01]

Συγχαρητήρια σε όλους! Μόλις πάω στον Desktop μου θα ποστάρω τη λύση μου για το θέμα του γυμνασίου. (Είμαι 12ος)
-----------------------
@kostassite: καλά έχεις ακούσει: http://pdp.gr/default.asp?pid=6&la=1&fid=3
Πέρισυ μας άφησαν αρκετό χρόνο για να εξοικιωθούμε με το περιβάλλον (Gnome + dev. applications (Anjuta, Kate etc) ) και μας είπαν πώς να σετάρουμε τις ρυθμίσεις που αφορούσαν την δικτύωση σωστά.

Δεν υπάρχει σύνδεση με WWW. Ωστόσο (αν δεν με απατάει η μνήμη μου) υπάρχει STL reference.

[chris]

Πέρασα 9ος στο γυμνάσιο , θα δώσω την λύση μου το μεσημέρι.

[thodoris]

Βγηκα 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

[compileGuy]

Συγχαριτήρια σε όλους

Πέρασα και εγω 10ος απο το γυμνάσιο. Πολύ ενδιαφέρον αλγόριθμος για το πρόβλημα του Λυκείου

[thetrojan01]

Ορίστε το προγραμματάκι μου για το θέμα του γυμνασίου. Δεν βασίζεται σε γνωστό αλγόριθμο (απ' όσο ξέρω τουλάχιστον) αν και θα είχα αναπτύξει κάποιον από τους γνωστούς αν δεν βαριόμουνα

Κώδικας: Επιλογή όλων

/* 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;
}

αυτό βρήκα τώρα στο PC μου αν και νομίζω πριν να υποβάλλω τη λύση μου είχα αλλάξει το:

Κώδικας: Επιλογή όλων

                if( strSearch[j] == strDisk[ possible_beg.front() + j ] )
                    continue;
                else
                { 

σε

Κώδικας: Επιλογή όλων

                if( strSearch[j] != strDisk[ possible_beg.front() + j ] ) {

[thodoris]

Βασικά απ όσο ξέρω το πρόβλημα του γυμνασίου λύνεται με μια απλή strstr και strpos. Νομίζω ότι και μόνο με strpos(text,find) τελειώνεις. Και για να αυξήσεις λίγο την ταχύτητα δεν χρησιμοποιείς STL αλλά φιάχνεις δικιά σου. Η strpos βρίσκεται στην lib string.h . Αν δεν υπάρχει τότε αναγκαστικά την φιάχνεις μόνος σου

[thodoris]

Εκανα μια πολύ απλή λύση σε αυτή του γυμνασίου. Δεν ξέρω καν αν παίζει σωστά(με τα 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;
}

[kostassite]

@kostassite: καλά έχεις ακούσει: http://pdp.gr/default.asp?pid=6&la=1&fid=3
Πέρισυ μας άφησαν αρκετό χρόνο για να εξοικιωθούμε με το περιβάλλον (Gnome + dev. applications (Anjuta, Kate etc) ) και μας είπαν πώς να σετάρουμε τις ρυθμίσεις που αφορούσαν την δικτύωση σωστά.

Δεν υπάρχει σύνδεση με WWW. Ωστόσο (αν δεν με απατάει η μνήμη μου) υπάρχει STL reference.

Είμαι χρήστης ubuntu αρκετα χρόνια αλλα με βολεύει καλύτερα το xcode(mac).
Επίσης μπορούμε να έχουμε μαζί κάποια υποπρογράμματα δικά μας? Μαλλον δε γίνετε αλλα μια ερώτηση δε βλάπτει.
Σε ubuntu ποιο πρόγραμμα προτείνετε για c?

[thodoris]

Εγώ στα ubuntu έχω το Geany (sudo apt-get install geany)

[pman]

Εγώ βγήκα 4ος. .

[compileGuy]

@kostassite: καλά έχεις ακούσει: http://pdp.gr/default.asp?pid=6&la=1&fid=3
Πέρισυ μας άφησαν αρκετό χρόνο για να εξοικιωθούμε με το περιβάλλον (Gnome + dev. applications (Anjuta, Kate etc) ) και μας είπαν πώς να σετάρουμε τις ρυθμίσεις που αφορούσαν την δικτύωση σωστά.

Δεν υπάρχει σύνδεση με WWW. Ωστόσο (αν δεν με απατάει η μνήμη μου) υπάρχει STL reference.

Είμαι χρήστης ubuntu αρκετα χρόνια αλλα με βολεύει καλύτερα το xcode(mac).
Επίσης μπορούμε να έχουμε μαζί κάποια υποπρογράμματα δικά μας? Μαλλον δε γίνετε αλλα μια ερώτηση δε βλάπτει.
Σε ubuntu ποιο πρόγραμμα προτείνετε για c?

Το περιβάλλον εργασίας είναι σε linux οπως είπε και ο thetrojan01. Για C γίνεται να γράψει σε Kate και μετα με terminal να κανεις compile με gcc . Αλλιώς μπορείς να χρησιμοποιήσεις τον Anjuta .

[kostassite]

Ευχαριστω θα τα δω και τα δυο το σαββατοκυριακο γιατι εχω και αοδε
Και τα δυο ειναι επιτρεπτα στη 3 φαση??

[thodoris]

Έκανα τεράστια βελτίωση στην λύση του γυμνασίου: Και για τα 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;    
}

[thodoris]

Οπα στην λυση του γυμνασιου το return abs(p - find); κάντε το return abs(p - find + 1); και είμαστε κομπλε

[chris]

@kostassite: καλά έχεις ακούσει: http://pdp.gr/default.asp?pid=6&la=1&fid=3
Πέρισυ μας άφησαν αρκετό χρόνο για να εξοικιωθούμε με το περιβάλλον (Gnome + dev. applications (Anjuta, Kate etc) ) και μας είπαν πώς να σετάρουμε τις ρυθμίσεις που αφορούσαν την δικτύωση σωστά.

Δεν υπάρχει σύνδεση με WWW. Ωστόσο (αν δεν με απατάει η μνήμη μου) υπάρχει STL reference.

Είμαι χρήστης ubuntu αρκετα χρόνια αλλα με βολεύει καλύτερα το xcode(mac).
Επίσης μπορούμε να έχουμε μαζί κάποια υποπρογράμματα δικά μας? Μαλλον δε γίνετε αλλα μια ερώτηση δε βλάπτει.
Σε ubuntu ποιο πρόγραμμα προτείνετε για c?

Το περιβάλλον εργασίας είναι σε linux οπως είπε και ο thetrojan01. Για C γίνεται να γράψει σε Kate και μετα με terminal να κανεις compile με gcc . Αλλιώς μπορείς να χρησιμοποιήσεις τον Anjuta .

Για text-editor/IDE:
Το 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;
}

[Virus•Hacker•Kontos]

Συγχαριτιρια σε ολους, εγω περασα 2ος στο γυμνασιο!!!!!!

Δεν το περιμενα, και ειμαι εντυπωσιασμενος!
Φανταζομαι πρεπει να μαθω πληροφοριες σχετικα με την 3η φαση.

δεν εχω χρονο ομως τωρα, μονο για να δω τα αποτελεσματα μπηκα...
φροντιστιρια...

[thetrojan01]

Βασικά απ όσο ξέρω το πρόβλημα του γυμνασίου λύνεται με μια απλή strstr και strpos. Νομίζω ότι και μόνο με strpos(text,find) τελειώνεις. Και για να αυξήσεις λίγο την ταχύτητα δεν χρησιμοποιείς STL αλλά φιάχνεις δικιά σου. Η strpos βρίσκεται στην lib string.h . Αν δεν υπάρχει τότε αναγκαστικά την φιάχνεις μόνος σου

Πώς στο καλό μου ξέφυγε η strstr ??? Και να φανταστείς ψαχνόμουν με τις συναρτήσεις στην cstring όταν τέλειωσα το γράψιμο της λύσης μου!

[chris]

έλα μου ντε, υπήρχε έτοιμη συνάρτηση, 3 γραμμές πρόγραμμα... -_-

[thodoris]

Η strstr ωστόσο είναι η πιο γρηγόρη συνάρτηση για να κάνεις αναζήτηση σε string. Απλή η strstr επιστρέφει pointer οπότε πρέπει να συνοδευτεί και απο την strpos για να βρεις την θέση που βρέθηκε. Ναι είναι όντως ακριβώς 3 γραμμές κώδικα. Στην λύση που έδωσα παραπάνω απλά έγραψα δικιά μου strstr για ακόμη μεγαλύτερη ταχύτητα...

Νομίζω ότι θα βγαίνατε μέσα στην 3αδα πολύ χαλαρά.