Contents
Chef and Bulb Invention Solution
Chef is trying to invent the light bulb that can run at room temperature without electricity. So he has N gases numbered from 00 to N−1 that he can use and he doesn’t know which one of the N gases will work but we do know it.
Now Chef has worked on multiple search algorithms to optimize search. For this project, he uses a modulo-based search algorithm that he invented himself. So first he chooses an integer KK and selects all indices ii in increasing order such that imodK=0imodK=0 and test the gases on such indices, then all indices ii in increasing order such that imodK=1imodK=1, and test the gases on such indices, and so on.
Given N, the index of the gas p that will work, and K, find after how much time will he be able to give Chefland a new invention assuming that testing 1 gas takes 1 day.
Also See: August Long Challenge 2021 Solutions
For example, consider N=5,p=2N=5,p=2 and K=3K=3.
- On the 1st1st day, Chef tests gas numbered 00 because 0mod3=00mod3=0.
- On the 2nd2nd day, Chef tests gas numbered 33 because 3mod3=03mod3=0.
- On the 3rd3rd day, Chef tests gas numbered 11 because 1mod3=11mod3=1.
- On the 4th4th day, Chef tests gas numbered 44 because 4mod3=14mod3=1.
- On the 5th5th day, Chef tests gas numbered 22 because 2mod3=22mod3=2.
So after 55 days, Chef will be able to give Chefland a new invention
Input Format
- The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
- The first and only line of each test case contains three space-separated integers NN, pp, and KK.
Output Format
For each test case, print a single line containing one integer — after how much time Chef will be able to give Chefland a new invention assuming that testing 11 gas takes 11 day.
Constraints
- 1≤T≤1051≤T≤105
- 1≤N,K≤1091≤N,K≤109
- 0≤p<N0≤p<N
Subtasks
Subtask #1 (100 points): Original constraints
Sample Input 1
4
10 5 5
10 6 5
10 4 5
10 8 5
Sample Output 1
2
4
9
8
Explanation
Test case 11: On the day 11 Chef will test gas numbered 00 and on the day 22 Chef will test gas numbered 55.
Test case 22: On the day 11 Chef will test gas numbered 00, on the day 22 Chef will test gas numbered 55, on the day 33 Chef will test gas numbered 11, and on the day 44 Chef will test gas numbered 66.
Test case 33: On the day 11 Chef will test gas numbered 00, on the day 22 Chef will test gas numbered 55, on the day 33 Chef will test gas numbered 11, on the day 44 Chef will test gas numbered 66, on the day 55 Chef will test gas numbered 22, on the day 66 Chef will test gas numbered 77, on the day 77 Chef will test gas numbered 33, on the day 88 Chef will test gas numbered 88, and on the day 99 Chef will test gas numbered 44.
Test case 44: On the day 11 Chef will test gas numbered 00, on the day 22 Chef will test gas numbered 55, on the day 33 Chef will test gas numbered 11, on the day 44 Chef will test gas numbered 66, on the day 55 Chef will test gas numbered 22, on the day 66 Chef will test gas numbered 77, on the day 77 Chef will test gas numbered 33, and on the day 88 Chef will test gas numbered 88.
Solution
Program Python: Chef and Bulb Invention Solution
t=int(input())
while(t>0):
n,p,k=list(map(int,input().split()))
ns=n//k
sno=p%k
if n%k==0:
print((sno*ns)+((p-sno)//k)+1)
#elif sno==p and (p+1)%k==0:
#print((sno*ns)+((p-sno)//k)+(p%k))
else:
if sno>(n-1)%k:
print((sno*ns)+((p-sno)//k)+((n-1))%k+2)
else:
print((sno*ns)+((p-sno)//k)+1+(p%k))
t-=1 Program C++: Chef and Bulb Invention Solution
#include <iostream>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int n, p, k;
cin >> n >> p >> k;
int ans = 0;
int q = p%k;
q--;
int s = (((n-1)/k)*k);
s = n-1-s;
if(q > s) {
ans += (s+1)*((n-1)/k+1)+ (q-s)*((n-1)/k);
} else {
ans += ((n-1)/k+1)*(q+1);
}
for(int i = q+1; i <= n-1; i+=k) {
ans++;
if(i == p) {
cout << ans << endl;
break;
}
}
}
}