Hướng dẫn giải của Chocolate Buying
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=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; }
Bình luận
không biết là mình có thể thay những code mẫu này bằng việc nêu ý tưởng được không ạ? Đọc code khó hiểu qué