SPCP3 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: alpha_ashwin
Tester: raysh07
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Chef has A marbles, and his friend has B.
What’s the minimum number of marbles that need to be transferred from one person to another, so that Chef’s marble count is divisible by his friend’s marble count?
Both people must have at least one marble.

EXPLANATION:

Suppose some marbles are transferred one way or another, and Chef ends up with X marbles.
The total number of marbles is A+B, so his friend must have A+B-X marbles.

This is a “good” final state if and only if X is a multiple of A+B-X.
Further, it’s easy to see that exactly |A-X| marbles need to be transferred to achieve this state:

  • If X\geq A, Chef’s friend gives X-A marbles to him.
  • If X\lt A, Chef gives A-X marbles to his friend.

Now, notice that X can only be between 1 and A+B-1, since there are A+B marbles in total, and both Chef and his friend should have at least one each.
So, loop over all such values of X, compute A+B-X, and check if it divides X.
If it does, you need |A-X| marbles to be transferred.
The final answer is the minimum among all these |A-X| values.

TIME COMPLEXITY:

\mathcal{O}(A+B) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    a, b = map(int, input().split())
    ans = 1000
    for x in range(1, a+b):
        y = a+b-x
        if x%y == 0: ans = min(ans, abs(a-x))
    print(ans)
1 Like
2

why this code give run time error. Pls tell me-

include
#include<bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
int t;cin>>t;
while(t–){
int a,b;

     cin>>a>>b;
     int ans =1000;
   //  int x =1;
     for(int i=1; i<=a+b; i++){
         int y = a + b -i;
         if(y%i==0)ans = min(ans,abs(a-i));
     }
     cout<<ans<<endl;
}
 


return 0;

}

1 Like
5 
#include <iostream>
#include<bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
	int T;
	cin>>T;
	while(T--){
	    int A, B;
	    cin>>A>>B;
	    int ans = 1000;
	    for(int i = 1; i < A + B; i++){
	        int  y = A + B - i;
	        if(i % y == 0){
	            ans = min(ans, abs(A - i));
	        }
	    }
	    cout<<ans<<endl;
	}
	return 0;
}
yes this work right answer