# Solution Tin học trẻ Đà Nẵng C2 2022

## Bài 1 - Thập phân
### Đề bài
Cho số thực $x$, làm tròn số $x$ tới số nguyên gần nhất, nếu có nhiều số gần nó thì in ra số nhỏ nhất
### Solution
Tách thành phần nguyên và phần thập phân
Để tính phần nguyên ban đầu, ta dùng ép kiểu `int(x)`

- Nếu phần thập phân $\le 0.5$ thì giữ phần nguyên
- Ngược lại, tăng phần nguyên lên 1 đơn vị.

In ra phần nguyên.

## Bài 2 - Robot
Cho một xâu $S$ và hai phép biến đổi:
- Dịch sang trái (L): dịch các ký tự sang trái 1 đơn vị, riêng ký tự đầu tiên dời về cuối
- Dịch sang phải ( R )

Cho một xâu gồm $L, R$. thực hiện tuần tự các phép dịch, tìm xâu $S$ kết quả.

### Solution
Tính chất
1. Thực hiện theo thứ tự nào không quan trọng:
Ví dụ: $RLR$, $LRR$, $RRL$ đều cho ra kết quả như nhau
$\Rightarrow$ Đếm số ký tự $L$, $R$.
2. Gọi $n = |S|$ là độ dài của xâu $S$. Nếu dịch $L$ đủ $n$ lần, hoặc dịch $R$ đủ $n$ lần, thì ta coi như xâu chưa dịch chuyển
$\Rightarrow$ Lấy số lượng ký tự của mỗi loại $\mod n$.
4. Một ký tự $L$ sẽ hủy được một ký tự $R$ (dịch trái một lần rồi dịch lại phải một lần, thì không khác gì không dịch chuyển cả)
$\Rightarrow$ tìm chênh lệch $R-L$
- Nếu $R - L > 0$ thì ta dịch phải $R-L$ lần
- Nếu $R-L < 0$ thì ta dịch trái $L-R$ lần

Từ đó ta sẽ cắt ghép xâu đúng 1 lần, dựa vào nhận xét 3 và hình dưới đây


s = input(); n = len(s)
a = input()

cntL = 0; cntR = 0                # nhận xét 1
for c in a:
    if c == 'L': cntL += 1
    if c == 'R': cntR += 1

cntL %= n; cntR %= n              # nhận xét 2
batdau = cntL - cntR              # nhận xét 3
if (batdau < 0): batdau += n

dapan = s[batdau:] + s[:batdau]   # tự figure ra tại sao
print(dapan)

## Bài 3 - Bộ ba số
Cho dãy $A$ gồm $n$ phần tử, tìm $\max\limits_{i<j<k} 3A_i+2A_j-5A_k$

### Hint
#### Cách 1
Lượt 1 lấy số được chọn nhân 3, lượt 2 nhân 2, lượt 3 nhân -5.
Ta goi $f[pos][turn]$ là đáp án tốt nhất ở lượt $turn$ khi xét $pos$ số đầu tiên của dãy.
#### Cách 2
Với mỗi $j$, ta tìm $A_i$ lớn nhất và $A_k$ nhỏ nhất.

::: spoiler
dùng mảng max/min dồn
:::

## Bài 4
Có $n$ trò có độ vui $A_1, A_2, \dots, A_n$.

Có $k$ lượt chơi, lượt $k$ chơi trò $i_k$ sẽ nhận độ vui $A_{i_k}$, và sau đó trò đó giàm độ vui đi 1 đơn vị.

Tìm độ vui lớn nhất.
### Hint
Tham lam: Tại lượt chơi thứ $i$, tìm trò có độ vui lớn nhất để chơi, chơi xong giảm đi 1 đơn vị.

:::spoiler
tự tìm hiểu về heap (Priority Queue)
:::

:::spoiler

n, k = map(int, input().split())
a = [0] + sorted(list(map(int, input().split())), reverse=True) + [0]

def sum(l: int, r: int) -> int:
    return (r-l+1) * (l+r) // 2

answer = 0
for i in range(1, n + 1):
    diff = a[i] - a[i + 1]
    if diff == 0:
        continue

    maxTurn = diff * i        # số lượt chơi trước khi nhập với a[i + 1]
    if maxTurn <= k:
        answer += i * sum(a[i+1] + 1, a[i])
        k -= maxTurn                      # hết lượt nhớ trừ ra
    else:
        rows = k // i
        rem = k % i
        answer += i * sum(a[i] - rows + 1, a[i])
        answer += rem * (a[i] - rows)     # số lượng dư ra * giá trị của các phần tử dư
        break

print(answer)

:::