บทนำ
โจทย์: กำหนดตัวเลขเป็นสตริง และตัวหารสองตัว (prefix_dividend, suffix_dividend) หาตำแหน่งตัดที่ทำให้ส่วนหน้า (prefix) หารตัวหารแรกลงตัว และส่วนท้าย (suffix) หารตัวหารที่สองลงตัว
ขั้นตอนการแก้ปัญหา
- รับสตริงตัวเลขและตัวหารสองตัว
- สร้าง prefix โดยอ่านทีละหลักจากซ้ายไปขวา จนกว่าจะหารตัวหารแรกลงตัว
- ส่วนที่เหลือเป็น suffix
- ตรวจสอบ suffix ว่าหารตัวหารที่สองลงตัวหรือไม่
- ถ้าทั้งคู่ลงตัว → พิมพ์ทั้งสองส่วน, มิฉะนั้น → "Not possible"
ตัวอย่างโค้ด
#include <bits/stdc++.h>
using namespace std;
void checkTheDivisabilityOfPrefixAndSuffix(string num, int prefix_dividend, int suffix_dividend) {
int N = num.length();
bool is_prefix_divisable = false, is_suffix_divisable = false;
int index = 0;
int prefix = num[index] - '0';
while (index < N) {
if (prefix % prefix_dividend == 0) {
is_prefix_divisable = true;
break;
}
prefix = prefix * 10 + (num[++index] - '0');
}
int suffix = num[++index] - '0';
while (index < N - 1) {
suffix = suffix * 10 + (num[++index] - '0');
}
if (suffix % suffix_dividend == 0) {
is_suffix_divisable = true;
}
if (is_prefix_divisable && is_suffix_divisable) {
cout << prefix << " " << suffix << endl;
} else {
cout << "Not possible" << endl;
}
}
int main() {
string number = "125333";
int prefix_dividend = 5;
int suffix_dividend = 3;
checkTheDivisabilityOfPrefixAndSuffix(number, prefix_dividend, suffix_dividend);
return 0;
}
ผลลัพธ์
125 333
คำอธิบาย
- Prefix: 125 หาร 5 ลงตัว (125 ÷ 5 = 25)
- Suffix: 333 หาร 3 ลงตัว (333 ÷ 3 = 111)
ข้อควรระวัง
โค้ดนี้หา prefix แบบ Greedy (เจอตัวแรกที่หารลงตัวหยุดเลย) อาจไม่ได้คำตอบที่ดีที่สุดหากมีหลายตำแหน่งตัดที่เป็นไปได้
สรุป
โจทย์แบ่งสตริงตัวเลขด้วยเงื่อนไขการหาร ใช้ได้กับเลขใหญ่ที่เกินชนิดข้อมูลมาตรฐาน
