Τα αποτελέσματα της Α' φάσης ανακοινώθηκαν

Γενικά θέματα για το διαγωνισμό. Ερωτήσεις, προτάσεις και ό,τι άλλο ταιριάζει.
thodoris
Δημοσιεύσεις: 45
Εγγραφή: Σάβ Σεπ 26, 2009 10:25 am

Τα αποτελέσματα της Α' φάσης ανακοινώθηκαν

Δημοσίευση από thodoris »

http://pdp.gr/default.asp?pid=6&la=1&fid=1

Συγχαρητήρια σε όλα τα παιδιά που έλαβαν μέρος και να ευχηθώ καλή συνέχεια! :D

Ιδού η λύση μου(Βγήκα 4ος)

Είναι ένα διαφορετικό implementation του αλγόριθμου quick sort αρκετά optimized!

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

#include <stdio.h>
#define exch(A,B) { int t[2]; t[0]=A[0]; t[1]=A[1]; A[0] = B[0]; A[1]=B[1]; B[0] = t[0]; B[1]=t[1]; }

void quicksort(int (*a)[2], int l, int r)
{
   int k, i = l-1, j = r, p = l-1, q = r, v = a[r][1], v0 = a[r][0];
   if (r <= l) return;
	
   while(1)
   {
      while (a[++i][1] > v || (a[i][1] == v && a[i][0] < v0) ) ;
      while (v > a[--j][1] || (a[j][1] == v && a[j][0] > v0)) if (j == l) break;
      if (i >= j) break;
      exch(a[i], a[j]);
   }

    exch(a[i], a[r]); j = i-1; i = i+1;
    for (k = l; k < p; k++, j--) exch(a[k], a[j]);
    for (k = r-1; k > q; k--, i++) exch(a[i], a[k]);
    quicksort(a, l, j);
    quicksort(a, i, r);
}

int main() {
	FILE *in = fopen("hydrogen.in", "r");
    int out_arr[10000][2],i,x,y,in_len,out_len = 0;

	fscanf(in, "%d", &in_len);

	for (i = 0; i < in_len; i++)
    {
       fscanf(in,"%d %d",&x,&y);
		if (y==0)
			continue;           //An oi blables einai 0 de tis theloyme...
		out_arr[out_len][0] = x;
		out_arr[out_len][1] = y;
		out_len++;    //Auto tha katametrisei posa tmhmata exoyme. Einai osa eixame stin arxi plhn auta poy einai 0
    }

	fclose(in);

	quicksort(out_arr, 0, out_len-1);

	FILE *out = fopen("hydrogen.out", "w");  //Open output file

	fprintf(out, "%d\r\n", out_len);    //Tmhmata

	for (i = 0; i<out_len; i++)         //Print data!
		fprintf(out, "%d\r\n", out_arr[i][0]);

	fclose(out);
	return 0;
}
Έίχα κάνει και μερικές αλλαγές όμως δεν υπάρχει στο hellenico. Αυτό είναι ένα παλιό backup
stathis
Site Admin
Δημοσιεύσεις: 381
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Τα αποτελέσματα ανακοινώθηκαν

Δημοσίευση από stathis »

Ντρέπομαι. :lol:
Αν, και πολύ μου είναι η 25η θέση για το χρόνο που αφιέρωσα φέτος στην Α' φάση-δηλαδή άντε το πολύ 1-2 ώρες, lol.
Ορίστε κι η λύση μου, έτσι για να τις μαζεύουμε.

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

#include <stdio.h>


typedef struct hydr { int id, damage; } hydr;
hydr hydro[ 10001 ];

void swap( hydr *i, hydr *j )
{
   hydr t = *i;
   *i = *j;
   *j = t;
}

void sort( int p, int r )
{
	if ( p < r )
	{
		int q = part( p, r );
		sort( p, q - 1 );
		sort( q + 1, r );
	}
}

int part( int p, int r )
{
	int x = hydro[ r ].damage;
	int i = p - 1;
	int j;
	for ( j = p; j <= r - 1; j++ )
	{
		if ( hydro[ j ].damage >= x )
		{
			i++;
			swap( &hydro[ i ], &hydro[ j ] );
		}
	}
	swap( &hydro[ i + 1 ], &hydro[ r ] );
	return i + 1;
}

int main( void )
{
	int i, j, k, Total = 0, StationsNum;

	FILE *fin = fopen( "hydrogen.in", "r" );
	fscanf( fin, "%d\n", &StationsNum );
	for ( i = 0; i < StationsNum; i++ )
	{
		fscanf( fin, "%d %d\n", &j, &k );
		if ( k == 0 )
		{
			continue;
		}
		hydro[ Total ].id = j;
		hydro[ Total ].damage = k;
		Total++;
	}
	fclose( fin );

	// This is where the main sorting is done! (:
	sort( 0, Total );
	
	// Workaround -- didn't have too much time to think about it
	for ( i = 0; i < Total; i++ ) {
		for ( j = 0; j < Total; j++ ) {
			if ( hydro[ j ].damage == hydro[ i ].damage
				&& hydro[ j ].id > hydro[ i ].id ) {
				swap( &hydro[ i ], &hydro[ j ] );
			}
		}
	}
	
	FILE *fout = fopen( "hydrogen.out", "w" );
	fprintf( fout, "%d\n", Total );
	for ( i = 0; i < Total; i++ )
	{
		fprintf( fout, "%d\n", hydro[ i ].id );
	}
	fclose( fout );
	
	return 0;
}
Rania
Δημοσιεύσεις: 33
Εγγραφή: Δευ Νοέμ 09, 2009 7:37 pm

Re: Τα αποτελέσματα ανακοινώθηκαν

Δημοσίευση από Rania »

61η :lol:

Σταθη εγω τα σχολια μου τα ειχα σε greeklish. :P
Ποτε θα βγει η ασκηση της δευτερης φασης;
stathis
Site Admin
Δημοσιεύσεις: 381
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Τα αποτελέσματα ανακοινώθηκαν

Δημοσίευση από stathis »

Rania έγραψε:Σταθη εγω τα σχολια μου τα ειχα σε greeklish. :P
Ποτε θα βγει η ασκηση της δευτερης φασης;
Greeklish = fail
Βγήκε ήδη
Άβαταρ μέλους
compileGuy
Δημοσιεύσεις: 218
Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm

Re: Τα αποτελέσματα ανακοινώθηκαν

Δημοσίευση από compileGuy »

Μπράβο σε όλα τα παιδια που πέρασαν ;)
Spoiler: show
75ος!! Ε με την Shell Sort τι περιμένω?? :oops:

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

#include <fstream>
#include <iostream>
#include <stdlib.h>
using namespace std;

#define MAX_N 10000
int ArithTmima [MAX_N];
int SynTmima [MAX_N];

void ShellSort(int a[],int b[],int length)
{
     int i, temp, flag = 1;
     int d = length;
     while( flag || (d > 1))
     {
          flag = 0;       
          d = (d+1) / 2;
          for (i = 0; i < (length - d); i++)
        {
               if (a[i + d] > a[i])
              {
                      temp = a[i + d];   
                      a[i + d] = a[i];
                      a[i] = temp;
                      
                      temp = b[i + d];
                      b[i + d] = b[i];
                      b[i] = temp;
                      flag = 1;                 
              }
              if (a[i+d]==a[i] && b[i+d]<b[i])
              {
                               int tmp=b[i+d];
                               b[i+d]=b[i];
                               b[i]=tmp; 
              }
         }
     }
     return;
}
                              
int main()
{
    ifstream TextIn ("gen.hydrogen.in" ,ios::in );
    ofstream TextOut("hydrogen.out2",ios::out);
    unsigned int N, count=0, times=0; 
    
    TextIn>>N;
    for (int i=0; i<N; i++)
    {
        TextIn>>ArithTmima[i]>>SynTmima[i];
        if (SynTmima[i]!=0)
           count++;
    }
    TextIn.close();
    ShellSort(SynTmima,ArithTmima,N);
    TextOut<<count<<"\n";
    for (int i=0; i<count; i++)
    {
              TextOut<<ArithTmima[i]<<"\n"; 
    }
    TextOut.close();
    return 0;
}
Rania
Δημοσιεύσεις: 33
Εγγραφή: Δευ Νοέμ 09, 2009 7:37 pm

Re: Τα αποτελέσματα ανακοινώθηκαν

Δημοσίευση από Rania »

Μουαχαχα, σε περασα με pascal ΚΑΙ bubblesort! :lol:

Εριξα μια ματια στην ασκηση της β' φασης και ζαλιστηκα. Καληνυχτα παιδες, και συγχαρητηρια μας :D
stathis
Site Admin
Δημοσιεύσεις: 381
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Τα αποτελέσματα ανακοινώθηκαν

Δημοσίευση από stathis »

Rania έγραψε:Μουαχαχα, σε περασα με pascal ΚΑΙ bubblesort! :lol:
I hate bubble sort. Θεωρώ πως είναι υπερβολικά πολύπλοκη χωρίς λόγο, μόνο και μόνο για να έχει την ίδια πολυπλοκότητα με την Insertion sort.
chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Τα αποτελέσματα ανακοινώθηκαν

Δημοσίευση από chris »

10ος μαζί με τον trojan! Αρκετά ευχαριστημένος, θα ποστάρω την λύση μου μόλις την βρώ. Αν την βρώ. ;)

Έκανα μια δική μου quicksort με pivot πρώτο στοιχείο, ήταν η πρώτη και μοναδική μου υποβολή! Νόμιζα ότι το σύστημα έκλεινε την Παρασκευή, και έχω μια μισο-τελειωμένη radixsort αρκετά πιο γρήγορη...

Τέλος πάντων, συγχαρητήρια σε όλους! 8-)

EDIT:
Βρε Στάθη, insertion? :P
Πάρε μια έτοιμη quicksort από την stl!
pman
Δημοσιεύσεις: 419
Εγγραφή: Τρί Φεβ 10, 2009 9:49 pm

Re: Τα αποτελέσματα ανακοινώθηκαν

Δημοσίευση από pman »

15ος βγήκα. Περίμενα πιο πάνω με τέτοια λύση που έδωσα. Ξέρει κανείς πότε θα μας δώσουν τους χρόνους?
Stonos
Δημοσιεύσεις: 5
Εγγραφή: Δευ Φεβ 08, 2010 3:32 pm

Re: Τα αποτελέσματα ανακοινώθηκαν

Δημοσίευση από Stonos »

Συγχαρητήρια σε όσους περάσανε! :D

Εγώ προσωπικά βγήκα ή 4ος ή 9ος (δεν είμαι σίγουρος, γιατί λείπουν μερικοί αριθμοί από την αύξουσα αρίθμηση; Αυτοί που έχουν ίδιο Α/Α να φανταστώ ότι ισοβάθμησαν; Τότε που είναι οι αριθμοί που λείπουν;)
userresu
Δημοσιεύσεις: 191
Εγγραφή: Τρί Δεκ 16, 2008 9:53 pm

Re: Τα αποτελέσματα ανακοινώθηκαν

Δημοσίευση από userresu »

Δίνω και τη δική μου

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

#include <iostream>
#include <fstream>
using namespace std;

int n[10001],v[10001];

void quicksort (int l,int r)
{
    int i=l,j=r,k=v[(l+r)/2],m=n[(l+r)/2];
    
    while (i<=j)
    {
        while (i<=j && (v[i]>k || (v[i]==k && n[i]<m))) ++i;
        while (i<=j && (v[j]<k || (v[j]==k && n[j]>m))) --j;
        
        if (i<=j)
        {
           n[0]=n[i];
           n[i]=n[j];
           n[j]=n[0];
           v[0]=v[i];
           v[i]=v[j];
           v[j]=v[0];
           ++i;
           --j;
        }
    }
    if (l<j) quicksort (l,j);
    if (i<r) quicksort (i,r);
}
           
int main ()
{
    int N;
    int valid;
    int a,b;
    ifstream fin ("hydrogen.in");
    fin >> N;
    valid=0;
    for (int i=1;i<=N;++i)
    {
       fin >> a >> b;
       if (b==0)
       continue;
       
       ++valid;
       n[valid]=a;
       v[valid]=b;
    }

    quicksort(1,valid);
    ofstream fout ("hydrogen.out");
    fout << valid << endl;
    for (int i=1;i<=valid;++i)
    fout << n[i] << endl;
        
    return 0;
}
kostassite
Δημοσιεύσεις: 65
Εγγραφή: Δευ Δεκ 21, 2009 10:21 pm
Επικοινωνία:

Re: Τα αποτελέσματα ανακοινώθηκαν

Δημοσίευση από kostassite »

εγω βγήκα 72ος. θα δώ τις λύσεις σας να δω τι διαφορά έχουν(μαλλον μεγάλη) γιατι ως πρωτάρης, αφου δούλευε το άφησα.Στη δεύτερη μου φαίνετε καλή η λύση μου πάντως :lol:
chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Τα αποτελέσματα ανακοινώθηκαν

Δημοσίευση από chris »

Stonos έγραψε:Συγχαρητήρια σε όσους περάσανε! :D

Εγώ προσωπικά βγήκα ή 4ος ή 9ος (δεν είμαι σίγουρος, γιατί λείπουν μερικοί αριθμοί από την αύξουσα αρίθμηση; Αυτοί που έχουν ίδιο Α/Α να φανταστώ ότι ισοβάθμησαν; Τότε που είναι οι αριθμοί που λείπουν;)
Δεν λείπουν αριθμοί. Απλά αν 3 άτομα ισοβάθμισαν στην θέση 2, τότε θεωρείται πως ισοβάθμισαν στην θέση 2 3 και 4, οπότε οι επόμενοι θα πάνε από την θέση 5 και μετά. ;) Υποθέτω...
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
thanos
Δημοσιεύσεις: 4
Εγγραφή: Τετ Δεκ 09, 2009 12:39 am
Επικοινωνία:

Re: Τα αποτελέσματα ανακοινώθηκαν

Δημοσίευση από thanos »

Ορίστε και η λύση μου.Μία απλή χρήση της quicksort γραμμένο σε C.

Βγήκα 19ος..

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

#include <stdio.h>
#include <stdlib.h>

int compare (const void * a, const void * b) {

    return ( (((int *)b)[1] - ((int *)a)[1]) ? (((int *)b)[1] - ((int *)a)[1]) : (((int *)a)[0] - ((int *)b)[0]));
}

int main(void) {

   FILE *in = fopen("./hydrogen.in","r");
   FILE *out = fopen("./hydrogen.out", "w");
   int p[10000][2];
   int L = 0;
   int C,x,y,i;
   
   fscanf(in, "%d" , &C);
   
   for(i=0;i<C;i++)
   {
	fscanf(in,"%d %d",&x,&y);
        if(y != 0) 
        {
	    p[L][0] = x;
            p[L][1] = y;
            L++;
        }
   }
   
   fclose(in); 

   qsort(p,L,2*sizeof(int),compare); 

   fprintf(out, "%d\n", L);

   for (i = 0; i< L; i++)

	fprintf(out, "%d\n", p[i][0]);

   fclose(out);

   return 0;
}
Faith means not wanting to know what is true."Friedrich Nietze"


http://dudescorner.eu
stathis
Site Admin
Δημοσιεύσεις: 381
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Τα αποτελέσματα ανακοινώθηκαν

Δημοσίευση από stathis »

chris, είχα σκοπό να την φτιάξω κάποια στιγμή, αλλά αυτή η στιγμή ποτέ δεν ήρθε - εξ ου και τα workaround comments XD
Βασικά είναι quick sort+insertion sort
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm

Re: Τα αποτελέσματα της Α' φάσης ανακοινώθηκαν

Δημοσίευση από thetrojan01 »

10ος μαζί με τον Chris!

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

/*
  TASK: hydrogen
  LANG: C++
  CONTESTANT: Loukas Xanthos
*/

#include <stdio.h>
#include <cstdlib>

#define MAX 10001

struct arrays_t {
    int faultperid;
    int idseq;
}arrays[MAX];

int comparator(const void* a, const void* b)
{
    arrays_t *elem1 = (arrays_t *)a;
    arrays_t *elem2 = (arrays_t *)b;
    if(elem1->faultperid > elem2->faultperid) return -1;
    if(elem1->faultperid < elem2->faultperid) return 1;
    if(elem1->faultperid == elem2->faultperid)
    {
        if(elem1->idseq > elem2->idseq) return 1;
        if(elem1->idseq < elem2->idseq) return -1;
        if(elem1->idseq == elem2->idseq) return 0;
    }
}

int main()
{
    int l;
    int C=0, L=0;
    int tmpid=0, tmpfaults=0;
    register int i=0;

    FILE* fp;


    /*---initialization---*/
    for(i=0; i<MAX; i++){ arrays[i].faultperid = 0; arrays[i].idseq = 0;}

    /*---input---*/
    fp=fopen("hydrogen.in","r");

    fscanf(fp, "%d", &C);

    for(i=0; i<C; ++i)
    {
        fscanf(fp, "%d %d", &tmpid, &tmpfaults);

        if(tmpfaults != 0){
            L++;
            arrays[tmpid].faultperid = tmpfaults;
            arrays[tmpid].idseq = tmpid;
        }
    }
    fclose(fp);

    /*---sort the list of faults---*/
    qsort(arrays, MAX, sizeof(arrays_t), comparator);

    /*---output---*/
    fp = fopen("hydrogen.out", "w");
    fprintf(fp, "%d\n", L);

    for(i=0; i < MAX; ++i)
    {
        if(arrays[i].idseq != 0)
            fprintf(fp, "%d\n", arrays[i].idseq);
    }
    fclose(fp);

    return 0;
}

STL FTW! ;)
(Νομίζω ότι αυτό έστειλα...)
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
stathis
Site Admin
Δημοσιεύσεις: 381
Εγγραφή: Κυρ Δεκ 14, 2008 6:01 pm
Τοποθεσία: Αθήνα
Επικοινωνία:

Re: Τα αποτελέσματα της Α' φάσης ανακοινώθηκαν

Δημοσίευση από stathis »

Μου 'ρθε mail με την αναλυτική βαθμολογία. Σύμφωνα με αυτό:

Test cases | Time
1 0
2 0
3 0,008
4 0,008
5 0,02
6 0
7 0,032
8 0,048
9 0,064
10 0,084

Συνολική Βαθμολογία: 100
Συνολικός Χρόνος Εκτέλεσης: 0,264
thanos
Δημοσιεύσεις: 4
Εγγραφή: Τετ Δεκ 09, 2009 12:39 am
Επικοινωνία:

Re: Τα αποτελέσματα της Α' φάσης ανακοινώθηκαν

Δημοσίευση από thanos »

Test cases | Time
1. 0
2. 0
3. 0,004
4. 0,004
5. 0,004
6. 0
7. 0,004
8. 0,004
9. 0,008
10. 0,0012

Συνολική Βαθμολογία: 100
Συνολικός Χρόνος Εκτέλεσης: 0,04
Faith means not wanting to know what is true."Friedrich Nietze"


http://dudescorner.eu
Virus•Hacker•Kontos
Δημοσιεύσεις: 170
Εγγραφή: Πέμ Νοέμ 26, 2009 9:59 pm

Re: Τα αποτελέσματα της Α' φάσης ανακοινώθηκαν

Δημοσίευση από Virus•Hacker•Kontos »

Συγχαριτιρια σε οσπθς περασανε...
Εβγαλα πολυ μικρο χρονο λογο του sort... Και ελεγα να βρω λυση με την quicksort...

Στον 3ο γυρο δεν θα υπαρχει προσβαση στο Ιντερνετ να φανταστω...

Κακως που το ελυσα ετσι το προβλημα... :oops: :oops:
θα το ξαναλυσω με handmade...
Να παραδεχτω οτι δεν μπορουσα να γραψω μονος μου τετοιο κωδικα... :oops: :oops: :oops: :oops: :oops: :oops: :?
Anyway, το εχω πιασει ηδη πιο σοβαρα και τα κανω handmade τον κωδικα...
Παντως καλα τα νεα σημερα που εχω και τη γιορτη μου...
Δεν περιμενα να βγω 4ος...
Χρονοι:
1. 0
2. 0
3. 0
4. 0
5. 0
6. 0
7. 0,004
8. 0,004
9. 0,004
10. 0,008

Λυση

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

#include "stdio.h"
#include "stdlib.h"
#include <iostream>
//#include <algorithm>



// Afto to kommati to vrika sto GOOGLE... :(
int CmpTwoArrays(int *id, int *errors)
{
	if (errors[i] != errors[j])
		return errors[i] - errors[j];
	return id[i] - id[j];
}
// Mexri edw...

short i;

FILE * in_file;
FILE * out_file;
int in_numl;
int out_numl = 0;


int main()
{
	in_file = fopen ("hydrogen.in","r");
	out_file = fopen ("hydrogen.out","w+");
	fscanf (in_file, "%d", &in_numl);

int in_id[in_numl];
int in_er[in_numl];
int num0 = 0;





	for(i = 0; i < in_numl; i++)
	{
		in_er[i] = -1;
		fscanf (in_file, "%d", &in_id[i]);
		fscanf (in_file, "%d", &in_er[i]);

		if(in_er[i] == 0)
			num0++;
	}
	

out_numl = in_numl - num0;


	sort(in_id,in_numl,sizeof(int),CmpTwoArrays(in_id, in_er)); 

	fprintf(out_file,"%d\n",out_numl);

	for (int i=0; i<out_numl; ++i)
    fprintf(out_file,"%d\n",in_id[idx[i]]);

	fclose(in_file);
	return 0;
}
DFS Hole:
Spoiler: show
http://virushackerwhizkid.blogspot.com/ ... ze-it.html
DFS = Deep Freeze System
Είμαι σίγουρος ότι το πιστέψατε.
chris
Δημοσιεύσεις: 528
Εγγραφή: Κυρ Δεκ 28, 2008 9:27 am

Re: Τα αποτελέσματα της Α' φάσης ανακοινώθηκαν

Δημοσίευση από chris »

Test cases

1. 0
2. 0
3. 0
4. 0,004
5. 0,004
6. 0
7. 0,004
8. 0,008
9. 0
10. 0,004

Συνολική Βαθμολογία: 100
Συνολικός Χρόνος Εκτέλεσης: 0,024
Μετα από 397 δημοσιεύσεις, έβαλα και υπογραφή.
Απάντηση