Σελίδα 1 από 1
Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
Δημοσιεύτηκε: Τρί Μαρ 01, 2011 10:36 pm
από thetrojan01
Ο τίτλος τα λέει όλα!
Εγώ είμαι λύκειο, πόσταρα την αναδρομική, ενώ είχα γράψει και μια επαναληπτική:
αναδρομική:
[pastebin]
http://pastebin.com/fQCF2KqF[/pastebin]
επαναληπτική:
[pastebin]
http://pastebin.com/4SgRVjrj[/pastebin]
Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
Δημοσιεύτηκε: Τρί Μαρ 01, 2011 11:28 pm
από ntziris
Να και η δικιά μου λύση (Λύκειο):
[pastebin]
http://pastebin.com/ep8AmZQs[/pastebin]
Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
Δημοσιεύτηκε: Τρί Μαρ 01, 2011 11:41 pm
από 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;
}
Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
Δημοσιεύτηκε: Τετ Μαρ 02, 2011 5:55 pm
από 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);
}
Από κάτω(χαμάληδες) προς τα πάνω(διευθυντές), δεν κοιτάει πίσω
Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
Δημοσιεύτηκε: Τετ Μαρ 02, 2011 11:45 pm
από 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.
Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
Δημοσιεύτηκε: Πέμ Μαρ 03, 2011 1:28 am
από madshockie
Κώδικας: Επιλογή όλων
#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;
}
Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
Δημοσιεύτηκε: Πέμ Μαρ 03, 2011 3:46 pm
από mr.muffin
Tι σημενει στο e-mail που πηρα TL? στο grade?
Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
Δημοσιεύτηκε: Πέμ Μαρ 03, 2011 4:21 pm
από compileGuy
mr.muffin έγραψε:Tι σημενει στο e-mail που πηρα TL? στο grade?
Λογικά σημαίνει "Time Limit"
Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
Δημοσιεύτηκε: Πέμ Μαρ 03, 2011 5:00 pm
από Memas
έπρεπε να χρησιμοποιήσω LongInt και με τόση μνήμη που μου έφαγαν 64 bit έκαστως άντε να τρέξει γρήγορα...
Κώδικας: Επιλογή όλων
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.
Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
Δημοσιεύτηκε: Πέμ Μαρ 03, 2011 5:27 pm
από 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);
}
Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
Δημοσιεύτηκε: Κυρ Μαρ 06, 2011 4:50 am
από 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 με αυτή.