Sherlock Holmes is stuck and cannot leave until he solves this puzzle. There are $$$n$$$ lamps in another chamber and $$$m$$$ switches in his current room. Each lamp can have up to $$$k$$$ distinct heat levels, which Sherlock can sense with his hands. He is very sensitive and can detect subtle changes, and after Valentine's Day, he finds himself with nothing but switches and lamps for company. Don't worry, all coders understand: love may crash, but programs run forever.
Sherlock needs to determine with absolute certainty which switch controls which lamp $$$(n \le m)$$$, knowing that he can enter the lamp room at most $$$t$$$ times. Each time he enters, he can observe for every lamp whether it is on or off and its temperature level.
Determine whether it is possible for Sherlock to map every lamp to its switch under these constraints.
The first line contains four integers $$$n , m , k , t (1 \le n \le m \le 10^{18}, 1 \le k \le 10^9, 1 \le t \le 10^6)$$$.
Print YES if it is possible for Sherlock to determine the mapping with certainty, or NO otherwise.
4 16 6 2
YES
28 28 5 4
YES
10 11 7 1
YES
8 9 10 10
YES
1. The Classic Riddle SetupThe Scenario: ($$$n = 1, m = 3, k =2, t = 1$$$)
You are in a room with 3 switches ($$$m=3$$$). Only one connects to a light bulb in the next room. The Constraint: You can flip switches as much as you like, but you can only enter the bulb room once ($$$t=1$$$).
The Goal: Find the correct switch.
2. The Solution (The Physical "Trick")
The standard solution exploits the fact that a light bulb gets hot.
Turn Switch 1 ON and leave it for 10 minutes (to generate heat).
Turn Switch 1 OFF.
Turn Switch 2 ON.
Walk into the room immediately.
3. The Diagnosis:
If the bulb is ON: It's Switch 2.
If the bulb is OFF but HOT: It's Switch 1.
If the bulb is OFF and COLD: It's Switch 3.
