# 25thtb18 - THT C2 Đà Nẵng 2022

## Thập phân

*Đề gây lú: Nhầm lẫn: Luôn làm tròn xuống*

Làm tròn tới **số gần nhất**. Nếu có nhiều số gần nhất, chọn số nhỏ hơn.

Trường hợp: `a.5` --> làm tròn xuống $a$

Python

x = float(input())
le = x - int(x)
if le <= 0.5: print(int(x))
else: print(int(x) + 1)

C++

#include<bits/stdc++.h>
using namespace std;

int main()
{
	float x;
	cin >> x;
	float le = x - int(x);
	if (le <= 0.5) cout << int(x);
	else cout << int(x) + 1;
}

## Robot
> Cũng là robot

### Sub 1: 50% - Mô phỏng

### Sub 2:
Một 'R' sẽ triệt tiêu một 'L' (và ngược lại)

Chỉ cần quan tâm số lượng phép biến đổi.

Thuật toán:
1. Coi R = 1, L = -1
1. Tính d = tổng của xâu lệnh a
1. d = d chia lấy dư cho n
1. Biến đổi dựa trên d

VD :
S = abcde,
a = 'LL'
--> cde + ab
tương đương 'RRR'

qua trái i lần == qua phải n - i lần

**Bug Quý (C++)**
**biến int chia lấy dư cho s.size()**

Khi lấy biến `int` chia lấy dư (hoặc cộng trừ) cho biến `unsigned int`, kết quả sẽ bị ảnh hưởng theo modulo $2^k$

## BỘ BA SỐ

### Sub 1:
Chạy 3 for để lấy 3 vị trí

### Sub 2:

Chạy for phần tử ở giữa (a[j]). Nhận thấy:
$$3a_i + 2a_j - 5a_k$$

3 > 0 Chọn $a_i$ là phần tử MAX trước pt giữa a[j]

-5 < 0 Chọn $a_k$ là phần tử MIN sau pt giữa a[j]

Dùng vòng lặp For để tính

### Sub 3:
Dùng mảng Prefix-Sum (sửa lại để tính Min / Max)

`S[i] = S[i-1] + a[i]`
`S[i] = max(S[i-1], a[i])`

Suffix:
`S[i] = max(S[i+1], a[i])`

## Độ vui vẻ

### Sub 1:

for (lượt từ 1 tới k) {
    1. Tìm vị trí phần tử lớn nhất a[i_max]:
        i_max = 1
        for (i từ 2 tới n) {
            nếu a[i] > a[i_max] thì i_max = i
        }
    2. Tổng = tổng + a[i_max]
    3. a[i_max] -= 1
}

### Sub 2:

for (lượt từ 1 tới k) {
    1. Tìm vị trí phần tử lớn nhất a[i_max]
    2. Tổng = tổng + a[i_max]
    3. a[i_max] -= 1
}

C++ `priority_queue`: heap
Bước 1. tốn độ phức tạp $O(\log (n))$

Python: https://docs.python.org/3/library/heapq.html

1 3 3 4 8 9 12

1 3 3 4 8 9 9

k = 11
11 / 3 = 3

1 3 3 4 8 8 8

1 3 3 4 5 5 5
k -= 3*3
k = 2

### Sub 3