2139A — Maple and Multiplication

Idea: installb Preparation: installb,2014CAIS01

If $$$a=b$$$ we need $$$0$$$ steps.

If $$$a$$$ can be divided by $$$b$$$, we only need $$$1$$$ step, which is to multiply $$$b$$$ by $$$\frac{a}{b}$$$. Same for the case when $$$b$$$ can be divided by $$$a$$$.

Otherwise, we need at most $$$2$$$ steps. As both $$$a$$$ and $$$b$$$ are positive integers, we can first multiply $$$a$$$ by $$$b$$$ and then multiply $$$b$$$ by the original value of $$$a$$$. Both number will be equal to $$$a\times b$$$.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int solve(){
    int a,b;
    cin >> a >> b;
    if(a == b) return 0;
    if(a % b == 0 || b % a == 0) return 1;
    return 2;
}
 
int main(){
    ios::sync_with_stdio(false);
    int TC;
    cin >> TC;
    while(TC --){
        cout << solve() << '\n';
    }
    return 0;
}

2139B — Cake Collection

Idea: installb Preparation: installb

The number of cakes collected from an oven depends only on the last time Maple visits it. Therefore, in the optimal strategy, she should visit distinct ovens in the last $$$\min(m,n)$$$ seconds.

Let's think in reverse: suppose we fix an order $$$p_1,\dots,p_n$$$ of the ovens. Then at second $$$m$$$ we visit oven $$$p_1$$$, at second $$$m-1$$$ we visit oven $$$p_2$$$, and so on. For the $$$i$$$-th oven in this order, we collect $$$a_{p_i}\cdot \max(0, m-i+1)$$$ cakes.

To maximize the total number of cakes collected, ovens with larger $$$a_i$$$ should be visited later (i.e., assigned larger multipliers). Thus we sort $$$a$$$ in non-increasing order first.

The final answer is $$$\sum_{i=1}^n a_i \cdot \max(0, m-i+1)$$$.

• Code (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
 
void solve(){
    int n,t;
    cin >> n >> t;
    ll ans = 0;
    vector <int> a(n);
    for(int i = 0;i < n;i ++) cin >> a[i];
    sort(a.begin(),a.begin() + n,greater <int>());
    for(int i = 0;i < n;i ++) ans += 1ll * a[i] * max(0,t - i);
    cout << ans << '\n';
}
 
int main(){
    ios::sync_with_stdio(false);
    int TC;
    cin >> TC;
    while(TC --){
        solve();
    }
    return 0;
}

2138A — Cake Assignment

Idea: wjy666 Preparation: wjy666

Hint: You can backtrack from the final state.

Solution:

Denote the state $$$(a,b)$$$ that indicates Chocola has $$$a$$$ cakes and Vanilla has $$$b$$$ cakes.

After one operation of type $$$1$$$, Vanilla's number of cakes will definitely be at least half of the total, and similarly for operation $$$2$$$. If $$$0 \lt a \lt 2^{k}$$$, then $$$2^{k} \lt b \lt 2^{k+1}$$$, meaning the previous operation must have been type $$$1$$$. Similarly, if $$$0 \lt b \lt 2^{k}$$$, the previous operation must have been type $$$2$$$.

Therefore, you can backtrack from the final state $$$(x,2^{k+1}-x)$$$, until it reaches the initial state $$$(2^k,2^k)$$$.

Now let's analyze how many steps we need to do during the process.

For the state $$$(a, b)$$$, where $$$a, b \neq 0$$$, assume $$$a = i \cdot 2^{p_a}$$$ and $$$b = j \cdot 2^{p_b}$$$, $$$i$$$ and $$$j$$$ are positive odd integers.

Since $$$a + b = 2^{k+1}$$$, it must be true that $$$ 0 \le p_a = p_b \le k$$$ , and after one operation $$$1$$$ or $$$2$$$, both $$$p_a$$$ and $$$p_b$$$ decrease by exactly $$$1$$$.

Therefore, the whole process takes at most $$$k$$$ steps, so we solve the problem with $$$O(tk)$$$ time complexity.

include <bits/stdc++.h>

using namespace std; int main(){ int t; cin>>t; while(t--){ long long k,x,kk; cin>>k>>x; kk=1ll<<k; if (!x||x==kk*2) {cout<<"-1\n"; continue;} long long y=kk*2-x; vector ans; ans.clear(); while(x!=kk){ if (x>y) ans.push_back(2),x-=y,y*=2; else ans.push_back(1),y-=x,x*=2; } cout<<ans.size()<<"\n"; while(!ans.empty()) cout<<ans.back()<<' ',ans.pop_back(); cout<<"\n"; } return 0; }

2138B — Antiamuny Wants to Learn Swap

Idea: tarjen Preparation: installb,tarjen,2014CAIS01

2138C1 — Maple and Tree Beauty (Easy Version)

2138C2 — Maple and Tree Beauty (Hard Version)

Idea: installb Preparation: installb,tarjen,2014CAIS01

2139D — Antiamuny and Slider Movement

Idea: tarjen,StarSilk Preparation: installb,tarjen,StarSilk

2139E1 — Determinant Construction (Easy Version)

Idea: wjy666 Preparation: wjy666

2139E2 — Determinant Construction (Hard Version)

Idea: wjy666 Preparation: wjy666

2139F — Ode to the Bridge Builder

Idea: installb Preparation: installb

For convenience, we mark the targets point and the points on the initial segment with $$$A(0,0),B(1,0),C(p,q)$$$.

The problem asks us to do at most $$$\left\lceil 2|AC|\right\rceil$$$ moves. This constraint is actually not quite usual. We can first show that the theoretical lower bound should be $$$x=\left\lceil |AC|\right\rceil+\left\lceil |BC|\right\rceil−1$$$. We can show we can't get less moves by following: If we have already constructed the final structure, then $$$AC$$$ and $$$BC$$$ should be connected with a path, and we can find a path from $$$A$$$ to $$$C$$$ and a path from $$$B$$$ to $$$C$$$ that don't intersect (except at point $$$C$$$), otherwise the structure can't be built with non-degenerate triangles.

And we have to alternate progressing through two paths every time we construct a triangle, otherwise we must draw a line longer than $$$1$$$. The last triangle will cover both paths, so the number of steps will be decreased by one. The optimal path is two straight segments (which is not always possible).

Case 1.1: We first try some simple strategies. Two triangles can form a parallelogram, so we can connect $$$AC$$$, choose a point $$$D$$$ on $$$AC$$$ which makes $$$|AD|=\frac{|AC|}{\lceil|AC|\rceil}$$$, which is always in range $$$[0.5,1]$$$ when $$$|AC|\ge 1$$$. And from $$$\triangle ADB$$$ we can construct a parallelogram. We draw a line passing $$$D$$$ that is parallel to $$$AB$$$, a line passing $$$B$$$ that is parallel to $$$AC$$$, and they intersects at $$$E$$$. Then we pile up the same parallelogram structure until we reach $$$C$$$. This always works when $$$30^\circ\le\angle CAB\le60^\circ$$$.

Proof: We first prove that all segments has length between $$$0.5$$$ and $$$1$$$. Because we stack the same parallelogram structure, all segments have length equal to $$$AB,BD$$$ or $$$AD$$$. $$$AB$$$ and $$$AD$$$ already meets the requirement. When $$$30^\circ\le\angle CAB\le60^\circ$$$, the length of $$$BD$$$ is at least $$$0.5$$$ as the distance between two parallel lines is at least $$$0.5$$$, and at most $$$1$$$ as $$$AB=1$$$ and $$$\angle CAB$$$ is never the largest angle in $$$\triangle DAB$$$. We can calculate that the number of moves we used is $$$2\left\lceil |AC|\right\rceil-1\le\left\lceil 2|AC|\right\rceil$$$ which matches the requirement (for the last parallelogram we only need one triangle).

Case 1.2: We can change the way we construct parallelograms (with sides $$$AB,BC$$$) and this method always works when $$$30^\circ\le\angle CBx\le60^\circ$$$. The number of moves is $$$\left\lceil2|BC|\right\rceil\le \left\lceil 2|AC|\right\rceil$$$. This case is actually necessary, which will be explained in the following part.

Case 2: If $$$\angle CAB \lt \angle CBx \lt 30^\circ$$$. We first build a point $$$D$$$ which makes $$$AD=1$$$ and $$$\angle DAB=30^\circ$$$ and construct $$$\triangle DAB$$$.

We can show that the constraint is actually easier to meet in this situation, because when $$$\angle CAB \lt \angle CBx \lt 30^\circ$$$, $$$|BC| \lt |AC|-0.5$$$. With this, $$$\left\lceil |AC|\right\rceil+\left\lceil |BC|\right\rceil−1=\left\lceil 2|AC|\right\rceil-1$$$ always holds, allowing us one extra move.

Then we draw a line passing $$$D$$$ parallel to $$$BC$$$. We can show that if $$$\angle DAB=30^\circ$$$ and $$$0\le \angle CAB\le 30^\circ$$$, the distance from $$$D$$$ to line $$$BC$$$ is at least $$$0.5$$$. So all segments with ends on different lines will have length $$$\ge 0.5$$$.

Then we select a point $$$E$$$ on $$$BC$$$, which makes $$$DE=1$$$. We can show that $$$\sqrt{3}-1\le |BE|\le 1$$$ based on some calculations in this case. Then we do a similar parallelogram construction process to $$$C$$$. The total number of moves is $$$2\left\lceil |CE|\right\rceil+2$$$.

There are still two cases here to analyze to prove the number of steps fulfills our requirement. We write $$$|BC|=a+b$$$ where $$$a$$$ is the integer part of $$$|BC|$$$, then we analyze cases about $$$b$$$.

• Case 2.1: When $$$b\ge\sqrt{3}-1$$$ or $$$b=0$$$, we can show that $$$2\left\lceil |AC|\right\rceil=\left\lceil 2|AC|\right\rceil$$$, and $$$\left\lceil |AC|\right\rceil=\left\lceil |BC|\right\rceil+1$$$ if $$$|AC|\ge 2$$$. The number of steps is $$$2\left\lceil |EC|\right\rceil+2\le 2\left\lceil |BC|\right\rceil+2=2\left\lceil |AC|\right\rceil$$$.

• Case 2.2: When $$$0 \lt b \lt \sqrt{3}-1$$$, we can show that $$$\left\lceil |EC|\right\rceil=\left\lceil |BC|\right\rceil-1$$$. Total moves equals to $$$2+2\left\lceil |CE|\right\rceil=2\left\lceil |BC|\right\rceil\le \left\lceil |AC|\right\rceil+\left\lceil |BC|\right\rceil=\left\lceil 2|AC|\right\rceil$$$.

Be careful with small cases where $$$|BC|$$$ is too short, which may make $$$|DF|=|EG| \lt 0.5$$$.

Note that there are some cases where $$$\angle CBx \gt 30^\circ$$$ and $$$\angle CAB \lt 30^\circ$$$, where Case 2 strategy doesn't work. So case 1.2 is required.

Case 3: If $$$\angle CBx \gt \angle CAB \gt 60^\circ$$$. We first build a point $$$D$$$ which makes $$$AD=1$$$ and $$$\angle DAB=60^\circ$$$ and construct $$$\triangle DAB$$$. We write $$$|AC|=a+b$$$ where $$$a$$$ is integer, then we analyze two cases about $$$b$$$.

Case 3.1: When $$$b \gt 0.5$$$ or $$$b=0$$$, $$$2\left\lceil |AC|\right\rceil=\left\lceil 2|AC|\right\rceil$$$. We begin a same parallelogram construction as Case 1 where the sides of parallelogram are $$$BC,BD$$$. We can show that $$$30^\circ\le\angle CBD\le60^\circ$$$. So it is possible to pile up to $$$C$$$ from $$$BD$$$ in $$$2\left\lceil |BC|\right\rceil-1$$$ moves. And in total we need $$$2\left\lceil |BC|\right\rceil\le2\left\lceil |AC|\right\rceil=\left\lceil 2|AC|\right\rceil$$$ moves.

Case 3.2: When $$$0 \lt b\le 0.5$$$, $$$2\left\lceil |AC|\right\rceil=\left\lceil 2|AC|\right\rceil+1$$$. We instead connect $$$CD$$$ and construct parallelogram with sides $$$DC,DB$$$. We can show that $$$120^\circ\le\angle CDB\le150^\circ$$$ so we can still do the parallelogram construction. When $$$|AC|\ge \sqrt{3}$$$, $$$\left\lceil |CD|\right\rceil=\left\lceil |AC||\right\rceil-1$$$, making the number of moves $$$2\left\lceil |CD|\right\rceil+1=2\left\lceil |AC|\right\rceil-1=\left\lceil 2|AC|\right\rceil$$$.

Actually case 1.1 is not required, because it is impossible to construct a testcase where $$$\angle CAB \lt 60^\circ, \angle CBx \gt 60^\circ,0 \lt b\le 0.5$$$ and Case 3.2 fails.

#include <bits/stdc++.h>
using namespace std;
typedef double db;
const db pi = acos(-1.0);
const int N = 1000005;

inline int sgn(db x){
    if(x < 1e-13 && x > -1e-13) return 0;
    if(x > 0) return 1;
    return -1;
}

struct point{
    db x,y;
    point (db _x = 0.0,db _y = 0.0) : x(_x), y(_y) {}
};
point operator + (const point &p1,const point &p2){
	return point(p1.x + p2.x,p1.y + p2.y);
}
point operator - (const point &p1,const point &p2){
	return point(p1.x - p2.x,p1.y - p2.y);
}
point operator * (db x,const point &p){
	return point(x * p.x,x * p.y);
} 
bool operator == (point x,point y){
	return sgn(x.x - y.x) == 0 && sgn(x.y - y.y) == 0;
}

inline db dot(point p1,point p2){
    return p1.x * p2.x + p1.y * p2.y;
}

inline db det(point p1,point p2){
	return p1.x * p2.y - p2.x * p1.y;
}

inline db len(point p){
    return sqrtl(1.0 * p.x * p.x + 1.0 * p.y * p.y);
}

point project_point(point x,point ya,point yb){
	point v = yb - ya;
	return ya + (dot(v,x - ya) / dot(v,v)) * v;
}

db distp(point x,point ya,point yb){
	return fabs(det(ya - x,yb - x)) / len(yb - ya);
}

point line_circle_intersec_point(point o,point la,point lb){
	db dis = distp(o,la,lb),l;
	point pj = project_point(o,la,lb);
	l = sqrt(1.0 - dis * dis);
	point ret = pj + (l / len(lb - la)) * (lb - la);
	return ret;
}

tuple <int,int,int> ans[N];
point p[N],target;
int step;

bool check(int n){
    set <pair <int,int> > st;
    st.insert({1,2});
    if(n > step) return 0;
    db eps_len = 1e-8,eps_dis = 1e-4;
    int fl = 0;
    for(int i = 1;i <= n;i ++){
        auto [u,v,w] = ans[i];
        if(u > v) swap(u,v);
        if(st.find({u,v}) == st.end()) return 0;
        if(len(p[u] - p[w]) < 0.5 - eps_len || len(p[u] - p[w]) > 1.0 + eps_len) return 0;
        if(len(p[v] - p[w]) < 0.5 - eps_len || len(p[v] - p[w]) > 1.0 + eps_len) return 0;
        st.insert({u,w}); st.insert({v,w});
        if(len(p[w] - target) <= eps_dis) fl = 1;
    }
    return 1;
}

int solve1a(){
    point dir = target - p[1];
    int split = ceil(len(dir) - 1e-9);
    int c = 2;
    for(int i = 1;i < split;i ++){
        ++ c; p[c] = p[1] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
        ++ c; p[c] = p[2] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
        // construct one parallelogram
    }
    ++ c; p[c] = target;
    ans[c - 2] = {c - 2,c - 1,c};
    if(check(c - 2)) return c - 2;
    return 0;
}

int solve1b(){
    point dir = target - p[2];
    int split = ceil(len(dir) - 1e-9);
    int c = 2;
    for(int i = 1;i <= split;i ++){
        ++ c; p[c] = p[1] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
        ++ c; p[c] = p[2] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
    }
    if(check(c - 2)) return c - 2;
    return 0;
}

int solve2(){
    p[3] = point(sqrt(3.0) / 2,0.5);
    p[4] = line_circle_intersec_point(p[3],p[2],target);
    if(len(p[4] - p[2]) > 1)
        p[4] = p[2] + (1.0 / len(target - p[2])) * (target - p[2]);
    ans[1] = {1,2,3};
    ans[2] = {2,3,4};
    point dir = target - p[4];
    int split = ceil(len(dir) - 1e-9);
    int c = 4;
    for(int i = 1;i <= split;i ++){
        ++ c; p[c] = p[3] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
        ++ c; p[c] = p[4] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
    }
    if(check(c - 2)) return c - 2;
    return 0;
}

int solve3a(){
    p[3] = point(0.5,sqrt(3.0) / 2);
    ans[1] = {1,2,3};
    point dir = target - p[2];
    int split = ceil(len(dir) - 1e-9);
    int c = 3;
    for(int i = 1;i < split;i ++){
        ++ c; p[c] = p[2] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
        ++ c; p[c] = p[3] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
    }
    ++ c; p[c] = target;
    ans[c - 2] = {c - 2,c - 1,c};
    if(check(c - 2)) return c - 2;
    return 0;
}

int solve3b(){
    p[3] = point(0.5,sqrt(3.0) / 2);
    ans[1] = {1,2,3};
    point dir = target - p[3];
    int split = ceil(len(dir) - 1e-9);
    int c = 3;
    for(int i = 1;i <= split;i ++){
        ++ c; p[c] = p[2] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
        ++ c; p[c] = p[3] + (1.0 * i / split) * dir;
        ans[c - 2] = {c - 2,c - 1,c};
    }
    if(check(c - 2)) return c - 2;
    return 0;
}

int solve(){
    if(int res = solve1a()) return res;
    if(int res = solve1b()) return res;
    if(int res = solve2()) return res;
    if(int res = solve3a()) return res;
    if(int res = solve3b()) return res;
    return 0;
}

int main(){
    int TC; scanf("%d",&TC);
    p[1] = point(0,0);
    p[2] = point(1,0);
    while(TC --){
        int tx,ty;
        scanf("%d %d %d",&tx,&ty,&step);
        step = ceil(2.0 * sqrt(1.0 * tx * tx + 1.0 * ty * ty));
        target = point(tx,ty);
        int n = solve();
        assert(n > 0);
        printf("%d\n",n);
        for(int i = 1;i <= n;i ++){
            auto [u,v,w] = ans[i];
            printf("%d %d %.12lf %.12lf\n",u,v,p[w].x,p[w].y);
        }
    }
    return 0;
}