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

Virus•Hacker•Kontos · Πέμ Μαρ 18, 2010 9:50 pm

Παντως νομιζω τελικα πως δεν βολευουν οι ετοιμες...
Για δειτε και τη δικια μου λυση:

#include "stdio.h"
short i,i2;
FILE * in_file;
FILE * out_file;
unsigned short in_fn,in_ssn,letternumber=0;
int main()
{
	in_file = fopen ("matrix.in","r");
	out_file = fopen ("matrix.out","w+");
	fscanf(in_file,"%d",&in_fn);
	char stf[in_fn];
	fseek(in_file,1,SEEK_CUR);
	fread (&stf,1,in_fn,in_file);
	fscanf(in_file,"%d",&in_ssn);
	fseek(in_file,1,SEEK_CUR);
	char sts[in_ssn];
	fread (&sts,1,in_ssn,in_file);
	short ltr,ltr2;
        for(i=0;i<in_ssn;i++)					
	{
		ltr=0;
		if(stf[ltr] == sts[i]) // To Prwto gramma einai sosto...
		{
			ltr++; // 2o Gramma
			for(i2=1;i2<in_fn;i2++)
			{
				ltr2 = ltr;
				if(stf[ltr] == sts[i+i2]) // An to ?? Gramma einai iso me to tou arxikou...
				{
					ltr++; // Epomeno gramma
				}				
				if(ltr==in_fn)
				{
					letternumber=i+1;
					fprintf(out_file,"%d\n",letternumber);
					fclose(in_file);
					fclose(out_file);
					return 0;
				}
				if(ltr2 == ltr) //To LTR den anevike, ara dn vrike gramma
				{					
					break;
				}
			}
		}

	}
	fprintf(out_file,"F\n",letternumber);

	fclose(in_file);
	fclose(out_file);
	return 0;
}

Πέμ Μαρ 18, 2010 10:17 pm

Virus•Hacker•Kontos έγραψε:Παντως νομιζω τελικα πως δεν βολευουν οι ετοιμες...
Για δειτε και τη δικια μου λυση:

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

#include "stdio.h"
short i,i2;
FILE * in_file;
FILE * out_file;
unsigned short in_fn,in_ssn,letternumber=0;
int main()
{
	in_file = fopen ("matrix.in","r");
	out_file = fopen ("matrix.out","w+");
	fscanf(in_file,"%d",&in_fn);
	char stf[in_fn];
	fseek(in_file,1,SEEK_CUR);
	fread (&stf,1,in_fn,in_file);
	fscanf(in_file,"%d",&in_ssn);
	fseek(in_file,1,SEEK_CUR);
	char sts[in_ssn];
	fread (&sts,1,in_ssn,in_file);
	short ltr,ltr2;
        for(i=0;i<in_ssn;i++)					
	{
		ltr=0;
		if(stf[ltr] == sts[i]) // To Prwto gramma einai sosto...
		{
			ltr++; // 2o Gramma
			for(i2=1;i2<in_fn;i2++)
			{
				ltr2 = ltr;
				if(stf[ltr] == sts[i+i2]) // An to ?? Gramma einai iso me to tou arxikou...
				{
					ltr++; // Epomeno gramma
				}				
				if(ltr==in_fn)
				{
					letternumber=i+1;
					fprintf(out_file,"%d\n",letternumber);
					fclose(in_file);
					fclose(out_file);
					return 0;
				}
				if(ltr2 == ltr) //To LTR den anevike, ara dn vrike gramma
				{					
					break;
				}
			}
		}

	}
	fprintf(out_file,"F\n",letternumber);

	fclose(in_file);
	fclose(out_file);
	return 0;
}

Με πέρασε η BruteForce?!?

compileGuy · Πέμ Μαρ 18, 2010 10:38 pm

Και μένα με πέρασε

Ίσως τα testcases ήταν " κατάλληλα " για απλούς αλγόριθμους και οι σύνθετοι έκαναν παραπάνω χρόνο ...

Πέμ Μαρ 18, 2010 10:41 pm

compileGuy έγραψε:Και μένα με πέρασε

Ίσως τα testcases ήταν " κατάλληλα " για απλούς αλγόριθμους και οι σύνθετοι έκαναν παραπάνω χρόνο ...

Αχά αυτό εννοούσα

...

kernelpanic · Πέμ Μαρ 18, 2010 10:43 pm

thodoris έγραψε:Απλή η strstr επιστρέφει pointer οπότε πρέπει να συνοδευτεί και απο την strpos για να βρεις την θέση που βρέθηκε.

Δεν υπάρχει strpos στην C, αλλά με μία απλή αφαίρεση δεικτών μπορείς να βρείς τη θέση.

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

char str1[MAX];
char str2[MAX];
char *pos;

//κανε τι θες

pos=strstr(str1,str2);

if(!pos) panic("shit happens.");
else printf("8esh: %d\n",[b]pos-str1[/b]);

ΥΓ1:Λένε πως τουλάχιστον οι συναρτήσεις της string.h είναι γραμμένες σε χειροποίητη assembly, άρα μάλλον είναι ταχύτερες από τις αντίστοιχες σε C.
ΥΓ2:Να και ο κώδιξ μου, έχει μέσα ό,τι δεν πρέπει να κάνει ένας σοβαρός προγραμματιστής:

goto σε C
ανάγνωση text αρχείου σε binary mode
κανένας έλεγχος στην ουρά, μόνο μια and για να ρολάρει
κανένα επεξηγητικό σχόλιο

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

#include"stdio.h"

#define NEWLINE 1

typedef struct{
    short x;
    short y;
}Point;

FILE *io;

int n,m,x,y,area=0;

int i=0,j=0;

char mappa[3001+NEWLINE][3001+NEWLINE];

Point q[16384];
short lvl=1;

char *ptr=&mappa[1][1];

/*
void printout(){
	int i=0;
	for(ptr=&mappa[1][1];i<m;i++,ptr+=3001+NEWLINE)printf("%s",ptr);
	//getchar();
	}
*/
int main(){
	io=fopen("fire.in","rb");
	fscanf(io,"%d %d %d %d",&n,&m,&x,&y);
    printf("%d %d %d %d\n",n,m,x,y);
    fseek(io,NEWLINE,SEEK_CUR);

    for(n+=NEWLINE;i<m;i++,ptr+=3001+NEWLINE)fread(ptr,1,n,io);

	q[0].x=x;
	q[0].y=y;

	for(i=0;i!=lvl;i++,i&=16383){
		Point t=q[i];
		//printf("Trying %d %d %d %d\n",t.x,t.y,i,lvl);getchar();
		if(mappa[t.y][t.x]=='#')goto diplana;
		if(mappa[t.y][t.x]=='.'){
			mappa[t.y][t.x]='#';
			diplana:
			area++;
			t.y--;
			//printf("Proc'ing %d %d\n",t.x,t.y);printout();
			if(mappa[t.y][t.x]=='.'){
				//printf("Caught! %d %d\n",t.x,t.y);
				q[lvl]=t;
				mappa[t.y][t.x]='#';
				lvl++;
				lvl&=16383;
				}
			t.y+=2;
			if(mappa[t.y][t.x]=='.'){
				//printf("Caught! %d %d\n",t.x,t.y);
				q[lvl]=t;
				mappa[t.y][t.x]='#';
				lvl++;
				lvl&=16383;
				}
			t.y--;
			t.x++;
			if(mappa[t.y][t.x]=='.'){
				//printf("Caught! %d %d\n",t.x,t.y);
				q[lvl]=t;
				mappa[t.y][t.x]='#';
				lvl++;
				lvl&=16383;
				}
			t.x-=2;
			if(mappa[t.y][t.x]=='.'){
				//printf("Caught! %d %d\n",t.x,t.y);
				q[lvl]=t;
				mappa[t.y][t.x]='#';
				lvl++;
				lvl&=16383;
				}
			}

		}

	freopen("fire.out","w",io);
	fprintf(io,"%d\n",area);
	fclose(io);
	return(0);
	}

ΥΓ3:Έστειλαν αναλυτικό μέηλ σε κανέναν;

Virus•Hacker•Kontos · Πέμ Μαρ 18, 2010 10:54 pm

Μπα, οχι ακομα...

Πιστευω πως θα στειλουν απο αυριο...

Πέμ Μαρ 18, 2010 11:12 pm

kernelpanic έγραψε: ΥΓ2:Να και ο κώδιξ μου, έχει μέσα ό,τι δεν πρέπει να κάνει ένας σοβαρός προγραμματιστής:

goto σε C

ανάγνωση text αρχείου σε binary mode

κανένας έλεγχος στην ουρά, μόνο μια and για να ρολάρει

κανένα επεξηγητικό σχόλιο
ΥΓ3:Έστειλαν αναλυτικό μέηλ σε κανέναν;

Δομημένος Προγραμματισμός δηλαδή

... Πάντως, συγχαρητήρια για τη θέση σου!

Όχι, ούτε σε εμένα έχουν στείλει ακόμα email.

chris · Παρ Μαρ 19, 2010 8:02 pm

Πράγματι πολύ παράξενο να βγεί η απλή bruteforce τόσο μπροστά...!
Όπως και να 'χει, περάσαμε

Τα λέμε στην Αθήνα

kostassite · Παρ Μαρ 19, 2010 10:18 pm

Να και η δικιά μου υποβολη σε c
Πολυ μεγάλη αλλα γρηγορη

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

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

int main (void) {
	FILE *in,*out,*afile;
	in = fopen("fire.in","r");
	out = fopen("fire.out","w");
	afile = fopen("a.out","a");
	
	char den[1002][1002];
	int allx,ally,xenx,xeny,i,flag=0,x,y,sum=1,up,down,tempup,tempdown,right,left,tempright,templeft;
	
	fscanf(in,"%d %d",&allx,&ally);
	fscanf(in,"%d %d",&xenx,&xeny);
	ally--;
	allx--;
	xeny--;
	xenx--;
	for (i=0; i<=ally; i++) {
		fscanf(in,"%s",den[i]);
	}
	
	den[xeny][xenx]= 'k';
	tempup=xeny;
	tempdown=xeny;
	templeft=xenx;
	tempright=xenx;
	
	//na min xekinisei
	if ((den[xeny][xenx+1]== '@')&&(den[xeny][xenx-1]== '@')&&(den[xeny+1][xenx]== '@')&&(den[xeny-1][xenx]== '@')) {
		flag=1;
	}
	
	while (flag==0)	{
		flag=1;
		
		if (tempdown>ally) 
			tempdown=ally;
		down=tempdown;
		
		if (tempup<0) 
			tempup=0;
		up=tempup;
		
		
		
		for (y=up; y<=down; y++) {
			if (templeft<0) 
				templeft=0;
			left=templeft;
			
			if (tempright>allx)
				tempright=allx;
			right=tempright;	
			
			for (x=left; x<=right; x++) {
				x=x+strcspn(&den[y][x], "k");
				
				if (den[y][x]=='k') {
					den[y][x]='e';
					
					if ((den[y][x-1]=='.')&&(x-1>=0)) {
						den[y][x-1] = 'k';
						
						if (x==left)
							templeft--;
						sum++;
						flag=0;
					}
					if ((den[y][x+1]=='.')&&(x+1<=allx)) {
						den[y][x+1] = 'k';
						
						if (x==right)
							tempright++;
						sum++;
						flag=0;
					}
					if ((den[y-1][x]=='.')&&(y-1>=0)) {
						den[y-1][x] = 'k';
						
						if (y==up) 
							tempup--;
						sum++;
						flag=0;
					}
					if ((den[y+1][x]=='.')&&(y+1<=ally)) {
						den[y+1][x] = 'k';
						
						if (y==down) 
							tempdown++;
						sum++;
						flag=0;
					}
				}
			}
		}
		
		
		if (flag==0) {
			flag=1;
			if (tempdown>ally) 
				tempdown=ally;
			down=tempdown;
			
			if (tempup<0) 
				tempup=0;
			up=tempup;
			
			for (y=down; y>=up; y--) {
				if (templeft<0) 
					templeft=0;
				left=templeft;
				
				if (tempright>allx)
					tempright=allx;
				right=tempright;	
				for (x=right; x>=left; x--) {
					
					while ((den[y][x]!='k')&&(x>left)) {
						x--;
					}
					
					if (den[y][x]=='k') {
						den[y][x]='e';
						if ((den[y][x-1]=='.')&&(x-1>=0)) {
							den[y][x-1] = 'k';
							
							if (x==left)
								templeft--;
							sum++;
							flag=0;
						}
						if ((den[y][x+1]=='.')&&(x+1<=allx)) {
							den[y][x+1] = 'k';
							
							if (x==right)
								tempright++;
							sum++;
							flag=0;
						}
						if ((den[y-1][x]=='.')&&(y-1>=0)) {
							den[y-1][x] = 'k';
							
							if (y==up) 
								tempup--;
							sum++;
							flag=0;
						}
						if ((den[y+1][x]=='.')&&(y+1<=ally)) {
							den[y+1][x] = 'k';
							
							if (y==down) 
								tempdown++;
							sum++;
							flag=0;
						}
					}
				}
			}
		}
	}
	
	fprintf(out,"%i\n",sum);
	
	return 0;
}

Σάβ Μαρ 20, 2010 12:58 pm

kostassite έγραψε:Να και η δικιά μου υποβολη σε c
Πολυ μεγάλη αλλα γρηγορη

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

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

int main (void) {
	FILE *in,*out,*afile;
	in = fopen("fire.in","r");
	out = fopen("fire.out","w");
	afile = fopen("a.out","a");
	
	char den[1002][1002];
	int allx,ally,xenx,xeny,i,flag=0,x,y,sum=1,up,down,tempup,tempdown,right,left,tempright,templeft;
	
	fscanf(in,"%d %d",&allx,&ally);
	fscanf(in,"%d %d",&xenx,&xeny);
	ally--;
	allx--;
	xeny--;
	xenx--;
	for (i=0; i<=ally; i++) {
		fscanf(in,"%s",den[i]);
	}
	
	den[xeny][xenx]= 'k';
	tempup=xeny;
	tempdown=xeny;
	templeft=xenx;
	tempright=xenx;
	
	//na min xekinisei
	if ((den[xeny][xenx+1]== '@')&&(den[xeny][xenx-1]== '@')&&(den[xeny+1][xenx]== '@')&&(den[xeny-1][xenx]== '@')) {
		flag=1;
	}
	
	while (flag==0)	{
		flag=1;
		
		if (tempdown>ally) 
			tempdown=ally;
		down=tempdown;
		
		if (tempup<0) 
			tempup=0;
		up=tempup;
		
		
		
		for (y=up; y<=down; y++) {
			if (templeft<0) 
				templeft=0;
			left=templeft;
			
			if (tempright>allx)
				tempright=allx;
			right=tempright;	
			
			for (x=left; x<=right; x++) {
				x=x+strcspn(&den[y][x], "k");
				
				if (den[y][x]=='k') {
					den[y][x]='e';
					
					if ((den[y][x-1]=='.')&&(x-1>=0)) {
						den[y][x-1] = 'k';
						
						if (x==left)
							templeft--;
						sum++;
						flag=0;
					}
					if ((den[y][x+1]=='.')&&(x+1<=allx)) {
						den[y][x+1] = 'k';
						
						if (x==right)
							tempright++;
						sum++;
						flag=0;
					}
					if ((den[y-1][x]=='.')&&(y-1>=0)) {
						den[y-1][x] = 'k';
						
						if (y==up) 
							tempup--;
						sum++;
						flag=0;
					}
					if ((den[y+1][x]=='.')&&(y+1<=ally)) {
						den[y+1][x] = 'k';
						
						if (y==down) 
							tempdown++;
						sum++;
						flag=0;
					}
				}
			}
		}
		
		
		if (flag==0) {
			flag=1;
			if (tempdown>ally) 
				tempdown=ally;
			down=tempdown;
			
			if (tempup<0) 
				tempup=0;
			up=tempup;
			
			for (y=down; y>=up; y--) {
				if (templeft<0) 
					templeft=0;
				left=templeft;
				
				if (tempright>allx)
					tempright=allx;
				right=tempright;	
				for (x=right; x>=left; x--) {
					
					while ((den[y][x]!='k')&&(x>left)) {
						x--;
					}
					
					if (den[y][x]=='k') {
						den[y][x]='e';
						if ((den[y][x-1]=='.')&&(x-1>=0)) {
							den[y][x-1] = 'k';
							
							if (x==left)
								templeft--;
							sum++;
							flag=0;
						}
						if ((den[y][x+1]=='.')&&(x+1<=allx)) {
							den[y][x+1] = 'k';
							
							if (x==right)
								tempright++;
							sum++;
							flag=0;
						}
						if ((den[y-1][x]=='.')&&(y-1>=0)) {
							den[y-1][x] = 'k';
							
							if (y==up) 
								tempup--;
							sum++;
							flag=0;
						}
						if ((den[y+1][x]=='.')&&(y+1<=ally)) {
							den[y+1][x] = 'k';
							
							if (y==down) 
								tempdown++;
							sum++;
							flag=0;
						}
					}
				}
			}
		}
	}
	
	fprintf(out,"%i\n",sum);
	
	return 0;
}

Λίγα σχόλια ρε Κώστα , χάθηκα με τον κώδικά σου ......
Αυτός είναι ο δικός μου :

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

#include <stdio.h>

int main ( void ) {
	FILE *in = fopen ( "fire.in" , "r" ) ;
	FILE *out = fopen ( "fire.out" , "w" ) ;
	int N , M , i , times = 1 , cur = 0 , y[1000001] , x[1000001] ;
	char areas[1003][1003] ;
	
	/*The y and x arrays hold the area from which the fire came*/
	
	/*Reading data*/
	fscanf ( in , "%d %d %d %d" , &N , &M , &x[0] , &y[0] ) ;
	for ( i = 0 ; i < M ; i++ ) {
		fscanf ( in , "%s" , areas[i] ) ;
	}

	y[0]-- ;

	x[0]-- ;
	areas[y[0]][x[0]] = '@' ;
	/*BURN*/
	while ( 1 ) {
		if ( areas[y[cur]][x[cur] + 1] == '.' ) {
			cur++ ;
			y[cur] = y[cur-1] ;
			x[cur] = x[cur-1] + 1 ;
			/*We store the coordinates of the fire we are going to examine now*/

			times++ ;

			areas[y[cur]][x[cur]] = '@' ;
			/*We consider this area a rock-area one since it can't be reburnt*/
			continue ;
		}
		if ( areas[y[cur] + 1][x[cur]] == '.' ) {
			cur++ ;
			y[cur] = y[cur-1] + 1 ;
			x[cur] = x[cur-1] ;

			times++ ;

			areas[y[cur]][x[cur]] = '@' ;
			continue ;
		}
		if ( areas[y[cur]][x[cur] - 1] == '.' ) {
			cur++ ;
			y[cur] = y[cur-1] ;
			x[cur] = x[cur-1] - 1 ;

			times++ ;

			areas[y[cur]][x[cur]] = '@' ;
			continue ;
		}
		if ( areas[y[cur] - 1][x[cur]] == '.' ) {
			cur++ ;
			y[cur] = y[cur-1] - 1 ;
			x[cur] = x[cur-1] ;

			times++ ;

			areas[y[cur]][x[cur]] = '@' ;
			continue ;
		}
		if ( cur == 0 ) break ;
		/*If we reach cur=0 , it means that everything has been burnt
		( everytime an area is burnt and it has COMPLETELY spead the
		fire , we return to the previous area ( next line ) ) */
		cur-- ;
	}
	/*Print*/
	fprintf ( out , "%d\n" , times ) ;
	fclose ( in ) ; fclose ( out ) ;
	return 0 ;
}

userresu · Σάβ Μαρ 20, 2010 4:51 pm

Ανέβασαν τα testcases.
Για το λύκειο, 8 από τα 10 είχαν Μ*Ν<=10.000 και τα 2 που είχαν Μ*Ν=1.000.000 ήταν τελείως απλά

Virus•Hacker•Kontos · Σάβ Μαρ 20, 2010 9:42 pm

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

Συνολική Βαθμολογία: 100
Συνολικός Χρόνος: 0,004

Δεν το πιστευω!!! 0,004 συνολικος χρόνος!!!

Και τωρα τι γινεται, και πως ειναι η 3η φαση? Μου ειπε ο Σωτηρης πληροφοριες, και μαλιστα αρκετες, αλλα πως θα επικοινωνησουν? μεσω τηλεφωνου?

compileGuy · Σάβ Μαρ 20, 2010 10:20 pm

Virus•Hacker•Kontos έγραψε: Και τωρα τι γινεται, και πως ειναι η 3η φαση? Μου ειπε ο Σωτηρης πληροφοριες, και μαλιστα αρκετες, αλλα πως θα επικοινωνησουν? μεσω τηλεφωνου?

Μέσω email γίνεται

Spoiler: show: Συνολική Βαθμολογία: 79
Συνολικός Χρόνος: 0

Τώρα πως γίνεται να παρεις 79 (!!) δεν ξέρω

chris · Κυρ Μαρ 21, 2010 10:54 am

Συνολική Βαθμολογία: 89 (!)
Συνολικός Χρόνος: 0,008
Πως γίνεται να πάρεις 89 ξέρει κανείς;

userresu · Κυρ Μαρ 21, 2010 12:33 pm

Ε προφανώς κάποιο testcase έπιανε 11 και το χασες.

kostassite · Κυρ Μαρ 21, 2010 1:27 pm

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

Time
1-->0
2-->0
3-->0,024
4-->0,008
5-->0
6-->0,004
7-->0,004
8-->0
9-->0
10-->0

Συνολική Βαθμολογία: 100

Συνολικός Χρόνος: 0,04

Να και οι δικοι μου χρονοι

Τελικά πότε είναι η τελική φαση??Παλιά ελεγε 17 Απριλιου. Σημερα είδα 16. Αρα παρασκευη???

Κυρ Μαρ 21, 2010 3:01 pm

kostassite έγραψε:

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

Τελικά πότε είναι η τελική φαση??Παλιά ελεγε 17 Απριλιου. Σημερα είδα 16. Αρα παρασκευη???[/quote]

[quote="info@pdp.gr"]Συνολική Βαθμολογία: 67
Συνολικός Χρόνος: 0
[/quote]
Χεχε τουλάχιστον χωρίς πολύ κούραση πάω Γ φάση.  :) 

Παιδιά, να περιμένετε ότι θα είναι κάαπου εκεί, 16, 17 Απρίλη, αλλά λογικά ακόμα δεν έχουν προγραμματιστεί όλα από την ΟΕ. Πιστεύω θα μας ειδοποιήσουν με email ή θα μας τηλεφωνήσουν για τις λεπτομέρειες.

Μέχρι τότε ας προετοιμαστούμε όσο μπορούμε  ;) 

thetrojan01

kostassite · Κυρ Μαρ 21, 2010 7:34 pm

thetrojan01 έγραψε: Μέχρι τότε ας προετοιμαστούμε όσο μπορούμε

Δυστυχως δε υπαρχει χρόνος για προετοιμασία. Έρχονται πανελλήνιες...

Δευ Μαρ 22, 2010 1:21 am

kostassite έγραψε:
thetrojan01 έγραψε: Μέχρι τότε ας προετοιμαστούμε όσο μπορούμε
Δυστυχως δε υπαρχει χρόνος για προετοιμασία. Έρχονται πανελλήνιες...

Όταν το έγραφα σκεπτόμουν κυρίως τους μαθητές Γυμνασίου...
Καλή επιτυχία στη Γ λυκείου! Κουράγιο...