CodeX[1] тэмцээний бодолт

M. Munkhbagana

• 2025-05-06

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

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

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

ХЭРЭГЖҮҮЛЭЛТИЙН БОДЛОГУУД

Хэрэгжүүлэлтийн (implementation) төрлийн бодлогуудыг ихэнх сурагч амжилттай бодсон бөгөөд “Хамтдаа бодоцгооё” цуврал нийтлэлүүдэд ижил төстэй бодлогууд хэдийн оруулсан байгаа тул энэ удаад бодолтыг тайлбарлахгүй байхаар шийдлээ.

ХОЁР ДАХЬ ШАЛГУУР

Энэ бодлого нь өмнөх CodeX[0] сорилго тэмцээнд багтсан бодлого юм. Өгүүлбэрийг шинэчилж оруулсан бөгөөд сурагчид өмнөх сорилын бодлогуудыг дахин бодож, өөрийгөө сорих нь чухал гэдгийг сануулах зорилготой болно.

АЛИБАБА БА 40 ДЭЭРЭМЧИН

Уг бодлого нь тэмдэгт мөртэй (string) холбоотой ба дээрэмчдийн хэлсэн үг палиндром эсэхийг шалгаж, зохих гаралтыг хэвлэх шаардлагатай. Палиндром гэж ямар үгийг тооцох талаар бодлогын тайлбарт нарийн бичигдсэн тул анхааралтай унших нь чухал.

a = input()          # Хэрэглэгчээс string (үсэг, тоо г.м) оруулна
b = a[::-1]           # 'a' гийн эсрэг чиглэлтэй (хойноос нь уншсан) хувилбар болох 'b'-г үүсгэнэ
if a == b:            # Хэрэв a болон b ижил байвал (палиндром бол)
    print("YES")      # "YES" гэж хэвлэнэ
else:
    print("NO")       # Харин үгүй бол "NO" гэж хэвлэнэ

Python хэл дээр тэмдэгт мөрийг ард нь эргүүлэх хамгийн хялбар арга бол [::-1] бичиглэл юм. Энэ нь тэмдэгт мөрийг эхнээс нь биш, сүүлээс нь унших гэсэн үг. Ингэснээр бид анхны үг болон урвуу үгийг хооронд нь харьцуулж, тэдгээр ижил байвал палиндром гэж үзэж болно.

#include <iostream>
#include <string>
#include <algorithm>  // reverse функцэд шаардлагатай

using namespace std;

int main() {
    string a;
    cin >> a;                // Хэрэглэгчээс string оруулна

    string b = a;            // 'a'-г 'b'-д хуулж өгнө
    reverse(b.begin(), b.end());  // 'b'-г урвуу болгоно

    if (a == b) {
        cout << "YES" << endl;    // Палиндром байвал "YES"
    } else {
        cout << "NO" << endl;     // Үгүй бол "NO"
    }

    return 0;
}

Харин C++ програмчлалын хэлэнд Python шиг тэмдэгт мөрийг шууд урвуугаар унших бичиглэл байдаггүй. Харин үүний оронд <algorithm> стандарт сангийн reverse() функц-ийг ашиглан тэмдэгт мөрийг ар талаас нь урвуулах боломжтой. Энэ функц нь хоёр заагч (iterator) хүлээн авдаг бөгөөд тухайн мужид орших тэмдэгтүүдийн дарааллыг урвуу болгоно.

АНГИЙН АЯЛАЛ

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

n = int(input())         # Оролт: хэдэн хүн байгаа (нийт элементүүдийн тоо)
sol = [0, 0, 0, 0]       # 1, 2, 3, 4 хүнтэй багуудын тоог хадгалах массив

for _ in range(n):
    number = int(input())
    sol[number - 1] += 1  # 1-ийг 0-р индекст, 2-г 1-р индекст гэх мэт хадгална

result = 0

# 3 хүнтэйг 1 хүнтэй хослуулна
pair_3_and_1 = min(sol[2], sol[0])
result += pair_3_and_1
sol[2] -= pair_3_and_1
sol[0] -= pair_3_and_1

# Үлдсэн 3 хүнтэйг тусдаа таксинд
result += sol[2]

# 2 хүнтэй багууд
result += sol[1] // 2
if sol[1] % 2 == 1:
    result += 1  # сондгой тооны 2 хүнтэй баг үлдвэл
    sol[0] = max(0, sol[0] - 2)  # түүн дээр 2 ширхэг 1-ийг нэмээд баг бүрдүүлнэ

# 4 хүнтэй багууд
result += sol[3]

# Үлдсэн 1 хүнтэй багууд
result += sol[0] // 4
if sol[0] % 4 != 0:
    result += 1

print(result)

Энэхүү хэрэгжүүлэлтийг C++ хэл дээр бичвэл :

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int number;
    int sol[4] = {0};  // 1-ээс 4 хүртэлх хүмүүсийн тоог тоолно

    while (n--) {
        cin >> number;
        sol[number - 1]++;
    }

    int result = 0;

    // 3 хүнтэйг 1 хүнтэй хослуулна
    int pair_3_and_1 = min(sol[2], sol[0]);
    result += pair_3_and_1;
    sol[2] -= pair_3_and_1;
    sol[0] -= pair_3_and_1;

    // Үлдсэн 3-ууд тусдаа сууна
    result += sol[2];

    // 2 хүнтэй багууд
    result += sol[1] / 2;
    if (sol[1] % 2 == 1) {
        result += 1; // Сондгой 2-той баг үлдвэл
        sol[0] = max(0, sol[0] - 2); // Түүн дээр 2 нэг хүнтэйг нэмээд 4 болгоно
    }

    // 4 хүнтэй багууд
    result += sol[3];

    // Үлдсэн 1-үүд
    result += sol[0] / 4;
    if (sol[0] % 4 != 0)
        result++;

    cout << result;
    return 0;
}

Кодын бүх мөрийн ард тайлбар нэмсэн байгаа шүү! Тиймээс сурагч та бүхэн анхааралтай уншаад, яагаад ийм алхам хийж байгааг ойлгохыг хичээгээрэй.

НУУЦ МӨРДЛӨГ

Энэ бодлого нь жагсаалт болон массив зэрэг өгөгдлийн бүтэцтэй ажиллах хэрэгжүүлэлтийн (implementation) төрлийн бодлого юм. Бидэнд 2 жагсаалт өгөгдсөн ба эхний болон дараагийн жагсаалтуудаас нэг үг дутуу. Энэ үгийг олон гаралт болгон хэвлэхэд хангалттай.

n = int(input())               # Жагсаалтын уртыг оруулна
first_list = input().split()    # Анхны жагсаалтыг оруулна
second_list = input().split()   # Хоёр дахь жагсаалтыг оруулна

# Анхны жагсаалтын үгсийг нэг бүрчлэн шалгана
for word in first_list:
    found = False  # Үгийг олсон эсэхийг шалгах хувьсагч
    for i in range(len(second_list)):
        if word == second_list[i]:  # Хэрвээ үг хоёр дахь жагсаалтад байгаа бол
            second_list.pop(i)  # Үгийг хасна
            found = True  # Олдсон гэж тэмдэглэнэ
            break  # Дараагийн үг рүү шилжинэ
    if not found:  # Хэрвээ үг олдсонгүй бол
        print(word)  # Тухайн үгийг хэвлэнэ
        break  # Программыг зогсооно

Бид оролтын утгуудыг авч, жагсаалт бүрийн элементээр давхар давталт (nested loop) ашиглан дутуу үгийг хайж байна. Энэхүү алгоритмын ажиллах хугацаа нь O(n²) бөгөөд n-ийн утга их байвал гүйцэтгэлд сөргөөр нөлөөлнө. Гэсэн хэдий ч, бидний алгоритм дутуу үгийг анхны олдсон даруйд давталтаас гарч зогсох тул ихэнх тохиолдолд шаардлагатай хугацаанд багтах боломжтой. Энэ нь муу тохиолдолд O(n²) ажиллах ч, сайн тохиолдолд эрт зогсох боломжтой гэсэн шунахай (greedy) шинж чанартай шийдэл болж байна.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;  // Жагсаалтын урт
    vector<string> first_list(n);
    vector<string> second_list(n);

    // Анхны жагсаалтыг оруулах
    for (int i = 0; i < n; i++) {
        cin >> first_list[i];
    }

    // Хоёр дахь жагсаалтыг оруулах
    for (int i = 0; i < n; i++) {
        cin >> second_list[i];
    }

    // Анхны жагсаалтын үгсийг нэг бүрчлэн шалгана
    for (const string& word : first_list) {
        bool found = false;  // Үгийг олсон эсэхийг шалгах хувьсагч
        for (int i = 0; i < second_list.size(); i++) {
            if (word == second_list[i]) {  // Хэрвээ үг хоёр дахь жагсаалтад байгаа бол
                second_list.erase(second_list.begin() + i);  // Үгийг хасна
                found = true;  // Олдсон гэж тэмдэглэнэ
                break;  // Дараагийн үг рүү шилжинэ
            }
        }
        if (!found) {  // Хэрвээ үг олдсонгүй бол
            cout << word << endl;  // Тухайн үгийг хэвлэнэ
            break;  // Программыг зогсооно
        }
    }

    return 0;
}

Уг хэрэгжүүлэлтийг C++ хэл дээр мөн ижил логиктойгоор бичсэн бөгөөд үүнд vector өгөгдлийн бүтцийг ашигласан болно.

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