- Forum
- General C++ Programming
- Competitive progrsmming
Competitive progrsmming
https://www.codechef.com/JUNE18B/problems/BINSHFFL this is the problem link
please tell how to solve this!
please tell how to solve this!
it is showing up the problem ..but still if you cant go to codechef and june long contest and then division two problem name is binary shuffle! thanks
a lot of us are on limited / monitored web access @ work.
unless you want to post the problem I can't see it. But there is an EPIC thread on a binary shuffle problem on these forums... look for it, its recent and ongoing, and may or may not apply to your problem.
unless you want to post the problem I can't see it. But there is an EPIC thread on a binary shuffle problem on these forums... look for it, its recent and ongoing, and may or may not apply to your problem.
Chef has two integers A and B. He can perform the following operation on A an arbitrary number of times (including zero):
write A as a binary number with an arbitrary number of leading zeroes (possibly without any)
shuffle the binary digits of A in an arbitrary way, obtaining a number s
replace A by s+1
Chef is wondering about the minimum number of operations he has to perform on A in order to obtain B. Compute this number or determine that it is impossible.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains two space-separated integers A and B.
Output
For each test case, print a single line containing one integer — the minimum number of operations or −1 if it is impossible to obtain B from A.
Constraints
1≤T≤105
0≤A,B≤1018
Subtasks
Subtask #1 (20 points): A,B≤27
Subtask #2 (80 points): original constraints
Example Input
2
2 4
1 5
Example Output
2
1
Explanation
Example case 1: One optimal solution is to not shuffle anything, so Chef just adds 1 twice.
Example case 2: We can obtain 5 from 1 in one operation.
write A as a binary number with an arbitrary number of leading zeroes (possibly without any)
shuffle the binary digits of A in an arbitrary way, obtaining a number s
replace A by s+1
Chef is wondering about the minimum number of operations he has to perform on A in order to obtain B. Compute this number or determine that it is impossible.
Input
The first line of the input contains a single integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of each test case contains two space-separated integers A and B.
Output
For each test case, print a single line containing one integer — the minimum number of operations or −1 if it is impossible to obtain B from A.
Constraints
1≤T≤105
0≤A,B≤1018
Subtasks
Subtask #1 (20 points): A,B≤27
Subtask #2 (80 points): original constraints
Example Input
2
2 4
1 5
Example Output
2
1
Explanation
Example case 1: One optimal solution is to not shuffle anything, so Chef just adds 1 twice.
Example case 2: We can obtain 5 from 1 in one operation.
Topic archived. No new replies allowed.