Editorial for Chocolate Buying


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=100000;
var n:longint;
    x,re:int64;
    p,a:array[1..maxn] of int64;

procedure rf;
var i:longint;
begin
     read(n,x);
     for i:=1 to n do read(p[i],a[i]);
end;

procedure sort(l,r:longint);
var i,j:longint; x,y:int64;
begin
     i:=l; j:=r; x:=p[(i+j) shr 1];
     repeat
           while p[i]<x do i:=i+1;
           while p[j]>x do j:=j-1;
           if i<=j then
           begin
                y:=p[i]; p[i]:=p[j]; p[j]:=y;
                y:=a[i]; a[i]:=a[j]; a[j]:=y;
                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 pr;
var i:longint; t:int64;
begin
     sort(1,n);
     for i:=1 to n do
     begin
          t:=x div p[i];
          if t>a[i] then t:=a[i];
          re:=re+t;
          x:=x-t*p[i];
          if x=0 then break;
     end;
     writeln(re);
end;

begin
     rf;
     pr;
end.

Code mẫu của happyboy99x

#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std;

#define N 100005
typedef long long LL;
int n;
LL b;
pair<LL, LL> a[N];

int main() {
    scanf("%d%lld",&n,&b);
    for(int i = 0; i < n; ++i) scanf( "%lld%lld", &a[i].first, &a[i].second);
    sort(a, a+n); LL res = 0;
    for(int i = 0; i < n; ++i) {
        LL buy = b / a[i].first;
        if( buy > a[i].second ) buy = a[i].second;
        b -= buy * a[i].first;
        if( buy == 0 ) break;
        res += buy;
    }
    printf("%lld\n", res);
    return 0;
}

Code mẫu của ladpro98

program cbuying;
uses    math;
type    int = record
        p:int64;
        c:int64;
        end;
const   fi='';
var     a:array[1..100001] of int;
        n:longint;
        s,res:int64;

procedure swap(i,j:longint);
var     t:int;
begin
        t:=a[i];
        a[i]:=a[j];
        a[j]:=t;
end;

procedure sort(l,r:longint);
var     pivot:int64;
        i,j:longint;
begin
        if l>=r then exit;
        pivot:=a[random(r-l+1)+l].p;
        i:=l;
        j:=r;
        repeat
                while  a[i].p<pivot do inc(i);
                while  a[j].p>pivot 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 process;
var     i:longint;
begin
        sort(1,n);

        i:=1;
        while (i<=n) and ((s div a[i].p)>=a[i].c) do
        begin
                s:=s-a[i].p*a[i].c;
                inc(res,a[i].c);
                inc(i);
        end;
        if i<=n then inc(res,s div a[i].p);
end;

procedure input;
var     inp:text;
        i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n,s);
        for i:=1 to n do
        readln(inp,a[i].p,a[i].c);
        close(inp);
end;

procedure output;
begin
        write(res);
end;

begin
        input;
        process;
        output;
end.

Code mẫu của RR

uses math;
var
  p,c:array[1..100111] of int64;
  n,i:longint;
  res,b,now:int64;

procedure swap(var a,b:int64);
    var
      tmp:int64;
    begin
      tmp:=a; a:=b; b:=tmp;
    end;

procedure sort(l,r:longint);
    var
      i,j:longint;
      mid:int64;
    begin
      i:=l; j:=r; mid:=p[l+random(r-l+1)];
      repeat
        while p[i]<mid do inc(i);
        while p[j]>mid do dec(j);
        if i<=j then
          begin
            swap(p[i],p[j]);
            swap(c[i],c[j]);
            inc(i); dec(j);
          end;
      until i>j;
      if i<r then sort(i,r);
      if l<j then sort(l,j);
    end;

begin
  read(n,b);
  for i:=1 to n do read(p[i],c[i]);
  sort(1,n);

  res:=0;
  for i:=1 to n do
    begin
      now:=min(b div p[i],c[i]);
      b:=b-now*p[i];
      inc(res,now);
    end;

  writeln(res);
end.

Code mẫu của hieult

#include <iostream>

using namespace std;
//#include <conio.h>
long long n,B,a[100001],b[100001];
void quicksort(int l,int r)
{
     if(l>=r) return;
     int i=l;
     int j=r;
     long long x=a[(l+r)/2];//x=A[random(l-r)]
     while(i<=j)
     {
                while(a[i]<x) i++;
                while(a[j]>x) j--;
                if(i<=j)
                {
                        long long temp=a[i];a[i]=a[j];a[j]=temp;
                        temp=b[i];b[i]=b[j];b[j]=temp;
                        i++;j--;
                }
     }
     quicksort(l,j);
     quicksort(i,r);

}

void sort(long long min,long long max,long long a[],long long b[])
{
     long long i=min;
     long long j=max;
     long long r=a[(min+max)/2];
     while(i<=j)
     {
         while(a[i]<r) i++;
         while(a[j]>r) j--;
         if(i<=j)
         {
                 long long 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)
          sort(min,j,a,b);
     if(i<max)
          sort(i,max,a,b);
}

main()
{
     // long long n,B,a[100001],b[100001];

      scanf("%lld %lld",&n,&B);
     // cin>>n>>B;
      for(long long i=1;i<=n;i++)
           scanf("%lld %lld",&a[i],&b[i]);
        // cin>>a[i]>>b[i];
      sort(1,n,a,b);
      long long KQ=0,t=1;
      while(t<=n)
      {
          if(B*1./a[t]>=b[t])
          {
               KQ+=b[t];
               B=B-a[t]*b[t];
               t++;
          }
          else
          {
               KQ=KQ+B/a[t];
               break;
          }
         // printf("%lld\n",KQ);
      }
      cout<<KQ;
      //printf("%lld",KQ);
     // getch();
}

Code mẫu của ll931110

{$R+,Q+}
program CBUYING;
const
  input  = '';
  output = '';
  maxn = 100000;
var
  n: longint;
  b,res: int64;
  p,c: array[1..maxn] of int64;

procedure init;
var
  f: text;
  i: longint;
begin
  assign(f, input);
    reset(f);

  readln(f, n, b);
  for i := 1 to n do readln(f, p[i], c[i]);

  close(f);
end;

procedure sort(l,h: longint);
var
  i,j: longint;
  k,tmp: int64;
begin
  if l >= h then exit;
  i := l;  j := h;  k := p[random(h - l + 1) + l];

  repeat
    while p[i] < k do inc(i);
    while p[j] > k do dec(j);
    if i <= j then
      begin
        if i < j then
          begin
            tmp := p[i];  p[i] := p[j];  p[j] := tmp;
            tmp := c[i];  c[i] := c[j];  c[j] := tmp;
          end;

        inc(i);
        dec(j);
      end;
  until i > j;

  sort(l,j);  sort(i,h);
end;

procedure solve;
var
  i: longint;
  ext: int64;
begin
  res := 0;
  for i := 1 to n do
    begin
      if b div p[i] >= c[i] then ext := c[i] else ext := b div p[i];
      res := res + ext;
      b := b - p[i] * ext;
    end;
end;

procedure printresult;
var
  f: text;
begin
  assign(f, output);
    rewrite(f);
    writeln(f, res);
  close(f);
end;

begin
  init;
  sort(1,n);
  solve;
  printresult;
end.

Code mẫu của skyvn97

#include<algorithm>
#include<cstdio>
#include<iostream>
#define MAX   100100
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define fi   first
#define se   second
using namespace std;
typedef long long ll;
pair<ll,ll> a[MAX];
int n;
ll allow;
void process(void) {
    cin>>n>>allow;
    FOR(i,1,n) cin>>a[i].fi>>a[i].se;
    sort(a+1,a+n+1);
    ll res=0;
    FOR(i,1,n) {
        ll tmp=min(allow/a[i].fi,a[i].se);
        res+=tmp;
        allow-=tmp*a[i].fi;
    }
    cout<<res<<endl;
}
int main(void) {
    ios::sync_with_stdio(false);
    process();
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.