พิมพ์ทิศทางเคลื่อนที่อยู่ในขอบเขต [-k, +k] ใน C++

โจทย์

ให้ขอบเขต K และอาร์เรย์ค่าการเคลื่อนที่ ต้องการหาลำดับทิศทาง (Positive/Negative) ที่ทำให้ตำแหน่งไม่เกิน [-K, +K] ตลอดเวลา

ตัวอย่าง: K=56, array=[25,14,31,16,5] → Positive, Positive, Negative, Positive, Positive

อัลกอริทึม

position = 0
For each move a[i]:
    If position + a[i] in [-K, K]: move Positive, position += a[i]
    Else if position - a[i] in [-K, K]: move Negative, position -= a[i]
    Else: No valid moves

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

void StepsTaken(int a[], int n, int k) {
    int position = 0;
    for (int i = 0; i < n; i++) {
        if (position + a[i] <= k && position + a[i] >= -k) {
            position += a[i];
            cout << "POSITIVE \t";
        } else if (position - a[i] >= -k && position - a[i] <= k) {
            position -= a[i];
            cout << "NEGATIVE \t";
        } else {
            cout << -1;
            return;
        }
    }
}

int main() {
    int a[] = {12, 24, 9, 17, 8};
    int n = sizeof(a) / sizeof(a[0]);
    int k = 40;
    StepsTaken(a, n, k);
    return 0;
}

ผลลัพธ์

POSITIVE   POSITIVE   NEGATIVE    NEGATIVE   POSITIVE