1038B - Non-Coprime Partition - CodeForces Solution


constructive algorithms math *1100

Please click on ads to support us..

Python Code:

import math
n=int(input())

if n == 1 or n == 2:
    print("No")
else:
    print("Yes")
    l1=[];l2=[]
    
    if n%2 == 0:
        l1.append(1);
        l1.append(n);
        
        for item in range(2,n):
            l2.append(item)
    else:
        l1.append(math.ceil(n/2))
        for item in range(1,n+1):
            if l1[0]!=item:
                l2.append(item)
    
    print(len(l1),end=" ")
    for item in l1:
        print(item,end=" ")
    print()
    print(len(l2),end=" ")
    for item in l2:
        print(item,end=" ")
    print()

C++ Code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll; 
int main()
{
    int n,target=-1;
    cin>>n;
    ll x=(n*(n+1))/2;
    for(ll i=2;i<=n;i++)
    {
        if(__gcd(i,x-i)>1)
        {
            target=i;
            break;
        }
    }
    if(target==-1)
    cout<<" No";
    else
    {
        cout<<" Yes\n";
        cout<<n-1<<" ";
        for(int i=1;i<=n;i++)
        {
            if(i!=target)
            cout<<i<<" ";
        }
        cout<<"\n";
        cout<<1<<" "<<target;
    }

}


Comments

Submit
0 Comments
More Questions

1699A - The Third Three Number Problem
1617B - GCD Problem
841A - Generous Kefa
1690B - Array Decrements
1692C - Where's the Bishop
104A - Blackjack
1438A - Specific Tastes of Andre
1711C - Color the Picture
1194C - From S To T
110B - Lucky String
1114A - Got Any Grapes
224B - Array
125B - Simple XML
567B - Berland National Library
431B - Shower Line
282C - XOR and OR
1582B - Luntik and Subsequences
609A - Флеш-карты
1207A - There Are Two Types Of Burgers
371C - Hamburgers
343B - Alternating Current
758B - Blown Garland
1681B - Card Trick
1592A - Gamer Hemose
493D - Vasya and Chess
1485A - Add and Divide
337B - Routine Problem
1392D - Omkar and Bed Wars
76E - Points
762C - Two strings