Friday 11 June 2021

Another Problem About Dividing Numbers :: Codeforces Round 725 D

Problem link

In this problem you will be given two integer number a and b. You need to make a and b equal in exactly k operation(s).  In one operation you can either,

  • Take an integer ( and should be divisible by ) and replace with
  • Take an integer
    • (and should be divisible by ) and replace with .

Observations: If we at least  need x moves to make a and b equal and we have at most y moves which is total number of moves we can make in total. A move is choosing such a C discussing above. Then we can also make a and b equal by x+1,x+2,x+3.......y-2,y-1,y moves. [for better understanding a paperwork may help]

Explanation:

For finding the minimum number of moves to make a and b (if a!=b) are equal will be 1 or 2. 

>>if gcd(a,b)==min(a,b) then it will be 1.

lets say, a=36 and b=12;

gcd(36,12) = min(36,12) = 12 

we can make a=12 by dividing 36 by 3 in one move.

>>if gcd(a,b)!=min(a,b) then it will be 2. Because we need to divide both a and b to make equal to its gcd.

For finding the at most moves we have, we had to find number of prime factors both for a and b. because at most we can divide them until they left any prime factors.

For calculating the Number of prime factors. we will be needed prime numbers. For this purpose a simple sieve will work fine.

Code: 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define int long long
#define IOS ios::sync_with_stdio(false);
int gcd(int a, int b) { if (a == 0) return b; return gcd(b % a, a);}
const int maxn=100005;
bitset<maxn+5>bs;
vector<int> prime;
void seive(){
  bs.set();
  bs[0]=0;
  bs[1]=0;
  for(int i=2;i<maxn;i++){
    if(bs[i]){
      prime.pb(i);
      for(int j = i*i; j<maxn;j+=i)bs[j]=0;
    }
  }
}
///solution
void solution(){
    int a,b,k;
    cin>>a>>b>>k;
    if(a==b && k==1){
        cout << "NO\n";
        return;
    }
    int cnta=0,cntb=0,now=a;
    for(auto it:prime){
      if(it*it>now){
        break;
      }
      while(now%it == 0){
        now/=it;
        cnta++;
      }
    }
    if(now>1)cnta++;
    now=b;
    for(auto it:prime){
      if(it*it>now )break;
      while(now%it == 0){
        now/=it;
        cntb++;
      }
    }
    if(now>1)cntb++;

    int x=gcd(a,b);
    int atmost=cnta+cntb,least=0;
    if(x==min(a,b))least=1;
    else least=2;
    if(least<=k && atmost>=k){
      cout << "YES\n";
    }
    else cout << "NO\n";
}
signed main()
{
  IOS
    int t;
    t=1;
    seive();
    cin>>t;
    while(t--){
        solution();
    }
    return 0;
}
Posted by at 2 comments:
Labels: ,

Sunday 6 June 2021

Atcoder Beginner Contest 204 (A to D) Explanation with code

Contest Link

Problem A:

There are three players playing rock, paper, scissors. Given first two players hand thrown. What will be the last player hand shape if they have a draw.

Explanation: 

1.If the two players has same type of hand shape, then the last player must  have the same hand shape too.

2. If the two players has different type of hand shape, then the last player must have a hand shape other than the each of the players.

Code of A:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);

///solution
void solution(){
    int x,y;
    cin>>x>>y;
    if(x==y){
    	cout << x << endl;
    }
    else cout << (3-(x+y)) << endl;
}
signed main()
{
  IOS
    int t;
    t=1;
    //cin>>t;
    while(t--){
        solution();
    }
    return 0;
}
///Alhamdulillah
Problem B:

Explanation: We had to calculate the sum of max(tree[i]-10,0) for every tree i from 1 to n.

Code of B:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define int long long
#define IOS ios::sync_with_stdio(false);
///solution
void solution(){
    int n;
    cin>>n;
    int ans=0;
    for(int i=0;i<n;i++){
    	int x;
    	cin>>x;
    	if(x>10){
    		ans+= (x-10);
    	}
    }
    cout << ans << endl;
}
signed main()
{
  IOS
    int t;
    t=1;
    //cin>>t;
    while(t--){
        solution();
    }
    return 0;
}
///Alhamdulillah
Problem C:

This problem asks that how many ways we can choose two cities as one as origin and one as destination.

Explanation: We can go a city x from a city y iff the city x is connected to y. For this purpose we just need to check how many cities are connected to city y. where y will be every city from 1 to n.

Code of C:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define int long long
#define f0(n) for(int i=0;i<n;i++)
#define ms(x) memset(x,0,sizeof(x))
#define IOS ios::sync_with_stdio(false);
const int maxn=2005;
int ans=0;
vector<int>adj[maxn];
void bfs(int u){
	int vis[maxn];
	ms(vis);
	vis[u]=1;
	int cnt=0;
	queue<int>q;
	q.push(u);
	while(!q.empty()){
		int x=q.front();
		q.pop();
		for(int i=0;i<adj[x].size();i++){
			int v=adj[x][i];
			if(vis[v]==0){
				q.push(v);
				vis[v]=1;
				cnt++;
			}
		}
	}
	ans+=cnt;
}
///solution
void solution(){
    int n,m;
    cin>>n>>m;
    ans=n;
    int mark[n+1];
    ms(mark);
    for(int i=0;i<m;i++){
    	int u,v;
    	cin>>u>>v;
    	adj[u].pb(v);
    }
    for(int i=1;i<=n;i++){
    	bfs(i);
    }
    cout << ans << endl;
}
signed main()
{
  IOS
    int t;
    t=1;
    //cin>>t;
    while(t--){
        solution();
    }
    return 0;
}
///Alhamdulillah
Problem D:

we have a set. we have to partition it into two sets. Lets say,

S1 = sum of first set

S2 = sum of second set.

then our answer will be maximum of S1 and S2. We had partition this sets such a way that the answer will be minimum.

Explanation:

To do such task in efficient way we have to go with a DP solution.

where,

dp[i][j]==true if some subset has a sum equal to j. for the first i elements. Otherwise 0.

where, (1<=i<=n), (0<=j<=sum)

Then we just check that if we can choose such j where there has an subset. where( 0<=j<=sum/2)

Then this is valid partition where we can partitioned these two sets,

S1 = sum-j;

S2 = j;

Code of D:


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);
int Mini(int arr[], int n)
{
  int sum = 0;
  for (int i = 0; i < n; i++)
    sum += arr[i];
  bool dp[n+1][sum+1];
  for (int i = 0; i <= n; i++)
    dp[i][0] = true;
  for (int i = 1; i <= sum; i++)
    dp[0][i] = false;
  for (int i=1; i<=n; i++)
  {
    for (int j=1; j<=sum; j++)
    {
      dp[i][j] = dp[i-1][j];
      if (arr[i-1] <= j)
        dp[i][j] |= dp[i-1][j-arr[i-1]];
    }
  }
  int diff = INT_MAX;
  for (int j=sum/2; j>=0; j--)
  {
    if (dp[n][j] == true)
    {
      diff = max(sum-j,j);
      break;
    }
  }
  return diff;
}
///solution
void solution(){
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)cin>>arr[i];
    cout << Mini(arr,n);
}
signed main()
{
  IOS
    int t;
    t=1;
    //cin>>t;
    while(t--){
        solution();
    }
    return 0;
}
Posted by at No comments:
Labels: , ,
Subscribe to: Posts (Atom)

Monkey Banana Problem lightoj 1004

  In this problem we will check which adjacent cell will benefits the monkey best. For this, we will check all possible solution of this pro...