16.6 แบบฝึกหัด

เขียนแต่ละข้อเป็นไฟล์ใหม่ใน Code::Blocks รันแล้วเทียบกับผลลัพธ์ที่ต้องได้ให้ตรงทุกตัวอักษร รวมถึงช่องว่างและการขึ้นบรรทัด ติดจริงๆ ค่อยเปิดคำใบ้ และเปิดเฉลยหลังทำเสร็จแล้วเท่านั้น

ข้อ 1 สูงกว่าค่าเฉลี่ย

ระดับง่าย เวลาไม่เกิน 1 วินาที

ครูจดคะแนนสอบย่อยของนักเรียนลงสมุดทีละคน จดเสร็จแล้วปิดท้ายด้วย -1 ครูไม่ได้นับไว้ว่ามีกี่คน ครูอยากรู้ว่ามีนักเรียนกี่คนที่ได้คะแนนสูงกว่าค่าเฉลี่ยของห้อง และคนเหล่านั้นได้คะแนนเท่าไรบ้าง

คนที่ได้คะแนนเท่ากับค่าเฉลี่ยพอดีไม่นับว่าสูงกว่า

ข้อมูลเข้า

คะแนนของนักเรียนทีละคนตามลำดับในสมุด คั่นด้วยช่องว่างหรือขึ้นบรรทัดใหม่ แต่ละคะแนนเป็นจำนวนเต็มตั้งแต่ 0 ถึง 100 และตามด้วย -1 ซึ่งไม่ใช่คะแนน มีนักเรียนอย่างน้อย 1 คน และไม่เกิน 100000 คน

ข้อมูลออก

บรรทัดแรกพิมพ์จำนวนนักเรียนที่ได้คะแนนสูงกว่าค่าเฉลี่ย

บรรทัดที่สองพิมพ์คะแนนของนักเรียนเหล่านั้นตามลำดับในสมุด คั่นด้วยช่องว่างหนึ่งช่อง ถ้าไม่มีนักเรียนที่สูงกว่าค่าเฉลี่ยเลย ไม่ต้องพิมพ์บรรทัดที่สอง

72 85 64 90 58 -1

2
85 90

80 80 80
80 -1

0

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int> score;
    int x;
    while (cin >> x && x != -1) {
        score.push_back(x);
    }
    long long total = 0;
    for (int s : score) {
        total += s;
    }
    long long count = score.size();
    vector<int> above;
    for (int s : score) {
        if (s * count > total) {
            above.push_back(s);
        }
    }
    cout << above.size() << '\n';
    if (!above.empty()) {
        for (int i = 0; i < (int)above.size(); i++) {
            if (i > 0) {
                cout << ' ';
            }
            cout << above[i];
        }
        cout << '\n';
    }
    return 0;
}

ข้อ 2 หมุนรูป

ระดับง่าย เวลาไม่เกิน 1 วินาที

แอปแต่งรูปเก็บรูปขาวดำเป็นตารางตัวเลข R แถว C คอลัมน์ แต่ละช่องคือความสว่างของจุดหนึ่งจุด ตั้งแต่ 0 (ดำ) ถึง 255 (ขาว) ให้หมุนรูปไปทางขวา 90 องศาตามเข็มนาฬิกา แถวบนสุดของรูปเดิมจะกลายเป็นคอลัมน์ขวาสุดของรูปใหม่ รูปใหม่จึงมี C แถว R คอลัมน์

ขนาดของรูปรู้ตอนรันเท่านั้น และรูปอาจผอมยาวมาก เช่น 1 แถว 200000 คอลัมน์ หรือ 200000 แถว 1 คอลัมน์

ข้อนี้ตั้งใจให้ฝึกย้ายวิธีจากข้อหมุนรูปภาพในบทที่ 7 มาเขียนด้วย C++ วิธีหมุนเหมือนเดิม ที่ต่างคือขนาดของรูป ซึ่งอาเรย์สองมิติขนาดตายตัวรับไม่ไหว ต้องใช้ vector ที่สร้างตามขนาดจริง

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม R และ C คั่นด้วยช่องว่าง (1 ≤ R, C และ R × C ≤ 200000)

อีก R บรรทัด บรรทัดละ C จำนวน คือความสว่างของแต่ละแถวจากบนลงล่าง แต่ละจำนวนเป็นจำนวนเต็มตั้งแต่ 0 ถึง 255

ข้อมูลออก

รูปที่หมุนแล้ว C บรรทัด บรรทัดละ R จำนวน คั่นด้วยช่องว่างหนึ่งช่อง

2 3
1 2 3
4 5 6

4 1
5 2
6 3

3 2
0 255
128 64
10 20

10 128 0
20 64 255

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int rows, cols;
    cin >> rows >> cols;
    vector<vector<int>> photo(rows, vector<int>(cols));
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            cin >> photo[r][c];
        }
    }
    for (int c = 0; c < cols; c++) {
        for (int r = rows - 1; r >= 0; r--) {
            cout << photo[r][c];
            if (r > 0) {
                cout << ' ';
            }
        }
        cout << '\n';
    }
    return 0;
}

ข้อ 3 ร้านใกล้บ้าน

ระดับง่าย เวลาไม่เกิน 1 วินาที

แอปสั่งอาหารมีร้านในระบบ N ร้าน ร้านที่ i อยู่ห่างจากบ้านของน้อง d_i เมตร หน้าแรกของแอปจะแสดงร้านที่ใกล้ที่สุด K ร้าน เรียงจากใกล้ไปไกล ถ้าสองร้านอยู่ห่างเท่ากัน ร้านที่มีหมายเลขน้อยกว่าขึ้นก่อน ให้หาว่าหน้าแรกแสดงร้านหมายเลขอะไรบ้าง

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ K คั่นด้วยช่องว่าง (1 ≤ K ≤ N ≤ 100000)

บรรทัดที่สองมีระยะทาง d₁ ถึง d_N ของร้านหมายเลข 1 ถึง N คั่นด้วยช่องว่าง แต่ละค่าเป็นจำนวนเต็มตั้งแต่ 0 ถึง 10⁹

ข้อมูลออก

บรรทัดเดียว หมายเลขร้าน K ร้านตามลำดับที่แสดง คั่นด้วยช่องว่างหนึ่งช่อง

5 3
450 120 800 120 300

2 4 5

4 4
700 700 700 50

4 1 2 3

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<pair<int, int>> shops(n);
    for (int i = 0; i < n; i++) {
        cin >> shops[i].first;
        shops[i].second = i + 1;
    }
    sort(shops.begin(), shops.end());
    for (int i = 0; i < k; i++) {
        if (i > 0) {
            cout << ' ';
        }
        cout << shops[i].second;
    }
    cout << '\n';
    return 0;
}

ข้อ 4 ซื้อ 3 จ่าย 2

ระดับง่าย เวลาไม่เกิน 1 วินาที

ร้านเครื่องเขียนจัดโปรโมชัน "ซื้อ 3 จ่าย 2" ลูกค้าวางสินค้าบนสายพานเรียงเป็นแถว แคชเชียร์แบ่งสินค้าเป็นกลุ่มละสามชิ้นตามลำดับบนสายพาน คือชิ้นที่ 1 ถึง 3 ชิ้นที่ 4 ถึง 6 ไปเรื่อยๆ ในแต่ละกลุ่ม ชิ้นที่ถูกที่สุดได้ฟรี ถ้ามีหลายชิ้นถูกที่สุดเท่ากัน ฟรีแค่ชิ้นเดียว ส่วนสินค้าที่เหลือท้ายแถวไม่ครบสามชิ้นต้องจ่ายเต็มราคา

น้องซื้อสินค้า N ชิ้น และเลือกได้ว่าจะวางชิ้นไหนก่อนหลัง ให้หาว่าต้องจ่ายน้อยที่สุดกี่บาท

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N (1 ≤ N ≤ 200000)

บรรทัดที่สองมีราคาของสินค้า N ชิ้น คั่นด้วยช่องว่าง แต่ละราคาเป็นจำนวนเต็มตั้งแต่ 1 ถึง 10⁶ บาท

ข้อมูลออก

ราคารวมที่ต้องจ่ายน้อยที่สุด

6
120 35 80 50 15 60

285

4
100 100 100 100

300

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> price(n);
    for (int &p : price) {
        cin >> p;
    }
    sort(price.begin(), price.end(), greater<int>());
    long long total = 0;
    for (int i = 0; i < n; i++) {
        if (i % 3 != 2) {
            total += price[i];
        }
    }
    cout << total << '\n';
    return 0;
}

ข้อ 5 รายชื่อหน้าห้อง

ระดับกลาง เวลาไม่เกิน 1 วินาที

โรงเรียนเปิดรับสมัครค่ายวิทยาศาสตร์ นักเรียน N คนกรอกใบสมัครเรียงตามเวลาที่ส่ง แต่ละใบมีชื่อเล่น เลขห้อง และคะแนนสอบคัดเลือก ครูต้องการพิมพ์รายชื่อเพื่อติดหน้าห้องตามกติกานี้

• เรียงตามเลขห้องจากน้อยไปมาก
• ในห้องเดียวกัน คะแนนมากกว่าอยู่ก่อน
• ถ้าห้องเดียวกันและคะแนนเท่ากัน คนที่ส่งใบสมัครก่อนอยู่ก่อน

ชื่อเล่นซ้ำกันได้ เพราะนักเรียนต่างห้องอาจชื่อเดียวกัน หรือแม้แต่ในห้องเดียวกันก็มีได้

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N (1 ≤ N ≤ 100000)

อีก N บรรทัด เรียงตามเวลาที่ส่งใบสมัคร บรรทัดละหนึ่งคน มีชื่อเล่น เลขห้อง และคะแนน คั่นด้วยช่องว่าง ชื่อเล่นเป็นตัวพิมพ์เล็กภาษาอังกฤษยาว 1 ถึง 10 ตัว เลขห้องเป็นจำนวนเต็มตั้งแต่ 1 ถึง 20 คะแนนเป็นจำนวนเต็มตั้งแต่ 0 ถึง 100

ข้อมูลออก

N บรรทัดตามลำดับในรายชื่อ บรรทัดละหนึ่งคน มีเลขห้อง ชื่อเล่น และคะแนน คั่นด้วยช่องว่างหนึ่งช่อง

6
ploy 3 85
beam 1 70
mint 3 92
film 1 70
earth 2 60
fah 3 85

1 beam 70
1 film 70
2 earth 60
3 mint 92
3 ploy 85
3 fah 85

4
nam 5 40
nam 5 40
palm 2 100
nam 2 100

2 palm 100
2 nam 100
5 nam 40
5 nam 40

#include <bits/stdc++.h>
using namespace std;

struct Student {
    string name;
    int room;
    int score;
};

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<Student> list(n);
    for (Student &s : list) {
        cin >> s.name >> s.room >> s.score;
    }
    stable_sort(list.begin(), list.end(), [](const Student &a, const Student &b) {
        if (a.room != b.room) {
            return a.room < b.room;
        }
        return a.score > b.score;
    });
    for (const Student &s : list) {
        cout << s.room << ' ' << s.name << ' ' << s.score << '\n';
    }
    return 0;
}

ข้อ 6 รหัสกุญแจ

ระดับกลาง เวลาไม่เกิน 1 วินาที

น้องลืมรหัสกุญแจตู้เก็บของ จำได้แค่ว่ารหัสใช้ตัวเลขชุดหนึ่ง ใช้ครบทุกตัวตัวละหนึ่งครั้ง แต่จำลำดับไม่ได้ และจำได้อีกอย่างว่ารหัสนั้นเป็นจำนวนที่หารด้วย K ลงตัว ตัวเลขในชุดอาจซ้ำกันได้ เช่น ชุด 1 1 2 สร้างรหัสที่ต่างกันได้แค่ 112 121 และ 211

รหัสที่มีหลายหลักขึ้นต้นด้วย 0 ไม่ได้ ถ้าชุดมีตัวเลขตัวเดียว รหัส 0 ใช้ได้

ให้หาว่ามีรหัสที่เป็นไปได้กี่แบบ และรหัสที่น้อยที่สุดคืออะไร

ข้อมูลเข้า

บรรทัดเดียว มีสตริง S ซึ่งเป็นตัวเลขในชุด เขียนติดกัน ยาว 1 ถึง 8 ตัว และจำนวนเต็ม K (1 ≤ K ≤ 10⁶) คั่นด้วยช่องว่าง

ข้อมูลออก

บรรทัดแรกพิมพ์จำนวนรหัสที่ต่างกันทั้งหมดที่ใช้ตัวเลขครบชุดและหารด้วย K ลงตัว

บรรทัดที่สองพิมพ์รหัสที่น้อยที่สุดในบรรดารหัสเหล่านั้น ถ้าไม่มีเลยให้พิมพ์ -1

1203 3

18
1023

112 7

1
112

#include <bits/stdc++.h>
using namespace std;

int main()
{
    string digits;
    int k;
    cin >> digits >> k;
    sort(digits.begin(), digits.end());
    int count = 0;
    int smallest = -1;
    do {
        if (digits.size() > 1 && digits[0] == '0') {
            continue;
        }
        int value = 0;
        for (char ch : digits) {
            value = value * 10 + (ch - '0');
        }
        if (value % k == 0) {
            count++;
            if (smallest == -1) {
                smallest = value;
            }
        }
    } while (next_permutation(digits.begin(), digits.end()));
    cout << count << '\n';
    cout << smallest << '\n';
    return 0;
}

ข้อ 7 สองไฟล์ลงแฟลชไดรฟ์

ระดับกลาง เวลาไม่เกิน 1 วินาที

น้องมีไฟล์วิดีโอ N ไฟล์ ไฟล์ที่ i มีขนาด s_i ไบต์ และมีแฟลชไดรฟ์ที่ว่างอยู่ B ไบต์ น้องอยากเลือกไฟล์สองไฟล์ที่ต่างกันไปให้เพื่อน โดยต้องใส่ทั้งสองไฟล์ลงแฟลชไดรฟ์ได้ คือขนาดรวมไม่เกิน B ให้นับว่ามีวิธีเลือกกี่วิธี

การเลือกไฟล์ที่ i กับไฟล์ที่ j นับเป็นวิธีเดียวกับการเลือกไฟล์ที่ j กับไฟล์ที่ i และไฟล์สองไฟล์ที่ขนาดเท่ากันยังถือเป็นคนละไฟล์

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ B คั่นด้วยช่องว่าง (2 ≤ N ≤ 200000 และ 1 ≤ B ≤ 4 × 10⁹)

บรรทัดที่สองมีขนาดของไฟล์ N ไฟล์ คั่นด้วยช่องว่าง แต่ละขนาดเป็นจำนวนเต็มตั้งแต่ 1 ถึง 2 × 10⁹

ข้อมูลออก

จำนวนวิธีเลือกไฟล์สองไฟล์ที่ขนาดรวมไม่เกิน B

5 1500
700 300 1200 500 900

6

4 8
4 4 4 4

6

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long space;
    cin >> n >> space;
    vector<int> size(n);
    for (int &s : size) {
        cin >> s;
    }
    sort(size.begin(), size.end());
    long long ways = 0;
    for (int i = 0; i < n; i++) {
        long long left = space - size[i];
        auto start = size.begin() + i + 1;
        ways += upper_bound(start, size.end(), left) - start;
    }
    cout << ways << '\n';
    return 0;
}

ข้อ 8 บ้านที่ใกล้จุดพบลูกน้ำ

ระดับกลาง เวลาไม่เกิน 1 วินาที

ถนนสายหนึ่งในหมู่บ้านเป็นเส้นตรงยาว มีบ้าน N หลังตั้งอยู่ริมถนน บ้านหลังที่ i อยู่ที่ตำแหน่ง x_i เมตร นับจากหลักกิโลเมตรศูนย์ ค่าติดลบคืออยู่ก่อนถึงหลัก บ้านหลายหลังอาจอยู่ตำแหน่งเดียวกันได้ เช่น ห้องแถวที่อยู่ในตึกเดียวกัน

อาสาสมัครสาธารณสุขเดินสำรวจริมถนนแล้วพบแหล่งน้ำขังที่มีลูกน้ำยุงลาย Q จุด จุดที่ j อยู่ที่ตำแหน่ง p_j ทุกจุดที่พบ อาสาสมัครจะไปแจ้งบ้านที่อยู่ใกล้จุดนั้นที่สุดให้ช่วยเทน้ำทิ้ง ระยะระหว่างตำแหน่ง a กับ b คือ |a - b| ถ้ามีบ้านสองตำแหน่งที่ห่างเท่ากัน ให้ไปแจ้งบ้านที่ตำแหน่งน้อยกว่า ให้หาว่าแต่ละจุดต้องไปแจ้งบ้านที่ตำแหน่งไหน

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ Q คั่นด้วยช่องว่าง (1 ≤ N, Q ≤ 200000)

บรรทัดที่สองมีตำแหน่งของบ้าน N หลัง คั่นด้วยช่องว่าง แต่ละตำแหน่งเป็นจำนวนเต็มตั้งแต่ -10⁹ ถึง 10⁹ ไม่ได้เรียงมา

บรรทัดที่สามมีตำแหน่ง p₁ ถึง p_Q ของจุดที่พบลูกน้ำ คั่นด้วยช่องว่าง แต่ละตำแหน่งเป็นจำนวนเต็มตั้งแต่ -10⁹ ถึง 10⁹

ข้อมูลออก

Q บรรทัด บรรทัดที่ j คือตำแหน่งของบ้านที่ต้องไปแจ้งสำหรับจุดที่ j

6 6
120 -40 300 120 75 500
100 0 400 -500 900 120

120
-40
300
-40
500
120

3 4
10 30 30
20 25 35 10

10
30
30
10

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> house(n);
    for (int &x : house) {
        cin >> x;
    }
    sort(house.begin(), house.end());
    for (int i = 0; i < q; i++) {
        int p;
        cin >> p;
        int k = lower_bound(house.begin(), house.end(), p) - house.begin();
        int answer;
        if (k == n) {
            answer = house[n - 1];
        } else if (k == 0) {
            answer = house[0];
        } else if (p - house[k - 1] <= house[k] - p) {
            answer = house[k - 1];
        } else {
            answer = house[k];
        }
        cout << answer << '\n';
    }
    return 0;
}

ข้อ 9 ห้องอ่านหนังสือ

ระดับยาก เวลาไม่เกิน 1 วินาที

ห้องอ่านหนังสือของห้องสมุดใช้บัตรนักเรียนแตะเข้าออก ระบบเก็บประวัติไว้ N รายการ รายการที่ i บอกว่านักเรียนคนหนึ่งแตะเข้าที่เวลา s_i และแตะออกที่เวลา e_i เวลาเป็นวินาทีนับจากวันที่ระบบเริ่มบันทึก นักเรียนคนนั้นอยู่ในห้องตั้งแต่วินาทีที่ s_i จนถึงก่อนวินาทีที่ e_i ถ้าคนหนึ่งแตะออกที่เวลา t และอีกคนแตะเข้าที่เวลา t พอดี ถือว่าสองคนนี้ไม่ได้อยู่ในห้องพร้อมกัน

บรรณารักษ์อยากรู้ว่าห้องเคยมีคนอยู่พร้อมกันมากที่สุดกี่คน และจำนวนนั้นเกิดขึ้นครั้งแรกที่เวลาเท่าไร

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N (1 ≤ N ≤ 200000)

อีก N บรรทัด บรรทัดละหนึ่งรายการ มีจำนวนเต็ม s และ e คั่นด้วยช่องว่าง (0 ≤ s < e ≤ 10⁹) รายการไม่ได้เรียงตามเวลา

ข้อมูลออก

บรรทัดเดียว มีจำนวนคนที่อยู่พร้อมกันมากที่สุด ตามด้วยช่องว่าง แล้วตามด้วยเวลาแรกสุดที่ห้องมีคนจำนวนนั้น

5
10 50
20 30
40 70
25 45
60 80

3 25

3
0 10
10 20
20 30

1 0

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<pair<int, int>> events;
    events.reserve(2 * n);
    for (int i = 0; i < n; i++) {
        int enter, leave;
        cin >> enter >> leave;
        events.push_back({enter, 1});
        events.push_back({leave, -1});
    }
    sort(events.begin(), events.end());
    int inside = 0;
    int best = 0;
    int best_time = 0;
    for (auto [time, change] : events) {
        inside += change;
        if (inside > best) {
            best = inside;
            best_time = time;
        }
    }
    cout << best << ' ' << best_time << '\n';
    return 0;
}

ข้อ 10 อันดับไม่ข้ามเลข

ระดับยาก เวลาไม่เกิน 1 วินาที

เกมมือถือเกมหนึ่งจัดอันดับผู้เล่น N คนจากแต้มสะสม แต้มมากได้อันดับดีกว่า ผู้เล่นที่แต้มเท่ากันได้อันดับเดียวกัน และอันดับถัดไปไม่ข้ามเลข เช่น แต้ม 90 85 85 70 ได้อันดับ 1 2 2 3 ไม่ใช่ 1 2 2 4 อย่างการจัดอันดับแบบนับจำนวนคนที่ดีกว่า

ให้บอกอันดับของผู้เล่นทุกคนตามลำดับในข้อมูลเข้า

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N (1 ≤ N ≤ 200000)

บรรทัดที่สองมีแต้มของผู้เล่นคนที่ 1 ถึงคนที่ N คั่นด้วยช่องว่าง แต่ละค่าเป็นจำนวนเต็มตั้งแต่ 0 ถึง 10⁹

ข้อมูลออก

บรรทัดเดียว อันดับของผู้เล่นคนที่ 1 ถึงคนที่ N คั่นด้วยช่องว่างหนึ่งช่อง

4
85 90 70 85

2 1 3 2

7
300 1200 300 950 1200 0 950

3 1 3 2 1 4 2

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> points(n);
    for (int &p : points) {
        cin >> p;
    }
    vector<int> distinct = points;
    sort(distinct.begin(), distinct.end());
    distinct.erase(unique(distinct.begin(), distinct.end()), distinct.end());
    int d = distinct.size();
    for (int i = 0; i < n; i++) {
        int pos = lower_bound(distinct.begin(), distinct.end(), points[i]) - distinct.begin();
        if (i > 0) {
            cout << ' ';
        }
        cout << d - pos;
    }
    cout << '\n';
    return 0;
}