A. Havo harorati

Hint: 20 kiritilganda natija qanday bo'ladi? 30 kiritilsachi?

Yechim: Harorat [-5: 19] orasida bo'lsa harorat sovuq, [20: 30] oralig'ida mo'tadil, [31:50] oralig'idagi harorat esa issiq hisoblanadi.

Time complexity: O(1)

python

n = int(input())
if n < 20:
    print("sovuq")
elif n > 30:
    print("issiq")
else:
    print("yaxshi")

c++

#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    if(n < 20){
        cout << "sovuq";
    }
    else if(n > 30){
        cout << "issiq";
    }
    else{
        cout << "yaxshi";
    }
    return 0;
}

B. Tez yozish

Hint: Har bir so'z kichik harf bilan tugallanishi kafolatlanadi. Ushbu gapga yaxshilab e'tibor qiling.

Yechim: Ketma-ket kelgan 2 tadan ko'p bo'lmasa shift bilan, aks holda capslock bilan yozgan ma'qul. Har bir so'z kichik harf bilan tugasa, demak biror so'zni yozish davomida capslock bosilsa, so'z oxirida albatta capslock ikkinchi marta bosilishi shart.

Time complexity: O(|s|), bu yerda |s| satr uzunligi.

python

n = int(input())
a = input()
ans = len(a)
cnt = 0
for i in a:
    if i == i.upper() and i != ' ':
        cnt += 1
    else:
        ans += min(2, cnt)
        cnt = 0
print(ans)

c++

#include <iostream>
using namespace std;
int main(){
    int n;
    cin >> n;
    int ans = n-1;
    for(int i = 0; i < n; ++i){
        string s; cin >> s;
        ans += s.size();
        int cnt = 0;
        for(char c: s){
            if(c != ' ' && isupper(c)) {
                cnt ++;
            }
            else {
                ans += min(cnt, 2);
                cnt = 0;
            }
        }
    }
    cout << ans;
    return 0;
}

C. ICPC. Jamoa yig'ish

Hint: Berilgan massivni tartiblash orqali nimaga erishish mumkin?

Yechim: Agar biz massivni tartiblab oladigan bo'lsak, jamoa tuzish mumkin bo'lgan odamlar ketma-ket joylashib qolgan bo'ladi.

Time complexity: O(n*log(n))

python

n = int(input())
a = list(map(int, input().split()))

a.sort()

ans = 0

i = 0
while i + 2 < n:
  if a[i + 2] - a[i] <= 1:
    ans += 1
    i += 3
  else:
    i += 1

print(ans)

c++

#include <bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int &x: a) cin >> x;
    sort(a.begin(), a.end());

    int ans = 0;

    int i = 0;
    while (i + 2 < n)
    {
        if (a[i + 2] - a[i] <= 1){
            ans++;
            i += 3;
        } else {
            i++;
        }
    }

    cout << ans;
    return 0;
}

D. Turkey camp

Hint: Sonning raqamlari soni ko'p bo'lishi uning qiymatiga qanday ta'sir qiladi?

Yechim: Borish biletining eng kichik qiymati bilan qaytish biletining eng katta qiymatini birgalikda olish eng yaxshi variant. Chunki biz har bir bilet uchun sherik topishimiz zarur.

Time complexity: O(n*log(n))

python

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort(reverse=True)
ans = 0
def f(n):
    p = 1
    while n > 0:
        n //= 10
        p *= 10
    return p
for i in range(n):
    ans += a[i]*f(b[i]) + b[i]
print(ans)

c++

#include <bits/stdc++.h>

using namespace std;

int f(int x){
    int p = 1;
    while(x > 0){
        p *= 10;
        x /= 10;
    }
    return p;
}

int main(){
    int n; cin >> n;
    vector<int> a(n), b(n);
    for(int &x: a) cin >> x;
    for(int &x: b) cin >> x;
    sort(a.begin(), a.end());
    sort(b.rbegin(), b.rend());
    long long ans = 0;
    for(int i = 0; i < n; ++i)
        ans += 1ll*a[i]*f(b[i]) + b[i];
    cout << ans;
    return 0;
}

E. Shokolad bo'lagi

Hint: Yechim aynan \(C \times D \) emas, \(C \times D \) ta bo'lak bo'lgan shaklni qidiring.

Yechim: Bizga aynan \(C \times D \) shakldagi emas, shuncha miqdorga teng bo'lgan to'rtburchak kesib olishimiz kifoya. Buning uchun \(C \times D\) sonining har bo'luvchisini tekshirib chiqish zarur. Ushbu sonning eng katta qiymati \(10^{18}\) bo'lib ketishi mumkin, bunday holatda uning bo'luvchilarini ko'rib chiqish imkonsiz. Biz C ning bo'luvchilarini alohida va D ning bo'luvchilarini alohida ko'rib chiqqan holda ularni birlashtirishimiz mumkin. n sonining bo'luvchilari soni taxminan \(log(n)\) ga teng va \([1, 10^9]\) orasida eng ko'p bo'luvchiga ega sonning bo'luvchilari soni 1344 ta (931170240). Bu esa har bir holatni ko'rib chiqish uchun yetarli.

Time complexity: \(O(\sqrt{C+D})\)

python

import math

def f(n):
  a = [] 
  b = []  

  for i in range(1, int(math.sqrt(n)) + 1):
    if n % i == 0:
      a.append(i)   
      if i * i != n:
        b.append(n // i) 

  return a + b[::-1]

def main():
  a, b, c, d = map(int, input().split())

  if a > b:
    a, b = b, a

  ans = c * d

  primec = f(c)
  primed = f(d)

  for prc in primec:
    for prd in primed:
      x = prc * prd 
      y = ans / x       
      
      if x > y:
        y, x = x, y 
        
      if x <= a and y <= b:
        print("YES")
        return

  print("NO")

main()

c++

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

vector<int> f(int n) {
	vector<int> a;
	vector<int> b;  

	for (int i = 1; i <= sqrt(n); ++i) {
		if (n % i == 0) {
			a.push_back(i);   
			if (i * i != n) {
				b.push_back(n / i); 
			}
		}
	}

	vector<int> pr = a;
	for (int i = b.size() - 1; i >= 0; --i) {
		pr.push_back(b[i]);
	}

	return pr;
}

int main() {
	int a, b, c, d;
	cin >> a >> b >> c >> d;

	if (a > b) {
		swap(a, b);
	}
	ll ans = (ll)c * d;

	vector<int> primec = f(c);
	vector<int> primed = f(d);

	for (int prc : primec) {
		for (int prd : primed) {
			ll x = (ll)prc * prd;
			ll y = ans / x;

			if (x > y) {
				swap(x, y);
			}

			if (x <= a && y <= b) {
				cout << "YES" << endl;
				return 0;
			}
		}
	}

	cout << "NO" << endl;

	return 0;
}