# [CHG::OJ] Lời giải Free Fire Contest 2023 - 01

:::info
:bulb: Educational contest written by sweetestlove

:timer_clock: Thời gian làm bài: 180 phút

:::

## Bài 1: Valentine
:book: Thuật toán: Bruteforce

:::spoiler C++ Solution

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    long long X, Y;
    cin >> X >> Y;
    int i = 1, ans = 1;
    while ((X << i) <= Y) {
        ans++;
        i++;
    }
    cout << ans << "\n";
}

:::

---

## Bài 2: Tình yêu đôi lứa
:book: Thuật toán: Tham lam

:point_right: Chi tiết thuật toán:
Trong bài toán, bạn được yêu cầu viết số lớn nhất có thể cho số sơn mà bạn có và số sơn mà bạn cần viết cho mỗi chữ số.

Vì số càng dài thì càng lớn nên ta ưu tiên tìm số dài nhất có thể. Do đó, chúng ta chọn chữ số lớn nhất trong những chữ số cần ít sơn nhất. Đặt số sơn cho chữ số $d$ là $x$, và chúng ta có tổng cộng $v$ lít sơn. Sau đó ta biết được chiều dài là $floor(v/x)$.

Bây giờ chúng ta đã biết độ dài của số, đặt nó là $len$. Đặt kết quả tạm thời là dãy độ dài $len$ gồm toàn các chữ số $d$. Chúng ta còn dư $v-len*x$ lít sơn. Để tối ưu cho đáp án, chúng ta có thể thử cập nhật số ngay từ đầu và hoán đổi từng chữ số với giá trị lớn nhất có thể. Điều đó luôn đúng vì các số có độ dài bằng nhau được so sánh ở các chữ số cao nhất trước. Trong số các chữ số lớn hơn hiện tại, chúng ta chọn một số mà còn đủ sơn, sau đó cập nhật câu trả lời và số sơn hiện tại.

Trong trường hợp không tìm được số phù hợp, in ra $-1$;

:::spoiler C++ Soltuion

#include<iostream>
using namespace std;
int i, n, s = 1000001, l, a[9];
int main() {
	cin >> n;
	while (cin >> a[i++]) s = min(s, a[i - 1]); l = n / s; if (!l)cout << -1;
	while (l--) for (i = 8; i >= 0; i--)
			if ((n - a[i]) / s == l && n >= a[i]) {
				cout << i + 1; n -= a[i]; break;
			}
	return 0;
}

:::

---

## Bài 3: Nối chuỗi

:book: Thuật toán: Tham lam, sắp xếp

:point_right: Chi tiết thuật toán:
Sắp xếp tất cả các chuỗi theo thứ tự $a + b < b + a$ và ghép chúng lại với nhau.

Chứng minh: Tính chất bắc cầu. Xem xét một câu trả lời tối ưu với hai chuỗi theo thứ tự ngược lại bởi toán tử đó. Do tính bắc cầu của toán tử, chúng ta có thể giả sử rằng cặp chuỗi là liên tiếp. Nhưng sau đó chúng ta có thể hoán đổi chúng và nhận được câu trả lời tốt hơn.

:::spoiler C++ Solution

#include <bits/stdc++.h>
using namespace std;
int i, n;
string m[50005];
bool f(string a, string b) {
	return a + b < b + a;
}
int main() {
	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> m[i];
	}
	sort(m, m + n, f);
	for (i = 0; i < n; i++) {
		cout << m[i];
	}
}

:::

---