## Solution BKDNOJ - Contest 7
###### 📋 Mục lục:
###### [TOC]
----
### A. Thang máy
`tham lam`
- Ta thêm tầng f vào mảng $e$ và đặt $e_0=f$
- Đầu tiên ta sắp xếp mảng $e$ theo thứ tự tăng dần. Giả sử ta được $e_{i_0},e_{i_1},...,e_{i_n}$ với $(i_0,i_1,...,i_n)$ là 1 hoán vị của $(0,1,...,n)$. Ta đặt mảng $e_{i_0},e_{i_1},...,e_{i_n}$ này là $a_0,a_1,...,a_n$.
- Ta sẽ sử dụng 1 mảng $V[0..n]$ để đánh dấu tầng đã đi qua chưa.
- Ta sẽ lần lượt duyệt qua các cặp $(e_i, e_{i+1})$ với $i=0..n-1$ của mảng $e$. Vì nó được sắp xếp theo thứ tự thời gian nên thứ tự được đảm bảo.
- Cho $V[0]=true$
- Khi đó, mỗi lần gặp 1 phần tử $e_{i+1}$ mà nó chưa được đi qua thì ta xét cặp phần tử $(a_m, a_n)$ tương ứng với $(e_i, e_{i+1})$. Khi đó ta xét các phần tử $a_t$ nằm trong khoảng $a_m$ và $a_n$ , đưa nó vào mảng kết quả và đánh dấu nó là đã đi qua và tiếp tục xét $(e_{i+1}, e_{i+2})$
- Độ phức tạp :$O(n^2)$
:::success
:::spoiler Code
```c++
#include <bits/stdc++.h>
#define ll long long
using namespace std;
void solve()
{
int n,f;
cin>>n>>f;
vector<int> a(n+1),b(n+1),res;
vector<bool> visited(n+1);
unordered_map<int,int> m,t;
a[0]=b[0]=f;
t[f]=0;
visited[0]=true;
for (int i=1;i<=n;i++)
{
cin>>a[i];
t[a[i]]=i;
b[i]=a[i];
}
sort(b.begin(),b.end());
for (int i=0;i<=n;i++)
{
m[b[i]]=i;
}
int cur_floor=f;
int next_floor=f;
for (int i=1;i<=n;i++)
{
if (!visited[i])
{
next_floor=a[i];
int l,r,sign=1;
l=m[cur_floor]; r=m[next_floor];
if (l>r) sign=-1;
for (int j=l;j!=r+sign;j+=sign)
{
if (!visited[t[b[j]]])
{
res.push_back(b[j]);
visited[t[b[j]]]=true;
}
}
cur_floor=next_floor;
}
}
for (int i=0;i<res.size()-1;i++)
{
cout<<res[i]<<" ";
}
cout<<res[res.size()-1];
}
int main()
{
solve();
}
```
:::
### B. Bò ăn cỏ
`toán`
- Ta có hình vẽ mô phỏng bài toán như sau:
- Trong đó hình tròn tâm O là bãi cỏ, B là vị trí cái cây cột con bò, r là độ dài sợi dây(Khi đó diện tích phần cỏ con bò có thể ăn tối đa là phần không tô màu).
- Dễ thấy diện tích phần cỏ bị ăn (S) = diện tích quạt BAC (S<sub>1</sub>) + 2*[diện tích quạt OAB (S<sub>2</sub>) - diện tích tam giác OAB (S<sub>3</sub>)]
- Ta có: $$cos(\alpha) = \frac{2R^2 - r^2}{2R^2} \rightarrow \alpha = arccos(\frac{2R^2 - r^2}{2R^2})$$
- Diện tích quạt BAC:
$$ S_1 =\frac{1}{2} r^2\beta = \frac{1}{2}r^2(\pi - \alpha) $$
- Diện tích quạt OAB: $$S_2 =\frac{1}{2} R^2\alpha$$
- Diện tích tam giác OAB:
$$S_3 =\frac{1}{2} R^2sin(\alpha) $$
- Do đó diện tích phần cỏ bị ăn:
$$ S = S_1 + 2(S_2 - S_3) = \frac{1}{2}r^2(\pi - \alpha) + 2[\frac{1}{2} R^2\alpha - \frac{1}{2} R^2sin(\alpha)] = \frac{1}{2}r^2(\pi - \alpha) + R^2(\alpha - sin(\alpha)] $$ Trong đó: $$\alpha = arccos(\frac{2R^2 - r^2}{2R^2})$$
Khi đó ta dễ dàng tìm được độ dài r thỏa mãn $S = x\pi R^2$ bằng cách chặt nhị phân.
:::success
:::spoiler Code
```c++
#include<bits/stdc++.h>
using namespace std;
#define f(i, n) for(int i = 0; i < n; i++)
#define fo(i, n) for(int i = 1; i <= n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FOD(i, a, b) for(int i = a; i >= b; i--)
#define MOD 998244353
#define inf 1e18
#define pb push_back
#define fi first
#define se second
#define vi vector<int>
#define vll vector<ll>
#define vpl vector<pair<ll, ll>>
typedef long long ll;
double Pi = 3.14;
double Cal(double r, double R)
{
double phi = acos((2*R*R - r*r)/(2*R*R));
double S = r*r*(Pi - phi)/2 + R*R*(phi - sin(phi));
return S;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int t = 100;
cin >> t;
while(t--) {
double R, x;
cin >> R >> x;
double S = Pi*R*R*x;
double l = 0, r = 2*R;
for(int i = 0; i <= 100; i++)
{
double mid = (l + r)/2;
double s = Cal(mid, R);
if(s > S) r = mid;
else l = mid;
}
cout << setprecision(6) << fixed << l << "\n";
}
return 0;
}
```
:::
### C. Lão tiều phu OCD
`toán`
- Nói cách khác, để độ dài $x$ của một khúc cây đốn về là một số nguyên, không bỏ sót một khúc gỗ nào và $x$ lớn nhất có thể, thì $x$ phải là ước chung lớn nhất của dãy: $[a_1+k,a_2+k,...,a_n+k]$.
- Với giới hạn dữ liệu $N,Q\le2\cdot10^5$, ta thường nghĩ đến một cách tiền xử lý và thực hiện truy vấn trong khoảng $O(1)$ hoặc $O(logN)$.
- Để ý đến tính chất: $gcd(a,b) = gcd(a,abs(a-b))$. Như vậy thì $gcd(a_1+k,a_2+k) = gcd(a_1+k,abs(a_1-a_2))$.
Áp dụng tính chất trên với cả mảng:
$gcd(a_1+k,a_2+k,..., a_n+k) = gcd(a_1+k,abs(a_1-a_2),..., abs(a_1-a_n))$
- Như vậy chỉ với việc tính toán trước giá trị của $A = gcd(abs(a_1-a_2),...,abs(a_1-a_n)).$ Có thể dễ dàng tính toán giá trị cần tìm là $gcd(a_1+k,A)$.
:::success
:::spoiler Code
```c++
#include <bits/stdc++.h>
using namespace std;
void solve(){
int n, m;
cin >> n>>m;
vector<long long> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<long long> b(m);
for (int i = 0; i < m; i++) {
cin >> b[i];
}
long long g = 0;
for (int i = 1; i < n; i++) {
g = __gcd(g, abs(a[i] - a[0]));
}
for (int i = 0; i < m; i++) {
if (i > 0) {
cout << endl;
}
cout << __gcd(g, a[0] + b[i]);
}
cout << endl;
}
int main() {
solve();
}
```
:::
### D. Cho mèo vào chuồng
`tìm kiếm nhị phân`
- Bài toán yêu cầu chúng ta phân bổ các chú mèo vào các chuồng mèo sao cho khoảng cách lớn nhất trong các trường hợp phân bổ là nhỏ nhất.
- Ta có công thức tính khoảng cách là $\sqrt{h^2 + (a[i] - b[j])^2}$, ta biến đổi về thành $\sqrt{h^2 + d^2}$.
- Ta nhận thấy rằng $h$ luôn cố định, cho nên muốn khoảng cách nhỏ nhất thì $d$ phải nhỏ nhất.
- Trước tiên ta sắp xếp mảng $A$ và $B$ theo thứ tự tăng dần sau đó ta tiến hành chặt nhị phân $d$, sau đó kiểm tra thử với khoảng cách lớn nhất là $d$ thì có thể xếp $n$ chú mèo vào $m$ chuồng được không ?
- Cách kiểm tra tối ưu là đối với con mèo thứ $i$ ta sẽ tìm vị trị $j$ nhỏ nhất sao cho $|A[i] - B[j]| \leq d$.
- Chúng ta có thể dễ thấy rằng nếu càng mở rộng $d$ thì cơ hội các chú mèo vào chuồng sẽ tăng lên, còn không thì ngược lại. Con mèo thứ $i$ sẽ tìm $j$ nhỏ nhất để vào, ví dụ con mèo thứ $i$ sẽ vào được chuồng $j,j+1,j+2$, nếu để con mèo thứ $i$ vào chuồng $j + 1$ hay $j + 2$ thì tỉ lệ chú mèo $i + 1$ vào được chuồng sẽ giảm xuống.
- Còn mảng $C[j]$ thể hiện sức chứa của chuồng $j$, nếu chuồng $j$ hết chổ thì vị trí sẽ nhảy sang chuồng $j+1$.
- Ta sẽ chặt nhị phân $d$ và kiểm thử bằng $2$ con trỏ, do đó độ phức tạp sẽ là $O(N * log2(10^9))
:::success
:::spoiler Code
```c++
// N = 2e5 + 100
// ll = long long
// fi = first
// se = second
ll a[N], d[N], n , m , h;
pll b[N];
bool check(int mid){
int j = 1;
for (int i = 1; i <= m; i++) d[i] = b[i].se;
for (int i = 1; i <= n; i++){
while (j <= m && abs(b[j].fi - a[i]) > mid){
j++;
}
if (j > m) return false;
d[j]--;
if (d[j] == 0) j++;
}
return true;
}
int main()
{
cin >> n >> m >> h;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= m; i++) cin >> b[i].fi;
for (int i = 1; i <= m; i++) cin >> b[i].se;
sort(a + 1,a + 1 + n);
sort(b + 1,b + 1 + m);
ll l = 0 , r = 1e9, res = 1e9;
while (l <= r){
int mid = (l + r) >> 1;
if (check(mid)){
res = mid;
r = mid - 1;
} else l = mid + 1;
}
double p = sqrt(1LL * h * h + 1LL * res * res);
cout << setprecision(2) << fixed << p;
return 0;
}
```
:::
### E. Chiến thắng anh trai
- Trong bài toán này chúng ta sẽ sử dụng thuật toán sweep line để quét qua những chiếc thuyền và đánh dấu chúng lại.
- Giả sử ta đang xét quả bom $j$ có tọa độ là $p_j,q_j$, ta sẽ đánh dấu những chiếc thuyền có tọa độ trong đoạn $[p_j - r , p_j ]$, để làm được điều đó ta sử dụng STL::Set để cho các điểm trong đoạn $[p_j - r , p_j]$ vào một tập hợp và được sắp xếp theo tung độ tăng dần. Sau đó ta sẽ thực hiện tìm các thuyền có thọa độ trong đoạn $[q_j - r , q_j + r]$ bằng `lower_bound`. Khi tìm xong thì chúng ta đánh dấu chúng lại và được xem như là chiếc thuyền bị phá hủy.
- Khi đó chúng ta đã xác đinh được các chiếc thuyền sẽ bị phá hủy trong hình chữ nhật có chiều ngang là $[p_j - r , p_j]$ và chiều dọc là $[q_j - r , q_j + r]$.
- Làm tương tự với đoạn $[p_j, p_j + r]$, ta sẽ được hình vuông $[p_j - r , p_j + r] , [q_j - r , q_j + r]$.
- Sau khi đánh dấu xong chúng ta đếm số thuyền bị phá hủy, lấy tổng số thuyền trừ đi số thuyền bị phá hủy sẽ được số thuyền không bị phá hủy.
- Độ phức tạp : Sắp xếp chúng lại $O((n + m)log(n + m))$, sau đó duyệt $2$ lần và tìm kiếm trên Set $O(2*(n+m)log(n))$.
:::success
:::spoiler Code
```c++
// N = 2e5 + 100
// fi = first
// se = second
// all(x) = x.begin(),x.end()
struct Point{
int x,y,type,id;
// Point(int _x,int _y) : x(_x) , y(_y) {}
bool operator < (const Point & other){
if (x != other.x) return x < other.x;
return y < other.y;
}
};
struct CompareSet{
bool operator () (const Point & a,const Point & b){
if (a.y != b.y) return a.y < b.y;
return a.x < b.x;
}
};
set <Point,CompareSet> s;
int n , m , r;
Point a[N] , b[N];
int avail[N] , w[N];
vector <Point> V;
bool check(const Point & a,const Point & b){
// b in a
if (a.x - r <= b.x && b.x <= a.x + r && a.y - r <= b.y && b.y <= a.y + r) return true;
return false;
}
int solve_by_sweepline(){
int j = 0;
for (int i = 1; i <= n; i++) w[i] = 0;
s.clear();
for (int i = 0; i < V.size(); i++){
if (V[i].type == 1){
s.insert(V[i]);
}
else{
while (j < i && V[j].x < V[i].x - r){
if (V[j].type == 2){
j++;
continue;
}
auto it = s.find(V[j]);
if (it != s.end())
s.erase(it);
j++;
}
while (!s.empty()){
auto it = s.lower_bound((Point){(int)-1e9,V[i].y - r,1,0});
if (it == s.end()) break;
Point cur = *it;
if (cur.y > V[i].y + r) break;
if (check(V[i],cur)) s.erase(it) , w[cur.id] = 1;
}
}
}
s.clear();
reverse(all(V));
j = 0;
for (int i = 0; i < V.size(); i++){
if (V[i].type == 1){
s.insert(V[i]);
}
else{
while (j < i && V[j].x > V[i].x + r){
if (V[j].type == 2){
j++;
continue;
}
auto it = s.find(V[j]);
if (it != s.end())
s.erase(it);
j++;
}
while (!s.empty()){
auto it = s.lower_bound((Point){(int)-1e9,V[i].y - r,0,0});
if (it == s.end()) break;
Point cur = *it;
if (cur.y > V[i].y + r) break;
if (check(V[i],cur)) s.erase(it) , w[cur.id] = 1;
}
}
}
int res = 0;
for (int i = 1; i <= n; i++) res += (w[i] == 0);
return res;
}
int solveBru(){
for (int i = 1; i <= n; i++) avail[i] = 0;
for (int j = 1; j <= m; j++){
for (int i = 1; i <= n; i++)
if (check(b[j],a[i])) avail[i] = 1;
}
int res = 0;
for (int i = 1; i <= n; i++) res += (avail[i] == 0);
return res;
};
int main()
{
srand(time(NULL));
// ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n >> m >> r;
for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y , a[i].type = 1 , a[i].id = i;
for (int i = 1; i <= m; i++) cin >> b[i].x >> b[i].y , b[i].type = 2 , b[i].id = i;
sort(a + 1,a + 1 + n);
sort(b + 1,b + 1 + m);
V.clear();
for (int i = 1; i <= n; i++) V.push_back(a[i]);
for (int i = 1; i <= m; i++) V.push_back(b[i]);
sort(all(V));
int r2 = solve_by_sweepline();
cout << r2;
return 0;
}
```
:::
### F. Trò chơi bốc thăm
`quy hoạch động` `chặt nhị phân`
- Tóm tắt đề: Cho một dãy gồm $n$ số nguyên dương, và một số nguyên dương $k$, xoá đi $n-k$ phần tử trên dãy sao cho dãy còn lại $k$ phần tử và $min(max(a_1,a_3,...),max(a_2,a_4,...))$ đạt giá trị nhỏ nhất.
- Chúng ta sẽ tiếp cận bằng cách chặt nhị phân kết quả. Giả sử $x$ là kết quả của bài toán, ta sẽ xây dựng lại mảng con có độ dài dài nhất có thể, sao cho $min(max(a_1,a_3,...),max(a_2,a_4,...)) \le x$
- Ta sẽ tính bằng quy hoạch động, gọi $dp[i][j]$ là độ dài lớn nhất đạt được khi xét đến phần tử $i$, $j=1$ để đánh dấu phần tử cuối cùng thuộc dãy số có $max\le x$.
- Từ đó ta được công thức:
\begin{cases}
dp[i][0] = dp[i-1][1]+1\\
dp[i][1] = dp[i-1][0]+1 \ \ (a[i]\le x)\\
dp[i][1] = dp[i-1][1] \ \ \ \ \ \ \ \ \ (a[i]> x)
\end{cases}
- Phần còn lại là kiểm tra $max(dp[n][0],dp[n][1])$ có đạt được giá trị $k$ hay không
:::success
:::spoiler Code
```c++
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
const long long MOD = 1e9+7;
using namespace std;
int arr[200005];
vector<int> ca;
int dp[200005][2];
int n,m;
bool ok(int val){
int cnt = 1;
for (int i =1; i<=n; i++){
dp[i][0] = dp[i-1][1]+1;
if (arr[i]<=val){
dp[i][1]= dp[i-1][0]+1;
}
else{
dp[i][1] = dp[i-1][1];
}
}
int res = max(dp[n][1],dp[n][0]);
if (res>=m) return 1;
return 0;
}
void solve(){
cin>>n>>m;
for (int i =1; i<=n; i++){
cin>>arr[i];
ca.push_back(arr[i]);
}
sort(ca.begin(),ca.end());
ok(3);
int l = -1, r = n;
while(l<r-1){
int mid = (l+r)/2;
if (ok(ca[mid])) r = mid;
else l = mid;
}
cout<<ca[r]<<endl;
}
int32_t main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}
```
:::
Sign in with Wallet
Connect another wallet