Hướng dẫn giải của Need For Speed
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const maxn=10010; ep=0.000000001; var n,ff,mm,r,l,last,x:longint; re:real; f,m,d:array[0..maxn] of longint; dau:array[0..maxn] of boolean; procedure sort(l,r:longint); var i,j,x,y,t:longint; begin i:=l; j:=r; x:=f[(i+j) shr 1]; y:=m[(i+j) shr 1]; repeat while f[i]*y>m[i]*x do i:=i+1; while f[j]*y<m[j]*x do j:=j-1; if i<=j then begin t:=f[i]; f[i]:=f[j]; f[j]:=t; t:=m[i]; m[i]:=m[j]; m[j]:=t; t:=d[i]; d[i]:=d[j]; d[j]:=t; i:=i+1; j:=j-1; end; until i>j; if i<r then sort(i,r); if l<j then sort(l,j); end; procedure rf; var i:longint; begin read(ff,mm,x); n:=0; for i:=1 to x do begin inc(n); read(f[n],m[n]); d[n]:=i; if ff*m[n]>=f[n]*mm then dec(n); end; sort(1,n); end; procedure pr; var i,j,k,cm,cf,z:longint; begin re:=ff/mm; r:=mm; cm:=0; cf:=0; for k:=1 to n do begin cm:=cm+m[k]; cf:=cf+f[k]; if ((abs((ff+cf)/(mm+cm)-re)<=ep) and (mm+cm<r)) or ((ff+cf)/(mm+cm)-re>ep) then begin re:=(ff+cf)/(mm+cm); r:=mm+cm; l:=k; end; end; for i:=1 to l do dau[d[i]]:=true; if l=0 then writeln('NONE') else for i:=1 to x do if dau[i] then writeln(i); end; begin rf; pr; end.
Code mẫu của happyboy99x
#include<cstdio> #include<algorithm> #include<vector> using namespace std; class component { public: long long f, m; int id; component(): f(0), m(0), id(0) {}; component(long long f, long long m, int id): f(f), m(m), id(id) {} bool operator < (const component & o) const { return f * o.m > m * o.f; } }; component car; vector<component> cpns; int main() { int f, m, n; scanf("%d%d%d", &f, &m, &n); car = component(f, m, 0); for(int i = 1; i <= n; ++i) { scanf("%d%d", &f, &m); cpns.push_back(component(f, m, i)); } sort(cpns.begin(), cpns.end()); vector<int> ans; for(typeof(cpns.begin()) it = cpns.begin(); it != cpns.end(); ++it) { if(*it < car) { ans.push_back(it->id); car.f += it->f; car.m += it->m; } } if(!ans.empty()) { sort(ans.begin(), ans.end()); for(vector<int>::iterator it = ans.begin(); it != ans.end(); ++it) printf("%d\n", *it); } else puts("NONE"); return 0; }
Code mẫu của ladpro98
program sboost; uses math; const fi=''; type part=record f,m,order:longint; rate:real; end; var a:array[1..10001] of part; f,m,n,d:longint; aa:real; res:array[1..10001] of longint; procedure input; var inp:text; i:longint; begin assign(inp,fi); reset(inp); readln(inp,f,m,n); for i:=1 to n do begin readln(inp,a[i].f,a[i].m); a[i].rate:=a[i].f/a[i].m; a[i].order:=i; end; close(inp); end; procedure swap(i,j:longint); var t:part; begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end; procedure sort(l,r:longint); var i,j:longint; p:real; begin if l>=r then exit; p:=a[random(r-l+1)+l].rate; i:=l;j:=r; repeat while a[i].rate>p do inc(i); while a[j].rate<p do dec(j); if i<=j then begin if i<j then swap(i,j); inc(i);dec(j); end; until i>j; sort(l,j);sort(i,r); end; procedure sort2(l,r:longint); var i,j,t:longint; p:real; begin if l>=r then exit; p:=a[res[random(r-l+1)+l]].order; i:=l;j:=r; repeat while a[res[i]].order<p do inc(i); while a[res[j]].order>p do dec(j); if i<=j then begin if i<j then begin t:=res[i]; res[i]:=res[j]; res[j]:=t; end; inc(i);dec(j); end; until i>j; sort2(l,j);sort2(i,r); end; procedure greedy; var i:longint; begin aa:=f/m; d:=0; for i:=1 to n do begin if (f+a[i].f)/(m+a[i].m)>aa then begin inc(d); res[d]:=i; f:=f+a[i].f; m:=m+a[i].m; aa:=f/m; end; end; end; procedure output; var i:longint; begin if d=0 then write('NONE') else begin sort2(1,d); for i:=1 to d do writeln(a[res[i]].order); end; end; begin input; sort(1,n); greedy; output; end.
Code mẫu của RR
#include <iostream> #include <algorithm> #define FOR(i,a,b) for(long i=a; i<=b; i++) #define FORD(i,a,b) for(long i=a; i>=b; i--) #define F first #define S second #define MP make_pair #define MAXN 10111 using namespace std; pair<pair<double,long>,pair<long long,long long> > a[MAXN]; long long mm,ff,m[MAXN],f[MAXN]; long ok[MAXN],n; int main() { // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); scanf("%lld %lld %ld",&ff,&mm,&n); FOR(i,1,n) { scanf("%lld %lld",&a[i].S.F,&a[i].S.S); a[i].F.F=a[i].S.F/a[i].S.S; a[i].F.S=i; } sort(a+1,a+n+1); FORD(i,n,1) if (mm*(ff+a[i].S.F)>ff*(mm+a[i].S.S)) { ok[a[i].F.S]=1; mm+=a[i].S.S; ff+=a[i].S.F; } long res=0; FOR(i,1,n) res+=ok[i]; if (!res) { printf("NONE\n"); return 0; } FOR(i,1,n) if (ok[i]) printf("%ld\n",i); return 0; }
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> void sort(int min,int max,double a[],int b[]) { int i=min; int j=max; double r=a[(min+max)/2]; while(i<=j) { while(a[i]>r) i++; while(a[j]<r) j--; if(i<=j) { double temp=a[j]; a[j]=a[i]; a[i]=temp; int tem=b[j]; b[j]=b[i]; b[i]=tem; i++; j--; } } if(j>min) sort(min,j,a,b); if(i<max) sort(i,max,a,b); } void sort1(int min,int max,int a[],int b[]) { int i=min; int j=max; int r=b[(min+max)/2]; while(i<=j) { while(b[i]<r) i++; while(b[j]>r) j--; if(i<=j) { int temp=a[j]; a[j]=a[i]; a[i]=temp; temp=b[j]; b[j]=b[i]; b[i]=temp; i++; j--; } } if(j>min) sort1(min,j,a,b); if(i<max) sort1(i,max,a,b); } main() { int m[10002],b[10002],c[10002],M,n,so; long long f[10002],F; double a[10002]; scanf("%lld %d %d",&F,&M,&n); for(int i=1;i<=n;i++) { scanf("%lld %d",&f[i],&m[i]); b[i]=i; a[i]=f[i]*1./m[i]; } //for(int i=1;i<=n;i++) // printf("%lf %d ",a[i],b[i]); sort(1,n,a,b); //for(int i=1;i<=n;i++) // printf("%lf %d ",a[i],b[i]); int u=1,v=1; int t=1; while(t<=n) { if(F*m[b[t]]<f[b[t]]*M) { F=F+f[b[t]]; M=M+m[b[t]]; t++; } else break; } t--; if(t==0) printf("NONE"); else { sort1(1,t,c,b); for(int i=1;i<=t;i++) printf("%d\n",b[i]); } // getch(); }
Code mẫu của ll931110
{ ID: ll9311102 PROB: sboost LANG: PASCAL } {$N+} program sboost; const input = ''; output = ''; maxn = 13000; maxv = 2 * 1e6; eps = 1e-10; var fi,fo: text; f,m,a: array[0..maxn] of extended; res: extended; n,cc: longint; procedure openfile; begin assign(fi, input); reset(fi); assign(fo, output); rewrite(fo); end; procedure closefile; begin close(fo); close(fi); end; procedure init; var i: longint; begin readln(fi, f[0], m[0], n); for i := 1 to n do readln(fi, f[i], m[i]); end; function ok(x: extended): boolean; var i: longint; tot: extended; begin for i := 0 to n do a[i] := f[i] - x * m[i]; tot := a[0]; for i := 1 to n do if a[i] > 0 then tot := tot + a[i]; ok := (tot >= -eps); end; procedure solve; var inf,sup,med: extended; begin inf := f[0]/m[0]; res := inf; sup := maxv; while sup - inf > eps do begin med := (inf + sup)/2; if ok(med) then begin res := med; inf := med; end else sup := med; end; end; procedure trace(x: extended); var i: longint; begin for i := 1 to n do a[i] := f[i] - x * m[i]; cc := 0; for i := 1 to n do if a[i] > 0 then inc(cc); end; procedure printresult; var i: longint; begin trace(res); if cc = 0 then writeln(fo, 'NONE') else for i := 1 to n do if a[i] > 0 then writeln(fo, i); end; begin openfile; init; solve; printresult; closefile; end.
Bình luận