14.6 แบบฝึกหัด

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

ข้อ 1 กองจาน

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

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

PUSH x วางจานหมายเลข x ไว้บนสุด
POP หยิบจานบนสุดออกไป ให้พิมพ์หมายเลขจานใบนั้น ถ้าไม่มีจานเหลือเลยให้พิมพ์ EMPTY
TOP ดูจานบนสุดโดยไม่หยิบออก ให้พิมพ์หมายเลขจานใบนั้น ถ้าไม่มีจานให้พิมพ์ EMPTY
SIZE พิมพ์จำนวนจานที่อยู่ในตั้ง

ข้อมูลเข้า

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

อีก Q บรรทัด บรรทัดละหนึ่งคำสั่งตามรูปแบบข้างบน หมายเลขจาน x เป็นจำนวนเต็ม 1 ≤ x ≤ 1000000000 รับประกันว่ามีคำสั่ง POP TOP หรือ SIZE อย่างน้อยหนึ่งคำสั่ง

ข้อมูลออก

สำหรับคำสั่ง POP TOP และ SIZE แต่ละคำสั่ง ให้พิมพ์คำตอบหนึ่งบรรทัด ตามลำดับของคำสั่ง

9
PUSH 12
PUSH 7
TOP
PUSH 30
SIZE
POP
POP
TOP
SIZE

5
POP
PUSH 5
POP
TOP
SIZE

EMPTY
5
EMPTY
0

ดูคำใบ้

ใช้ stack ด้วยอาเรย์กับตัวแปร size แบบหน้า 14.4 อาเรย์ต้องมีอย่างน้อยแสนช่อง เพราะอาจเป็นคำสั่ง PUSH ทั้งหมด อ่านชื่อคำสั่งด้วย %s แล้วเทียบด้วย strcmp จากหน้า 6.4 อ่าน x เฉพาะเมื่อเป็น PUSH และก่อน POP หรือ TOP ต้องเช็กว่า size เป็น 0 หรือไม่ก่อนทุกครั้ง

ดูเฉลย

#include <stdio.h>
#include <string.h>

int stack[100000];
int size = 0;

int main()
{
    int q;
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        char command[5];
        scanf("%4s", command);
        if (strcmp(command, "PUSH") == 0) {
            int dish;
            scanf("%d", &dish);
            stack[size] = dish;
            size++;
        } else if (strcmp(command, "POP") == 0) {
            if (size == 0) {
                printf("EMPTY\n");
            } else {
                size--;
                printf("%d\n", stack[size]);
            }
        } else if (strcmp(command, "TOP") == 0) {
            if (size == 0) {
                printf("EMPTY\n");
            } else {
                printf("%d\n", stack[size - 1]);
            }
        } else {
            printf("%d\n", size);
        }
    }
    return 0;
}

ข้อ 2 แถวรถไฟเหาะ

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

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

JOIN x คนที่ถือบัตรหมายเลข x มาต่อท้ายแถว
RIDE k รถไฟเที่ยวใหม่มีที่นั่ง k ที่ คนจากหัวแถวขึ้นไปนั่งทีละคนจนกว่าที่นั่งจะเต็มหรือแถวจะหมด ให้พิมพ์หมายเลขบัตรของทุกคนที่ได้ขึ้นเที่ยวนี้ตามลำดับในบรรทัดเดียว คั่นด้วยช่องว่างหนึ่งช่อง ถ้าไม่มีใครในแถวเลยให้พิมพ์ EMPTY
COUNT พิมพ์จำนวนคนที่ยังรออยู่ในแถว

ข้อมูลเข้า

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

อีก Q บรรทัด บรรทัดละหนึ่งคำสั่งตามรูปแบบข้างบน โดยที่ 1 ≤ x ≤ 1000000000 และ 1 ≤ k ≤ 100000 รับประกันว่ามีคำสั่ง RIDE หรือ COUNT อย่างน้อยหนึ่งคำสั่ง

ข้อมูลออก

สำหรับคำสั่ง RIDE และ COUNT แต่ละคำสั่ง ให้พิมพ์คำตอบหนึ่งบรรทัด ตามลำดับของคำสั่ง

10
JOIN 101
JOIN 102
JOIN 103
JOIN 104
RIDE 3
COUNT
JOIN 105
RIDE 4
RIDE 2
COUNT

101 102 103
1
104 105
EMPTY
0

5
RIDE 5
JOIN 7
COUNT
RIDE 1
COUNT

EMPTY
1
7
0

ดูคำใบ้

ใช้ queue ด้วยอาเรย์แบบแรกของหน้า 14.5 คนเข้าแถวรวมกันไม่เกินแสนคน อาเรย์แสนช่องจึงพอโดยไม่ต้องวนกลับ คำสั่ง RIDE k ให้เอาคนออกทีละคนจนกว่าจะครบ k คน หรือแถวว่าง อย่าวนครบ k รอบโดยไม่ดูว่าแถวหมดหรือยัง และระวังช่องว่างเกินท้ายบรรทัด

ดูเฉลย

#include <stdio.h>
#include <string.h>

int queue[100000];
int head = 0, tail = 0;

int main()
{
    int q;
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        char command[6];
        scanf("%5s", command);
        if (strcmp(command, "JOIN") == 0) {
            int ticket;
            scanf("%d", &ticket);
            queue[tail] = ticket;
            tail++;
        } else if (strcmp(command, "RIDE") == 0) {
            int seats;
            scanf("%d", &seats);
            if (head == tail) {
                printf("EMPTY\n");
                continue;
            }
            int boarded = 0;
            while (boarded < seats && head < tail) {
                if (boarded > 0) {
                    printf(" ");
                }
                printf("%d", queue[head]);
                head++;
                boarded++;
            }
            printf("\n");
        } else {
            printf("%d\n", tail - head);
        }
    }
    return 0;
}

ข้อ 3 สำรับไพ่ของนักมายากล

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

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

TOP x วางไพ่หมายเลข x ไว้บนสุดของสำรับ
BOTTOM x สอดไพ่หมายเลข x ไว้ใต้สุดของสำรับ
DRAWTOP หยิบไพ่ใบบนสุดออก ให้พิมพ์หมายเลขของมัน ถ้าสำรับไม่มีไพ่ให้พิมพ์ EMPTY
DRAWBOTTOM หยิบไพ่ใบล่างสุดออก ให้พิมพ์หมายเลขของมัน ถ้าสำรับไม่มีไพ่ให้พิมพ์ EMPTY

จบการแสดงแล้ว ให้พิมพ์ไพ่ที่เหลือทั้งสำรับเรียงจากบนสุดลงไปล่างสุด

ข้อมูลเข้า

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

อีก Q บรรทัด บรรทัดละหนึ่งคำสั่งตามรูปแบบข้างบน หมายเลขไพ่ x เป็นจำนวนเต็ม 1 ≤ x ≤ 1000000000

ข้อมูลออก

สำหรับคำสั่ง DRAWTOP และ DRAWBOTTOM แต่ละคำสั่ง ให้พิมพ์คำตอบหนึ่งบรรทัดตามลำดับ

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

7
TOP 5
TOP 8
BOTTOM 3
DRAWBOTTOM
TOP 1
BOTTOM 9
DRAWTOP

3
1
8 5 9

4
DRAWTOP
BOTTOM 4
DRAWTOP
DRAWBOTTOM

EMPTY
4
EMPTY
EMPTY

ดูคำใบ้

สำรับที่เพิ่มและหยิบได้ทั้งสองด้านคือ deque ในหน้า 14.5 ให้ด้านบนเป็นหัวคิว ด้านล่างเป็นท้ายคิว ไพ่ในสำรับพร้อมกันมีไม่เกินแสนใบ จึงใช้ circular queue ขนาดแสนช่องได้ ระวังสูตรถอยหลัง ต้องเป็น (head - 1 + capacity) % capacity ส่วนบรรทัดสุดท้ายให้เดินจาก head ไป count ใบ โดยใช้ (head + i) % capacity

ดูเฉลย

#include <stdio.h>
#include <string.h>

int deck[100000];
int capacity = 100000;
int head = 0, tail = 0, count = 0;

int main()
{
    int q;
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        char command[11];
        scanf("%10s", command);
        if (strcmp(command, "TOP") == 0) {
            int card;
            scanf("%d", &card);
            head = (head - 1 + capacity) % capacity;
            deck[head] = card;
            count++;
        } else if (strcmp(command, "BOTTOM") == 0) {
            int card;
            scanf("%d", &card);
            deck[tail] = card;
            tail = (tail + 1) % capacity;
            count++;
        } else if (count == 0) {
            printf("EMPTY\n");
        } else if (strcmp(command, "DRAWTOP") == 0) {
            printf("%d\n", deck[head]);
            head = (head + 1) % capacity;
            count--;
        } else {
            tail = (tail - 1 + capacity) % capacity;
            printf("%d\n", deck[tail]);
            count--;
        }
    }
    if (count == 0) {
        printf("EMPTY\n");
    } else {
        for (int i = 0; i < count; i++) {
            if (i > 0) {
                printf(" ");
            }
            printf("%d", deck[(head + i) % capacity]);
        }
        printf("\n");
    }
    return 0;
}

ข้อ 4 ตรวจวงเล็บในสูตร

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

โปรแกรมตารางคำนวณต้องตรวจวงเล็บในสูตรก่อนคำนวณ สูตรประกอบด้วยตัวอักษรภาษาอังกฤษ ตัวเลข เครื่องหมาย + - * / และวงเล็บสามชนิด คือ ( ) [ ] และ { } สูตรที่วงเล็บถูกต้องคือ วงเล็บปิดทุกตัวคู่กับวงเล็บเปิดชนิดเดียวกันตัวล่าสุดที่ยังไม่ถูกปิด และไม่มีวงเล็บเปิดเหลือค้างเมื่อจบสูตร ตัวอักษรอื่นที่ไม่ใช่วงเล็บไม่มีผลกับการตรวจ

ถ้าสูตรผิด โปรแกรมต้องบอกตำแหน่งที่ผิดด้วย ตำแหน่งนับจาก 1 ที่ตัวอักษรแรกของสูตร

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

ข้อมูลเข้า

บรรทัดแรกมีจำนวนเต็ม T คือจำนวนสูตร โดยที่ 1 ≤ T ≤ 1000

อีก T บรรทัด บรรทัดละหนึ่งสูตร ไม่มีช่องว่างในสูตร แต่ละสูตรยาว 1 ถึง 100000 ตัวอักษร และทุกสูตรยาวรวมกันไม่เกิน 1000000 ตัวอักษร

ข้อมูลออก

T บรรทัด ตอบสูตรละหนึ่งบรรทัดตามลำดับ ถ้าวงเล็บถูกต้องให้พิมพ์ OK ถ้าผิดให้พิมพ์ ERROR ตามด้วยช่องว่างและตำแหน่งที่ผิด

5
{a+[b*(c-d)]}
(a+b]*c
((a)+b
a+b)
x*(y+(z)

OK
ERROR 5
ERROR 1
ERROR 4
ERROR 3

ดูคำใบ้

เริ่มจากโปรแกรม brackets ในหน้า 14.4 แต่ให้ stack เก็บตำแหน่งของวงเล็บเปิดแทนตัววงเล็บ จะรู้ทั้งชนิดของมัน (ดูจากสูตรที่ตำแหน่งนั้น) และรู้ว่ามันอยู่ตรงไหน ถ้าจบแล้วยังมีของค้าง วงเล็บเปิดตัวซ้ายสุดที่ค้างอยู่คือตัวที่อยู่ก้น stack ซึ่งก็คือช่อง 0 ตัวอักษรที่ไม่ใช่วงเล็บข้ามไปได้เลย สูตรยาวได้แสนตัว อาเรย์ของสูตรกับ stack ต้องมีอย่างน้อย 100001 ช่อง และอย่าลืมเริ่ม stack ว่างใหม่ทุกสูตร

ดูเฉลย

#include <stdio.h>

char formula[100001];
int stack[100000];
int size = 0;

char opening_of(char c)
{
    if (c == ')') {
        return '(';
    } else if (c == ']') {
        return '[';
    }
    return '{';
}

int first_error(void)
{
    size = 0;
    for (int i = 0; formula[i] != '\0'; i++) {
        char c = formula[i];
        if (c == '(' || c == '[' || c == '{') {
            stack[size] = i;
            size++;
        } else if (c == ')' || c == ']' || c == '}') {
            if (size == 0 || formula[stack[size - 1]] != opening_of(c)) {
                return i + 1;
            }
            size--;
        }
    }
    if (size > 0) {
        return stack[0] + 1;
    }
    return 0;
}

int main()
{
    int t;
    scanf("%d", &t);
    for (int k = 0; k < t; k++) {
        scanf("%100000s", formula);
        int position = first_error();
        if (position == 0) {
            printf("OK\n");
        } else {
            printf("ERROR %d\n", position);
        }
    }
    return 0;
}

ข้อ 5 เครื่องคิดเลข postfix

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

เครื่องคิดเลขรุ่นเก่ารุ่นหนึ่งไม่มีปุ่มวงเล็บ ผู้ใช้ต้องป้อนนิพจน์แบบ postfix คือเขียนเครื่องหมายไว้หลังตัวเลขสองตัวที่มันใช้ เช่น (8 - 3) * 4 ป้อนเป็น 8 3 - 4 * ให้เขียนโปรแกรมคำนวณนิพจน์ postfix ที่ป้อนเข้ามา

นิพจน์มีเครื่องหมายสี่แบบ คือ + - * และ / การหารให้ผลเป็นจำนวนเต็มแบบเดียวกับ / ของภาษา C คือตัดเศษทิ้งไปทาง 0 เช่น 7 หาร 2 ได้ 3 และ -7 หาร 2 ได้ -3

ข้อมูลเข้า

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

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

รับประกันว่านิพจน์ถูกต้อง ไม่มีการหารด้วยศูนย์ และผลระหว่างทางทุกค่ารวมถึงคำตอบ มีค่าสัมบูรณ์ไม่เกิน 10¹⁸

ข้อมูลออก

ค่าของนิพจน์

5
8 3 - 4 *

5
2 7 - 2 /

-2

ดูคำใบ้

ใช้วิธีในหน้า 14.4 แต่ระวังสามจุดที่โปรแกรม postfix ในหน้านั้นไม่ได้เตรียมไว้ หนึ่ง ตัวเลขถึง 10⁹ และผลระหว่างทางถึง 10¹⁸ stack ต้องเป็น long long สอง stack สูงได้ถึงราวห้าหมื่นเมื่อตัวเลขมาก่อนเครื่องหมายทั้งหมด อาเรย์พันช่องจึงไม่พอ สาม ผลลบเกิดขึ้นได้ระหว่างทาง ตัวที่ pop ออกมาก่อนคือตัวขวา ทดสอบกับ 2 7 - 2 / ซึ่งต้องได้ -2

ดูเฉลย

#include <stdio.h>

long long stack[100000];
int size = 0;

void push(long long x)
{
    stack[size] = x;
    size++;
}

long long pop(void)
{
    size--;
    return stack[size];
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        char token[12];
        scanf("%11s", token);
        if (token[0] >= '0' && token[0] <= '9') {
            long long number = 0;
            for (int j = 0; token[j] != '\0'; j++) {
                number = number * 10 + (token[j] - '0');
            }
            push(number);
        } else {
            long long right = pop();
            long long left = pop();
            if (token[0] == '+') {
                push(left + right);
            } else if (token[0] == '-') {
                push(left - right);
            } else if (token[0] == '*') {
                push(left * right);
            } else {
                push(left / right);
            }
        }
    }
    printf("%lld\n", pop());
    return 0;
}

ข้อ 6 ส่งลูกบอล

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

เด็ก N คนนั่งเป็นวงกลม มีหมายเลข 1 ถึง N เรียงตามเข็มนาฬิกา เด็กหมายเลข N นั่งติดกับเด็กหมายเลข 1 เกมเริ่มโดยเด็กหมายเลข 1 ถือลูกบอล แต่ละรอบเล่นแบบนี้

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

เล่นไปจนทุกคนออกจากวง ให้หาว่าเด็กออกจากวงในลำดับใด

ข้อมูลเข้า

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

ข้อมูลออก

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

5 2

2 4 1 5 3

7 3

3 6 2 7 5 1 4

ดูคำใบ้

ให้วงเป็น queue หัวคิวคือคนที่ถือลูกบอล การส่งลูกบอลหนึ่งครั้งคือเอาหัวคิวไปต่อท้าย ส่วนคนที่ออกคือ dequeue ทิ้ง แต่ถ้าส่งครบ K - 1 ครั้งจริงๆ เมื่อ K เป็นพันล้านจะไม่ทันเวลา สังเกตว่าวงที่มี m คน ส่งครบ m ครั้งลูกบอลกลับมาที่เดิม จึงส่งแค่ (K - 1) % m ครั้งก็พอ คนเข้าคิวรวมกันได้หลายล้านครั้ง แต่ในคิวมีพร้อมกันไม่เกิน N คน ใช้ circular queue ขนาด N ช่องตามหน้า 14.5

ดูเฉลย

#include <stdio.h>

int circle[5000];
int capacity;
int head = 0, tail = 0, count = 0;

void enqueue(int x)
{
    circle[tail] = x;
    tail = (tail + 1) % capacity;
    count++;
}

int dequeue(void)
{
    int x = circle[head];
    head = (head + 1) % capacity;
    count--;
    return x;
}

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    capacity = n;
    for (int i = 1; i <= n; i++) {
        enqueue(i);
    }
    for (int round = 0; round < n; round++) {
        int passes = (k - 1) % count;
        for (int p = 0; p < passes; p++) {
            enqueue(dequeue());
        }
        if (round > 0) {
            printf(" ");
        }
        printf("%d", dequeue());
    }
    printf("\n");
    return 0;
}

ข้อ 7 เคอร์เซอร์

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

น้องเขียนโปรแกรมบันทึกการกดแป้นพิมพ์ของโทรศัพท์รุ่นเก่า แป้นพิมพ์มีปุ่มตัวอักษร a ถึง z ปุ่มเลื่อนเคอร์เซอร์ซ้าย ปุ่มเลื่อนเคอร์เซอร์ขวา และปุ่มลบ บันทึกที่ได้เป็นข้อความยาวหนึ่งบรรทัด แต่ละตัวอักษรคือการกดหนึ่งครั้ง

a ถึง z พิมพ์ตัวอักษรนั้นลงที่ตำแหน่งเคอร์เซอร์ แล้วเคอร์เซอร์อยู่หลังตัวที่เพิ่งพิมพ์
< เลื่อนเคอร์เซอร์ไปทางซ้ายหนึ่งตัว ถ้าอยู่หน้าสุดแล้วไม่เกิดอะไร
> เลื่อนเคอร์เซอร์ไปทางขวาหนึ่งตัว ถ้าอยู่ท้ายสุดแล้วไม่เกิดอะไร
# ลบตัวอักษรที่อยู่ทางซ้ายของเคอร์เซอร์หนึ่งตัว ถ้าไม่มีตัวอักษรทางซ้ายไม่เกิดอะไร

ตอนเริ่ม ข้อความว่าง ให้หาว่าหลังกดครบทุกปุ่มตามบันทึก บนจอเหลือข้อความอะไร

ข้อมูลเข้า

บรรทัดเดียว เป็นบันทึกการกดปุ่ม ยาว 1 ถึง 2000000 ตัวอักษร ประกอบด้วย a ถึง z < > และ # เท่านั้น

ข้อมูลออก

ข้อความที่เหลือบนจอ ถ้าไม่เหลือตัวอักษรเลยให้พิมพ์ EMPTY

abc<<x>y#z

axbzc

hi#<#>##

EMPTY

ดูคำใบ้

ถ้าเก็บข้อความในอาเรย์เดียวแล้วแทรกหรือลบด้วยการเลื่อนแบบหน้า 5.5 บันทึกอย่าง a<b<c<... ที่พิมพ์หน้าสุดทุกครั้ง จะต้องเลื่อนรวมกันราว 5 × 10¹¹ ครั้ง ไม่ทัน ให้มองว่าเคอร์เซอร์แบ่งข้อความเป็นสองส่วน แล้วเก็บแต่ละส่วนใน stack ของตัวเอง ส่วนซ้ายมีตัวบนสุดเป็นตัวที่ติดเคอร์เซอร์ทางซ้าย ส่วนขวามีตัวบนสุดเป็นตัวที่ติดเคอร์เซอร์ทางขวา พิมพ์คือ push ลง stack ซ้าย ลบคือ pop จาก stack ซ้าย เลื่อนเคอร์เซอร์คือย้ายตัวบนสุดข้าม stack ตอนพิมพ์ผล stack ซ้ายพิมพ์จากก้นขึ้นบน stack ขวาพิมพ์จากบนลงก้น ทั้งบันทึกและ stack ยาวได้สองล้านตัว ต้องประกาศไว้นอก main

ดูเฉลย

#include <stdio.h>

char keys[2000001];
char left[2000000];
char right[2000000];
int left_size = 0, right_size = 0;

int main()
{
    scanf("%2000000s", keys);
    for (int i = 0; keys[i] != '\0'; i++) {
        char c = keys[i];
        if (c == '<') {
            if (left_size > 0) {
                left_size--;
                right[right_size] = left[left_size];
                right_size++;
            }
        } else if (c == '>') {
            if (right_size > 0) {
                right_size--;
                left[left_size] = right[right_size];
                left_size++;
            }
        } else if (c == '#') {
            if (left_size > 0) {
                left_size--;
            }
        } else {
            left[left_size] = c;
            left_size++;
        }
    }
    if (left_size + right_size == 0) {
        printf("EMPTY\n");
        return 0;
    }
    for (int i = 0; i < left_size; i++) {
        printf("%c", left[i]);
    }
    for (int i = right_size - 1; i >= 0; i--) {
        printf("%c", right[i]);
    }
    printf("\n");
    return 0;
}

ข้อ 8 ร้านข้าวมันไก่

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

ร้านข้าวมันไก่หน้าตลาดมีแม่ครัวคนเดียว ทำได้ทีละจาน และมีเก้าอี้ให้ลูกค้านั่งรอ K ตัว วันนี้มีลูกค้า N คน ลูกค้าคนที่ i มาถึงร้านที่เวลา t_i และจานของเขาใช้เวลาทำ s_i นาที ลูกค้าเรียงตามลำดับที่มาถึง ถ้ามาถึงเวลาเดียวกัน คนที่อยู่ก่อนในข้อมูลเข้าถือว่ามาก่อน

ร้านทำงานตามกฎนี้

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

ให้หาว่าลูกค้าแต่ละคนได้รับจานที่เวลาเท่าไร

ข้อมูลเข้า

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

อีก N บรรทัด บรรทัดที่ i มีจำนวนเต็ม t_i และ s_i คั่นด้วยช่องว่าง โดยที่ 0 ≤ t₁ ≤ t₂ ≤ ... ≤ t_N ≤ 1000000000 และ 1 ≤ s_i ≤ 100000

ข้อมูลออก

N บรรทัด บรรทัดที่ i คือเวลาที่ลูกค้าคนที่ i ได้รับจาน ถ้าเขากลับบ้านเพราะเก้าอี้เต็ม ให้พิมพ์ -1

ดูคำใบ้

เก็บเวลาที่แม่ครัวจะทำจานปัจจุบันเสร็จไว้ในตัวแปร finish และเก็บลูกค้าที่นั่งรอเป็น queue ของหมายเลขลูกค้า เมื่อลูกค้าคนใหม่มาถึงที่เวลา t ให้วนก่อนว่า ถ้ามีคนรอและ finish ไม่เกิน t คนหัวแถวได้เริ่มทำจานที่เวลา finish เขาจึงได้จานที่เวลา finish + s ทำซ้ำจนแถวว่างหรือ finish เกิน t จากนั้นค่อยตัดสินคนใหม่ตามกฎ จบวันแล้วอย่าลืมทำจานให้คนที่ยังรออยู่ให้ครบ เวลารวมเกิน int ได้ เพราะทำต่อกันแสนจาน จานละแสนนาที ใช้ long long คิวมีคนรอพร้อมกันไม่เกิน K คน จะใช้ circular queue ขนาด K แบบร้านชานมในหน้า 14.5 ก็ได้

ดูเฉลย

#include <stdio.h>

long long arrive[100000];
long long cook_time[100000];
long long served_at[100000];
int waiting[100000];
int capacity;
int head = 0, tail = 0, count = 0;

void enqueue(int x)
{
    waiting[tail] = x;
    tail = (tail + 1) % capacity;
    count++;
}

int dequeue(void)
{
    int x = waiting[head];
    head = (head + 1) % capacity;
    count--;
    return x;
}

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    capacity = k;
    for (int i = 0; i < n; i++) {
        scanf("%lld %lld", &arrive[i], &cook_time[i]);
    }
    long long finish = 0;
    for (int i = 0; i < n; i++) {
        long long t = arrive[i];
        while (count > 0 && finish <= t) {
            int next = dequeue();
            finish += cook_time[next];
            served_at[next] = finish;
        }
        if (count == 0 && finish <= t) {
            finish = t + cook_time[i];
            served_at[i] = finish;
        } else if (count < k) {
            enqueue(i);
        } else {
            served_at[i] = -1;
        }
    }
    while (count > 0) {
        int next = dequeue();
        finish += cook_time[next];
        served_at[next] = finish;
    }
    for (int i = 0; i < n; i++) {
        printf("%lld\n", served_at[i]);
    }
    return 0;
}

ข้อ 9 สับเปลี่ยนตู้รถไฟ

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

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

I x y พ่วงตู้ใหม่หมายเลข y ไว้ข้างหลังตู้หมายเลข x ทันที ถ้า x เป็น 0 แปลว่าพ่วงตู้ y ไว้หน้าสุดของขบวน รับประกันว่าตู้ x อยู่ในขบวน และตู้ y ไม่ได้อยู่ในขบวนตอนนั้น ตู้ y อาจเป็นตู้ที่เคยถูกปลดออกไปแล้วก็ได้
D x ปลดตู้หมายเลข x ออกจากขบวน ตู้ที่อยู่ข้างหน้าและข้างหลังมันต่อกันตามเดิม รับประกันว่าตู้ x อยู่ในขบวน

ให้หาว่าทำครบทุกคำสั่งแล้ว ขบวนรถเรียงตู้อย่างไร

ข้อมูลเข้า

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

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

ข้อมูลออก

บรรทัดเดียว มีหมายเลขตู้ทั้งหมดในขบวนเรียงจากหัวไปท้าย คั่นด้วยช่องว่างหนึ่งช่อง ถ้าไม่มีตู้เหลือเลยให้พิมพ์ EMPTY

7 2 9 3 4 1

1 2
D 1
I 0 300000

ดูคำใบ้

ถ้าเก็บขบวนในอาเรย์ แต่ละคำสั่งต้องหาตำแหน่งของตู้ x แล้วเลื่อนตู้ครึ่งขบวน คำสั่งสองแสนครั้งกับขบวนแสนตู้ไม่ทันแน่นอน หมายเลขตู้ไม่ซ้ำกันและไม่เกินสามแสน จึงใช้หมายเลขตู้เป็น index ของ node ได้เลย ทำลิสต์สองทางด้วย prev[] กับ next[] ขนาด 300001 ช่อง ให้ node 0 เป็นหัวขบวนปลอมแบบโปรแกรม line-up ในหน้า 14.3 คำสั่ง I 0 y ก็คือแทรกหลัง node 0 พอดี ไม่ต้องเขียนกรณีพิเศษ ส่วนตู้ที่เคยถูกปลดแล้วกลับมา prev กับ next ของมันถูกตั้งใหม่ตอนแทรกอยู่แล้ว

ดูเฉลย

#include <stdio.h>

int prev[300001];
int next[300001];

void remove_car(int x)
{
    next[prev[x]] = next[x];
    prev[next[x]] = prev[x];
}

void insert_after(int p, int x)
{
    prev[x] = p;
    next[x] = next[p];
    prev[next[p]] = x;
    next[p] = x;
}

int main()
{
    int n, q;
    scanf("%d %d", &n, &q);
    for (int car = 1; car <= n; car++) {
        insert_after(prev[0], car);
    }
    for (int i = 0; i < q; i++) {
        char command;
        scanf(" %c", &command);
        if (command == 'I') {
            int x, y;
            scanf("%d %d", &x, &y);
            insert_after(x, y);
        } else {
            int x;
            scanf("%d", &x);
            remove_car(x);
        }
    }
    if (next[0] == 0) {
        printf("EMPTY\n");
        return 0;
    }
    for (int car = next[0]; car != 0; car = next[car]) {
        printf("%d", car);
        if (next[car] != 0) {
            printf(" ");
        }
    }
    printf("\n");
    return 0;
}

ข้อ 10 ตึกที่สูงกว่าหลังแรก

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

ถนนเส้นหนึ่งวิ่งจากทิศตะวันตกไปทิศตะวันออก มีตึก N หลังเรียงกันริมถนน หมายเลข 1 ถึง N จากตะวันตกไปตะวันออก ตึกหลังที่ i สูง h_i เมตร ช่างภาพจะขึ้นไปถ่ายวิวทางทิศตะวันออกจากดาดฟ้าของตึกทุกหลัง ตึกที่เตี้ยกว่าหรือสูงเท่ากับตึกที่ยืนอยู่ไม่บังวิว แต่ตึกหลังแรกที่สูงกว่าจะบังทุกอย่างที่อยู่ข้างหลังมัน

ให้หาว่าสำหรับตึกแต่ละหลัง ตึกหลังแรกทางทิศตะวันออกที่สูงกว่ามันอย่างเคร่งครัดคือหลังหมายเลขอะไร

ข้อมูลเข้า

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

บรรทัดที่สองมีจำนวนเต็ม N ตัว คือ h₁ ถึง h_N คั่นด้วยช่องว่าง โดยที่ 1 ≤ h_i ≤ 1000000000

ข้อมูลออก

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

7
3 7 4 4 9 2 8

2 5 5 5 0 7 0

3
5 5 5

0 0 0

ดูคำใบ้

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

ดูเฉลย

#include <stdio.h>

int height[500001];
int answer[500001];
int stack[500000];
int size = 0;

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