ens-ulm-1

google hashcode 2014 source for team ens-ulm-1
git clone https://a3nm.net/git/ens-ulm-1/
Log | Files | Refs

commit b03e4a743a584f068d0cc6b9ce0075b58fa9767e
parent be72025727f3b4a16d933af4c10f3e664c3041b6
Author: Marc Jeanmougin <marc@jeanmougin.fr>
Date:   Sat,  5 Apr 2014 15:51:30 +0200

plop

Diffstat:
contest/mc/mc2.cpp | 78++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------
1 file changed, 72 insertions(+), 6 deletions(-)

diff --git a/contest/mc/mc2.cpp b/contest/mc/mc2.cpp @@ -1,16 +1,53 @@ -#include "lecture.cpp" +#include "../louis/louis.cpp" +#include "prune.cpp" vector<int> sortie[8]; +int choose(vector<int> sss,vector<bool> eee,int pt){ +// return rand()%(adj[pt].size()); + vector<int> p(10,0); + int somme=0; + for(int aaaa=0;aaaa<adj[pt].size();aaaa++){ + if(eee[id_arete[make_pair(pt,adj[pt][aaaa])]])p[aaaa]=1; + else p[aaaa]=10000/(sss[adj[pt][aaaa]])*(sss[adj[pt][aaaa]]); + //else if(sss[adj[pt][aaaa]])p[aaaa]=200; +// else p[aaaa]=10000; + somme+=p[aaaa]; + } + int aaaa=rand() % somme; + int target=0; + int cumul=0; + + for(int i=0;i<adj[pt].size();i++){ + + if(aaaa >= cumul && aaaa < cumul+p[i]) return i; + + cumul+=p[i]; + } +printf("NON\n"); +} + + + +void completion_hasard(int t, int i,vector<int> sss,vector<bool> eee){ + + -void completion_hasard(int t, int i){ int pt=sortie[i][sortie[i].size()-1]; while(true){ - int d=rand()%(adj[pt].size()); +// int d=rand()%(adj[pt].size()); + +int d=choose(sss,eee,pt); +if(d>=adj[pt].size()) printf("NON %d %d\n",d,adj[pt].size()); + +// + int ar=id_arete[make_pair(pt,adj[pt][d])]; if(t+cout[ar]>t_autorise) break; t+=cout[ar]; + eee[ar]=true; + sss[pt]+=1; sortie[i].push_back(adj[pt][d]); pt=adj[pt][d]; } @@ -22,31 +59,60 @@ void completion_hasard(int t, int i){ int main(){ srand(time(NULL)); lecture_entree(); - +init_use(); printf("%d\n",n_vehicules); int bsol=0; vector<int> best_sol[8]; -for(int test=0;test<1000;test++){ +for(int test=0;test<100;test++){ +vector<int> sss(12000,1); +vector<bool> eee(18000,false); for(int i=0;i<n_vehicules;i++){ sortie[i].clear(); int pt=s_depart; sortie[i].push_back(s_depart); - completion_hasard(0,i); + completion_hasard(0,i,sss,eee); } int aaa=score_solution(sortie); if( aaa > bsol){ for(int i=0;i<n_vehicules;i++)best_sol[i]=sortie[i]; bsol=aaa;fprintf(stderr,"%d\n",aaa);} } + + + +vector<int> sortiesuivante[8]; +vector<int> bs2[8]; + +fprintf(stderr,"pruning\n"); +prune(best_sol,sortiesuivante); +fprintf(stderr,"pruned\n"); + +for(int i=0;i<n_vehicules;i++)bs2[i]=complete(sortiesuivante[i]); + +fprintf(stderr,"completed %d\n",score_solution(bs2)); + + +//affichage de la solution +/* +for(int i=0;i<n_vehicules;i++){ + printf("%d\n",bs2[i].size()); + for(int j=0;j<bs2[i].size();j++){printf("%d\n",bs2[i][j]);} +} +*/ + for(int i=0;i<n_vehicules;i++){ printf("%d\n",best_sol[i].size()); for(int j=0;j<best_sol[i].size();j++){printf("%d\n",best_sol[i][j]);} } + + + + }