Hướng dẫn giải của VOI 08 Bài 3 - Quà tết
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 fi=''; fo=''; base=1000000000; dg=9; type bignum=array[0..100] of longint; var n:longint; x,y:qword; z,h:bignum; p:array[0..41] of qword; procedure rf; begin read(n,x,y); y:=p[n]-1-y; end; procedure wf; var i,j,t:longint; s:string; begin for i:=z[0] downto 1 do begin if i<z[0] then begin str(z[i],s); t:=length(s); for j:=t+1 to dg do write(0); end; write(z[i]); end; write(' '); end; procedure plus(var h:bignum); var i,mem:longint; begin mem:=0; for i:=1 to h[0] do begin h[i]:=h[i] shl 1+mem; if h[i]>=base then begin mem:=1; h[i]:=h[i]-base; end else mem:=0; end; if mem>0 then begin inc(h[0]); h[h[0]]:=1; end; end; procedure minus(var a:bignum;b,c:bignum); var i,mem:longint; begin mem:=-1; for i:=1 to b[0] do begin a[i]:=b[i]-c[i]-mem; if a[i]<0 then begin a[i]:=a[i]+base; mem:=1; end else mem:=0; end; a[0]:=b[0]; while (a[a[0]]=0) and (a[0]>1) do dec(a[0]); end; procedure pr; var i:longint; begin fillchar(z,sizeof(z),0); fillchar(h,sizeof(h),0); z[0]:=1; z[1]:=1; h[0]:=1; h[1]:=1; for i:=n downto 1 do begin plus(h); if x>=p[i-1] then begin minus(z,h,z); x:=p[i]-1-x; end; plus(h); if y>=p[i-1] then begin minus(z,h,z); y:=p[i]-1-y; end; end; minus(z,h,z); wf; end; procedure init; var i:longint; begin p[0]:=1; for i:=1 to 41 do p[i]:=p[i-1]*2; end; begin assign(input,fi); reset(input); assign(output,fo); rewrite(output); init; rf; pr; read(x,y); y:=p[n]-1-y; pr; close(input); close(output); end.
Code mẫu của ladpro98
#include <cstring> #include <vector> #include <list> #include <map> #include <set> #include <queue> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <climits> #include <cstdlib> #include <ctime> #include <memory.h> #include <cassert> #define FOR(i, a, b) for(int i = (a); i < (b); i++) #define REP(i, a, b) for(int i = (a); i <=(b); i++) #define FORD(i, a, b) for(int i = (a); i > (b); i--) #define REPD(i, a, b) for(int i = (a); i >=(b); i--) #define TR(it, a) for(typeof((a).begin()) it = (a).begin(); it != (a).end(); ++it) #define RESET(a, v) memset((a), (v), sizeof((a))) #define SZ(a) (int((a).size())) #define ALL(a) (a).begin(), (a).end() #define PB push_back #define MP make_pair #define LL long long #define LD long double #define II pair<int, int> #define X first #define Y second #define VI vector<int> const int BASE = 10000; const int LEN = 4; using namespace std; typedef VI big; void fix(big &a) { a.PB(0); FOR(i, 0, SZ(a) - 1) { a[i + 1] += a[i] / BASE; a[i] %= BASE; if (a[i] < 0) {a[i] += BASE; a[i + 1]--;} } while (SZ(a) > 1 && a.back() == 0) a.pop_back(); } void operator += (big &a, big &b) { a.resize(max(SZ(a), SZ(b))); FOR(i, 0, SZ(b)) a[i] += b[i]; fix(a); } void operator -= (big &a, big &b) {FOR(i, 0, SZ(b)) a[i] -= b[i]; fix(a);} big operator + (big a, big b) {a += b; return a;} big operator - (big a, big b) {a -= b; return a;} LL lim, p, q, u, v; big POW[100]; big ans(int k, LL x, LL y, big pos) { if (k == 0) return pos; big h = POW[lim - k << 1]; LL mid = 1ll << (k - 1); bool uu = x < mid, ll = y < mid; if (ll && uu) return ans(k - 1, x, mid - 1 - y, h - pos + big(1, 1)); if (!ll && uu) return ans(k - 1, x, y - mid, h + h + h + pos); if (ll && !uu) return ans(k - 1, mid * 2 - x - 1, mid - 1 - y, h + pos); return ans(k - 1, mid * 2 - x - 1, y - mid, h + h + h - pos + big(1, 1)); } ostream& operator << (ostream& cout, const big &a) { printf("%d", a.back()); REPD(i, SZ(a) - 2, 0) printf("%04d", a[i]); return cout; } int main() { POW[0] = big(1, 1); FOR(i, 1, 100) POW[i] = POW[i - 1] + POW[i - 1]; cin >> lim >> p >> q >> u >> v; cout << ans(lim, p, q, big(1, 1)) << ' ' << ans(lim, u, v, big(1, 1)); return 0; }
Code mẫu của RR
#include <iostream> #include <algorithm> #define FOR(i,a,b) for(int i=a; i<=b; i++) #define FORD(i,a,b) for(int i=a; i>=b; i--) #define ll long long #define P pair<ll,ll> #define F first #define S second #define BASE 1000000000000000LL #define LBASE 15 using namespace std; int debug=0; int k; P lt2[80],i,j,one; P operator + (P a,P b) { P c; c.S = a.S + b.S; int nho; if (c.S>=BASE) { nho=1; c.S-=BASE; } else nho=0; c.F = a.F + b.F + nho; return c; } P operator - (P a,P b) { P c; c.S = a.S - b.S; int nho; if (c.S>=0) nho=0; else { nho=1; c.S += BASE; } c.F = a.F - b.F - nho; return c; } P operator * (P a,ll k) { P c; c.S = a.S * k; int nho=c.S/BASE; c.S%=BASE; c.F = a.F * k + nho; return c; } void print(P a) { if (a.F) { cout<<a.F; char s[20]; sprintf(s,"%lld",a.S); FOR(i,1,LBASE-strlen(s)) cout<<"0"; } cout<<a.S; } void init() { lt2[0].S = 1; FOR(i,1,80) lt2[i]=lt2[i-1]*2; if (debug) FOR(i,0,80) print(lt2[i]); } void get(int u,P i,P j,P pos) { P res; if (u==0) { print(pos); return ; } if (i<lt2[u-1]) pos = pos+lt2[2*k-2*u]; else { i = lt2[u]-i-one; pos = lt2[2*k - 2*u] + one - pos; } if (j<lt2[u-1]) { j = lt2[u-1]-j-one; pos = lt2[2*k - 2*u +1]+one-pos; } else { pos = pos+lt2[2*k-2*u+1]; j = j - lt2[u-1]; } get(u-1,i,j,pos); } void solve() { P pos; pos.F = 0; pos.S = 1; get(k,i,j,pos); } int main() { init(); cin >>k; i.F = j.F = 0; one.F = 0; one.S = 1; cin >>i.S >>j.S; solve(); cout<<" "; cin >>i.S >>j.S; solve(); return 0; }
Code mẫu của khuc_tuan
import java.io.*; import java.math.*; import java.util.*; public class Main { static int[][] mh = {{0,-1},{1,0},{3,0},{2,-1}}; static int[][] hm = { {0,0,1,0, 0,1,-1,-1}, {1,0,-1,-1, 0,1,-1,-1}, {0,0,1,0, 0,-1,1,0}, {1,0,-1,-1, 0,-1,1,0} }; static long K, u, v, p, q; static BigInteger[] pow2; static void xet(long k, long u, long v, BigInteger vt) { if(k==0) { System.out.println(vt); return; } int t = (u>=(1L<<(k-1))) ? 1 : 0; if(v>=(1L<<(k-1))) t += 2; BigInteger nvt = BigInteger.ZERO; for(int tt=0;tt<mh[t][0];++tt) nvt = nvt.add(pow2[(int)((K-k)*2)]); if(mh[t][1]==-1) nvt = nvt.add(pow2[(int)(K-k)*2]).add(pow2[0]).subtract(vt); else nvt = nvt.add(vt); xet( k-1, hm[t][0]*(1L<<k)+hm[t][1]*(1L<<(k-1))+hm[t][2]*u+hm[t][3], hm[t][4]*(1L<<k)+hm[t][5]*(1L<<(k-1))+hm[t][6]*v+hm[t][7], nvt); } public static void main(String[] args) throws Exception { //BufferedReader kb = new BufferedReader(new InputStreamReader(System.in)); Scanner sc = new Scanner(System.in); K = sc.nextLong(); u = sc.nextLong(); v = sc.nextLong(); p = sc.nextLong(); q = sc.nextLong(); pow2 = new BigInteger[100]; pow2[0] = BigInteger.ONE; for(int i=1;i<=80;++i) pow2[i] = pow2[i-1].add(pow2[i-1]); xet( K, u, v, pow2[0]); xet( K, p, q, pow2[0]); } }
Bình luận