# Lời giải đề thi thử lần 2 môn Tin học PEA
*written by ntan, vson, tminh, haison, mduc, dhuy*

## SỐ ĐẶC BIỆT

**Sub1:** $n \le 10^6$

Đầu tiên ta viết hàm tính tổng chữ số

int cal_digit(int x) {
    int res = 0;

    while(x != 0) {
        res = res * 10 + x % 10;
        x /= 10;
    }

    return res;
}

Đếm số lượng các số từ $1$ đến $n$ chia hết cho $2$, $3$ và tổng chữ số chia hết cho $9$:

In ra số thứ $n$ theo yêu cầu

void sub1() {
    int ans = 1, lens = 0;
    while(lens != n) {
        ans++;
        if(ans % 2 == 0 && ans % 3 == 0 && cal_digit(ans) % 9 == 0)
            lens++;
    }
    cout << ans;
}

**Sub2**: $n \le 10^9$
Ta nhận thấy số chia hết cho $2$, $3$ mà lại có tổng chữ số chia hết cho $9$ tức là số đó phải chia hết cho cả $2$ và $9$ hay số đó có dạng $18n$

void sub2() {
    cout << 18 * n;
}

**SOURCE CODE AC**

#include<bits/stdc++.h>

#define int int64_t

using namespace std;

int cal_digit(int x) {
    int res = 0;

    while(x != 0) {
        res = res * 10 + x % 10;
        x /= 10;
    }

    return res;
}

void sub1() {
    int ans = 1, lens = 0;
    while(lens != n) {
        ans++;
        if(ans % 2 == 0 && ans % 3 == 0 && cal_digit(ans) % 9 == 0)
            lens++;
    }
    cout << ans;
}

void sub2() {
    cout << 18 * n;
}

int n;

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    
    #define task "SODACBIET"
    if(fopen(task ".inp", "r")) {
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }

    cin >> n;
    if(n <= 1e6) 
        sub1();
    else 
        sub2();
}

## SỐ THẦN KỲ
**Subtask 1: Duyệt trâu**

Việc bạn cần làm là duyệt từ $1 -> n$ để đếm xem có bao nhiêu ước chẵn và lẻ rồi so sánh chúng với nhau

**Độ phức tạp: $O(q*n)$**

**Subtask 2: Tối ưu hoá duyệt trâu**

Giống như **sub1** nhưng thay vì duyệt từ $1->n$ thì bạn chỉ cần duyệt từ $1->sqrt(n)$ là được vì nếu $i$ là ước của $n$ thì $n/i$ cũng là ước của $n$.

**Lưu ý:** Đối với các số chính phương thì $n/i=i$ nên ta chỉ xét $i$ mà thôi.

**Độ phức tạp: $O(q*sqrt(n))$**

**Subtask 3: adhoc+Toán**

Giả sử $n=h*2^k$ ($h$ là số lẻ)

Khi đó giả sử $i$ là $1$ ước lẻ của $n$ thì $i*2^j$ cũng là ước của $n$ $(1 \le j \le k)$ vì vậy nếu như $n$ có $x$ ước là số lẻ thì $n$ sẽ có $x*k$ ước là số chẵn.

Vậy nên $n$ là "số thần kỳ" khi và chỉ khi $x \geq x*k \geq k \le 1$.

Từ đó bài toán đã cho trở thành kiểm tra số $n$ có không chia hết cho $4$ hay không.

**Độ phức tạp: $O(q)$**

**source code:**

#include<bits/stdc++.h>
using namespace std;
long long q;
void sub1(long long n)
{
    long long ans=0;
    for(long long i=1;i<=n;i++)
    {
        if(n%i==0)
        {
            if(i%2!=0) ans++;
            else ans--;
        }
    }
    if(ans>=0) cout<<"YES\n";
    else cout<<"NO\n";
}
void sub2(long long n)
{
    long long ans=0;
    for(long long i=1;i<=sqrt(n);i++)
    {
        if(n%i==0)
        {
            if(i%2!=0) ans++;
            else ans--;
            if((n/i)%2!=0) ans++;
            else ans--;
            if(i*i==n && i%2!=0) ans--;
            else if(i*i==n && i%2==0) ans++;
        }
    }
    if(ans>=0) cout<<"YES\n";
    else cout<<"NO\n";
}
void sub3(long long n)
{
    if(n%4==0) cout<<"NO\n";
    else cout<<"YES\n";
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    if(fopen("THANKY.inp","r"))
    {
        freopen("THANKY.inp","r",stdin);
        freopen("THANKY.out","w",stdout);
    }
    cin>>q;
    while(q--)
    {
        long long n;
        cin>>n;
        if(n<=1e6) sub1(n);
        else if(n<=1e12) sub2(n);
        else sub3(n);
    }
}

## PHẦN THƯỞNG

**Sub 1:**
Với giới hạn $n \le 10^3$ và $q \le 10^3$ ta có thể hoàn toàn duyệt trâu từng truy vấn với độ phức tạp $O(qn)$.

**Sub 2:**

Kết quả của các truy vấn dạng $1$ sẽ là:
$a[l] + a[l + 1] + a[l + 2] + … + a[r - 1] + a[r]$
+
$a[l + 1] + a[l + 2] + … + a[r - 1] + a[r]$
+
$a[l + 2] + … + a[r - 1] + a[r]$
+
…..
+
$a[r - 1] + a[r]$
+
$a[r]$

Nhìn vào đây ta dễ dàng có $1$ nhận xét có thể rút gọn kết quả trên bằng $prefix sum$(mảng cộng dồn):
Gọi $pre[i]$ là tổng từ $1$ đến $i$

$pre[r] - pre[l - 1]$

+

$pre[r] - pre[l]$

+

…..

+

$pre[r] - pre[r - 1]$

Vậy kết quả của các truy vấn $1$ sẽ bằng:
$pre[r] * (r - l + 1)$ $-$ Tổng từ $pre[l - 1]$ đến $pre[r - 1]$

Đến đây ta lại tiếc tục sử dụng kĩ thuật $prefix sum$ để có thể tính tổng của $pre[l - 1]$ đến $pre[r - 1]$ trong $O(1)$.

Với cách xử lý truy vấn như trên ta hoàn toàn có thể tiền xử lý trước các mảng cộng dồn trong độ phức tạp $O(n)$ và xử lý truy vấn trong độ phức tạp $O(1)$. Ở truy vấn $2$ ta giải tưởng tự như trên.

----------

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
#define fi first
#define pb push_back
#define se second
#define ii pair<int,int>

const int Nmax = 3000058;

int n , q , a[Nmax] , Ans;
int pre[Nmax] , suf[Nmax];
int Pre[Nmax] , Suf[Nmax];

void Sub1()
{
    while(q--)
    {
        int l , r;
        string type;
        Ans = 0;
        cin >> type >> l >> r;
        if(type == "1")
        {
            for (int i = l ; i <= r ; i++)
            Ans += a[i] * (i - l + 1);
        }
        else
        {
            for (int  i = l ; i <= r ; i++)
            Ans += a[i] * (r - i + 1);
        }
        cout << Ans << '\n';
    }
}

void Sub2(){
        for (int i = 1 ; i <= n ; i++)
    {
        pre[i] = pre[i - 1] + a[i];
        PRE[i] = PRE[i - 1] + pre[i];
    }

    for (int i = n ; i >= 1 ; i--)
    {
        suf[i] = suf[i + 1] + a[i];
        SUF[i] = SUF[i + 1] + suf[i];
    }

    while(q--)
    {
        int l , r;
        string type;
        cin >> type >> l >> r;
        if(type == "1") cout << pre[r] * (r - l + 1) - (PRE[r - 1] - PRE[l == 1 ? l - 1 : l - 2]) << '\n';
        if(type == "2" ) cout << suf[l] * (r - l + 1) - (SUF[l + 1] - SUF[r + 2]) << '\n';
    }
}

main(){
    // freopen( "ADDITION.INP" , "r" , stdin);
    // freopen( "ADDITION.OUT" , "w" , stdout);

    cin >> n >> q;
    for (int i = 1 ; i <= n ; i++)
    cin >> a[i];
    Sub2();
}

## BÀI TOÁN THẾ KỶ

**Subtask 1: $k \le 1e3$**
Đối với subtask này thì ta có thể chạy $0->min(n,k)$ để kiểm tra. Gọi $i(0 \le i \le min(n,k))$ là số lần tối đa để thay đổi vị trí các giá trị của mảng $a$ để giá trị ở vị trí $x$ là lớn nhất, thì khi đó số bước tối đa để thay đổi vị trí của các giá trị của mảng $v$ để giá trị ở vị trí $y$ là lớn nhất là $k-i$. Khi đó ta chỉ cần duyệt từ $0->k$ và xét max.
**Subtask2: $k\le 1e6$**
- Gọi $C[i]$ là giá trị lớn nhất của vị trí $x$ khi thay đổi tối đa $i$ lần thay đổi các vị trí trong mảng $a$
- Gọi $D[i]$ là giá trị lớn nhất của vị trí $y$ khi thay đổi tối đa $i$ lần thay đổi các vị trí trong mảng $a$
Khi đó ta cx sẽ làm tương tự như **Subtask1**, duyệt $i$ từ $0->min(n,k)$ và xét $max(C[i]+D[min(n,k-i)]$

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define ii pair<int,int>
#define lg2 20
const int maxn=2e5+1;
const int mod=109+7;
int n,a[maxn],b[maxn],k,x,y,d[maxn],c[maxn];
    signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>k>>x>>y;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    c[0]=a[x];
    d[0]=b[y];
    for(int i=1;i<=n;i++){
            c[i]=c[i-1],d[i]=d[i-1];
        if(x-i>=1)
            c[i]=max(c[i],a[x-i]);
        if(x+i<=n)
            c[i]=max(c[i],a[x+i]);
        if(y-i>=1)
            d[i]=max(d[i],b[y-i]);
        if(y+i<=n)
            d[i]=max(d[i],a[y+i]);
    }
    int ans=0;
    for(int i=0;i<=min(n,k);i++){
        ans=max(ans,c[i]+d[min(n,k-i)]);
    }
    cout<<ans;
}