Editorial for Need For Speed
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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.
Comments