Hello people , I am stuck at this problem SITTING ARRANGEMENTS , i read the editorial but couldn't figure why the solution works, if anyone can provide an explanation/proof for the solution , it would be great. Thanks in advance :)
This is the author's solution
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll solve(ll n,ll m)
{
if(n==0||m==0)
return 0;
else if(n%2==0&&m%2==0)
return solve(n/2,m/2); // Halving both dimensions doesn't change the number of tiles
else if(n%2==0&&m%2==1)
return (n+solve(n/ 2,m/ 2));// Use a row of 1x1 tiles
else if(n%2==1&&m%2==0)
return (m+solve(n/ 2,m/ 2));// Use a column of 1x1 tiles
else
return (n+m-1+solve(n/2,m/2)); //ROW OR COLUMN (WHICHEVER OVERLAP)
}
int main()
{
ll t;
cin>>t;
while(t--)
{
ll n,m,i,j,p,q,r;
cin>>n>>m;
cout<<solve(n,m)<<endl;
}
}