มีห้องที่มีหลอดไฟ n ดวงเปิดอยู่ทั้งหมด และมีปุ่ม 4 ปุ่ม หลังจากกดปุ่มทั้งหมด m ครั้ง (ไม่ทราบลำดับ) ต้องการหาจำนวนรูปแบบสถานะของหลอดไฟที่เป็นไปได้ หลอดไฟมีหมายเลข 1,2,3...,n ฟังก์ชันของปุ่ม 4 ปุ่ม:
- ปุ่ม 1: สลับหลอดไฟทั้งหมด
- ปุ่ม 2: สลับหลอดไฟเลขคู่
- ปุ่ม 3: สลับหลอดไฟเลขคี่
- ปุ่ม 4: สลับหลอดไฟเลข (3k+1) โดย k = 0,1,2,...
ตัวอย่าง: n = 3, m = 1 → มี 4 รูปแบบ: [off,on,off], [on,off,on], [off,off,off], [off,on,on]
วิธีแก้ปัญหา (สังเกตรูปแบบ)
ปัญหานี้มีรูปแบบคงที่ ไม่ต้องจำลองจริง:
- ถ้า n = 0 หรือ m = 0 → 1 รูปแบบ
- ถ้า n = 1 → 2 รูปแบบ
- ถ้า n = 2 → 3 รูปแบบ (ถ้า m=1) มิฉะนั้น 4 รูปแบบ
- ถ้า m = 1 → 4 รูปแบบ
- ถ้า m = 2 → 7 รูปแบบ มิฉะนั้น 8 รูปแบบ
ตัวอย่างโค้ด C++
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int flipLights(int n, int m) {
if (m == 0 || n == 0) return 1;
if (n == 1) return 2;
if (n == 2) return m == 1 ? 3 : 4;
if (m == 1) return 4;
return m == 2 ? 7 : 8;
}
};
int main() {
Solution ob;
cout << ob.flipLights(3, 1);
return 0;
}
Input
3 1
Output
4
