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.

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

Please read the guidelines before commenting.


There are no comments at the moment.