Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!

Γενικά θέματα για το διαγωνισμό. Ερωτήσεις, προτάσεις και ό,τι άλλο ταιριάζει.
Απάντηση
thetrojan01
Δημοσιεύσεις: 712
Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm

Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!

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

Ο τίτλος τα λέει όλα!

Εγώ είμαι λύκειο, πόσταρα την αναδρομική, ενώ είχα γράψει και μια επαναληπτική:

αναδρομική:
[pastebin]http://pastebin.com/fQCF2KqF[/pastebin]

επαναληπτική:
[pastebin]http://pastebin.com/4SgRVjrj[/pastebin]
svyr cercrv an inevrfnv cbyl tvn an gb iyrcrvf nhgb... cvtrar xnzvn ibygn yrj tj.
Άβαταρ μέλους
ntziris
Δημοσιεύσεις: 10
Εγγραφή: Παρ Δεκ 31, 2010 2:08 am
Τοποθεσία: Κρήτη

Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!

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

Να και η δικιά μου λύση (Λύκειο):
[pastebin]http://pastebin.com/ep8AmZQs[/pastebin]
userresu
Δημοσιεύσεις: 191
Εγγραφή: Τρί Δεκ 16, 2008 9:53 pm

Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!

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

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

#include <cstdio>
#include <vector>
typedef long long ll;
using namespace std;

int N,bpos,x;
vector<vector<int> > con(400001);
bool male[400001];
char buf[3610001],c;
ll tot[2];
FILE *fin,*fout;

struct st
{
    int x,y;
}tmp;

int readint ()
{
    x=0;
    while (1)
    {
        c=buf[bpos++];
        if (c>32) x=x*10+c-48;
        else return x;
    }
}

st dfs (int i)
{
    st t=(st){0,0};
    for (vector<int>::iterator J=con[i].begin();J!=con[i].end();++J)
    tmp=dfs(*J),t.x+=tmp.x,t.y+=tmp.y;
    if (male[i]) tot[1]+=t.y,++t.x;
    else tot[0]+=t.x,++t.y;
    return t;
}

int main ()
{
    fin=fopen("company.in","r");
	fout=fopen("company.out","w");
	fread(buf,1,3610000,fin);
    N=readint();
    int tmp,start,i;
    for (i=1;i<=N;++i)
    {
        tmp=readint();
        con[tmp].push_back(i);
        if (!tmp) start=i;
        male[i]=(buf[bpos]=='m'),bpos+=2;
    }
    dfs(start);
    ll res=tot[1]-tot[0];
    fprintf(fout,"%lld\n",res);
    return 0;
}
Άβαταρ μέλους
kernelpanic
Δημοσιεύσεις: 404
Εγγραφή: Κυρ Δεκ 21, 2008 8:16 pm
Τοποθεσία: Αθήνα

Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!

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

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

#include"stdio.h"
#include"assert.h"
#include"stdlib.h"

FILE *io;
int n;

int r_m=0,r_f=0;

int yfist_f[400001];
int yfist_m[400001];
int epipedo[400001];//ierarxias
int proist[400001];
int epom[400001];
char fylo[400001];
int epipeda[400001];
int stoiba[400001];
int sp=0;

char arxeio[5000000];//("x xxxxxx\n")*400000+1000000

void dedomena(){
	int i;
	printf("Ergates: %d\n",n);
	for(i=1;i<=n;i++){
		printf("Proist:%d Fylo:%c Epipedo:%d Yfist_f:%d Yfist_m:%d\n",
			proist[i],fylo[i],epipedo[i],yfist_f[i],yfist_m[i]);
	}
	getchar();
}


void anagnwsh(){
	int i,j,len;

	register int t;

	io=fopen("company.in","r");
	assert(io);

	fseek(io,0,SEEK_END);
	len=ftell(io);
	fseek(io,0,SEEK_SET);
	//printf("%d bytes\n",len);
	fread(arxeio,len,1,io);
	//printf("Text:\n%s",file);

	i=0;
	for(t=0;arxeio[i]>='0';i++){
		t*=10;
		t+=arxeio[i]-'0';
	}
	n=t;
	j=1;

	//i++;
	//i++;

	for(j=1;j<=n;j++){
		for(;arxeio[i]<'0';i++);

		for(t=0;arxeio[i]>='0';i++){
			t*=10;
			t+=arxeio[i]-'0';
		}
		proist[j]=t;

		i++;

		fylo[j]=arxeio[i];

		i++;
		//i++;

	}

}

/*
void anagnwsh(){
	int i;

	io=fopen("company.in","r");
	assert(io);

	fscanf(io,"%d",&n);
	for(i=1;i<=n;i++){
		fscanf(io,"%d %c\n",proist+i,fylo+i);
	}
}
*/

void eggrafh(){
	freopen("company.out","w",io);
	//printf("%d %d %d\n",r_m,r_f,r_m-r_f);
	fprintf(io,"%d\n",r_m-r_f);
	fclose(io);
}

void bale_se_epipeda(int poio,int epip){
	epipedo[poio]=epip;
	epom[poio]=epipeda[epip];
	epipeda[epip]=poio;
}

void ierarxia(){
	int i,j,k;

	for(i=1;i<=n;i++){

		//printf("Ergaths %d\n",i);

		if(epipedo[i])continue;

		//printf("emba8ynsh\n");

		//printf("anabainomen\n");
		for(j=proist[i];!epipedo[j];j=proist[j]){
			if(!j)break;
			//printf("proist: %d\n",j);
			stoiba[sp]=j;
			sp++;
		}

		//printf("katabainomen\n");
		for(j=epipedo[j],k=1;sp;sp--,k++){
			//printf("%d->%d\n",stoiba[sp-1],j+k);
			bale_se_epipeda(stoiba[sp-1],j+k);
		}
		//printf("%d->%d\n",i,j+k);
		bale_se_epipeda(i,j+k);
	}

}

void a8roish(){
	int i,j;

	for(i=n;i;i--){

		for(j=epipeda[i];j;j=epom[j]){
			//printf("Ergaths %d\n",j);

			yfist_f[proist[j]]+=yfist_f[j];
			yfist_m[proist[j]]+=yfist_m[j];

			if(fylo[j]=='f'){
				yfist_f[proist[j]]++;
				r_f+=yfist_m[j];
			}
			else if(fylo[j]=='m'){
				yfist_m[proist[j]]++;
				r_m+=yfist_f[j];
			}
			else{
				for(i=0;i<9;i++)printf("YYYYYYYYY!\n");
				printf("!!!!!!!!!\n");
				exit((int)"YYYYYYYYY!");
			}

		}

	}

}

int main(){
	int i,j,k;

	//getchar();

	anagnwsh();

	//freopen("err.log","w",stdout);

	//dedomena();

	ierarxia();

	a8roish();

	eggrafh();

	//dedomena();

	return(0);
}
Από κάτω(χαμάληδες) προς τα πάνω(διευθυντές), δεν κοιτάει πίσω :)
99 little bugs in the code,
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
mr.muffin
Δημοσιεύσεις: 43
Εγγραφή: Σάβ Νοέμ 20, 2010 11:32 am

Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!

Δημοσίευση από mr.muffin »

Καλα η δικια μ η λυση πιο γαμιστερη απο ολες μαζι!! (πλακα κανω φυσικα)

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


#include <fstream>
#include <iostream>

using namespace std;

int main () {
  
   
ifstream open("company.in");
int times,counter=1,final=0;
open >> times;

char filo[times];
int rank[times];
int suma[times]; 
while(counter<=times)
{
      open >> rank[counter];
      open >> filo[counter];
      suma[counter]=400010;
      counter++;
}

counter=1;
int counter2=1;

while(counter<=times)
{       
     counter2=counter;
     if(filo[counter]==filo[rank[counter]] &&  suma[rank[counter]]!=400010)
     {
      suma[counter]=suma[rank[counter]];
     }
     else
     {
      suma[counter]=0;
       while(rank[counter2]!=0)
       {
    
        if(filo[counter]!=filo[rank[counter2]])
        {
                                             if(filo[rank[counter2]]=='m')
                                               suma[counter]=suma[counter]+1;
                                               else 
                                              suma[counter]=suma[counter]-1;
        }                
                            
                            counter2=rank[counter2];              
    }  
}         
final=suma[counter]+final;
    counter++;  
}
    ofstream save("company.out");
      
                  save << final<< "\n";  
      

    save.close();
    
    return 0;
}
Εξηγηση:
Τον πρωτο που θα διαβασει απο την λιστα θα παει σε αυτον που δειχνει και σε αυτον που δειχνει αυτος που δειχνει... θα συγκρινει το φυλο τους και αναλογα θα προσθεση ή θα αφερεσει 1.
Παρατηρησα οτι οταν ενα male δειχνει σε ενα αλλο male ο αριθμος που θα προσθεθει αφερεθει ειναι ο ιδιος με αυτον του male.
madshockie
Δημοσιεύσεις: 14
Εγγραφή: Παρ Δεκ 19, 2008 1:48 pm
Τοποθεσία: Αθήνα

Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!

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

:idea: :idea: :idea: :idea: :idea:

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

#include<stdio.h>
#include<vector>
#define MAXN 500001
using namespace std;
int N, B[MAXN];
char sex[MAXN];
vector <int> A[MAXN];
int dfs(int x,char s){
	int i;
	if(sex[x]==s) B[x]++;
	for(i=0;i<A[x].size();i++) B[x] += dfs(A[x][i],s);
	return B[x];
}
int main() {
	int i, j, a, S;
	long long f=0,m=0;
	freopen("company.in","r",stdin);
	freopen("company.out","w",stdout);
    scanf("%d", &N);
    for(i=0;i<N;i++){
		scanf("%d %c\n", &a, &sex[i]);
		if(a==0)S = i;
		A[--a].push_back(i);
	}
	dfs(S,'m');for(i=0;i<N;i++)if(sex[i]=='f')f+=B[i];
	for(i=0;i<N;i++)B[i] = 0;
	dfs(S,'f');for(i=0;i<N;i++)if(sex[i]=='m')m+=B[i];	
	printf("%lld\n", m-f);
	return 0;
}
Εικόνα
mr.muffin
Δημοσιεύσεις: 43
Εγγραφή: Σάβ Νοέμ 20, 2010 11:32 am

Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!

Δημοσίευση από mr.muffin »

Tι σημενει στο e-mail που πηρα TL? στο grade?
Άβαταρ μέλους
compileGuy
Δημοσιεύσεις: 218
Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm

Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!

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

mr.muffin έγραψε:Tι σημενει στο e-mail που πηρα TL? στο grade?
Λογικά σημαίνει "Time Limit" ;)
Memas
Δημοσιεύσεις: 87
Εγγραφή: Παρ Δεκ 31, 2010 4:13 pm
Επικοινωνία:

Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!

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

έπρεπε να χρησιμοποιήσω LongInt και με τόση μνήμη που μου έφαγαν 64 bit έκαστως άντε να τρέξει γρήγορα... :lol:

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

program PDP23B;

var
  fin,fout:text;
  boss,z,i,x,y,sum,emp2,r_m,r_f,ar_yf,c:LongInt;
  p,f:char;
  r_c:array[1..400000,1..2] of LongInt;
  am_s:array [1..400000] of integer;
  emp:array [1..400000] of LongInt;

 begin


 assign (fin,'company.in');
 reset (fin);

 assign (fout,'company.out');
 rewrite (fout);

 readln (fin,sum);

 For i:=1 to sum do
  begin
  readln (fin,emp[i],p,f);
  If emp[i] <>0 Then
   begin
      If f='m' Then
      r_c[emp[i],1]:= r_c[emp[i],1]+1
      else
      r_c[emp[i],2]:= r_c[emp[i],2]+1;
      am_s[emp[i]]:= am_s[emp[i]]+1;
    end
   else
   boss:=i;
   end;

   x:=1;
   Repeat

   While am_s[x]<>0 Do
    begin
    x:=x+1;
    If x>sum Then
    x:=1;
    end;

    If am_s[emp[x]]=1 Then
    begin
    r_c[emp[x],1]:=r_c[emp[x],1]+r_c[x,1];
    r_c[emp[x],2]:=r_c[emp[x],2]+r_c[x,2];
    am_s[x]:=-1;
    am_s[emp[x]]:=0;
    end
    else
    Begin
    y:=0;
    i:=0;
    z:=0;
    Repeat
     i:=i+1;

    If emp[x]=emp[i] Then
     Begin
     y:=y+1;
     If am_s[i]=-1 Then
     z:=z+1;
     If am_s[i]=0 Then
      Begin
      r_c[emp[i],1]:=r_c[emp[i],1]+r_c[i,1];
      r_c[emp[i],2]:=r_c[emp[i],2]+r_c[i,2];
      z:=z+1;
      am_s[i]:=-1;
      End;
     End;

    Until y=am_s[emp[x]];

     If z=y Then
     am_s[emp[x]]:=0;
     end;


  Until am_s[boss]=0;


    reset (fin);
    readln (fin,sum);
    For i:=1 to sum do
     begin
     readln (fin,emp2,p,f);
     If f='m' Then
       r_m:=r_m+r_c[i,2]
      else
        r_f:=r_f+r_c[i,1];
     end;


     writeln (fout,r_m-r_f);
      close (fout);
      close (fin);
     halt(0);
 end.
alexandros
Δημοσιεύσεις: 11
Εγγραφή: Τετ Μαρ 17, 2010 7:20 pm

Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!

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

Λύση Λυκείου (Η λύση που έστειλα δεν χρησιμοποιούσε 64-bit int για το αποτέλεσμα):

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

#include <stdio.h>
#include <stdint.h>
#include <list>
#include <stack>
#define MAX 400000
using namespace std;
typedef list<int>::iterator it_t;

struct employee{
	char gender;
	list<int> children;
	int females;
	int males;
	bool visited;
};
int num,boss;
int64_t rm=0,rf=0;

employee emp[MAX];
stack<int> s;

void read_input(){
	freopen("company.in","r",stdin);
	freopen("company.out","w",stdout);
	scanf("%d\n",&num);
	for(int i=0;i<num;++i){
		int supervisor;
		scanf("%d %c\n",&supervisor,&emp[i].gender);
		if (supervisor==0){
			boss=i;
		}
		else{
			emp[supervisor-1].children.push_back(i);
		}
	}
}

void iterative_postorder(){
	s.push(boss);
	while(!s.empty()){
		int n=s.top();
		if (!emp[n].visited){
			for(it_t it=emp[n].children.begin();it!=emp[n].children.end();++it){
				s.push(*it);
			}
			emp[n].visited=true;
		}
		else{
			for(it_t it=emp[n].children.begin();it!=emp[n].children.end();++it){
				emp[n].females+=emp[*it].females;
				emp[n].males+=emp[*it].males;
				if(emp[*it].gender=='f'){
					++emp[n].females;
				}
				else{
					++emp[n].males;
				}
			}
			if(emp[n].gender=='m'){
				rm+=(int64_t)emp[n].females;
			}
			else{
				rf+=(int64_t)emp[n].males;
			}
			s.pop();
		}
	}
}

int main(){
	read_input();
	iterative_postorder();
	printf("%llu\n", rm-rf);
}
dbechrakis
Δημοσιεύσεις: 2
Εγγραφή: Πέμ Μαρ 03, 2011 10:18 pm

Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!

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

Εγώ έκανα μία αναδρομική λύση:

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

program company;
var
   p,N,x,i,r_m,r_f:LongInt;
   input_file,output_file:Text;
   S:string[2];
   R:array[1..400000] of LongInt;
   G:array[0..400000] of boolean;
   M:array[0..400000] of LongInt;
   F:array[0..400000] of LongInt;

procedure Calc(p: LongInt);
   var
      Next: LongInt;
   begin
      Next:=R[p];
      if Next<>0 then
         begin
            if M[Next]+F[Next]=0 then Calc(Next);
            if G[Next]=true then
               begin
                  M[p]:=M[Next]+1;
                  F[p]:=F[Next];
               end
            else
               begin
                  M[p]:=M[Next];
                  F[p]:=F[Next]+1;
               end;
         end
      else
         begin
            M[p]:=0;
            F[p]:=0;
         end;
   end;

begin
   assign(input_file,'company.in');
   reset(input_file);
   readln (input_file,N);
   for i:=1 to N do
      begin
         read(input_file,R[i]);
         read(input_file,S);
         if S[2]='m' then G[i]:=true else G[i]:=false;
      end;
   r_m:=0;
   r_f:=0;
   for i:=1 to N do
      begin
         Calc(i);
         if G[i]=true then r_f:=r_f+F[i] else r_m:=r_m+M[i];
      end;
    assign(output_file,'company.out');
    rewrite(output_file);
    writeln (output_file,r_m-r_f);
    close(input_file);
    close(output_file);
end.
Πήρα 100/100 με αυτή. :mrgreen: :mrgreen:
Απάντηση