9.6 แบบฝึกหัด

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

ข้อ 1 ป้ายไฟเลขฐานสอง

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

ป้ายหน้าห้องคอมพิวเตอร์แสดงตัวเลขด้วยหลอดไฟเรียงเป็นแถว หลอดที่ติดแทน 1 หลอดที่ดับแทน 0 อ่านเป็นเลขฐานสอง เช่น เลข 13 แสดงเป็น 1101 เพราะ 13 = 8 + 4 + 1 ให้แปลงจำนวนเต็ม N เป็นเลขฐานสองที่ป้ายต้องแสดง โดยไม่มีหลอดดับนำหน้า ยกเว้น N เป็น 0 ซึ่งป้ายแสดงหลอดดับหลอดเดียว

ข้อมูลเข้า

จำนวนเต็ม N หนึ่งตัว โดยที่ 0 ≤ N ≤ 10¹⁸

ข้อมูลออก

เลขฐานสองของ N ในบรรทัดเดียว ไม่มีเลข 0 นำหน้า ถ้า N เป็น 0 ให้พิมพ์ 0

13

1101

6

110

#include <stdio.h>

void print_binary(long long n)
{
    if (n >= 2) {
        print_binary(n / 2);
    }
    printf("%lld", n % 2);
}

int main()
{
    long long n;
    scanf("%lld", &n);
    print_binary(n);
    printf("\n");
    return 0;
}

ข้อ 2 ตัดริบบิ้น

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

ร้านดอกไม้มีริบบิ้น N ม้วน ม้วนที่ i ยาว a_i เซนติเมตร เจ้าของร้านอยากตัดริบบิ้นทุกม้วนเป็นชิ้นที่ยาวเท่ากันทุกชิ้น ความยาวของชิ้นเป็นจำนวนเต็มเซนติเมตร และต้องไม่เหลือเศษจากม้วนไหนเลย เพื่อให้ผูกช่อดอกไม้ได้สวย อยากได้ชิ้นที่ยาวที่สุดเท่าที่ทำได้ ให้หาว่าชิ้นยาวเท่าไร และได้ทั้งหมดกี่ชิ้น

ข้อมูลเข้า

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

บรรทัดที่สองมีจำนวนเต็ม a₁ ถึง a_N คั่นด้วยช่องว่าง โดยที่ 1 ≤ a_i ≤ 10⁹

ข้อมูลออก

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

3
84 60 36

12
15

2
7 5

1
12

#include <stdio.h>

int lengths[100000];

int gcd(int a, int b)
{
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &lengths[i]);
    }
    int piece = lengths[0];
    for (int i = 1; i < n; i++) {
        piece = gcd(piece, lengths[i]);
    }
    long long pieces = 0;
    for (int i = 0; i < n; i++) {
        pieces += lengths[i] / piece;
    }
    printf("%d\n", piece);
    printf("%lld\n", pieces);
    return 0;
}

ข้อ 3 ขีดบนไม้บรรทัด

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

ขีดบนไม้บรรทัดยาวไม่เท่ากัน ขีดตรงกลางยาวที่สุด ครึ่งซ้ายกับครึ่งขวาก็มีขีดกลางของตัวเองที่สั้นลงมาหนึ่งระดับ แบ่งครึ่งต่อไปเรื่อยๆ แบบนี้ น้องอยากพิมพ์ลายขีดของไม้บรรทัดลงหน้าจอ โดยวางไม้บรรทัดในแนวตั้ง ขีดหนึ่งขีดคือหนึ่งบรรทัด ความยาวของขีดคือจำนวนตัว - ในบรรทัดนั้น

ไม้บรรทัดระดับ K นิยามแบบนี้

• ไม้บรรทัดระดับ 1 คือขีดยาว 1 หนึ่งขีด
• ไม้บรรทัดระดับ K เมื่อ K ≥ 2 คือไม้บรรทัดระดับ K - 1 ตามด้วยขีดยาว K หนึ่งขีด แล้วตามด้วยไม้บรรทัดระดับ K - 1 อีกชุด

เช่น ไม้บรรทัดระดับ 2 มีสามขีด ยาว 1 2 1 ตามลำดับ ให้พิมพ์ไม้บรรทัดระดับ K

ข้อมูลเข้า

จำนวนเต็ม K หนึ่งตัว โดยที่ 1 ≤ K ≤ 15

ข้อมูลออก

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

3

-
--
-
---
-
--
-

#include <stdio.h>

void ruler(int k)
{
    if (k == 0) {
        return;
    }
    ruler(k - 1);
    for (int i = 0; i < k; i++) {
        printf("-");
    }
    printf("\n");
    ruler(k - 1);
}

int main()
{
    int k;
    scanf("%d", &k);
    ruler(k);
    return 0;
}

ข้อ 4 ค้นรายชื่อผู้เข้าสอบ

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

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

ข้อมูลเข้า

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

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

อีก Q บรรทัด แต่ละบรรทัดมีเลขที่ถูกถามหนึ่งตัว อยู่ระหว่าง 1 ถึง 10⁹

ข้อมูลออก

Q บรรทัด ตอบคำถามตามลำดับ บรรทัดละหนึ่งข้อ เป็นลำดับในรายชื่อ หรือ 0 ถ้าไม่มี

10 6
1012 1047 1105 1188 1230 1302 1377 1419 1460 1525
1460
1200
1012
1525
1000
2000

9
0
1
10
0
0

#include <stdio.h>

int ids[100000];

int search(int a[], int low, int high, int target)
{
    if (low > high) {
        return -1;
    }
    int mid = (low + high) / 2;
    if (a[mid] == target) {
        return mid;
    }
    if (a[mid] < target) {
        return search(a, mid + 1, high, target);
    }
    return search(a, low, mid - 1, target);
}

int main()
{
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 0; i < n; i++) {
        scanf("%d", &ids[i]);
    }
    for (int k = 0; k < q; k++) {
        int target;
        scanf("%d", &target);
        printf("%d\n", search(ids, 0, n - 1, target) + 1);
    }
    return 0;
}

ข้อ 5 นั่งเว้นที่

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

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

ข้อมูลเข้า

จำนวนเต็ม n หนึ่งตัว โดยที่ 1 ≤ n ≤ 20

ข้อมูลออก

พิมพ์ทุกแบบที่ไม่มี 1 สองตัวติดกัน บรรทัดละหนึ่งแบบ เรียงแบบพจนานุกรมโดยถือว่า 0 มาก่อน 1 บรรทัดสุดท้ายพิมพ์จำนวนแบบทั้งหมด

3

000
001
010
100
101
5

#include <stdio.h>

int n;
int total = 0;
char seats[22];

void place(int pos)
{
    if (pos == n) {
        seats[n] = '\0';
        printf("%s\n", seats);
        total++;
        return;
    }
    seats[pos] = '0';
    place(pos + 1);
    if (pos == 0 || seats[pos - 1] == '0') {
        seats[pos] = '1';
        place(pos + 1);
    }
}

int main()
{
    scanf("%d", &n);
    place(0);
    printf("%d\n", total);
    return 0;
}

ข้อ 6 จับฉลากของขวัญ

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

งานปีใหม่ของห้อง เพื่อน n คนหมายเลข 1 ถึง n ต่างคนต่างเอาของขวัญมาคนละหนึ่งชิ้น แล้วจับฉลากแลกกัน ทุกคนได้ของขวัญคนละหนึ่งชิ้น ของขวัญทุกชิ้นมีคนได้ และไม่มีใครได้ของขวัญที่ตัวเองเอามา ครูอยากเห็นผลจับฉลากทุกแบบที่เป็นไปได้

ผลจับฉลากหนึ่งแบบเขียนเป็นตัวเลข n ตัว g₁ g₂ ... g_n โดย g_i คือหมายเลขของเพื่อนที่เอาของขวัญชิ้นที่คนที่ i ได้มา

ข้อมูลเข้า

จำนวนเต็ม n หนึ่งตัว โดยที่ 1 ≤ n ≤ 8

ข้อมูลออก

ผลจับฉลากทุกแบบ บรรทัดละหนึ่งแบบ ในบรรทัดพิมพ์ g₁ ถึง g_n คั่นด้วยช่องว่างหนึ่งช่อง เรียงแบบพจนานุกรม คือเทียบตัวแรกก่อน ถ้าเท่ากันค่อยเทียบตัวถัดไป แบบที่น้อยกว่าพิมพ์ก่อน ถ้าไม่มีผลจับฉลากที่เป็นไปได้เลย ให้พิมพ์ none

3

2 3 1
3 1 2

#include <stdio.h>

int n;
int total = 0;
int gift[10];
int taken[10];

void draw(int pos)
{
    if (pos == n) {
        for (int i = 0; i < n; i++) {
            if (i > 0) {
                printf(" ");
            }
            printf("%d", gift[i]);
        }
        printf("\n");
        total++;
        return;
    }
    for (int v = 1; v <= n; v++) {
        if (taken[v] == 0 && v != pos + 1) {
            taken[v] = 1;
            gift[pos] = v;
            draw(pos + 1);
            taken[v] = 0;
        }
    }
}

int main()
{
    scanf("%d", &n);
    draw(0);
    if (total == 0) {
        printf("none\n");
    }
    return 0;
}

ข้อ 7 บันไดชำรุด

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

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

เช่น บันได 4 ขั้นที่ไม่มีขั้นชำรุดเลย มี 7 วิธี คือก้าว 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3 และ 3+1

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม n และ k คั่นด้วยช่องว่าง คือจำนวนขั้นและจำนวนขั้นที่ชำรุด โดยที่ 1 ≤ n ≤ 70 และ 0 ≤ k ≤ n - 1

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

ข้อมูลออก

จำนวนวิธีขึ้นไปถึงขั้น n รับประกันว่าคำตอบไม่เกิน 3 × 10¹⁸

4 0

7

6 1
3

8

#include <stdio.h>

int broken[71];
long long memo[71];

long long ways(int step)
{
    if (step < 0) {
        return 0;
    }
    if (broken[step] == 1) {
        return 0;
    }
    if (step == 0) {
        return 1;
    }
    if (memo[step] != -1) {
        return memo[step];
    }
    memo[step] = ways(step - 1) + ways(step - 2) + ways(step - 3);
    return memo[step];
}

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 0; i < k; i++) {
        int step;
        scanf("%d", &step);
        broken[step] = 1;
    }
    for (int i = 0; i <= n; i++) {
        memo[i] = -1;
    }
    printf("%lld\n", ways(n));
    return 0;
}

ข้อ 8 ฮานอยครั้งที่ K

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

พิพิธภัณฑ์วิทยาศาสตร์มีหุ่นยนต์ย้ายหอคอยฮานอยโชว์ทั้งวัน หอคอยมีแผ่นกลม n แผ่น หมายเลข 1 ถึง n จากเล็กไปใหญ่ เริ่มต้นทุกแผ่นอยู่ที่หลัก A หุ่นยนต์ย้ายทั้งหมดไปหลัก C ตามขั้นตอนนี้ทุกประการ

ย้าย m แผ่นจากหลัก X ไปหลัก Y โดยมีหลัก Z เป็นที่พัก ทำดังนี้

1. ถ้า m เป็น 0 ไม่ต้องทำอะไร
2. ย้าย m - 1 แผ่นจากหลัก X ไปหลัก Z โดยมีหลัก Y เป็นที่พัก
3. ย้ายแผ่นหมายเลข m จากหลัก X ไปหลัก Y หนึ่งครั้ง
4. ย้าย m - 1 แผ่นจากหลัก Z ไปหลัก Y โดยมีหลัก X เป็นที่พัก

หุ่นยนต์เริ่มด้วยการย้าย n แผ่นจากหลัก A ไปหลัก C โดยมีหลัก B เป็นที่พัก ซึ่งเป็นขั้นตอนเดียวกับโปรแกรมหอคอยฮานอยในหน้า 9.5 ผู้ชมถามคำถาม Q ข้อ แต่ละข้อถามว่าการย้ายครั้งที่ K หุ่นยนต์ย้ายแผ่นหมายเลขอะไร จากหลักไหนไปหลักไหน

ข้อมูลเข้า

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

อีก Q บรรทัด แต่ละบรรทัดมีจำนวนเต็ม K หนึ่งตัว โดยที่ 1 ≤ K ≤ 2ⁿ - 1

ข้อมูลออก

Q บรรทัด ตอบคำถามตามลำดับ แต่ละบรรทัดมีหมายเลขแผ่น หลักต้นทาง และหลักปลายทางของการย้ายครั้งที่ K คั่นด้วยช่องว่าง หลักเขียนเป็นตัวอักษร A B หรือ C

3 7
1
2
3
4
5
6
7

1 A C
2 A B
1 C B
3 A C
1 B A
2 B C
1 A C

#include <stdio.h>

long long power_of_two[61];

void find_move(int n, long long k, char from, char to, char via)
{
    long long middle = power_of_two[n - 1];
    if (k < middle) {
        find_move(n - 1, k, from, via, to);
    } else if (k == middle) {
        printf("%d %c %c\n", n, from, to);
    } else {
        find_move(n - 1, k - middle, via, to, from);
    }
}

int main()
{
    power_of_two[0] = 1;
    for (int i = 1; i <= 60; i++) {
        power_of_two[i] = power_of_two[i - 1] * 2;
    }
    int n, q;
    scanf("%d %d", &n, &q);
    for (int i = 0; i < q; i++) {
        long long k;
        scanf("%lld", &k);
        find_move(n, k, 'A', 'C', 'B');
    }
    return 0;
}