[0]zero-index clytie0x/zero-index

18.6 แบบฝึกหัด

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

ข้อ 1 นกที่พบในช่วงแรก

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

ชมรมดูนกของโรงเรียนออกสำรวจทุกวัน N วัน วันที่ i จดรหัสชนิดของนกตัวแรกที่เห็นในวันนั้นไว้ นกชนิดเดียวกันอาจถูกจดซ้ำได้หลายวัน ประธานชมรมมีคำถาม Q ข้อ แต่ละข้อถามว่า ตั้งแต่วันที่ 1 ถึงวันที่ k ชมรมเจอนกกี่ชนิดที่ไม่ซ้ำกัน

ข้อมูลเข้า

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

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

อีก Q บรรทัด บรรทัดละหนึ่งคำถาม มีจำนวนเต็ม k โดยที่ 1 ≤ k ≤ N

ข้อมูลออก

Q บรรทัด ตอบคำถามตามลำดับ บรรทัดละหนึ่งข้อ เป็นจำนวนชนิดนกที่ไม่ซ้ำกันตั้งแต่วันที่ 1 ถึงวันที่ k

6 5
7 3 7 12 3 5
1
3
4
6
2
1
2
3
4
2
3 3
1000000 1000000 1
2
3
1
1
2
1
ดูคำใบ้

ถ้าตอบแต่ละคำถามด้วยการไล่ k วันแรกใหม่ งานรวมคือ O(NQ) ซึ่งเป็น 4 × 1010 ไม่ทัน ให้เตรียมคำตอบของทุก k ไว้ก่อนในรอบเดียว ไล่วันที่ 1 ถึง N ใช้อาเรย์จำว่าชนิดไหนเคยเห็นแล้วแบบหน้า 5.3 นับชนิดใหม่สะสมไป แล้วเก็บจำนวนชนิดหลังวันที่ k ไว้ในช่องที่ k จากนั้นตอบคำถามละ O(1) รวมเป็น O(N + Q)

ดูเฉลย 
#include <bits/stdc++.h>
using namespace std;

bool seen[1000001];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<int> kinds(n + 1);
    kinds[0] = 0;
    for (int i = 1; i <= n; i++) {
        int b;
        cin >> b;
        kinds[i] = kinds[i - 1];
        if (!seen[b]) {
            seen[b] = true;
            kinds[i]++;
        }
    }
    for (int t = 0; t < q; t++) {
        int k;
        cin >> k;
        cout << kinds[k] << '\n';
    }
    return 0;
}

ข้อ 2 คิวร้านขนม

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

ร้านขนมหน้าโรงเรียนมีคิวเดียว ช่วงพักกลางวันมีเหตุการณ์เกิดขึ้น N ครั้งตามลำดับ แต่ละครั้งเป็นอย่างใดอย่างหนึ่ง

  • 1 x นักเรียนเลขประจำตัว x มาต่อท้ายคิว
  • 2 แม่ค้าขายขนมให้คนที่อยู่หัวคิว แล้วคนนั้นออกจากคิวไป

ทุกครั้งที่ขาย ให้พิมพ์เลขประจำตัวของคนที่ได้ขนม ถ้าตอนนั้นไม่มีใครในคิว ให้พิมพ์ empty แทน

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N โดยที่ 1 ≤ N ≤ 1000000

อีก N บรรทัด แต่ละบรรทัดเป็นเหตุการณ์ในรูปแบบข้างบน เลขประจำตัว x เป็นจำนวนเต็มตั้งแต่ 1 ถึง 1000000000 รับประกันว่ามีเหตุการณ์ 2 อย่างน้อยหนึ่งครั้ง

ข้อมูลออก

หนึ่งบรรทัดต่อเหตุการณ์ 2 หนึ่งครั้ง ตามลำดับ เป็นเลขประจำตัวของคนที่ได้ขนม หรือ empty

7
1 6701
1 6702
2
1 6815
2
2
2
6701
6702
6815
empty
3
2
1 1000000000
2
empty
1000000000
ดูคำใบ้

ถ้าเก็บคิวใน vector แล้วลบหัวคิวด้วย erase(v.begin()) ทุกครั้งที่ลบต้องเลื่อนคนที่เหลือทั้งแถว เมื่อคิวยาวหลายแสนคนจะไม่ทัน ใช้ queue จากบทที่ 17 ที่ push และ pop ได้ใน O(1) หรือเก็บใน vector แล้วจำตำแหน่งหัวคิวไว้ในตัวแปร แบบในหน้า 18.4

ดูเฉลย 
#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    queue<int> line;
    for (int i = 0; i < n; i++) {
        int type;
        cin >> type;
        if (type == 1) {
            int x;
            cin >> x;
            line.push(x);
        } else if (line.empty()) {
            cout << "empty\n";
        } else {
            cout << line.front() << '\n';
            line.pop();
        }
    }
    return 0;
}

ข้อ 3 คู่คะแนนพอดี

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

ครูจะจับนักเรียน N คนเป็นคู่ทำโครงงาน และอยากให้คะแนนเก็บของสองคนในคู่รวมกันได้ K พอดี เพื่อให้ทุกคู่มีกำลังเท่ากัน ให้หาว่ามีคู่ของนักเรียนสองคนที่ต่างกันกี่คู่ที่คะแนนรวมเท่ากับ K คู่ของคนที่ i กับคนที่ j นับเป็นคู่เดียวกับคู่ของคนที่ j กับคนที่ i

ข้อมูลเข้า

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

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

ข้อมูลออก

จำนวนคู่ที่คะแนนรวมเท่ากับ K

6 100
30 70 55 45 70 20
3
5 10
5 5 5 3 7
4
ดูคำใบ้

ไล่นักเรียนทีละคนจากซ้ายไปขวา คนที่มีคะแนน x จับคู่กับคนก่อนหน้าที่มีคะแนน K − x ได้ทุกคน ถ้าเก็บอาเรย์นับว่าคะแนนแต่ละค่าเคยเห็นมาแล้วกี่คนแบบหน้า 5.3 ก็บวกจำนวนนั้นได้ทันที แล้วค่อยนับคนปัจจุบันเพิ่ม รวมเป็น O(N) ระวังสองเรื่อง K − x อาจน้อยกว่า 1 หรือเกิน 1000000 ซึ่งอยู่นอกอาเรย์ และจำนวนคู่ใหญ่ได้ถึงราว 2 × 1010 ต้องใช้ long long

ดูเฉลย 
#include <bits/stdc++.h>
using namespace std;

#define MAX_SCORE 1000000
int seen[MAX_SCORE + 1];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    long long pairs = 0;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        int need = k - x;
        if (need >= 1 && need <= MAX_SCORE) {
            pairs += seen[need];
        }
        seen[x]++;
    }
    cout << pairs << '\n';
    return 0;
}

ข้อ 4 สองชิ้นพอดีงบ

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

ร้านขายอุปกรณ์มือถือเรียงสินค้า N ชิ้นตามราคาจากถูกไปแพง ไม่มีสินค้าสองชิ้นไหนราคาเท่ากัน น้องมีเงิน K บาท และอยากซื้อสินค้าสองชิ้นที่ต่างกันโดยใช้เงินหมดพอดี ให้หาว่ามีวิธีเลือกกี่วิธี การเลือกชิ้นที่ i กับชิ้นที่ j นับเป็นวิธีเดียวกับการเลือกชิ้นที่ j กับชิ้นที่ i

ข้อมูลเข้า

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

บรรทัดที่สองมีราคา N ค่า เรียงจากน้อยไปมาก ไม่มีค่าซ้ำ คั่นด้วยช่องว่าง แต่ละค่าเป็นจำนวนเต็มตั้งแต่ 1 ถึง 2000000000

ข้อมูลออก

จำนวนวิธีเลือกสินค้าสองชิ้นที่ราคารวมเท่ากับ K

7 1000
150 300 450 550 700 850 990
3
5 20
1 5 10 15 19
2
ดูคำใบ้

ข้อ 3 ใช้อาเรย์นับได้เพราะค่าไม่เกิน 106 ข้อนี้ราคาถึง 2 × 109 ใช้วิธีนั้นไม่ได้ แต่ราคาเรียงมาแล้วและไม่ซ้ำ ใช้สองตัวชี้ i เริ่มที่ชิ้นถูกสุด j เริ่มที่ชิ้นแพงสุด ถ้ารวมกันน้อยกว่า K ชิ้น i จับคู่กับชิ้นไหนที่เหลือก็ไม่พอ ให้เลื่อน i ไปทางขวา ถ้ามากกว่า K ให้เลื่อน j ไปทางซ้าย ถ้าพอดีให้นับแล้วเลื่อนทั้งคู่ ทำจน i กับ j มาเจอกัน เป็น O(N) ระวังราคาสองชิ้นรวมกันได้ถึงเกือบ 4 × 109 เกิน int และ K ก็เกิน int ได้

ดูเฉลย 
#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    long long k;
    cin >> n >> k;
    vector<long long> price(n);
    for (int i = 0; i < n; i++) {
        cin >> price[i];
    }
    int ways = 0;
    int i = 0, j = n - 1;
    while (i < j) {
        long long total = price[i] + price[j];
        if (total == k) {
            ways++;
            i++;
            j--;
        } else if (total < k) {
            i++;
        } else {
            j--;
        }
    }
    cout << ways << '\n';
    return 0;
}

ข้อ 5 นับรอบลูปคูณสอง

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

น้องอยากรู้ว่าโค้ดนี้ทำ count++ กี่ครั้ง แต่ถ้ารันตรงๆ เมื่อ N ใหญ่จะรอไม่ไหว ให้เขียนโปรแกรมที่ตอบจำนวนนั้นได้เร็ว

long long count = 0;
for (long long i = 1; i <= N; i++) {
    for (long long j = 1; j <= i; j *= 2) {
        count++;
    }
}

ตัวอย่างเช่น N = 5 รอบที่ i = 1 ลูปในวน 1 รอบ i = 2 และ 3 วน 2 รอบ i = 4 และ 5 วน 3 รอบ รวมเป็น 1 + 2 + 2 + 3 + 3 = 11

ข้อมูลเข้า

บรรทัดเดียว มีจำนวนเต็ม N โดยที่ 1 ≤ N ≤ 1000000000000000 (1015)

ข้อมูลออก

จำนวนครั้งที่ทำ count++

5
11
16
54
ดูคำใบ้

ลูปในของรอบที่ i วนเท่ากับจำนวนหลักของ i เมื่อเขียนเป็นเลขฐานสอง i ที่ 2b−1 ≤ i ≤ 2b − 1 วนลูปในเท่ากันคือ b รอบ และมี 2b−1 ตัว แบ่ง 1 ถึง N เป็นกลุ่มตาม b แล้วบวก b × จำนวนตัวในกลุ่ม กลุ่มสุดท้ายถูก N ตัดกลางทาง ต้องนับแค่ถึง N มีไม่เกินราว 50 กลุ่ม จึงเป็น O(log N)

ดูเฉลย 
#include <bits/stdc++.h>
using namespace std;

int main()
{
    long long n;
    cin >> n;
    long long count = 0;
    long long low = 1;
    for (int bits = 1; low <= n; bits++) {
        long long high = min(2 * low - 1, n);
        count += bits * (high - low + 1);
        low *= 2;
    }
    cout << count << '\n';
    return 0;
}

ข้อ 6 บีกเกอร์ตวงพอดี

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

ห้องแล็บมีบีกเกอร์ N ใบ ใบที่ i จุน้ำได้ ai มิลลิลิตร ครูให้เลือกบีกเกอร์สองใบที่ต่างกัน ใบแรกใช้ตักน้ำจนเต็มแล้วเทใส่ใบที่สองซ้ำหลายรอบ ถ้าความจุของใบที่สองหารด้วยความจุของใบแรกลงตัว ใบที่สองจะเต็มพอดีโดยน้ำไม่ล้น ให้นับว่ามีวิธีเลือกใบตักกับใบรับแบบนี้กี่วิธี

การเลือกใบที่ i ตักแล้วใบที่ j รับ ต่างจากใบที่ j ตักแล้วใบที่ i รับ ถ้าสองใบจุเท่ากัน ทั้งสองแบบใช้ได้และนับเป็นสองวิธี

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N โดยที่ 2 ≤ N ≤ 200000

บรรทัดที่สองมีความจุ a1 ถึง aN คั่นด้วยช่องว่าง แต่ละค่าเป็นจำนวนเต็มตั้งแต่ 1 ถึง 1000000

ข้อมูลออก

จำนวนวิธีเลือกใบตักกับใบรับที่เทแล้วเต็มพอดี

5
50 100 250 30 500
5
3
200 200 600
4
ดูคำใบ้

ไล่ทุกคู่ต้องหาร N(N − 1) ครั้ง ราว 4 × 1010 ไม่ทัน ความจุไม่เกิน 106 จึงนับด้วยอาเรย์ได้ว่าความจุแต่ละค่ามีกี่ใบ แล้วกลับด้านคำถาม แทนที่จะถามว่าใบที่รับหารด้วยอะไรลงตัว ให้ไล่ความจุของใบที่ตัก d แล้วกระโดดไปทุกพหุคูณ 2d 3d ... จนถึง 106 จำนวนรอบรวมคือ 106/1 + 106/2 + ... ซึ่งเป็น O(V log V) แบบลูป harmonic ในหน้า 18.3 คู่ที่ความจุเท่ากันต้องนับแยก เพราะห้ามใช้ใบเดียวกันทั้งตักและรับ คำตอบเกิน int ได้

ดูเฉลย 
#include <bits/stdc++.h>
using namespace std;

#define MAX_VOLUME 1000000
long long how_many[MAX_VOLUME + 1];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int v;
        cin >> v;
        how_many[v]++;
    }
    long long ways = 0;
    for (int d = 1; d <= MAX_VOLUME; d++) {
        if (how_many[d] == 0) {
            continue;
        }
        ways += how_many[d] * (how_many[d] - 1);
        for (int m = 2 * d; m <= MAX_VOLUME; m += d) {
            ways += how_many[d] * how_many[m];
        }
    }
    cout << ways << '\n';
    return 0;
}

ข้อ 7 ของขวัญสามชิ้น

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

ร้านของขวัญวางสินค้าเรียงเป็นแถว N ชิ้น ชิ้นที่ i ราคา pi บาท น้องมีเงิน K บาท และอยากซื้อของสามชิ้นที่ต่างกัน โดยใช้เงินหมดพอดี ให้หาว่ามีวิธีเลือกของสามชิ้นกี่แบบ การเลือกชิ้นเดียวกันในลำดับต่างกันนับเป็นแบบเดียว ของสองชิ้นที่ราคาเท่ากันนับเป็นคนละชิ้น

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม N และ K คั่นด้วยช่องว่าง โดยที่ 3 ≤ N ≤ 5000 และ 3 ≤ K ≤ 3000000

บรรทัดที่สองมีราคา p1 ถึง pN คั่นด้วยช่องว่าง แต่ละค่าเป็นจำนวนเต็มตั้งแต่ 1 ถึง 1000000

ข้อมูลออก

จำนวนแบบของการเลือกของสามชิ้นที่ราคารวมเท่ากับ K

6 100
20 50 30 10 40 60
3
4 9
3 3 3 3
4
ดูคำใบ้

N ≤ 5000 ลูปสามชั้นทำงานราว N3 / 6 ≈ 2 × 1010 ครั้ง ไม่ทัน แต่ O(N2) ยังทัน ให้ตรึงชิ้นกลาง j แล้วไล่ชิ้นท้าย k ที่อยู่หลัง j ราคาของชิ้นแรกต้องเป็น K − pj − pk พอดี ถ้ามีอาเรย์นับว่าราคาแต่ละค่าปรากฏกี่ครั้งในชิ้นที่อยู่ก่อน j ก็บวกได้ทันที ไล่ k ครบแล้วค่อยนับ pj ลงอาเรย์ ก่อนขยับ j ไปตัวถัดไป ราคาที่ต้องการอาจน้อยกว่า 1 หรือเกิน 1000000 และคำตอบเกิน int ได้

ดูเฉลย 
#include <bits/stdc++.h>
using namespace std;

#define MAX_PRICE 1000000
int before[MAX_PRICE + 1];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    vector<int> price(n);
    for (int i = 0; i < n; i++) {
        cin >> price[i];
    }
    long long ways = 0;
    for (int j = 0; j < n; j++) {
        for (int l = j + 1; l < n; l++) {
            int need = k - price[j] - price[l];
            if (need >= 1 && need <= MAX_PRICE) {
                ways += before[need];
            }
        }
        before[price[j]]++;
    }
    cout << ways << '\n';
    return 0;
}

ข้อ 8 เพลย์ลิสต์ไม่ซ้ำ

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

แอปฟังเพลงเก็บประวัติเพลงที่น้องเปิดฟัง N เพลงตามลำดับ เพลงแต่ละเพลงมีรหัสเป็นจำนวนเต็ม เพลงเดียวกันอาจถูกเปิดหลายครั้ง แอปอยากทำสรุปท้ายปีว่าช่วงที่ฟังเพลงติดกันโดยไม่มีเพลงไหนซ้ำเลยยาวที่สุดกี่เพลง ถ้ามีหลายช่วงที่ยาวเท่ากัน ให้ตอบช่วงที่เริ่มเร็วที่สุด

ข้อมูลเข้า

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

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

ข้อมูลออก

บรรทัดเดียว มีความยาวของช่วงที่ยาวที่สุด ตามด้วยลำดับของเพลงแรกในช่วงนั้น (นับเพลงแรกของประวัติเป็นเพลงที่ 1) คั่นด้วยช่องว่าง

8
4 7 4 9 2 7 5 9
5 3
6
1 2 3 1 2 3
3 1
ดูคำใบ้

ถ้าช่วงหนึ่งไม่มีเพลงซ้ำ ช่วงที่อยู่ข้างในก็ไม่มีเพลงซ้ำด้วย จึงใช้สองตัวชี้แบบหน้า 18.5 ได้ ขยาย r ทีละเพลง ใช้อาเรย์นับว่าในช่วงตอนนี้มีเพลงแต่ละรหัสกี่ครั้ง ถ้าเพลงใหม่ทำให้มีเพลงซ้ำ ให้เลื่อน l ไปพร้อมลดตัวนับจนไม่ซ้ำ ทั้ง l และ r เดินไปทางเดียวรวมไม่เกิน 2N ก้าว เป็น O(N) อัปเดตคำตอบเฉพาะตอนได้ช่วงที่ยาวกว่าเดิมจริงๆ จะได้ช่วงที่เริ่มเร็วที่สุดเอง

ดูเฉลย 
#include <bits/stdc++.h>
using namespace std;

int inside[1000001];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> song(n);
    for (int i = 0; i < n; i++) {
        cin >> song[i];
    }
    int best = 0, best_start = 0;
    int l = 0;
    for (int r = 0; r < n; r++) {
        inside[song[r]]++;
        while (inside[song[r]] > 1) {
            inside[song[l]]--;
            l++;
        }
        if (r - l + 1 > best) {
            best = r - l + 1;
            best_start = l;
        }
    }
    cout << best << ' ' << best_start + 1 << '\n';
    return 0;
}