Σελίδα 1 από 2

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

Δημοσιεύτηκε: Δευ Φεβ 08, 2010 12:19 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

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

Δημοσιεύτηκε: Δευ Φεβ 08, 2010 12:26 am
από 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;
}

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

Δημοσιεύτηκε: Δευ Φεβ 08, 2010 12:27 am
από Rania
61η :lol:

Σταθη εγω τα σχολια μου τα ειχα σε greeklish. :P
Ποτε θα βγει η ασκηση της δευτερης φασης;

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

Δημοσιεύτηκε: Δευ Φεβ 08, 2010 12:36 am
από stathis
Rania έγραψε:Σταθη εγω τα σχολια μου τα ειχα σε greeklish. :P
Ποτε θα βγει η ασκηση της δευτερης φασης;
Greeklish = fail
Βγήκε ήδη

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

Δημοσιεύτηκε: Δευ Φεβ 08, 2010 12:39 am
από 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;
}

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

Δημοσιεύτηκε: Δευ Φεβ 08, 2010 12:47 am
από Rania
Μουαχαχα, σε περασα με pascal ΚΑΙ bubblesort! :lol:

Εριξα μια ματια στην ασκηση της β' φασης και ζαλιστηκα. Καληνυχτα παιδες, και συγχαρητηρια μας :D

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

Δημοσιεύτηκε: Δευ Φεβ 08, 2010 12:51 am
από stathis
Rania έγραψε:Μουαχαχα, σε περασα με pascal ΚΑΙ bubblesort! :lol:
I hate bubble sort. Θεωρώ πως είναι υπερβολικά πολύπλοκη χωρίς λόγο, μόνο και μόνο για να έχει την ίδια πολυπλοκότητα με την Insertion sort.

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

Δημοσιεύτηκε: Δευ Φεβ 08, 2010 12:52 am
από chris
10ος μαζί με τον trojan! Αρκετά ευχαριστημένος, θα ποστάρω την λύση μου μόλις την βρώ. Αν την βρώ. ;)

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

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

EDIT:
Βρε Στάθη, insertion? :P
Πάρε μια έτοιμη quicksort από την stl!

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

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

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

Δημοσιεύτηκε: Δευ Φεβ 08, 2010 3:37 pm
από Stonos
Συγχαρητήρια σε όσους περάσανε! :D

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

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

Δημοσιεύτηκε: Δευ Φεβ 08, 2010 3:54 pm
από 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;
}

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

Δημοσιεύτηκε: Δευ Φεβ 08, 2010 4:16 pm
από kostassite
εγω βγήκα 72ος. θα δώ τις λύσεις σας να δω τι διαφορά έχουν(μαλλον μεγάλη) γιατι ως πρωτάρης, αφου δούλευε το άφησα.Στη δεύτερη μου φαίνετε καλή η λύση μου πάντως :lol:

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

Δημοσιεύτηκε: Δευ Φεβ 08, 2010 4:58 pm
από chris
Stonos έγραψε:Συγχαρητήρια σε όσους περάσανε! :D

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

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

Δημοσιεύτηκε: Δευ Φεβ 08, 2010 5:00 pm
από 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;
}

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

Δημοσιεύτηκε: Δευ Φεβ 08, 2010 8:06 pm
από stathis
chris, είχα σκοπό να την φτιάξω κάποια στιγμή, αλλά αυτή η στιγμή ποτέ δεν ήρθε - εξ ου και τα workaround comments XD
Βασικά είναι quick sort+insertion sort

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

Δημοσιεύτηκε: Δευ Φεβ 08, 2010 11:33 pm
από 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! ;)
(Νομίζω ότι αυτό έστειλα...)

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

Δημοσιεύτηκε: Τετ Φεβ 10, 2010 1:16 pm
από 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

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

Δημοσιεύτηκε: Τετ Φεβ 10, 2010 1:53 pm
από 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

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

Δημοσιεύτηκε: Τετ Φεβ 10, 2010 3:04 pm
από 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;
}

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

Δημοσιεύτηκε: Τετ Φεβ 10, 2010 5:03 pm
από 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