## A Chips Moving

description:
You are given n chips on a number line. The i-th chip is placed at the integer coordinate xi. Some chips can have equal coordinates.

You can perform each of the two following types of moves any (possibly, zero) number of times on any chip:

Move the chip i by 2 to the left or 2 to the right for free (i.e. replace the current coordinate xi with xi−2 or with xi+2);
move the chip i by 1 to the left or 1 to the right and pay one coin for this move (i.e. replace the current coordinate xi with xi−1 or with xi+1).
Note that it's allowed to move chips to any integer coordinate, including negative and zero.

Your task is to find the minimum total number of coins required to move all n chips to the same coordinate (i.e. all xi should be equal after some sequence of moves).

Input
The first line of the input contains one integer n (1≤n≤100) — the number of chips.

The second line of the input contains n integers x1,x2,…,xn (1≤xi≤1e9), where xi is the coordinate of the i-th chip.

Output
Print one integer — the minimum total number of coins required to move all n chips to the same coordinate.

Examples
input
3
1 2 3
output
1
input
5
2 2 2 3 3
output
2
Note
In the first example you need to move the first chip by 2 to the right and the second chip by 1 to the right or move the third chip by 2 to the left and the second chip by 1 to the left so the answer is 1.

In the second example you need to move two chips with coordinate 3 by 1 to the left so the answer is 2.

Problem solving:

code:

#include<bits/stdc++.h>
using namespace std;
const long long maxn = 105;
long long a[maxn];
int main()
{
long long n,ans=0,os=0,x;
cin>>n;
for(long long i=0;i<n;i++)
{
cin>>x;
if(x%2==0)    ans++;
else    os++;
}
cout<<min(ans,os)<<endl;
}


description:
Polycarp analyzes the prices of the new berPhone. At his disposal are the prices for n last days: a1,a2,…,an, where ai is the price of berPhone on the day i.

Polycarp considers the price on the day i to be bad if later (that is, a day with a greater number) berPhone was sold at a lower price. For example, if n=6 and a=[3,9,4,6,7,5], then the number of days with a bad price is 3 — these are days 2 (a2=9), 4 (a4=6) and 5 (a5=7).

Print the number of days with a bad price.

You have to answer t independent data sets.

Input
The first line contains an integer t (1≤t≤10000) — the number of sets of input data in the test. Input data sets must be processed independently, one after another.

Each input data set consists of two lines. The first line contains an integer n (1≤n≤150000) — the number of days. The second line contains n integers a1,a2,…,an (1≤ai≤1e6), where ai is the price on the i-th day.

It is guaranteed that the sum of n over all data sets in the test does not exceed 150000.

Output
Print t integers, the j-th of which should be equal to the number of days with a bad price in the j-th input data set.
Example
input
5
6
3 9 4 6 7 5
1
1000000
2
2 1
10
31 41 59 26 53 58 97 93 23 84
7
3 2 1 2 3 4 5
output
3
0
1
8
2

Problem solving:
(这道题我一开始没看懂意思，后来懂了，我太难了

code:

#include<bits/stdc++.h>
using namespace std;
const long long maxn = 150005;
long long a[maxn],b[maxn];
int main()
{
long long n,m;
cin>>n;
while(n--)
{
long long ans=0;
cin>>m;
for(long long i=0;i<m;i++)
{
cin>>a[i];
}
for(long long i=m-1;i>=0;i--)
{
if(i==m-1)    b[i]=a[i];
else    b[i]=min(b[i+1],a[i]);
}
for(long long i=0;i<m;i++)
{
if(a[i]!=b[i])    ans++;
}
cout<<ans<<endl;
}
}


description:
Polycarp is reading a book consisting of n pages numbered from 1 to n. Every time he finishes the page with the number divisible by m, he writes down the last digit of this page number. For example, if n=15 and m=5, pages divisible by m are 5,10,15. Their last digits are 5,0,5 correspondingly, their sum is 10.

Your task is to calculate the sum of all digits Polycarp has written down.

You have to answer q independent queries.

Input
The first line of the input contains one integer q (1≤q≤1000) — the number of queries.

The following q lines contain queries, one per line. Each query is given as two integers n and m (1≤n,m≤1016) — the number of pages in the book and required divisor, respectively.

Output
For each query print the answer for it — the sum of digits written down by Polycarp.

Example
input
7
1 1
10 1
100 3
1024 14
998244353 1337
123 144
1234312817382646 13
output
1
45
153
294
3359835
0
427262129093995

Problem solving:

0   0
1   1 2 3 4 5 6 7 8 9 0 1
2   2 4 6 8 0 2
3   3 6 9 2 5 8 1 4 7 0 3
4   4 8 2 6 0 4
5   5 0 5
6   6 2 8 4 0 6
7   7 4 1 8 5 2 9 6 3 0 7
8   8 6 4 2 0 8
9   9 8 7 6 5 4 3 2 1 0 9


1. m的个位是0，此时答案就是0
2. m的个位是5，此时循环长度是2，并且每一个循环的总和是5
3. m的个位是除了上面几种情况的偶数，此时循环长度是5，并且每一个循环的总和是20
4. m的个位是除了上面几种情况的奇数，此时循环长度是10，并且每一个循环的总和是45

code:

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
int main()
{
ll t;
cin>>t;
while(t--)
{
ll ans=0;
ll n,m;
cin>>n>>m;
if(m%10==0)    ans=0;
else if(m%10==5)
{
n/=m;
ans+=(n/2)*5;
n%=2;
ll mid=m%10;
for(ll i=0;i<n;i++)
{
ans+=mid;
mid=(mid+m%10)%10;
}
}
else if(m%10%2==0)
{
n/=m;
ans+=(n/5)*20;
n%=5;
ll mid=m%10;
for(ll i=0;i<n;i++)
{
ans+=mid;
mid=(mid+m%10)%10;
}
}
else if(m%10%2==1)
{
n/=m;
ans+=(n/10)*45;
n%=10;
ll mid=m%10;
for(ll i=0;i<n;i++)
{
ans+=mid;
mid=(mid+m%10)%10;
}
}
cout<<ans<<endl;
}
return 0;
}


#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[100];
int main()
{
ios::sync_with_stdio(false);
int t;
ll n,m;
cin>>t;
while (t --)
{
cin>>n>>m;
ll ans = 0,cnt = 0;
for (int i = 1;i <= 10;i ++)
a[i] = m*i%10,cnt += a[i];
n /= m;
ans = n/10*cnt;
for (int i = 1;i <= n%10;i ++) ans += a[i];
cout<<ans<<'\n';
}
return 0;
}


## D Equalizing by Division

description:
The only difference between easy and hard versions is the number of elements in the array.

You are given an array a consisting of n integers. In one move you can choose any ai and divide it by 2 rounding down (in other words, in one move you can set ai:=⌊ai2⌋).

You can perform such an operation any (possibly, zero) number of times with any ai.

Your task is to calculate the minimum possible number of operations required to obtain at least k equal numbers in the array.

Don't forget that it is possible to have ai=0 after some operations, thus the answer always exists.

Input
The first line of the input contains two integers n and k (1≤k≤n≤2⋅1e5) — the number of elements in the array and the number of equal numbers required.

The second line of the input contains n integers a1,a2,…,an (1≤ai≤2⋅1e5), where ai is the i-th element of a.

Output
Print one integer — the minimum possible number of operations required to obtain at least k equal numbers in the array.

Examples
input
5 3
1 2 2 4 5
output
1
input
5 3
1 2 3 4 5
output
2
input
5 3
1 2 3 3 3
output
0

Problem solving:

code:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5+10;
int a[maxn];
int main()
{
int n,k,ans=0x3f3f3f3f;
cin>>n>>k;
for(int i=0;i<n;i++)    cin>>a[i];
map<int,int> ma;//用来标记每个数的出现次数
map<int,int> maa;//用来标记转换到当前数需要的次数（局部的
sort(a,a+n);
for(int i=0;i<n;i++)
{
int cnt=0;//cnt记录的就是转换次数
int mid=a[i];
while(mid)
{
ma[mid]++;maa[mid]+=cnt;
if(ma[mid]>=k)  ans=min(ans,maa[mid]);//如果出现了出现次数大于等于k的数，更新答案
mid/=2;
cnt++;
}
}
cout<<ans<<endl;
}