A-Staircase
Authors: Invinc3,_NICkk
The answer contains such elements $$$a_i$$$ that $$$a_i+1=1$$$ since Chutki starts counting $$$1,2,3...$$$ again. Also add to the answer the last element $$$a_n$$$.
#include <bits/stdc++.h>
#define int long long
#define lop(i,a,b,c) for (int i=a;i<b;i+=c)
#define rlop(i,a,b,c) for (int i=a-1;i>=b;i-=c)
#define prii pair <int,int>
#define PB push_back
#define S second
#define F first
#define B begin()
#define E end()
using namespace std;
/*......................................................................*/
void solve(){
int n;cin>>n;
int arr[n+1];vector <int> vec;int p=0;
lop(i,0,n,1){
cin>>arr[i];
if (arr[i]>p)p=arr[i];
else {
vec.PB(p);p=1;
}
}vec.PB(p);
cout<<vec.size()<<"\n";
lop (i,0,vec.size(),1)cout<<vec[i]<<" ";
}
int32_t main(){
int t;t=1;
//cin>>t;
while (t--){
solve();
}
return 0;
}
n=int(input())
a=list(map(int,input().split()))
ans=[]
for i in range(n-1):
if a[i+1]==1:
ans.append(a[i])
ans.append(a[-1])
print(len(ans))
print(*ans)
B-XOR It
Authors: Invinc3,_NICkk
The XOR of two consecutive numbers will always be of the form $$$2^{x}-1$$$(trivial) for some $$$x>=0$$$
So we can convert the given number $$$n$$$ in this form for some value $$$x$$$
Thus, $$$2^{x}+1=n$$$
$$$x$$$ will be equal to $$$log_2(n+1)$$$
So now as we require the minimum possible value of $$$M$$$, it will be $$$(2^{x-1}-1)$$$.
The answer will be $$$-1$$$ for $$$n$$$ which is not of this form $$$2^{x}-1$$$
from math import log2
for _ in range(int(input())):
n=int(input())
k=log2(n+1)
if k%1==0:
k=int(k)
print(2**(k-1)-1)
else:
print(-1)
C-Sum with Twist
Authors: Invinc3,_NICkk
To approach this question you should know about divisor properties
Only perfect square have the property to have odd number of divisor {why ? Think about it}
so the condition $$$(p+q)\%2=0$$$ to be satisfied one number should be a perfect square and other should be a non-perfect square. Now you need to minimize the difference between those two numbers. To minimize the difference between those two number you should look for a number nearby half of the given number. {In practice look for the perfect square less than $$$n/2$$$ and perfect square greater then $$$n/2$$$ where $$$n$$$ is the given number, now check which have minimum difference keeping in mind only one number can be a perfect square i.e., both the numbers should not be a perfect square}.
#include <bits/stdc++.h>
#define int long long
#define lop(i,a,b,c) for (int i=a;i<b;i+=c)
#define rlop(i,a,b,c) for (int i=a-1;i>=b;i-=c)
#define prii pair <int,int>
#define PB push_back
#define S second
#define F first
#define B begin()
#define E end()
using namespace std;
/*......................................................................*/
void solve(){
int n;cin>>n;
int ans=1e18;int a=-1,b=-1;
int r=sqrt(n/2);
lop (i,-1,2,1){
int re=r+i;
int df=n-re*re;//cout<<re<<" "<<i<<" "<<df<<"\n";
int z=sqrt(df);
if (z*z==df or df<0 or re<=0)continue;
//cout<<re<<" "<<df<<" "<<abs(re*re-df)<<"\n";
if (ans>abs(re*re-df)){
ans=abs(re*re-df);
a=re*re;b=df;
}
}
if (a==-1){
cout<<a<<"\n";return;
}
else {
cout<<min(a,b)<<" "<<max(a,b)<<"\n";
}
}
int32_t main(){
int t;
cin>>t;
while (t--){
solve();
}
return 0;
}
from math import sqrt,floor,ceil
from sys import stdin,stdout
input=stdin.readline
for _ in range(int(input())):
a = int(input())
b=-1;c=-1;curr=10**15
res=floor(sqrt(a//2))
for i in range(-1,2):
new=res+i
diff=a-new**2
if diff>0 and sqrt(diff)%1==0:
continue
if curr>abs(diff-new**2):
curr=abs(diff-new**2)
c=diff;b=new**2
if b>0 and c>0:
print(min(b,c),max(b,c))
else:
print(-1)
D-XOR It, once again
Authors: Invinc3,_NICkk
We will find the value of K by finding its separate bits in binary representation.
Maximum number of bits present in $$$K$$$ can be 40 {think why!}.
For $$$i^{th}$$$ bit, if $$$x$$$ elements have this bit ON, implies $$$N - x$$$ elements have this bit OFF.
-> If this bit is ON in $$$K$$$ , then its contribution in final sum is $$$(N-x)*2^{i}$$$
-> If this bit is OFF in $$$K$$$, then its contribution in final sum is $$$x*2^{i}$$$
If $$$(N-x)>x$$$, then this bit will be OFF in K , otherwise this bit will be ON in K.
Hence, greedily we can find the value of K.
from sys import stdin,stdout
input=stdin.readline
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
bits = [0 for i in range(40)]
for x in a:
for j in range(40):
bits[j]+=(x>>j & 1)
ans=0
for i in range(40):
if (n-bits[i])<bits[i]:
ans+=(1<<i)
stdout.write(str(ans)+'\n')
#include <bits/stdc++.h>
#define int long long
#define lop(i,a,b,c) for (int i=a;i<b;i+=c)
#define rlop(i,a,b,c) for (int i=a-1;i>=b;i-=c)
#define prii pair <int,int>
#define PB push_back
#define S second
#define F first
#define B begin()
#define E end()
using namespace std;
/*......................................................................*/
void solve(){
int n;cin>>n;
int arr[64];memset(arr,0,sizeof(arr));
lop (i,0,n,1){
int a;scanf("%lld",&a);
string st=bitset<64>(a).to_string();int sz=st.size();
rlop (j,sz,0,1){
if (st[j]=='1'){
arr[sz-1-j]++;
}
}
}
int ans=0;int r=1;
lop (i,0,64,1){
int p=arr[i];
if (2*p>n){
ans+=r;
}
r=2*r;
}
cout<<ans<<"\n";
}
int32_t main(){
int t;
cin>>t;
while (t--){
solve();
}
return 0;
}