CodeX[0] сорилго тэмцээний бодолт

M. Munkhbagana

• 2025-03-29

Өнөө үеийн технологийн хувьсал, дижитал шилжилт нь мэдээллийн технологийн салбарын инженерүүдээс зөвхөн онолын мэдлэг төдийгүй, бодит асуудлыг шийдвэрлэх хурд, алгоритмын гүнзгий ойлголт, бүтээлч сэтгэлгээг шаарддаг болсон билээ. CodeX Олимпиад нь энэхүү шаардлагад нийцсэн ирээдүйн инженерүүдийг бэлтгэх, сорих зорилготой өрсөлдөөнт програмчлалын тэмцээн юм. Олимпиад нь алгоритм, өгөгдлийн бүтэц, математик логик зэрэг өрсөлдөөнт програмчлалын гол чадваруудыг шалгах ба оролцогчид хязгаарлагдмал хугацаанд төвөгтэй бодлогуудыг бодож, хамгийн оновчтой, хурдан шийдлийг олохыг эрмэлзэнэ.Энэхүү тэмцээн нь TEEE (The Essential Engineering Education) сургуулиас зохиож буй цуврал олимпиад бөгөөд сурагчдын оюуны чадамжийг хөгжүүлэхээс гадна олон улсын түвшинд өрсөлдөх чадвартай болох боломжийг бүрдүүлнэ.

CodeX Олимпиадад хүчээ сорьж, кодоор ирээдүйгээ бүтээцгээе!

Энэхүү нийтлэл нь олимпиадын үеэр өгөгдсөн бодлогуудын нарийвчилсан тайлбар, тэдгээрийг шийдвэрлэх боломжит арга замуудын талаар өгүүлэх болно. Бид бодлогын нөхцөлийг задлан шинжилж, бодох арга барил, оновчтой алгоритмууд болон шийдлийг тайлбарлахын зэрэгцээ, түгээмэл гардаг алдаа болон тэдгээрээс хэрхэн зайлсхийх талаар мөн онцлон хэлэлцэх болно.

1. Warm up

Энэхүү бодлого нь бие халаалтын буюу энгийн логиктой бодлого бөгөөд үндсэндээ өгөгдсөн нөхцөлийг шууд хэрэгжүүлэхэд л хангалттай. Тодруулбал, хэрэглэгчээс нэг тоо авах бөгөөд уг тоо 15-аас их байгаа эсэхийг шалгаж, үр дүнг харгалзан тохирох мэдээллийг хэвлэх шаардлагатай.

Хэрэгжүүлэлтийн хувьд дараах байдлаар бодож болно:

1. Оролт авах – Гараас нэг тоо унших.
2. Нөхцөл шалгах – Оролтод өгөгдсөн тоо 15-аас их эсэхийг шалгах.
3. Гаралт хэвлэх – Хэрэв 15-аас их бол YES, бага бол NO гэсэн утга хэвлэх.

Энэ нь үндсэндээ if-else нөхцөл ашиглан хялбархан шийдэж болох бодлого юм.

Python програмчлалын хэл дээр :

a = int(input())  # Хэрэглэгчээс бүхэл тоо аван, уг утгыг хувьсагчид хадгална.
if a > 15:  #хувьсагчийн утга 15-аас их эсэхийг шалгана.
    print("YES")  # Хэрэв 15-аас их бол "YES" гэж хэвлэнэ.
else:  # Үгүй бол (15-аас бага бол)
    print("NO")  # "NO" гэж хэвлэнэ.

C++ програмчлалын хэл дээр :

#include <iostream>  // Оролт, гаралт хийхийн тулд стандарт санг дуудна.
using namespace std; // std нэрийн санг ашиглана.

int main() {
    int a; // Бүхэл тоон хувьсагч зарлах.
    cin >> a; // Хэрэглэгчээс бүхэл тоо авах.

    if (a > 15) { // 'a' хувьсагчийн утга 15-аас их эсэхийг шалгах.
        cout << "YES" << endl; // Хэрэв 15-аас их бол "YES" гэж хэвлэх.
    } else { // Үгүй бол (15-аас бага бол)
        cout << "NO" << endl; // "NO" гэж хэвлэх.
    }

    return 0; // Програмыг дуусгах.
}

2. Нууцлаг ертөнц

Бодлого бодох явцын хамгийн чухал хэсэг нь өгүүлбэрийг зөв ойлгож унших явдал гэдгийг бид өмнөх нийтлэлүүддээ онцолсон бөгөөд энэхүү бодлогын үндсэн зорилго нь өгөгдсөн тоо хүртэлх бүх анхны тооны нийлбэрийг олох юм. Анхны тоо гэдэг нь зөвхөн 1 болон өөртөө хуваагддаг тоо бөгөөд өгөгдөх тооны хязгаар 1,000,000 хүртэл, хугацааны хязгаар 1 секунд байна. Давхар давталт (O(n²)) ашиглавал өндөр утгатай тоон дээр хэт их хугацаа шаардагдах тул өгөгдсөн хугацаанд бүх тестийг давахад хүндрэлтэй байж магадгүй. Тиймээс хугацааг багасгахын тулд бид тухайн тооны язгуур хүртэл л шалгах бөгөөд энэ нь ямар ч тооны хуваагч нь түүний язгуурын утгаас бага байдаг гэсэн математикийн үндсэн зарчимд тулгуурласан учир илүү оновчтой шийдэл болно.

Python програмчлалын хэл дээр :

n = int(input())  # Хэрэглэгчээс бүхэл тоо авах.
total_sum = 0  # Анхны тоонуудын нийлбэрийг хадгалах хувьсагч.

for i in range(2, n):  # 2-оос эхлэн n-1 хүртэл бүх тоог шалгана.
    is_prime = True  # Анхны тоо эсэхийг тэмдэглэх хувьсагч 

    for j in range(2, int(i**0.5) + 1): # i тооны язгуур хүртэл хуваагчийг шалгана.
        if i % j == 0:  # Хэрэв i тоо j-д хуваагдаж байвал анхны тоо биш гэж тэмдэглэнэ.
            is_prime = False
            break  # Давталтыг зогсооно, учир нь i нь анхны тоо биш гэдэг нь тодорхой болсон.

    if is_prime:  # Хэрэв i анхны тоо бол
        total_sum += i  # Нийлбэрт нэмнэ.

print(total_sum)  # Анхны тоонуудын нийлбэрийг хэвлэнэ.

C++ програмчлалын хэл дээр :

#include <iostream>  // Оролт, гаралт стандарт санг дуудна.
#include <cmath>     // Квадрат язгуур (sqrt) ашиглахын тулд math санг оруулна.

using namespace std; // std нэрийн санг ашиглах.

int main() {
    int n;  
    cin >> n;  // Хэрэглэгчээс бүхэл тоо авах.

    int total_sum = 0;  // Анхны тоонуудын нийлбэрийг хадгалах хувьсагч.

    for (int i = 2; i < n; i++) {  // 2-оос эхлэн n-1 хүртэл бүх тоог шалгах.
        bool is_prime = true;  // Анхны тоо эсэхийг шалгах хувьсагч.

        for (int j = 2; j <= sqrt(i); j++) {  // i тооны язгуур хүртэл бүх хуваагчийг шалгах.
            if (i % j == 0) {  // Хэрэв i тоо j-д хуваагдаж байвал анхны тоо биш гэж тэмдэглэнэ.
                is_prime = false;
                break;  // Давталтыг зогсооно, учир нь i анхны тоо биш нь батлагдсан.
            }
        }

        if (is_prime) {  // Хэрэв i анхны тоо бол
            total_sum += i;  // Нийлбэрт нэмнэ.
        }
    }

    cout << total_sum << endl;  // Анхны тоонуудын нийлбэрийг хэвлэх.
    return 0;  // Програмыг дуусгах.
}

3. Гаригийн тулалдаан : Хоёрдугаар эзэн

Энэхүү бодлогын хувьд толгой эргүүлсэн төвөгтэй өгүүлбэртэй ба энэ нь competitive programming -ийн нэг хэсэг билээ. Учир нь бид тухайн асуудлаас хамгийн гол хэсгийг ялгаж харах чадвартай байх хэрэгтэй. Бодлогын гол агуулга нь баатруудын хүч өгөгдөхөд 2 дохь хүчтэнийг олох юм. Энгийнээр бидэнд n тоо өгөгдөх ба дараа нь n ширхэг хүч өгөгдөнө. Ингээд бид энэхүү дарааллаас 2 дохь хамгийн их тоог олон түүний утгыг хэвлэхэд хангалттай.

Python програмчлалын хэл дээр :

n = int(input())  # Хэрэглэгчээс n тоог оруулж авах.
a = list(map(int, input().split()))  # Хэрэглэгчээс n ширхэг тоо оруулж, тэдгээрийг жагсаалтад хадгалах.

max_element = a[0]  # Эхэндээ хамгийн их элементийг утга a[0] гэж авна.
final_boss = a[0]  # Хоёр дахь хамгийн их элемент болох final_boss-ийн утга эхэндээ a[0] байна.
index = 0  # Эхний хамгийн их элементийг хаана байгааг илтгэх индексийг хадгална.

# Бүх элементийг шалгаж хамгийн их элементийг олох
for i in range(n):
    if a[i] >= max_element:  # Хэрэв a[i] нь одоогийн хамгийн их элементээс их буюу тэнцүү байвал
        max_element = a[i]  # Хамгийн их элементийг шинэчилнэ
        index = i  # Хамгийн их элементийг хаана байгаа индексийг хадгална.

# Хамгийн том элементийг олоход ашигласан индексийн байрлалд байх элементийг 0 болгож солино. 
a[index] = 0

# Бүх элементийг дахин шалгаж хамгийн их дараагийн элементийг (final_boss) олох
for i in range(n):
    if a[i] >= final_boss:  # Хэрэв a[i] нь final_boss-оос их буюу тэнцүү байвал
        final_boss = a[i]  # final_boss-ыг шинэчилнэ

# Эцсийн үр дүнд хоёр дахь хамгийн их элементийг хэвлэх
print(final_boss)

C++ програмчлалын хэл дээр :

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;  // Хэрэглэгчээс n тоог авах.

    int a[n];  // Тоон массивыг n хэмжээтэйгээр зарлана.

    // Массивын элементүүдийг гараас авах.
    for (int i = 0; i < n; i++) {
        cin >> a[i];  
    }

    int max_element = a[0];  // Эхэндээ хамгийн их элементийн утга a[0] байна.
    int final_boss = a[0];  // Хоёр дахь хамгийн их элементийн утга a[0] байна.
    int index = 0;  // Хамгийн их элементийн индексийг хадгалах.

    // Хамгийн их элементийг болон түүний индекстэй олох
    for (int i = 0; i < n; i++) {
        if (a[i] >= max_element) {
            max_element = a[i];  // Хамгийн их элементийг шинэчилнэ
            index = i;  // Хамгийн их элементийг хаана байгаа индексийг хадгална.
        }
    }

    // Хамгийн их элементийг 0 болгож солино.
    a[index] = 0;

    // Хоёр дахь хамгийн их элементийг олох
    for (int i = 0; i < n; i++) {
        if (a[i] >= final_boss) {
            final_boss = a[i];  // Хоёр дахь хамгийн их элементийг шинэчилнэ.
        }
    }
    cout << final_boss << endl;  // Хоёр дахь хамгийн их элементийг хэвлэнэ.
    return 0;
}

Энэхүү энгийн хэрэгжүүлэлтээс гадна бид баатруудын хүчийг гараас авч, жагсаалтад хадгалан, түүнийг эрэмбэлээд хамгийн их хоёр дахь элементийг хэвлэх аргаар ч ижил үр дүнд хүрэх билээ.

Хамгийн богино бодолт :

n = int(input())
a = list(map(int, input().split())) # Гараас утгууд авах
a.sort(reverse=True) # Урвуугаар эрэмбэлэх
print(a[1]) # 2 дохь их тоог хэвлэх

Бидний цуврал олимпиадын эхний шат болох Сорилго тэмцээний бодлогуудыг танилцууллаа. Тууштай хичээж, шантралгүй тэмцэж явбал гарцаагүй амжилтад хүрэх билээ. Энэ нь зөвхөн эхлэл бөгөөд ирээдүйн тэмцээнүүдэд илүү их мэдлэг, ур чадвараа сорих боломжтой. Дараа дараагийн тэмцээнүүдэд илүү амжилттай оролцохыг хүсье !