# Editorial for Pre Tuyển Sinh 1
[A1 - Robot di chuyển](https://codeforces.com/gym/522403/problem/A1)

Ta chỉ cần khởi tạo $x = 0, y = 0$ và các theo tác sau:
* $L : x = x - a$
* $R : x = x + a$
* $U : y = y + a$
* $D : y = y - a$

#include <bits/stdc++.h>

using namespace std;

long long x = 0, y = 0;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    freopen("TRAVEL.INP","r",stdin);
    freopen("TRAVEL.OUT","w",stdout);
    
    int t;
    cin >> t;
    while (t--)
    {
        char c;
        long long a;
        cin >> c >> a;
        if (c == 'L') x = x - a;
        if (c == 'R') x = x + a;
        if (c == 'U') y = y + a;
        if (c == 'D') y = y - a;
    }
    
    cout << x << ' ' << y;
    
    return 0;
}

[A2 - Bật đèn](https://codeforces.com/gym/522403/problem/A2)

Với subtask đầu tiên có $n,q \le 10^3$ ta có thể dùng brute-force để giải quyết bài toán với độ phức tạp thời gian $O(2q(r - l + 1))$ $=>$ $O(nq)$

#include <bits/stdc++.h>

using namespace std;

const int maxN = 1e6 + 17;
int n,q;
int a[maxN];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    freopen("LIGHTS.INP","r",stdin);
    freopen("LIGHTS.OUT","w",stdout);
    
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    while (q--)
    {
        int l,r;
        cin >> l >> r;
        int res = 0;
        
        //Xét 0 1 0 1 ...
        int curr = 0, ans = 0;
        for (int i = l; i <= r; ++i)
        {
            if (curr == a[i]) ++ans;
            curr = !curr;
        }
        res = ans;
        
        //Xét 1 0 1 0 ...
        curr = 1, ans = 0;
        for (int i = l; i <= r; ++i)
        {
            if (curr == a[i]) ++ans;
            curr = !curr;
        }
        
        cout << min(res,ans) << endl;
    }
    
    return 0;
}

Đối với subtask 2 thì không thể dùng thuật với độ phức tạp $O(nq)$ nên cần phải có 1 thuật khác để tối ưu hóa thuật toán.

1 trong những cách tối ưu là dùng prefix sum. Ta có thể tính toán trước những bóng đèn nào thỏa mãn trong 2 trường hợp 1010 và 0101. Và khi xử lý mỗi truy vấn ta chỉ cần thực hiện việc đó trong $O(1)$. Vậy tổng thể của thuật toán này là $O(n + q)$.

#include <bits/stdc++.h>

using namespace std;

const int maxN = 1e6 + 17;
int n,q;
int a[maxN], odd[maxN], even[maxN];

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    freopen("LIGHTS.INP","r",stdin);
    freopen("LIGHTS.OUT","w",stdout);
    
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    //Even: xét 0101
    int curr = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (curr == a[i]) even[i] = 1 + even[i - 1];
        else even[i] = even[i - 1];
        curr = !curr; //Đổi 1 thành 0 và ngược lại
    }
    
    //Odd: xét 1010
    curr = 1;
    for (int i = 1; i <= n; ++i)
    {
        if (curr == a[i]) odd[i] = 1 + odd[i - 1];
        else odd[i] = odd[i - 1];
        curr = !curr; //Đổi 1 thành 0 và ngược lại
    }
    
    while (q--)
    {
        int l,r;
        cin >> l >> r;
        cout << min(odd[r] - odd[l - 1], even[r] - even[l - 1]) << endl;
    }
    
    return 0;
}

[A3 - Số thứ tự đội hình](https://codeforces.com/gym/522403/problem/A3)

Với subtask 1: $n \le 10$ ta có thể dùng brute-force để tìm số thứ tự của hoán vị ấy.

#include <bits/stdc++.h>

using namespace std;

const int maxN = 5 * 1e5 + 17;
int n;
int a[maxN];
long long ans = 0;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    freopen("PERMUTATION.INP","r",stdin);
    freopen("PERMUTATION.OUT","w",stdout);
    
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    do
    ++ans;
    while (prev_permutation(a + 1, a + 1 + n));
    
    cout << ans;
    
    return 0;
}

Với subtask 2,3:
Cho ví dụ $A = [3,4,1,2]$

Đầu tiên ta cho $B = [1,2,3,4]$.

Để $a[i] = 3$ trong lần đầu tiên thì cần bao nhiêu hoán vị để đạt mục tiêu?

**Cách 1: Thủ công**
Ta brute-force từ từ sẽ ra kết quả:

1. $B = [1,2,3,4]$
2. $B = [1,2,4,3]$
3. $B = [1,3,2,4]$
4. $B = [1,3,4,2]$
5. $B = [1,4,2,3]$
6. $B = [1,4,3,2]$
7. $B = [2,1,3,4]$
8. $B = [2,1,4,3]$
9. $B = [2,3,1,4]$
10. $B = [2,3,4,1]$
11. $B = [2,4,1,3]$
12. $B = [2,4,3,1]$
13. $B = [3,1,2,4]$
14. $B = [3,1,4,2]$
15. $B = [3,2,1,4]$
16. $B = [3,2,4,1]$
17. $B = [3,4,1,2]$

Vậy $ans = 17$

Cách 2:
Ta cần chú ý hoán vị thứ 1 và hoán vị thứ 13. Tại sao lại là hoán vị thứ 13? Vì nó có $a[1] = 3$ ngay trong lần đầu tiên. Để ý thêm 1 điều nữa là khoảng cách giữa 2 hoán vị này là 12. Nếu biến đổi một chút thí $12 = 2.3!$ ($3!$ là công thức tính hoán vị 3 phần tử, $2$ là số lượng phần tử nhỏ hơn $a[1]$ và nằm đằng sau vị trí 1.

Quá trình thuật toán như sau:

$result = 0$

$factorial = \{0!,1!,2!,3!...,n!\}$

* Xét $i = 1$:

$cnt = 0$ (số lượng phần tử nhỏ hơn $a[i]$ và nằm đằng sau vị trí i)
$=> cnt = 2$

$result = result + factorial[n - 1]$ * cnt

$result = 0 + 3!*2 = 12$

* Xét $i = 2$:

$cnt = 0$
$=> cnt = 2$

$result = result + factorial[n - 2]$ * cnt

$result = 12 + 2!*2 = 16$

* Xét $i = 3$:

$cnt = 0$
$=> cnt = 0$

$result = result + factorial[n - 3]$ * cnt

$result = 16 + 1!*0 = 16$

* Xét $i = 4$:

$cnt = 0$
$=> cnt = 4$

$result = result + factorial[n - 4]$ * cnt

$result = 16 + 0!*0 = 16$

Cuối cùng in ra kết quả là $result + 1$.

*Giải thích tại $i = 2$:*

Mặc dù có 3 số nhỏ hơn 4 nhưng số 3 nó đứng trước số 4 nên $cnt = 2$. Vì sao lại thế? Do ta không thể có hoán vị như thế này:

$[3,1,2,4]$ ... $[3,2,1,4]$ ... ~~[3,3,1,4]~~ ... $[3,4,1,2]$

$[3,3,1,4]$ không hợp lệ vì xuất hiện 2 số 3.

**Tổng thể lại kết quả của bài toán là:**

$result = 1 + \sum\limits_{i = 1}^n (factorial[n - i] * query(1,a[i] - 1))$

Với $query(1, a[i] - 1)$ là đếm số lượng các phần tử sau vị trí $i$ thỏa $(1 \le x \le a[i] - 1)$

Với độ phức tạp $O(n^2)$ thì không mấy khó khăn để full subtask 2 và 3(nhớ mod nữa đấy).

#include <bits/stdc++.h>

using namespace std;

const int maxN = 5 * 1e5 + 17;
const long long mod = 1e9 + 7;

int n;
long long a[maxN], factorial[maxN];
long long result = 0;

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    freopen("PERMUTATION.INP","r",stdin);
    freopen("PERMUTATION.OUT","w",stdout);
    
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    
    //Khởi tạo mảng factorial
    factorial[0] = 1;
    for (int i = 1; i <= n; ++i) factorial[i] = (i * factorial[i - 1]) % mod;
    
    //Process
    for (int i = 1; i <= n; ++i)
    {
        //Đếm cnt
        long long cnt = 0;
        for (int j = i + 1; j <= n; ++j) 
            if (a[j] < a[i]) ++cnt;
            
        result = (result + factorial[n - i] * cnt) % mod;
    }
    
    cout << (result + 1) % mod;
    return 0;
}

Với subtask 4(chỉ để giải trí), ta có thể tối ưu việc tìm cnt thay vì trong $O(n)$ thành $O(logn)$ bằng [Fenwick tree](https://vnoi.info/wiki/algo/data-structures/fenwick.md). Khi đó, thuật toán giảm còn $O(n.logn)$.