log in
Active Users
Feedback
About and Contact
© 2020 DOUBTCOOL
Chefina and Swap
You are given a positive integer N. Consider the sequence S=(1,2,…,N). You should choose two elements of this sequence and
swap them.
A swap is nice if there is an integer M (1≤M<N) such that the sum of the first M elements of the resulting sequence is equal
to the sum of its last N−M elements. Find the number of nice swaps.
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 a single integer N.
Output
For each test case, print a single line containing one integer ― the number of nice swaps.
You are given a positive integer N. Consider the sequence S=(1,2,…,N). You should choose two elements of this sequence and
swap them.
A swap is nice if there is an integer M (1≤M<N) such that the sum of the first M elements of the resulting sequence is equal
to the sum of its last N−M elements. Find the number of nice swaps.
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 a single integer N.
Output
For each test case, print a single line containing one integer ― the number of nice swaps.
6 regular answers available
C++ code
#include<bits/stdc++.h>
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define mod 1000000007;
#define ll long long int
#define pq priority_queue <ll,vector<ll>,greater<ll>>
#define pqpii priority_queue <pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>>
int main()
{
fast;
ll t;cin>>t;
while(t--){
ll n;
cin >> n;
vector <ll> v1,v2;
ll x;
map <ll,ll> m;
for(ll i=0;i<n;i++)
{
cin >> x;
m[x]++;
v1.push_back(x);
}
for(ll i=0;i<n;i++)
{
cin >> x;
m[x]--;
v2.push_back(x);
}
bool flag = false;
v1.clear();
v2.clear();
ll mi = x;
for(auto i:m)
{
mi = min(mi, i.first);
x = abs(i.second);
if(x%2)
flag = true;
x = i.second;
if(x > 0)
{
x /= 2;
while(x--)
v1.push_back(i.first);
}
else if(x < 0)
{
x = abs(x)/2;
while(x--)
v2.push_back(i.first);
}
}
if(flag)
{
cout << -1 << endl;
continue;
}
reverse(v2.begin(),v2.end());
ll ans = 0;
for(int i=0;i<v1.size();i++)
ans += min(2*mi,min(v1[i],v2[i]));
cout << ans << endl;
v1.clear(),v2.clear();
}
}
from collections import Counter
for _ in range(int(input())):
n = int(input())
a = sorted(map(int,input().split()))
b = sorted(map(int,input().split()))
x=Counter(a)
y=Counter(b)
z=x+y
l=[]
q=min(a[0],b[0])
for k in z.keys():
if z[k]%2==1:
print(-1)
break
else:
l.extend([k]*(abs(x[k]-y[k])//2))
else:
l.sort()
ans=0
if l==[]:
print(0)
else:
for i in range((len(l)//2)):
ans+=min(l[i],2*q)
print(ans)
def niceSwaps(n):
if n==3:
return 2
if (n+1)%4==0 or n%4==0:
return n-sum_arr(n)
else:
return 0
def sum_arr(n):
index=[]
last_sum=1
last_amount=1
for i in range(3, n+1):
if (i+1)%4==0 or i%4==0:
sum_req= (i*(i+1))//4
for j in range(last_amount+1, i+1):
if last_sum+j<=sum_req:
last_sum= last_sum+ j
last_amount= j
else:
index.append(last_amount)
break
return max(index)
for _ in range(int(input())):
t= int(input())
print(niceSwaps(t))
PYTHON CODE
import math
def sumofn(x):
return int(x*(x-1)/2)
for o in range(int(input())):
n=int(input())
p=0
if n%4==3 or n%4==0:
a=(n*(n+1)/2)/2
c=math.floor((((1+(8*a))**(1/2))-1)/2)
if c*(c+1)/2==a:
p +=sumofn(c) + sumofn(n - c) + n - c
else:
p=n-c
print(p)
JAVA CODE
import java.util.*;
import java.io.*;
class Codechef{
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw= new BufferedWriter(new OutputStreamWriter(System.out));
int t=Integer.parseInt(br.readLine());
for(int i=0;i<t;i++){
long n=Long.parseLong(br.readLine());
long start=1,end=n,mid=0;
long sum=(((n*(n+1))*1l)/2);
//System.out.println(sum);
if(sum%2==0){
sum=sum/2;
while(start<=end){
mid=start+((end-start)/2);
long midSum=((mid*(mid+1)*1l)/2);
if(midSum==sum)
break;
else if(midSum<sum){
start=mid+1;
}else end=mid-1;
}
long midpoint=(mid*(mid+1)*1l)/2;
long ans=0l;
if(midpoint<sum){
ans=n-mid;
}else if(midpoint>sum){
ans=n-mid+1;
}else{
ans=((n-mid)*1l+((mid*(mid-1)*1l)/2)+(((n-mid)*(n-mid-1)*1l)/2));
}
bw.write(ans+"\n");
}else bw.write(0+"\n");
}
bw.flush();
}
}
C++ code
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000000007
int main() {
ll t;
cin >> t;
while(t--){
ll n;
cin >> n;
ll sum = ((n * (n + 1)))/2;
if(sum%2 != 0){
cout << 0 << endl;
} else {
double a = double(sqrt(1+4*sum) - 1) / 2;
ll res = a/1;
if(res*1 == a){
ll val = ll(a);
// cout << val;
ll ans1 = n - val;
cout <<ans1 + ((n-val-1)*(n-val))/2 + ((val-1)*val)/2 << endl;
}else{
ll val = ll(a);
//cout << val;
ll ans1 = n - val;
cout <<ans1<< endl;
}
}
}
}