Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
-
- Δημοσιεύσεις: 712
- Εγγραφή: Κυρ Δεκ 21, 2008 2:45 pm
Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
Ο τίτλος τα λέει όλα!
Εγώ είμαι λύκειο, πόσταρα την αναδρομική, ενώ είχα γράψει και μια επαναληπτική:
αναδρομική:
[pastebin]http://pastebin.com/fQCF2KqF[/pastebin]
επαναληπτική:
[pastebin]http://pastebin.com/4SgRVjrj[/pastebin]
Εγώ είμαι λύκειο, πόσταρα την αναδρομική, ενώ είχα γράψει και μια επαναληπτική:
αναδρομική:
[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.
Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
Να και η δικιά μου λύση (Λύκειο):
[pastebin]http://pastebin.com/ep8AmZQs[/pastebin]
[pastebin]http://pastebin.com/ep8AmZQs[/pastebin]
Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
Κώδικας: Επιλογή όλων
#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ος ΠΔΠ)!
Κώδικας: Επιλογή όλων
#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.
99 bugs in the code,
Fix one bug,
Compile again,
104 little bugs in the code.
Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
Καλα η δικια μ η λυση πιο γαμιστερη απο ολες μαζι!! (πλακα κανω φυσικα)
Εξηγηση:
Τον πρωτο που θα διαβασει απο την λιστα θα παει σε αυτον που δειχνει και σε αυτον που δειχνει αυτος που δειχνει... θα συγκρινει το φυλο τους και αναλογα θα προσθεση ή θα αφερεσει 1.
Παρατηρησα οτι οταν ενα male δειχνει σε ενα αλλο male ο αριθμος που θα προσθεθει αφερεθει ειναι ο ιδιος με αυτον του male.
Κώδικας: Επιλογή όλων
#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.
-
- Δημοσιεύσεις: 14
- Εγγραφή: Παρ Δεκ 19, 2008 1:48 pm
- Τοποθεσία: Αθήνα
Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
Κώδικας: Επιλογή όλων
#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ος ΠΔΠ)!
Tι σημενει στο e-mail που πηρα TL? στο grade?
- compileGuy
- Δημοσιεύσεις: 218
- Εγγραφή: Δευ Ιαν 19, 2009 5:39 pm
Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
Λογικά σημαίνει "Time Limit"mr.muffin έγραψε:Tι σημενει στο e-mail που πηρα TL? στο grade?
Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
έπρεπε να χρησιμοποιήσω 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.
- Spoiler: show
-
- Δημοσιεύσεις: 11
- Εγγραφή: Τετ Μαρ 17, 2010 7:20 pm
Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
Λύση Λυκείου (Η λύση που έστειλα δεν χρησιμοποιούσε 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);
}
-
- Δημοσιεύσεις: 2
- Εγγραφή: Πέμ Μαρ 03, 2011 10:18 pm
Re: Ποστάρετε τις λύσεις σας για τη Β φάση (23ος ΠΔΠ)!
Εγώ έκανα μία αναδρομική λύση:
Πήρα 100/100 με αυτή.
Κώδικας: Επιλογή όλων
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.