5.6 แบบฝึกหัด

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

ข้อ 1 กลับหลังหัน

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

หน้าเสาธงมีนักเรียนเข้าแถวตอนเรียงหนึ่ง N คน แต่ละคนมีเลขประจำตัว ครูสั่งกลับหลังหัน คนที่เคยอยู่ท้ายแถวจึงกลายเป็นหัวแถว ให้พิมพ์เลขประจำตัวของนักเรียนเรียงจากหัวแถวใหม่ไปท้ายแถวใหม่

ข้อมูลเข้า

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

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

ข้อมูลออก

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

5
10432 10518 10377 10291 10605

10605 10291 10377 10518 10432

#include <stdio.h>

int id[1000];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &id[i]);
    }
    for (int i = n - 1; i >= 0; i--) {
        printf("%d", id[i]);
        if (i > 0) {
            printf(" ");
        }
    }
    printf("\n");
    return 0;
}

ข้อ 2 ดาวสำหรับคนไม่ต่ำกว่าค่าเฉลี่ย

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

ครูประกาศว่า ใครได้คะแนนสอบไม่ต่ำกว่าค่าเฉลี่ยของห้อง จะได้ดาวคนละหนึ่งดวง ห้องนี้มีนักเรียน N คน ให้หาว่ามีกี่คนที่ได้ดาว ค่าเฉลี่ยคือผลรวมคะแนนของทุกคนหารด้วย N โดยไม่ปัดเศษ

ข้อมูลเข้า

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

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

ข้อมูลออก

จำนวนนักเรียนที่ได้คะแนนมากกว่าหรือเท่ากับค่าเฉลี่ย

6
70 85 90 65 80 58

3

3
50 50 50

3

#include <stdio.h>

int score[1000];

int main()
{
    int n;
    scanf("%d", &n);
    int total = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &score[i]);
        total += score[i];
    }
    int stars = 0;
    for (int i = 0; i < n; i++) {
        if (score[i] * n >= total) {
            stars++;
        }
    }
    printf("%d\n", stars);
    return 0;
}

ข้อ 3 อากาศบนยอดเขา

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

สถานีตรวจอากาศบนยอดเขาบันทึกอุณหภูมิตอนตีห้าไว้ N วัน เรียกว่าวันที่ 1 ถึงวันที่ N ให้หาวันที่อุ่นที่สุดและวันที่หนาวที่สุด ถ้าอุณหภูมิสูงสุดเกิดหลายวัน ให้ตอบวันแรกสุด แต่ถ้าอุณหภูมิต่ำสุดเกิดหลายวัน ให้ตอบวันหลังสุด

ข้อมูลเข้า

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

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

ข้อมูลออก

บรรทัดแรกพิมพ์อุณหภูมิสูงสุด ตามด้วยวันแรกสุดที่ได้อุณหภูมินั้น

บรรทัดที่สองพิมพ์อุณหภูมิต่ำสุด ตามด้วยวันหลังสุดที่ได้อุณหภูมินั้น

ตัวเลขในบรรทัดเดียวกันคั่นด้วยช่องว่างหนึ่งช่อง

7
3 -1 5 5 -2 0 -2

5 3
-2 7

#include <stdio.h>

int temp[1000];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &temp[i]);
    }
    int warmest = 0;
    int coldest = 0;
    for (int i = 1; i < n; i++) {
        if (temp[i] > temp[warmest]) {
            warmest = i;
        }
        if (temp[i] <= temp[coldest]) {
            coldest = i;
        }
    }
    printf("%d %d\n", temp[warmest], warmest + 1);
    printf("%d %d\n", temp[coldest], coldest + 1);
    return 0;
}

ข้อ 4 ตารางคะแนน

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

โรงเรียนจัดสอบวัดระดับ คะแนนเต็ม 100 มีนักเรียนเข้าสอบ N คน ฝ่ายวิชาการอยากได้ตารางว่าแต่ละคะแนนมีนักเรียนได้กี่คน เรียงจากคะแนนสูงไปคะแนนต่ำ ใส่เฉพาะคะแนนที่มีคนได้

ข้อมูลเข้า

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

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

ข้อมูลออก

บรรทัดละหนึ่งคะแนน แต่ละบรรทัดมีคะแนน ตามด้วยจำนวนนักเรียนที่ได้คะแนนนั้น คั่นด้วยช่องว่าง เรียงจากคะแนนมากไปน้อย พิมพ์เฉพาะคะแนนที่มีนักเรียนได้อย่างน้อยหนึ่งคน

8
70 85 70 100 64 85 70 0

100 1
85 2
70 3
64 1
0 1

#include <stdio.h>

int count[101];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        int score;
        scanf("%d", &score);
        count[score]++;
    }
    for (int s = 100; s >= 0; s--) {
        if (count[s] > 0) {
            printf("%d %d\n", s, count[s]);
        }
    }
    return 0;
}

ข้อ 5 แถวซื้อตั๋ว

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

แถวซื้อตั๋วคอนเสิร์ตมี N คน แต่ละคนถือบัตรคิวคนละเลข แล้วเกิดเหตุสองอย่างตามลำดับ

1. คนที่ยืนลำดับที่ P ออกจากแถวไป คนข้างหลังเขาขยับขึ้นมาคนละหนึ่งที่
2. คนถือบัตรเลข X เข้ามาแทรก ให้ตัวเองเป็นคนลำดับที่ Q ของแถว ลำดับนี้นับในแถวที่มีคนออกไปแล้ว ถ้า Q = N แปลว่าเขาไปต่อท้ายแถว

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

ข้อมูลเข้า

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

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

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

ข้อมูลออก

บรรทัดเดียว มีเลขบัตร N ตัว เรียงจากหัวแถว คั่นด้วยช่องว่างหนึ่งช่อง

6
11 12 13 14 15 16
3 2 99

11 99 12 14 15 16

#include <stdio.h>

int line[1000];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &line[i]);
    }
    int p, q, x;
    scanf("%d %d %d", &p, &q, &x);
    for (int i = p - 1; i < n - 1; i++) {
        line[i] = line[i + 1];
    }
    n--;
    for (int i = n; i > q - 1; i--) {
        line[i] = line[i - 1];
    }
    line[q - 1] = x;
    n++;
    for (int i = 0; i < n; i++) {
        printf("%d", line[i]);
        if (i < n - 1) {
            printf(" ");
        }
    }
    printf("\n");
    return 0;
}

ข้อ 6 ม้าหมุน

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

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

ข้อมูลเข้า

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

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

ข้อมูลออก

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

5 2
1 2 3 4 5

4 5 1 2 3

4 8
7 3 9 1

7 3 9 1

#include <stdio.h>

int horse[100000];

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &horse[i]);
    }
    int shift = k % n;
    for (int j = 0; j < n; j++) {
        printf("%d", horse[(j - shift + n) % n]);
        if (j < n - 1) {
            printf(" ");
        }
    }
    printf("\n");
    return 0;
}

ข้อ 7 บัตรคิวเลขซ้ำ

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

เครื่องออกบัตรคิวของโรงพยาบาลรวน บางครั้งพิมพ์เลขซ้ำกับบัตรที่ออกไปแล้ว วันนี้เครื่องออกบัตรไป N ใบ เรียกว่าใบที่ 1 ถึงใบที่ N ตามลำดับที่ออก ให้หาบัตรใบแรกที่มีเลขซ้ำกับบัตรใบใดใบหนึ่งที่ออกมาก่อนหน้า

ตัวอย่างเช่น ถ้าเลขบนบัตรเรียงเป็น 5 3 8 3 5 บัตรใบที่ 4 เลข 3 ซ้ำกับใบที่ 2 และเกิดก่อนใบที่ 5 เลข 5 ที่ซ้ำกับใบที่ 1 คำตอบจึงเป็นใบที่ 4

ข้อมูลเข้า

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

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

ข้อมูลออก

ถ้ามีบัตรที่ซ้ำ พิมพ์ลำดับของบัตรใบแรกที่ซ้ำ ตามด้วยเลขบนบัตรใบนั้น คั่นด้วยช่องว่าง ถ้าไม่มีบัตรใบไหนซ้ำเลย พิมพ์ -1

7
5 3 8 3 5 9 8

4 3

4
10 20 30 40

-1

#include <stdio.h>

int seen[1000001];

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        int number;
        scanf("%d", &number);
        if (seen[number] == 1) {
            printf("%d %d\n", i, number);
            return 0;
        }
        seen[number] = 1;
    }
    printf("-1\n");
    return 0;
}

ข้อ 8 ป้ายรถเมล์

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

ถนนสายหนึ่งเป็นเส้นตรง มีป้ายรถเมล์ N ป้าย หมายเลข 1 ถึง N เรียงจากต้นถนนไปท้ายถนน ระยะทางจากป้ายที่ i ไปป้ายที่ i + 1 คือ D_i เมตร มีผู้โดยสารถามคำถาม Q ข้อ แต่ละข้อถามว่าป้าย A กับป้าย B ห่างกันกี่เมตร หมายเลข A อาจมากกว่า B ก็ได้

ข้อมูลเข้า

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

บรรทัดที่สองมีจำนวนเต็ม N - 1 ตัว คือ D₁ ถึง D_N-1 คั่นด้วยช่องว่าง โดยที่ 1 ≤ D_i ≤ 100000

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

ข้อมูลออก

Q บรรทัด ตอบคำถามตามลำดับ บรรทัดละหนึ่งข้อ เป็นระยะทางระหว่างป้าย A กับป้าย B หน่วยเมตร

5 3
120 300 80 500
1 5
4 2
3 3

1000
380
0

#include <stdio.h>

long long dist[100001];

int main()
{
    int n, q;
    scanf("%d %d", &n, &q);
    dist[1] = 0;
    for (int i = 2; i <= n; i++) {
        int gap;
        scanf("%d", &gap);
        dist[i] = dist[i - 1] + gap;
    }
    for (int k = 0; k < q; k++) {
        int a, b;
        scanf("%d %d", &a, &b);
        if (a > b) {
            int temp = a;
            a = b;
            b = temp;
        }
        printf("%lld\n", dist[b] - dist[a]);
    }
    return 0;
}

ข้อ 9 ช่วงที่กำไรดีที่สุด

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

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

ข้อมูลเข้า

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

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

ข้อมูลออก

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

7 3
500 -200 800 300 -100 900 -400

1100 1

#include <stdio.h>

int profit[200000];
long long prefix[200001];

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; i++) {
        scanf("%d", &profit[i]);
    }
    prefix[0] = 0;
    for (int i = 1; i <= n; i++) {
        prefix[i] = prefix[i - 1] + profit[i - 1];
    }
    long long best = prefix[k] - prefix[0];
    int best_start = 1;
    for (int start = 2; start <= n - k + 1; start++) {
        long long total = prefix[start + k - 1] - prefix[start - 1];
        if (total > best) {
            best = total;
            best_start = start;
        }
    }
    printf("%lld %d\n", best, best_start);
    return 0;
}

ข้อ 10 นับผู้เล่นตามช่วงแต้ม

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

เกมออนไลน์เกมหนึ่งมีผู้เล่น N คน แต่ละคนมีแต้มสะสมเป็นจำนวนเต็มตั้งแต่ 0 ถึง 1000000 ทีมงานกำลังวางแผนแจกรางวัลตามช่วงแต้ม จึงถามคำถาม Q ข้อ แต่ละข้อถามว่ามีผู้เล่นกี่คนที่มีแต้มตั้งแต่ A ถึง B รวมทั้ง A และ B ด้วย

ข้อมูลเข้า

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

บรรทัดที่สองมีแต้มของผู้เล่น N คน คั่นด้วยช่องว่าง

อีก Q บรรทัด แต่ละบรรทัดมีจำนวนเต็ม A และ B คั่นด้วยช่องว่าง โดยที่ 0 ≤ A ≤ B ≤ 1000000

ข้อมูลออก

Q บรรทัด ตอบคำถามตามลำดับ บรรทัดละหนึ่งข้อ เป็นจำนวนผู้เล่นที่มีแต้มตั้งแต่ A ถึง B

6 4
120 50 999 50 0 1000000
0 1000000
50 50
51 998
0 49

6
2
1
1

#include <stdio.h>

int count[1000001];
int prefix[1000002];

int main()
{
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 0; i < n; i++) {
        int points;
        scanf("%d", &points);
        count[points]++;
    }
    prefix[0] = 0;
    for (int v = 0; v <= 1000000; v++) {
        prefix[v + 1] = prefix[v] + count[v];
    }
    for (int k = 0; k < q; k++) {
        int a, b;
        scanf("%d %d", &a, &b);
        printf("%d\n", prefix[b + 1] - prefix[a]);
    }
    return 0;
}