A. Yozuv terish mashinasi

Demak A → B ko'rinishiga, B → AB ko'rinishiga o'tar ekan. Shunday qilib, har bir qadamni o'zidan oldingi 2 ta qadamning yig'indisi sifatida ifodalash mumkin.

Python

n = int(input())
a, b = 0, 1
for i in range(n-1):
    a, b = b, a+b
print(a, b)

c++

#include <iostream>
using namespace std;
int main(){
    int n; cin >> n;
    int a = 0, b = 1;
    for(int i = 1; i < n; ++i){
        swap(a, b);
        b += a;
    }
    cout << a << ' ' << b;
}

Time complexity: \(O(n)\)

B. Ramka

Biz krossword chetiga ramka chizish o'rniga, katta maydon ichiga shartda aytilgandek joylashtirishimiz ancha oson va qulay.

python

n, m = map(int, input().split())
u, l, r, d = map(int, input().split())
a = []
for i in range(u+n+d):
    a.append(['.']*(l+m+r))
for i in range(len(a)):
    for j in range((i % 2), len(a[0]), 2):
        a[i][j] = '#'

for i in range(u, n+u):
    s = input()
    for j in range(l, m+l):
        a[i][j] = s[j-l]

for i in a:
    print(*i, sep="")

c++

#include <iostream>
#include <vector>
using namespace std;
int main(){
    int n, m; cin >> n >> m;
    int u, l, r, d; cin >> u >> l >> r >> d;
    vector a(n+u+d, vector(m+l+r, '.'));
    for(int i = 0; i < n+u+d; ++i)
        for(int j = (i & 1); j < m+l+r; j += 2)
            a[i][j] = '#';  
    for(int i = u; i < n+u; ++i)
        for(int j = l; j < m+l; ++j)
            cin >> a[i][j];

    for(auto x: a){
        for(auto y: x)
            cout << y;
        cout << '\n';
    }
}

Time complexity: \(O(n*m)\)

C. Musobaqa

Biz har bir 1, 2, 3, …, n kishilik jamoa yaratish orqali maksimal qancha odam finalga chiqishini hisoblashimiz mumkin. Garmonik summa orqali hisoblash amalga oshirilsa, umumiy vaqt \(N + S \times logS\) ga teng bo'ladi, bu yerda S massivdagi eng katta son.

python

def main():
    MAXV = 2000010

    N = int(input())
    
    num = [0] * MAXV
    a = list(map(int, input().split()))
    for x in a:
        num[x] += 1
    
    sol = N
    
    for i in range(1, 2000001):
        curr = 0
        for j in range(i, 2000001, i):
            curr += num[j]
        if curr > 1:
            sol = max(sol, curr * i)
    
    print(sol)

if __name__ == "__main__":
    main()

c++

#include <iostream>
#include <algorithm>

using namespace std;

const int MAXV = 2000010;

int N, num[MAXV];

int main() {
	cin >> N;
	
	for(int i = 0; i < N; ++i) {
		int x;
		cin >> x;
		++num[x];
	}
	
	long long sol = N;
	
	for(int i = 1; i <= 2000000; ++i) {
		int curr = 0;
		for(int j = i; j <= 2000000; j += i)
			curr += num[j];
		if(curr > 1) sol = max(sol, (long long)curr * i);
	}
	
	cout << sol;

  return 0;

}

Time complextiy: \(O(N + S\times logS\)

D. Ifodani maksimallashtirish.

Bunda maximum javobga olib boradigan bir nechta holatni ko’rish mumkin.

• i = 1 (yoki i = n):
  biz a[1] ni arraydagi maximum elementga almashtirsak javob (mx + and(2..n)) bo’lishi mumkin agar k ni 2 sifatida tanlasak.
  k > 2 uchun, a[1] ni doimo a[2] ga tenglashtirish optimal. Chunki a[1]&a[2] eng ko’pida a[2] ga teng bo’lishi mumkin. Shuning uchun a[1] ni a[2] ga tenglashtirsak biz qidirayotgan optimal javobdan uzoqlashib ketmaymiz. a[1] = a[2] qilib har k uchun (2 <= k < n) and(2..k) + suf_and(k + 1..n) dan maximumni tanlab olamiz. 
  i = n holatni ham xuddi shunay faqat massivdagi sonlarni teskari tartibda ko’rib chiqsa bo’ladi. 
    
• 1 < i < n:
  Tasavvur qilaylik a[i] ni birorta elementga o’zgartirdik. Biz qidirayotgan optimal k (k >= i) bo’lsin. 
  U holda biz o’zgartirilgan a[i] ning qiymati chap tomonga ta’sir ko’rsatadi. U holda biz a[i] ni shunday tanlashimiz kerakki i gacha bo’lgan elementlarning and’i kamaymasin. Buning uchun a[i] ni o’zidan oldingi birorta elementga tenglay olishimiz mumkin (ya’ni j < i). Qulaylik uchun j = 1 qilib belgilab olaylik (a[i] = a[1]). Shundan so’ng yangi hosil bo’lgan massivdan yana optimal k ni topshimiz kerak (bunda k >= i). Bunda shunchaki k ni [i..n – 1] oralig’ida iteratsiya qilish va suffix va prefix and larni avvaldan hisoblab olish yetarli. Shu bilan birga (k > i) holat uchun xuddi shu narsa massiv elementlarini teskari tartibda ko’rib hisoblab qo’yish yetarli.
   
• Lekin bizda i lar soni soni n ta va har safar optimal k ni topib ketaversak  O(n^2) lik yechim chiqib qoladi. Lekin biz hamma i larni tekshirishimiz shart emas. Faqatgina and(1..i – 1) and(1.. i) dan katta bo’lgan i larni ko’rish yetarli. Bunday i lar soni esa ko’pi bilan log(max_element(a)) ta bo’lishi mumkin. Chunki biz prefix array doim kamayuvchi bo’ladi va har safar kamayganda 31 bitdan kamida bittasi 0 ga aylanadi va bu holat ko’pi bilan 31 marta bo’lishi mumkin.
  Demak Biz O(Nlog(maxA)) lik ajoyib yechimga ega bo’ldik.

python

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    n = int(data[0])
    a = list(map(int, data[1:]))
    
    maxn = 10**5 + 5
    pr = [[0] * maxn for _ in range(2)]
    sf = [[0] * maxn for _ in range(2)]
    
    mx = 0
    for i in range(n):
        mx = max(mx, a[i])
    
    pr[0][1] = a[0]
    pr[1][1] = sf[1][n-1] = 1073741823
    sf[0][n-1] = a[n-1]
    
    for i in range(1, n):
        pr[0][i + 1] = pr[0][i] & a[i]
        pr[1][i + 1] = max(pr[0][i], pr[1][i] & a[i])
    
    for i in range(n-2, -1, -1):
        sf[0][i] = sf[0][i + 1] & a[i]
        sf[1][i] = max(sf[0][i + 1], sf[1][i + 1] & a[i])
    
    pr[1][1] = sf[1][n-1] = mx
    ans = 0
    for i in range(n):
        if i < n - 1:
            ans = max(ans, max(pr[1][i + 1] + sf[0][i + 1], pr[0][i + 1] + sf[1][i + 1]))
    
    print(ans)

if __name__ == "__main__":
    main()

c++

#include <bits/stdc++.h>
#define ar array
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;

const int maxn = 1e5 + 5;
ll pr[2][maxn], sf[2][maxn], a[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    ll n, mx = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) 
        cin >> a[i], mx = max(mx, a[i]);
    pr[0][1] = a[1];
    pr[1][1] = sf[1][n] = 1073741823;
    sf[0][n] = a[n];
    for (int i = 2; i <= n; i++) {
        pr[0][i] = pr[0][i - 1] & a[i];
        pr[1][i] = max(pr[0][i - 1], pr[1][i - 1] & a[i]);
    }
    for (int i = n - 1; i > 0; i--) {
        sf[0][i] = sf[0][i + 1] & a[i];
        sf[1][i] = max(sf[0][i + 1], sf[1][i + 1] & a[i]);
    }
    pr[1][1] = sf[1][n] = mx;
    ll ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, max(pr[1][i] + sf[0][i + 1], pr[0][i] + sf[1][i + 1]));
    cout << ans << '\n';
}

Time complexity: \(O(N\times log(maxA))\)

E. Xesh funksiya

Bu masala “meet-in-the-middle” texnikasi yordamida oson hal qilish mumkin. Biz umumiy \(26^{10}\) ta so'z hosil qilish o'rniga \(26^5\) ta prefix va \(26^5\) ta suffixni saqlab olib, ularni birlashtiramiz. Har bir prefix uchun biz uning xeshini hisoblashimiz va har bir bunday xesh necha marta paydo bo'lishini massivda saqlashimiz mumkin. Har bir suffix uchun biz yakuniy xesh K bo'lishi uchun prefixning xeshi qanday bo'lishi kerakligini hisoblashimiz mumkin va keyin massivdan ushbu suffixga mos keladigan prefixlar sonini topishimiz mumkin. Xesh nima bo'lishi kerakligini hisoblash uchun biz orqaga qarab ishlaymiz: yakuniy xeshni K deb hisoblaymiz va oxiridan bir vaqtning o'zida bitta harfni olib tashlaymiz.

Xeshning joriy qiymati S va keyingi harfning tartib raqami x deb faraz qilgan holda aytilgan xesh-funktsiyaning iteratsiyasini kuzatamiz.

S’ = ((S * 33) xor x) % MOD

Joriy holat S’ va bizni x holatga keltirgan harfning tartib raqamini bilsak, avvalgi S holatining qiymatini olishga harakat qilamiz.

Quyidagi holat o'rinli:

(A xor B) % MOD = (A % MOD) xor (B % MOD)

Shuning uchun:

S’ = ((S * 33) % MOD) xor (x % MOD)

chunki bitwise XOR o'ziga teskari va x har doim MOD dan kichik bo'ladi, shu sababli bu ham to'g'ri:

S’ xor x = (S * 33) % MOD

MOD o'lchami sohasida 33 ning modular multiplikativ inversiyasi, agar 33 va MOD o'zaro tub bo'lsa, mavjud bo'ladi. MOD ikkining darajasi bo'lgani uchun bu shart bajariladi. Modular inversiya kengaytirilgan Evklid algoritmi, binar darajaga oshirish yoki shunchaki ko'rib chiqish yordamida olish mumkin, chunki M etarlicha kichik.

Shunda:

(S’ xor x) * inv(33, MOD) = S

Shunday qilib, umumiy Time complexity \(O(26^{N/2}) \) ga teng.

python

import sys

maxMod = (1 << 25)

def rec1(state, iter, table, Mod):
    if iter:
        for z in range(1, 27):
            rec1(((state * 33) ^ z) & Mod, iter - 1, table, Mod)
    else:
        table[state] += 1

def rec2(state, iter, table, Mod, inv33):
    global solution
    if iter:
        for z in range(1, 27):
            rec2(((state ^ z) * inv33) & Mod, iter - 1, table, Mod, inv33)
    else:
        solution += table[state]

def load():
    global N, K, Mod, inv33
    N, K, Mod_input = map(int, input().split())
    Mod = (1 << Mod_input)
    e = Mod // 2 - 1
    b = 33
    inv33 = 1
    while e:
        if e & 1:
            inv33 = (inv33 * b) % Mod
        b = (b * b) % Mod
        e //= 2
    assert (33 * inv33) % Mod == 1
    Mod -= 1

def main():
    global solution
    load()
    table = [0] * maxMod
    rec1(0, N // 2, table, Mod)
    rec2(K, N - N // 2, table, Mod, inv33)
    print(solution)

if __name__ == "__main__":
    solution = 0
    main()

c++

#include <iostream>
#include <cassert>
#include <cstring>
using namespace std;
const int maxMod = (1 << 25);

int N, K, Mod, table[maxMod];
long long solution = 0, inv33;

void rec1(int state, int iter) {
  if (iter) {
    for (int z = 1; z <= 26; ++z) {
      rec1(((state * 33) ^ z) & Mod, iter - 1);
    }
  } else {
    ++table[state];
  }
}

void rec2(int state, int iter) {
  if (iter) {
    for (int z = 1; z <= 26; ++z) {
      rec2(((state ^ z) * inv33) & Mod, iter - 1);
    }
  } else {
    solution += table[state];
  }
}

void load() {
  cin >> N >> K >> Mod;
  Mod = (1 << Mod);
  int e = Mod / 2 - 1;
  long long b = 33;
  for (inv33 = 1; e; e /= 2) {
    if (e & 1) inv33 = (inv33 * b) % Mod;
    b = (b * b) % Mod;
  }
  assert((33ll * inv33) % Mod == 1);
  --Mod;
}

int main() {
  load();
  rec1(0, N / 2);
  rec2(K, N - N / 2);
  cout << solution;
  return 0;
}

Time complexity: \(O(26^{N/2})\)