Codeforces Constructive Problems
1. Codeforces Round #720 (Div. 2) A. Nastia and Nearly Good Numbers
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1521/A
Codeforces Round #720 (Div. 2) A. Nastia and Nearly Good Numbers
Nastia has 2 positive integers A and B. She defines that:
The integer is good if it is divisible by A⋅B;
Otherwise, the integer is nearly good, if it is divisible by A.
Find 3 different positive integers x, y, and z such that exactly one of
them is good and the other 2 are nearly good, and x+y=z.
*/
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
ll a,b;scanf("%lld%lld",&a,&b);
if(b==1)printf("NO\n");
else printf("YES\n%lld %lld %lld\n",(3*b-1)*a,a,3*a*b);
}
}
2. Educational Codeforces Round 103 A. K-divisible Sum
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1476/A
Educational Codeforces Round 103 A. K-divisible Sum
You are given two integers n and k.
You should create an array of n positive integers a1,a2,…,an
such that the sum (a1+a2+⋯+an) is divisible by k and maximum
element in a is minimum possible.
What is the minimum possible maximum element in a?
*/
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
ll n,k;scanf("%lld%lld",&n,&k);
if(k<n)k=k*((n-1)/k+1);
printf("%lld\n",(k-1)/n+1);
}
}
3. Codeforces Round #719 (Div. 3) C. Not Adjacent Matrix
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1520/C
Codeforces Round #719 (Div. 3) C. Not Adjacent Matrix
We will consider the numbers a and b as adjacent if they differ by
exactly one, that is, |a−b|=1.
We will consider cells of a square matrix n×n as adjacent if they have
a common side, that is, for cell (r,c) cells (r,c−1), (r,c+1), (r−1,c)
and (r+1,c) are adjacent to it.
For a given number n, construct a square matrix n×n such that:
Each integer from 1 to n2 occurs in this matrix exactly once;
If (r1,c1) and (r2,c2) are adjacent cells, then the numbers written in
them must not be adjacent.
*/
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
ll n,k;scanf("%lld%lld",&n,&k);
if(k<n)k=k*((n-1)/k+1);
printf("%lld\n",(k-1)/n+1);
}
}
4. Codeforces Global Round 7 A. Bad Ugly Numbers
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1326/A
Codeforces Global Round 7 A. Bad Ugly Numbers
You are given a integer n (n > 0). Find any integer s which satisfies
these conditions, or report that there are no such numbers:
In the decimal representation of s:
s > 0,
s consists of n digits,
no digit in s equals 0,
s is not divisible by any of it's digits.
*/
void run(){
int n;scanf("%d",&n);
if(n==1){
printf("-1\n");
return;
}
printf("2");
for(int i=0;i<n-1;i++){
printf("3");
}
printf("\n");
return;
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
5. Codeforces Round #360 (Div. 2) B. Lovely Palindromes
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/688/B
Codeforces Round #360 (Div. 2) B. Lovely Palindromes
Pari has a friend who loves palindrome numbers. A palindrome number is a
number that reads the same forward or backward. For example 12321, 100001
and 1 are palindrome numbers, while 112 and 1021 are not.
Pari is trying to love them too, but only very special and gifted people
can understand the beauty behind palindrome numbers. Pari loves integers
with even length (i.e. the numbers with even number of digits), so she
tries to see a lot of big palindrome numbers with even length (like a
2-digit 11 or 6-digit 122221), so maybe she could see something in them.
Now Pari asks you to write a program that gets a huge integer n from the
input and tells what is the n-th even-length positive palindrome number?
*/
void run(){
string s;
cin>>s;
cout<<s;
reverse(s.begin(),s.end());
cout<<s<<"\n";
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
6. Codeforces Round #396 (Div. 2) B. Mahmoud and a Triangle
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/766/B
Codeforces Round #396 (Div. 2) B. Mahmoud and a Triangle
Mahmoud has n line segments, the i-th of them has length a_i. Ehab
challenged him to use exactly 3 line segments to form a non-degenerate
triangle. Mahmoud doesn't accept challenges unless he is sure he can win,
so he asked you to tell him if he should accept the challenge. Given the
lengths of the line segments, check if he can choose exactly 3 of them to
form a non-degenerate triangle.
Mahmoud should use exactly 3 line segments, he can't concatenate two line
segments or change any length. A non-degenerate triangle is a triangle
with positive area.
*/
#define MAXN 300030
ll a[MAXN];
void run(){
int n;scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%lld",&a[i]);
sort(a,a+n);
for(int i=2;i<n;i++){
if(a[i-2]+a[i-1]>a[i]){
printf("YES\n");
return;
}
}
printf("NO\n");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
7. Codeforces Beta Round #89 (Div. 2) B. Present from Lena
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/118/B
Codeforces Beta Round #89 (Div. 2) B. Present from Lena
Vasya's birthday is approaching and Lena decided to sew a patterned
handkerchief to him as a present. Lena chose digits from 0 to n as the
pattern. The digits will form a rhombus. The largest digit n should be
located in the centre. The digits should decrease as they approach the
edges. For example, for n = 5 the handkerchief pattern should look like
that:
0
0 1 0
0 1 2 1 0
0 1 2 3 2 1 0
0 1 2 3 4 3 2 1 0
0 1 2 3 4 5 4 3 2 1 0
0 1 2 3 4 3 2 1 0
0 1 2 3 2 1 0
0 1 2 1 0
0 1 0
0
Your task is to determine the way the handkerchief will look like by the
given n.
*/
void run(){
int n;scanf("%d",&n);
auto print=[&](int i){
for(int j=0;j<2*(n+i+1)-1;j++){
if(j%2||j-2*(n-i)<0)printf(" ");
else {
int x=(j-2*(n-i))/2;
if(j>2*n){
x=i-(x-i);
printf("%d",x);
}else printf("%d",x);
}
}
printf("\n");
};
for(int i=0;i<=n;i++){
print(i);
}
for(int i=n-1;i>=0;i--){
print(i);
}
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
8. Educational Codeforces Round 101 (Rated for Div. 2) A. Regular Bracket Sequence
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1469/A
Educational Codeforces Round 101 (Rated for Div. 2) A. Regular Bracket Sequence
A bracket sequence is called regular if it is possible to obtain correct
arithmetic expression by inserting characters + and 1 into this sequence.
For example, sequences (())(), () and (()(())) are regular, while )(, (()
and (()))( are not. Let's call a regular bracket sequence "RBS".
You are given a sequence s of n characters (, ), and/or ?. There is
exactly one character ( and exactly one character ) in this sequence.
You have to replace every character ? with either ) or ( (different
characters ? can be replaced with different brackets). You cannot reorder
the characters, remove them, insert other characters, and each ? must be
replaced.
Determine if it is possible to obtain an RBS after these replacements.
*/
void run(){
string s;cin>>s;
int n=s.length();
#define no do{printf("NO\n");return;}while(0)
#define yes do{printf("YES\n");return;}while(0)
if(n%2)no;
int l=0,r=0;
for(int i=0;i<n;i++){
if(s[i]=='(')l++;
if(s[i]==')')r++;
}
if(l>n/2||r>n/2)no;
l=n/2-l;r=n/2-r;
for(int i=0;i<n;i++){
if(s[i]!='?')continue;
if(l)s[i]='(',l--;
else s[i]=')';
}
l=0;r=0;
for(int i=0;i<n;i++){
if(s[i]=='(')l++;
else r++;
if(r>l)no;
}
yes;
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
9. Codeforces Round #396 (Div. 2) A. Mahmoud and Longest Uncommon Subsequence
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/766/A
Codeforces Round #396 (Div. 2) A. Mahmoud and Longest Uncommon Subsequence
While Mahmoud and Ehab were practicing for IOI, they found a problem which
name was Longest common subsequence. They solved it, and then Ehab
challenged Mahmoud with another problem.
Given two strings a and b, find the length of their longest uncommon
subsequence, which is the longest string that is a subsequence of one of
them and not a subsequence of the other.
A subsequence of some string is a sequence of characters that appears in
the same order in the string, The appearances don't have to be
consecutive, for example, strings "ac", "bc", "abc" and "a" are
subsequences of string "abc" while strings "abbc" and "acb" are not. The
empty string is a subsequence of any string. Any string is a subsequence
of itself.
*/
void run(){
string a,b;
cin>>a>>b;
if(a==b){
printf("-1\n");
return;
}
int n=a.length(),m=b.length();
printf("%d\n",max(n,m));
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
10. Codeforces Round #702 (Div. 3) B. Balanced Remainders
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1490/B
Codeforces Round #702 (Div. 3) B. Balanced Remainders
You are given a number n (divisible by 3) and an array a[1 \dots n]. In
one move, you can increase any of the array elements by one. Formally, you
choose the index i (1 \le i \le n) and replace a_i with a_i + 1. You can
choose the same index i multiple times for different moves.
Let's denote by c_0, c_1 and c_2 the number of numbers from the array a
that have remainders 0, 1 and 2 when divided by the number 3,
respectively. Let's say that the array a has balanced remainders if c_0,
c_1 and c_2 are equal.
For example, if n = 6 and a = [0, 2, 5, 5, 4, 8], then the following
sequence of moves is possible:
initially c_0 = 1, c_1 = 1 and c_2 = 4, these values are not equal to
each other. Let's increase a_3, now the array a = [0, 2, 6, 5, 4, 8];
c_0 = 2, c_1 = 1 and c_2 = 3, these values are not equal. Let's increase
a_6, now the array a = [0, 2, 6, 5, 4, 9];
c_0 = 3, c_1 = 1 and c_2 = 2, these values are not equal. Let's increase
a_1, now the array a = [1, 2, 6, 5, 4, 9];
c_0 = 2, c_1 = 2 and c_2 = 2, these values are equal to each other, which
means that the array a has balanced remainders.
Find the minimum number of moves needed to make the array a have balanced
remainders.
*/
void run(){
int n;scanf("%d",&n);
vector<int> c(3,0);
for(int i=0;i<n;i++){
int x;scanf("%d",&x);
c[x%3]++;
}
int res=0,t=n/3;
for(int i=0;i<6;i++){
int d=c[i%3]-t;
if(d>0){
res+=d;
c[i%3]-=d;
c[(i+1)%3]+=d;
}
}
printf("%d\n",res);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
11. Codeforces Round #632 (Div. 2) A. Little Artem
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1333/A
Codeforces Round #632 (Div. 2) A. Little Artem
Young boy Artem tries to paint a picture, and he asks his mother Medina to
help him. Medina is very busy, that's why she asked for your help.
Artem wants to paint an n \times m board. Each cell of the board should be
colored in white or black.
Lets B be the number of black cells that have at least one white neighbor
adjacent by the side. Let W be the number of white cells that have at
least one black neighbor adjacent by the side. A coloring is called good
if B = W + 1.
The first coloring shown below has B=5 and W=4 (all cells have at least
one neighbor with the opposite color). However, the second coloring is not
good as it has B=4, W=4 (only the bottom right cell doesn't have a
neighbor with the opposite color).
<img class="tex-graphics"
src="https://espresso.codeforces.com/5611f0803c61268019d39e2781107538b4c56aeb.png" style="max-width: 100.0%;max-height: 100.0%;" />
Please, help Medina to find any good coloring. It's guaranteed that under
given constraints the solution always exists. If there are several
solutions, output any of them.
*/
void run(){
int n,m;scanf("%d%d",&n,&m);
/*
BWBWB
BWBWW
BWBWB
BWBWW
BWBWB
*/
if(n%2&&m%2){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(j==m-1){
if(i%2)printf("W");
else printf("B");
}else{
if(j%2)printf("W");
else printf("B");
}
}
printf("\n");
}
return;
}
/*
BBBBB
BWWWW
BBBBB
WWWWW
*/
if(n%2==0){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(i==1&&j==0)printf("B");
else{
if(i%2)printf("W");
else printf("B");
}
}
printf("\n");
}
return;
}
/*
BBBW
BWBW
BWBW
BWBW
BWBW
*/
if(m%2==0){
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(i==0&&j==1)printf("B");
else{
if(j%2)printf("W");
else printf("B");
}
}
printf("\n");
}
return;
}
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
12. Codeforces Round #696 (Div. 2) B. Different Divisors
Method 1: Prime Checking.
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1474/B
Codeforces Round #696 (Div. 2) B. Different Divisors
Positive integer x is called divisor of positive integer y, if y is
divisible by x without remainder. For example, 1 is a divisor of 7 and 3
is not divisor of 8.
We gave you an integer d and asked you to find the smallest positive
integer a, such that
a has at least 4 divisors;
difference between any two divisors of a is at least d.
*/
void run(){
int d;cin>>d;
auto isp=[](ll n){
for(int i=2;i*i<=n;i++)if(n%i==0)return false;
return true;
};
ll a=d+1;
while(!isp(a))a++;
ll b=a+d;
while(!isp(b))b++;
cout<<a*b<<endl;
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
Method 2: Save Next Prime.
#include<bits/stdc++.h>
#define MAXD 10000
#define MAXN (MAXD*2+1000)
using namespace std;
using ll=long long;
bool isp[MAXN];
int nxtp[MAXN];
void init(){
memset(isp,true,sizeof(isp));
// Eratosthenes Sieve.
isp[0]=isp[1]=false;
for(int i=2;i<MAXN;i++)if(isp[i])for(int j=i*i;j<MAXN;j+=i)isp[j]=false;
for(int i=MAXN-2;i>=2;i--)isp[i]?nxtp[i]=i:nxtp[i]=nxtp[i+1];
}
void run(){
int d;scanf("%d",&d);
ll a=nxtp[1+d];
ll b=nxtp[a+d];
printf("%lld\n",a*b);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
init();
int T;scanf("%d",&T);
while(T--){
run();
}
}
Method 3: Binary Search on Saved Primes.
#include<bits/stdc++.h>
#define MAXD 10000
#define MAXN (MAXD*2+1000)
using namespace std;
using ll=long long;
bool isp[MAXN];
vector<int> ps;
void init(){
memset(isp,true,sizeof(isp));
// Eratosthenes Sieve.
isp[0]=isp[1]=false;
for(int i=2;i<MAXN;i++)if(isp[i]){
ps.push_back(i);
for(int j=i*i;j<MAXN;j+=i)isp[j]=false;
}
}
void run(){
int d;scanf("%d",&d);
ll a=*lower_bound(ps.begin(),ps.end(),d+1);
ll b=*lower_bound(ps.begin(),ps.end(),a+d);
printf("%lld\n",a*b);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
init();
int T;scanf("%d",&T);
while(T--){
run();
}
}
13. Educational Codeforces Round 83 (Rated for Div. 2) B. Bogosort
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1312/B
Educational Codeforces Round 83 (Rated for Div. 2) B. Bogosort
You are given an array a_1, a_2, \dots , a_n. Array is good if for each
pair of indexes i < j the condition j - a_j \ne i - a_i holds. Can you
shuffle this array so that it becomes good? To shuffle an array means to
reorder its elements arbitrarily (leaving the initial order is also an
option).
For example, if a = [1, 1, 3, 5], then shuffled arrays [1, 3, 5, 1], [3,
5, 1, 1] and [5, 3, 1, 1] are good, but shuffled arrays [3, 1, 5, 1], [1,
1, 3, 5] and [1, 1, 5, 3] aren't.
It's guaranteed that it's always possible to shuffle an array to meet this
condition.
*/
#define MAXN 110
int a[MAXN];
void run(){
int n;scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
}
sort(a,a+n,[](int x,int y){return x>y;});
for(int i=0;i<n;i++)printf("%d%c",a[i]," \n"[i==n-1]);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
14. Codeforces Round #671 (Div. 2) D1. Sage’s Birthday (easy version)
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1419/D1
Codeforces Round #671 (Div. 2) D1. Sage's Birthday (easy version)
This is the easy version of the problem. The difference between the
versions is that in the easy version all prices a_i are different. You can
make hacks if and only if you solved both versions of the problem.
Today is Sage's birthday, and she will go shopping to buy ice spheres. All
n ice spheres are placed in a row and they are numbered from 1 to n from
left to right. Each ice sphere has a positive integer price. In this
version all prices are different.
An ice sphere is cheap if it costs strictly less than two neighboring ice
spheres: the nearest to the left and the nearest to the right. The
leftmost and the rightmost ice spheres are not cheap. Sage will choose all
cheap ice spheres and then buy only them.
You can visit the shop before Sage and reorder the ice spheres as you
wish. Find out the maximum number of ice spheres that Sage can buy, and
show how the ice spheres should be reordered.
*/
#define MAXN 100010
ll a[MAXN];
void run(){
int n;scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%lld",&a[i]);
sort(a,a+n);
int k=n/2;
if(n%2)printf("%d\n",k);
else printf("%d\n",k-1);
for(int i=0;i<k;i++){
printf("%lld %lld%c",a[k+i],a[i]," \n"[k+i==n-1]);
}
if(n%2)printf("%lld\n",a[n-1]);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
15. Educational Codeforces Round 96 (Rated for Div. 2) C. Numbers on Whiteboard
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1430/C
Educational Codeforces Round 96 (Rated for Div. 2) C. Numbers on Whiteboard
Numbers 1, 2, 3, \dots n (each integer from 1 to n once) are written on a
board. In one operation you can erase any two numbers a and b from the
board and write one integer \frac{a + b}{2} rounded up instead.
You should perform the given operation n - 1 times and make the resulting
number that will be left on the board as small as possible.
For example, if n = 4, the following course of action is optimal:
choose a = 4 and b = 2, so the new number is 3, and the whiteboard
contains [1, 3, 3];
choose a = 3 and b = 3, so the new number is 3, and the whiteboard
contains [1, 3];
choose a = 1 and b = 3, so the new number is 2, and the whiteboard
contains [2].
It's easy to see that after n - 1 operations, there will be left only one
number. Your goal is to minimize it.
*/
void run(){
int n;scanf("%d",&n);
int res=n;
vector<string> ans;
for(int i=n-1;i>=1;i--){
ans.push_back(to_string(res)+" "+to_string(i));
res=(res+i+1)/2;
}
printf("%d\n",res);
for(const auto& s:ans)cout<<s<<endl;
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
16. Codeforces Round #356 (Div. 2) B. Bear and Finding Criminals
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/680/B
Codeforces Round #356 (Div. 2) B. Bear and Finding Criminals
There are n cities in Bearland, numbered 1 through n. Cities are arranged
in one long row. The distance between cities i and j is equal to |i - j|.
Limak is a police officer. He lives in a city a. His job is to catch
criminals. It's hard because he doesn't know in which cities criminals
are. Though, he knows that there is at most one criminal in each city.
Limak is going to use a BCD (Bear Criminal Detector). The BCD will tell
Limak how many criminals there are for every distance from a city a. After
that, Limak can catch a criminal in each city for which he is sure that
there must be a criminal.
You know in which cities criminals are. Count the number of criminals
Limak will catch, after he uses the BCD.
*/
#define MAXN 200
int a[MAXN];
void run(){
int n,b;scanf("%d%d",&n,&b);
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
int res=0;
for(int i=0;;i++){
if(b+i>n&&b-i<1)break;
if(b-i<1&&a[b+i]==1)res++;
if(b+i>n&&a[b-i]==1)res++;
if(b-i>=1&&b+i<=n&&a[b+i]==a[b-i])res+=a[b+i]+(i==0?0:a[b+i]);
}
printf("%d\n",res);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
17. Codeforces Round #668 (Div. 2) B. Array Cancellation
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1405/B
Codeforces Round #668 (Div. 2) B. Array Cancellation
You're given an array a of n integers, such that a_1 + a_2 + \cdots + a_n
= 0.
In one operation, you can choose two different indices i and j (1 \le i, j
\le n), decrement a_i by one and increment a_j by one. If i < j this
operation is free, otherwise it costs one coin.
How many coins do you have to spend in order to make all elements equal to
0?
*/
#define MAXN 100100
ll a[MAXN];
void run(){
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
ll neg=0,res=0;
for(int i=n;i>=1;i--){
neg+=a[i];
if(neg>0){
res+=neg;
neg=0;
}
}
printf("%lld\n",res);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
18. CodeCraft-22 and Codeforces Round #795 (Div. 2) B. Shoe Shuffling
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1691/B
CodeCraft-22 and Codeforces Round #795 (Div. 2) B. Shoe Shuffling
A class of students got bored wearing the same pair of shoes every day, so
they decided to shuffle their shoes among themselves. In this problem, a
pair of shoes is inseparable and is considered as a single object.
There are n students in the class, and you are given an array s in
non-decreasing order, where s_i is the shoe size of the i-th student. A
shuffling of shoes is valid only if no student gets their own shoes and if
every student gets shoes of size greater than or equal to their size.
You have to output a permutation p of \{1,2,\ldots,n\} denoting a valid
shuffling of shoes, where the i-th student gets the shoes of the p_i-th
student (p_i \ne i). And output -1 if a valid shuffling does not exist.
A permutation is an array consisting of n distinct integers from 1 to n in
arbitrary order. For example, [2,3,1,5,4] is a permutation, but [1,2,2] is
not a permutation (2 appears twice in the array) and [1,3,4] is also not a
permutation (n=3 but there is 4 in the array).
*/
#define MAXN 100010
ll a[MAXN];
void run(){
int n;scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
vector<ll> res;
for(int i=1;i<=n;i++){
int j=i;
while(j<=n&&a[j]==a[i])j++;
if(j==i+1){
printf("-1\n");
return;
}
res.push_back(j-1);
for(int k=i;k<j-1;k++)res.push_back(k);
i=j-1;
}
for(const auto& x:res)printf("%lld ",x);
printf("\n");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
19. Codeforces Round #744 (Div. 3) E1. Permutation Minimization by Deque
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1579/E1
Codeforces Round #744 (Div. 3) E1. Permutation Minimization by Deque
In fact, the problems E1 and E2 do not have much in common. You should
probably think of them as two separate problems.
A permutation p of size n is given. A permutation of size n is an array of
size n in which each integer from 1 to n occurs exactly once. For example,
[1, 4, 3, 2] and [4, 2, 1, 3] are correct permutations while [1, 2, 4] and
[1, 2, 2] are not.
Let us consider an empty <a href="https://tinyurl.com/pfeucbux">deque
(double-ended queue). A deque is a data structure that supports adding
elements to both the beginning and the end. So, if there are elements [1,
5, 2] currently in the deque, adding an element 4 to the beginning will
produce the sequence [\color{red}{4}, 1, 5, 2], and adding same element to
the end will produce [1, 5, 2, \color{red}{4}].
The elements of the permutation are sequentially added to the initially
empty deque, starting with p_1 and finishing with p_n. Before adding each
element to the deque, you may choose whether to add it to the beginning or
the end.
For example, if we consider a permutation p = [3, 1, 2, 4], one of the
possible sequences of actions looks like this: <table
class="tex-tabular"><td class="tex-tabular-text-align-left">\quad 1.
<td class="tex-tabular-text-align-left">add 3 to the end of the deque:
<td class="tex-tabular-text-align-left">deque has a sequence
[\color{red}{3}] in it;
<td class="tex-tabular-text-align-left">\quad 2.
<td class="tex-tabular-text-align-left">add 1 to the beginning of the
deque:
<td class="tex-tabular-text-align-left">deque has a sequence
[\color{red}{1}, 3] in it;
<td class="tex-tabular-text-align-left">\quad 3.
<td class="tex-tabular-text-align-left">add 2 to the end of the deque:
<td class="tex-tabular-text-align-left">deque has a sequence [1, 3,
\color{red}{2}] in it;
<td class="tex-tabular-text-align-left">\quad 4.
<td class="tex-tabular-text-align-left">add 4 to the end of the deque:
<td class="tex-tabular-text-align-left">deque has a sequence [1, 3, 2,
\color{red}{4}] in it;
Find the lexicographically smallest possible sequence of elements in the
deque after the entire permutation has been processed.
A sequence [x_1, x_2, \ldots, x_n] is lexicographically smaller than the
sequence [y_1, y_2, \ldots, y_n] if there exists such i \leq n that x_1 =
y_1, x_2 = y_2, \ldots, x_{i - 1} = y_{i - 1} and x_i < y_i. In other
words, if the sequences x and y have some (possibly empty) matching
prefix, and the next element of the sequence x is strictly smaller than
the corresponding element of the sequence y. For example, the sequence [1,
3, 2, 4] is smaller than the sequence [1, 3, 4, 2] because after the two
matching elements [1, 3] in the start the first sequence has an element 2
which is smaller than the corresponding element 4 in the second sequence.
*/
#define MAXN 200202
int a[MAXN];
void run(){
int n;scanf("%d",&n);
deque<int> q;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
if(i==0)q.push_back(a[i]);
else{
if(a[i]<q.front())q.push_front(a[i]);
else q.push_back(a[i]);
}
}
for(const auto& x:q)printf("%d ",x);
printf("\n");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
20. Codeforces Round #812 (Div. 2) B. Optimal Reduction
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1713/B
Codeforces Round #812 (Div. 2) B. Optimal Reduction
Consider an array a of n positive integers.
You may perform the following operation:
select two indices l and r (1 \leq l \leq r \leq n), then
decrease all elements a_l, a_{l + 1}, \dots, a_r by 1.
Let's call f(a) the minimum number of operations needed to change array a
into an array of n zeros.
Determine if for all permutations^\dagger b of a, f(a) \leq f(b) is true.
^\dagger An array b is a permutation of an array a if b consists of the
elements of a in arbitrary order. For example, [4,2,3,4] is a permutation
of [3,2,4,4] while [1,2,2] is not a permutation of [1,2,3].
*/
#define MAXN 100101
ll a[MAXN];
void run(){
int n;scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
}
int pre=0;
while(pre+1<n&&a[pre+1]>=a[pre])pre++;
int suf=0;
while(n-2-suf>=0&&a[n-2-suf]>=a[n-1-suf])suf++;
if(pre+suf>=n-1)printf("YES\n");
else printf("NO\n");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
21. Codeforces Round #769 (Div. 2) B. Roof Construction
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1632/B
Codeforces Round #769 (Div. 2) B. Roof Construction
It has finally been decided to build a roof over the football field in
School 179. Its construction will require placing n consecutive vertical
pillars. Furthermore, the headmaster wants the heights of all the pillars
to form a permutation p of integers from 0 to n - 1, where p_i is the
height of the i-th pillar from the left (1 \le i \le n).
As the chief, you know that the cost of construction of consecutive
pillars is equal to the maximum value of the bitwise XOR of heights of all
pairs of adjacent pillars. In other words, the cost of construction is
equal to \max\limits_{1 \le i \le n - 1}{p_i \oplus p_{i + 1}}, where
\oplus denotes the <a
href="https://en.wikipedia.org/wiki/Bitwise_operation#XOR">bitwise XOR
operation.
Find any sequence of pillar heights p of length n with the smallest
construction cost.
In this problem, a permutation is an array consisting of n distinct
integers from 0 to n - 1 in arbitrary order. For example, [2,3,1,0,4] is a
permutation, but [1,0,1] is not a permutation (1 appears twice in the
array) and [1,0,3] is also not a permutation (n=3, but 3 is in the array).
*/
void run(){
int n;scanf("%d",&n);
int lz=__builtin_clz(n-1);
int mx=1<<(31-lz);
for(int i=1;i<mx;i++)printf("%d ",i);
printf("0 %d ",mx);
for(int i=mx+1;i<n;i++)printf("%d ",i);
printf("\n");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
22. Codeforces Round #410 (Div. 2) A. Mike and palindrome
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/798/A
Codeforces Round #410 (Div. 2) A. Mike and palindrome
Mike has a string s consisting of only lowercase English letters. He wants
to change exactly one character from the string so that the resulting one
is a palindrome.
A palindrome is a string that reads the same backward as forward, for
example strings "z", "aaa", "aba", "abccba" are palindromes, but strings
"codeforces", "reality", "ab" are not.
*/
void run(){
string s;cin>>s;
int n=s.length();
int cnt=0;
for(int i=0;i<n/2;i++)if(s[i]!=s[n-1-i])cnt++;
if(cnt==1||(cnt==0&&n%2))cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
23. Codeforces Round #741 (Div. 2) B. Scenes From a Memory
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1562/B
Codeforces Round #741 (Div. 2) B. Scenes From a Memory
During the hypnosis session, Nicholas suddenly remembered a positive
integer n, which doesn't contain zeros in decimal notation.
Soon, when he returned home, he got curious: what is the maximum number of
digits that can be removed from the number so that the number becomes not
prime, that is, either composite or equal to one?
For some numbers doing so is impossible: for example, for number 53 it's
impossible to delete some of its digits to obtain a not prime integer.
However, for all n in the test cases of this problem, it's guaranteed that
it's possible to delete some of their digits to obtain a not prime number.
Note that you cannot remove all the digits from the number.
A prime number is a number that has no divisors except one and itself. A
composite is a number that has more than two divisors. 1 is neither a
prime nor a composite number.
*/
bool isp[200];
void init(){
memset(isp,true,sizeof(isp));
isp[0]=isp[1]=false;
for(int i=2;i<200;i++)if(isp[i])for(int j=i*i;j<200;j+=i)isp[j]=false;
}
void run(){
int n;scanf("%d",&n);
string s;cin>>s;
vector<int> a;
int pcnt=0;
for(int i=0;i<n;i++){
a.push_back(s[i]-'0');
if(!isp[a[i]]){
printf("1\n%d\n",a[i]);
return;
}
}
for(int i=0;i<n;i++)
for(int j=i+1;j<n;j++){
int x=a[i]*10+a[j];
if(!isp[x]){
printf("2\n%d\n",x);
return;
}
}
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
init();
int T;scanf("%d",&T);
while(T--){
run();
}
}
24. Codeforces Round #839 (Div. 3) C. Different Differences
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1772/C
Codeforces Round #839 (Div. 3) C. Different Differences
An array a consisting of k integers is strictly increasing if a_1 < a_2
< \dots < a_k. For example, the arrays [1, 3, 5], [1, 2, 3, 4], [3,
5, 6] are strictly increasing; the arrays [2, 2], [3, 7, 5], [7, 4, 3],
[1, 2, 2, 3] are not.
For a strictly increasing array a of k elements, let's denote the
characteristic as the number of different elements in the array [a_2 -
a_1, a_3 - a_2, \dots, a_k - a_{k-1}]. For example, the characteristic of
the array [1, 3, 4, 7, 8] is 3 since the array [2, 1, 3, 1] contains 3
different elements: 2, 1 and 3.
You are given two integers k and n (k \le n). Construct an increasing
array of k integers from 1 to n with maximum possible characteristic.
*/
void run(){
int k,n;scanf("%d%d",&k,&n);
int x=1,cnt=0;
int d=1;
while(true){
if(n-x>=k-cnt-1){
printf("%d ",x);
}else{
for(int i=cnt;i<k;i++)printf("%d ",x-d+2+i-cnt);
printf("\n");
return;
}
cnt++;
if(cnt>=k)break;
x+=d;d++;
}
printf("\n");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
25. Codeforces Round #816 (Div. 2) B. Beautiful Array
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1715/B
Codeforces Round #816 (Div. 2) B. Beautiful Array
Stanley defines the beauty of an array a of length n, which contains
non-negative integers, as follows: \sum\limits_{i = 1}^{n} \left \lfloor
\frac{a_{i}}{k} \right \rfloor, which means that we divide each element by
k, round it down, and sum up the resulting values.
Stanley told Sam the integer k and asked him to find an array a of n
non-negative integers, such that the beauty is equal to b and the sum of
elements is equal to s. Help Sam — find any of the arrays satisfying the
conditions above.
*/
void run(){
ll n,k,b,s;
scanf("%lld%lld%lld%lld",&n,&k,&b,&s);
// [kb,kb+n*(k-1)]
ll mi=k*b;
ll mx=mi+n*(k-1);
if(s<mi||s>mx){
printf("-1\n");
return;
}
ll r=s-mi;
ll base=r/n;
ll rem=r%n;
for(int i=0;i<rem;i++)printf("%lld ",base+1);
for(int i=rem;i<n-1;i++)printf("%lld ",base);
printf("%lld\n",base+mi);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
26. Codeforces Round #682 (Div. 2) B. Valerii Against Everyone
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1438/B
Codeforces Round #682 (Div. 2) B. Valerii Against Everyone
You're given an array b of length n. Let's define another array a, also of
length n, for which a_i = 2^{b_i} (1 \leq i \leq n).
Valerii says that every two non-intersecting subarrays of a have different
sums of elements. You want to determine if he is wrong. More formally, you
need to determine if there exist four integers l_1,r_1,l_2,r_2 that
satisfy the following conditions:
1 \leq l_1 \leq r_1 \lt l_2 \leq r_2 \leq n;
a_{l_1}+a_{l_1+1}+\ldots+a_{r_1-1}+a_{r_1} =
a_{l_2}+a_{l_2+1}+\ldots+a_{r_2-1}+a_{r_2}.
If such four integers exist, you will prove Valerii wrong. Do they exist?
An array c is a subarray of an array d if c can be obtained from d by
deletion of several (possibly, zero or all) elements from the beginning
and several (possibly, zero or all) elements from the end.
*/
#define MAXN 1101
ll b[MAXN];
void run(){
int n;scanf("%d",&n);
unordered_map<ll,int> mp;
bool res=false;
for(int i=0;i<n;i++){
scanf("%lld",&b[i]);
if(mp.find(b[i])!=mp.end()){
res=true;
}
mp[b[i]]=1;
}
if(res)printf("YES\n");
else printf("NO\n");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
27. Codeforces Round #770 (Div. 2) C. OKEA
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1634/C
Codeforces Round #770 (Div. 2) C. OKEA
<div class="epigraph"><div class="epigraph-text">People worry that
computers will get too smart and take over the world, but the real problem
is that they're too stupid and they've already taken over the world.
<div class="epigraph-source">— Pedro Domingos
You work for a well-known department store that uses leading technologies
and employs mechanistic work — that is, robots!
The department you work in sells n \cdot k items. The first item costs 1
dollar, the second item costs 2 dollars, and so on: i-th item costs i
dollars. The items are situated on shelves. The items form a rectangular
grid: there are n shelves in total, and each shelf contains exactly k
items. We will denote by a_{i,j} the price of j-th item (counting from the
left) on the i-th shelf, 1 \le i \le n, 1 \le j \le k.
Occasionally robots get curious and ponder on the following question: what
is the mean price (arithmetic average) of items a_{i,l}, a_{i,l+1},
\ldots, a_{i,r} for some shelf i and indices l \le r? Unfortunately, the
old robots can only work with whole numbers. If the mean price turns out
not to be an integer, they break down.
You care about robots' welfare. You want to arrange the items in such a
way that the robots cannot theoretically break. Formally, you want to
choose such a two-dimensional array a that:
Every number from 1 to n \cdot k (inclusively) occurs exactly once.
For each i, l, r, the mean price of items from l to r on i-th shelf is an
integer.
Find out if such an arrangement is possible, and if it is, give any
example of such arrangement.
*/
void run(){
int n,k;scanf("%d%d",&n,&k);
if(k==1){
printf("YES\n");
for(int i=1;i<=n;i++)printf("%d\n",i);
return;
}
if(n%2){
printf("NO\n");
return;
}
printf("YES\n");
for(int i=1;i<=n;i++){
for(int j=0;j<k;j++){
printf("%d%c",i+j*n," \n"[j==k-1]);
}
}
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
28. Good Bye 2022: 2023 is NEAR B. Koxia and Permutation
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1770/B
Good Bye 2022: 2023 is NEAR B. Koxia and Permutation
Reve has two integers n and k.
Let p be a permutation^\dagger of length n. Let c be an array of length n
- k + 1 such that c_i = \max(p_i, \dots, p_{i+k-1}) + \min(p_i, \dots,
p_{i+k-1}). Let the cost of the permutation p be the maximum element of c.
Koxia wants you to construct a permutation with the minimum possible cost.
^\dagger A permutation of length n is an array consisting of n distinct
integers from 1 to n in arbitrary order. For example, [2,3,1,5,4] is a
permutation, but [1,2,2] is not a permutation (2 appears twice in the
array), and [1,3,4] is also not a permutation (n=3 but there is 4 in the
array).
*/
void run(){
int n,k;scanf("%d%d",&n,&k);
int l=1,r=n;bool flag=true;
while(l<=r){
printf("%d ",flag==true?r--:l++);
flag=!flag;
}
printf("\n");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
29. Codeforces Round #756 (Div. 3) C. Polycarp Recovers the Permutation
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1611/C
Codeforces Round #756 (Div. 3) C. Polycarp Recovers the Permutation
Polycarp wrote on a whiteboard an array p of length n, which is a
permutation of numbers from 1 to n. In other words, in p each number from
1 to n occurs exactly once.
He also prepared a resulting array a, which is initially empty (that is,
it has a length of 0).
After that, he did exactly n steps. Each step looked like this:
Look at the leftmost and rightmost elements of p, and pick the smaller of
the two.
If you picked the leftmost element of p, append it to the left of a;
otherwise, if you picked the rightmost element of p, append it to the
right of a.
The picked element is erased from p.
Note that on the last step, p has a length of 1 and its minimum element is
both leftmost and rightmost. In this case, Polycarp can choose what role
the minimum element plays. In other words, this element can be added to a
both on the left and on the right (at the discretion of Polycarp).
Let's look at an example. Let n=4, p=[3, 1, 4, 2]. Initially a=[]. Then:
During the first step, the minimum is on the right (with a value of 2),
so after this step, p=[3,1,4] and a=[2] (he added the value 2 to the
right).
During the second step, the minimum is on the left (with a value of 3),
so after this step, p=[1,4] and a=[3,2] (he added the value 3 to the
left).
During the third step, the minimum is on the left (with a value of 1), so
after this step, p=[4] and a=[1,3,2] (he added the value 1 to the left).
During the fourth step, the minimum is both left and right (this value is
4). Let's say Polycarp chose the right option. After this step, p=[] and
a=[1,3,2,4] (he added the value 4 to the right).
Thus, a possible value of a after n steps could be a=[1,3,2,4].
You are given the final value of the resulting array a. Find any possible
initial value for p that can result the given a, or determine that there
is no solution.
*/
#define MAXN 200200
int a[MAXN];
void run(){
int n;scanf("%d",&n);
for(int i=0;i<n;i++)scanf("%d",&a[i]);
if(a[0]!=n&&a[n-1]!=n){
printf("-1\n");
return;
}
for(int i=n-1;i>=0;i--)printf("%d%c",a[i]," \n"[i==0]);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
30. Codeforces Round #757 (Div. 2) B. Divan and a New Project
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1614/B
Codeforces Round #757 (Div. 2) B. Divan and a New Project
The company "Divan's Sofas" is planning to build n + 1 different buildings
on a coordinate line so that:
the coordinate of each building is an integer number;
no two buildings stand at the same point.
Let x_i be the coordinate of the i-th building. To get from the building i
to the building j, Divan spends |x_i - x_j| minutes, where |y| is the
absolute value of y.
All buildings that Divan is going to build can be numbered from 0 to n.
The businessman will live in the building 0, the new headquarters of
"Divan's Sofas". In the first ten years after construction Divan will
visit the i-th building a_i times, each time spending 2 \cdot |x_0-x_i|
minutes for walking.
Divan asks you to choose the coordinates for all n + 1 buildings so that
over the next ten years the businessman will spend as little time for
walking as possible.
*/
void run(){
int n;scanf("%d",&n);
vector<pair<int,int>> a;
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);
a.push_back({-x,i});
}
sort(a.begin(),a.end());
vector<int> res(n+1,0);
int cnt=1;
ll ans=0;
for(int i=0;i<n;i++){
res[a[i].second]=cnt;
ans+=2ll*abs(cnt)*(-a[i].first);
if(cnt<0)cnt=-cnt+1;
else cnt=-cnt;
}
printf("%lld\n",ans);
for(int i=0;i<=n;i++)printf("%d%c",res[i]," \n"[i==n]);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
31. Codeforces Global Round 16 C. MAX-MEX Cut
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1566/C
Codeforces Global Round 16 C. MAX-MEX Cut
A binary string is a string that consists of characters 0 and 1. A
bi-table is a table that has exactly two rows of equal length, each being
a binary string.
Let \operatorname{MEX} of a bi-table be the smallest digit among 0, 1, or
2 that does not occur in the bi-table. For example, \operatorname{MEX} for
\begin{bmatrix} 0011\\ 1010 \end{bmatrix} is 2, because 0 and 1 occur in
the bi-table at least once. \operatorname{MEX} for \begin{bmatrix} 111\\
111 \end{bmatrix} is 0, because 0 and 2 do not occur in the bi-table, and
0 < 2.
You are given a bi-table with n columns. You should cut it into any number
of bi-tables (each consisting of consecutive columns) so that each column
is in exactly one bi-table. It is possible to cut the bi-table into a
single bi-table — the whole bi-table.
What is the maximal sum of \operatorname{MEX} of all resulting bi-tables
can be?
*/
int solve(const string& s){
int res=count(s.begin(),s.end(),'0');
bool x=false,y=false;
for(const auto& c:s){
if(c=='0')x=true;
if(c=='1')y=true;
if(x&&y){
res++;
x=false;y=false;
}
}
return res;
}
void run(){
int n;cin>>n;
string s,t;cin>>s>>t;
int res=0;
string k;
for(int i=0;i<n;i++){
if(s[i]!=t[i]){
res+=2;
res+=solve(k);
k="";
}else k+=s[i];
}
cout<<res+solve(k)<<"\n";
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
cin.tie(0);cout.tie(0);
ios_base::sync_with_stdio(false);
int T;cin>>T;
while(T--){
run();
}
}
32. Codeforces Round #563 (Div. 2) A. Ehab Fails to Be Thanos
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1174/A
Codeforces Round #563 (Div. 2) A. Ehab Fails to Be Thanos
You're given an array a of length 2n. Is it possible to reorder it in such
way so that the sum of the first n elements isn't equal to the sum of the
last n elements?
*/
#define MAXN 3030
int a[MAXN];
void run(){
int n;scanf("%d",&n);
for(int i=0;i<2*n;i++)scanf("%d",&a[i]);
sort(a,a+2*n);
if(accumulate(a,a+n,0)==accumulate(a+n,a+2*n,0)){printf("-1\n");return;}
for(int i=0;i<2*n;i++)printf("%d%c",a[i]," \n"[i==2*n-1]);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
33. Codeforces Round #352 (Div. 2) B. Different is Good
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/672/B
Codeforces Round #352 (Div. 2) B. Different is Good
A wise man told Kerem "Different is good" once, so Kerem wants all things
in his life to be different.
Kerem recently got a string s consisting of lowercase English letters.
Since Kerem likes it when things are different, he wants all substrings of
his string s to be distinct. Substring is a string formed by some number
of consecutive characters of the string. For example, string "aba" has
substrings "" (empty substring), "a", "b", "a", "ab", "ba", "aba".
If string s has at least two equal substrings then Kerem will change
characters at some positions to some other lowercase English letters.
Changing characters is a very tiring job, so Kerem want to perform as few
changes as possible.
Your task is to find the minimum number of changes needed to make all the
substrings of the given string distinct, or determine that it is
impossible.
*/
void run(){
int n;string s;
cin>>n>>s;
unordered_map<char,int> mp;
for(const auto& c:s)mp[c]++;
int res=0;
for(const auto&[k,v]:mp)res+=v-1;
if(mp.size()+res>26){
printf("-1\n");
return;
}
printf("%d\n",res);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
34. Codeforces Round #782 (Div. 2) A. Red Versus Blue
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1659/A
Codeforces Round #782 (Div. 2) A. Red Versus Blue
Team Red and Team Blue competed in a competitive FPS. Their match was
streamed around the world. They played a series of n matches.
In the end, it turned out Team Red won r times and Team Blue won b times.
Team Blue was less skilled than Team Red, so b was strictly less than r.
You missed the stream since you overslept, but you think that the match
must have been neck and neck since so many people watched it. So you
imagine a string of length n where the i-th character denotes who won the
i-th match — it is R if Team Red won or B if Team Blue won. You imagine
the string was such that the maximum number of times a team won in a row
was as small as possible. For example, in the series of matches RBBRRRB,
Team Red won 3 times in a row, which is the maximum.
You must find a string satisfying the above conditions. If there are
multiple answers, print any.
*/
void run(){
int n,r,b;scanf("%d%d%d",&n,&r,&b);
int base=r/(b+1);
int rem=r%(b+1);
for(int i=0;i<b+1;i++){
if(i<rem)printf("R");
for(int j=0;j<base;j++)printf("R");
if(i<b)printf("B");
}
printf("\n");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
35. Codeforces Round #411 (Div. 2) B. 3-palindrome
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/805/B
Codeforces Round #411 (Div. 2) B. 3-palindrome
In the beginning of the new year Keivan decided to reverse his name. He
doesn't like palindromes, so he changed Naviek to Navick.
He is too selfish, so for a given n he wants to obtain a string of n
characters, each of which is either 'a', 'b' or 'c', with no palindromes
of length 3 appearing in the string as a substring. For example, the
strings "abc" and "abca" suit him, while the string "aba" doesn't. He also
want the number of letters 'c' in his string to be as little as possible.
*/
void run(){
int n;scanf("%d",&n);
for(int i=0;i<n;i++){
int k=i%4;
if(k<2)printf("b");
else printf("a");
}
printf("\n");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
36. Codeforces Round #411 (Div. 1) A. Find Amir
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/804/A
Codeforces Round #411 (Div. 1) A. Find Amir
A few years ago Sajjad left his school and register to another one due to
security reasons. Now he wishes to find Amir, one of his schoolmates and
good friends.
There are n schools numerated from 1 to n. One can travel between each
pair of them, to do so, he needs to buy a ticket. The ticker between
schools i and j costs <img align="middle" class="tex-formula"
src="https://espresso.codeforces.com/48a4e5770c4d95918ab20e59965b1361f52acc
70.png" style="max-width: 100.0%;max-height: 100.0%;" /> and can be used
multiple times. Help Sajjad to find the minimum cost he needs to pay for
tickets to visit all schools. He can start and finish in any school.
*/
void run(){
int n;scanf("%d",&n);
printf("%d\n",(n-1)/2);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
37. Codeforces Round #604 (Div. 2) A. Beautiful String
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1265/A
Codeforces Round #604 (Div. 2) A. Beautiful String
A string is called beautiful if no two consecutive characters are equal.
For example, "ababcb", "a" and "abab" are beautiful strings, while
"aaaaaa", "abaa" and "bb" are not.
Ahcl wants to construct a beautiful string. He has a string s, consisting
of only characters 'a', 'b', 'c' and '?'. Ahcl needs to replace each
character '?' with one of the three characters 'a', 'b' or 'c', such that
the resulting string is beautiful. Please help him!
More formally, after replacing all characters '?', the condition s_i \neq
s_{i+1} should be satisfied for all 1 \leq i \leq |s| - 1, where |s| is
the length of the string s.
*/
void run(){
string s;cin>>s;
int n=s.length();
for(int i=0;i<n-1;i++){
if(s[i]!='?'&&s[i]==s[i+1]){
printf("-1\n");
return;
}
}
int pre=0;
for(int i=0;i<n;i++){
if(s[i]!='?'){
pre=s[i]-'a';
continue;
}
pre=(pre+1)%3;
s[i]='a'+pre;
if(i+1<n&&s[i+1]==s[i]){
pre=(pre+1)%3;
s[i]='a'+pre;
}
}
cout<<s<<"\n";
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
38. Codeforces Round #550 (Div. 3) C. Two Shuffled Sequences
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1144/C
Codeforces Round #550 (Div. 3) C. Two Shuffled Sequences
Two integer sequences existed initially — one of them was strictly
increasing, and the other one — strictly decreasing.
Strictly increasing sequence is a sequence of integers [x_1 < x_2 <
\dots < x_k]. And strictly decreasing sequence is a sequence of
integers [y_1 > y_2 > \dots > y_l]. Note that the empty sequence and the
sequence consisting of one element can be considered as increasing or
decreasing.
They were merged into one sequence a. After that sequence a got shuffled.
For example, some of the possible resulting sequences a for an increasing
sequence [1, 3, 4] and a decreasing sequence [10, 4, 2] are sequences [1,
2, 3, 4, 4, 10] or [4, 2, 1, 10, 4, 3].
This shuffled sequence a is given in the input.
Your task is to find any two suitable initial sequences. One of them
should be strictly increasing and the other one — strictly decreasing.
Note that the empty sequence and the sequence consisting of one element
can be considered as increasing or decreasing.
If there is a contradiction in the input and it is impossible to split the
given sequence a to increasing and decreasing sequences, print "NO".
*/
#define MAXN 200202
int a[MAXN];
void run(){
int n;scanf("%d",&n);
unordered_map<int,int> mp;
bool flag=false;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
mp[a[i]]++;
if(mp[a[i]]>=3)flag=true;
}
if(flag){
printf("NO\n");
return;
}
sort(a,a+n);
vector<int> x,y;
for(int i=0;i<n;i++){
if(i==0)x.push_back(a[i]);
else{
if(a[i]==a[i-1])y.push_back(a[i]);
else x.push_back(a[i]);
}
}
if(y.empty()){
y.push_back(x.back());
x.pop_back();
}
reverse(y.begin(),y.end());
printf("YES\n");
printf("%d\n",x.size());
for(const auto&v:x)printf("%d ",v);
printf("\n");
printf("%d\n",y.size());
for(const auto&v:y)printf("%d ",v);
printf("\n");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
39. Codeforces Round #394 (Div. 2) A. Dasha and Stairs
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/761/A
Codeforces Round #394 (Div. 2) A. Dasha and Stairs
On her way to programming school tiger Dasha faced her first test — a huge
staircase!
<img class="tex-graphics"
src="https://espresso.codeforces.com/31ae258b18250cd0831c18db6108441e9b6731
17.png" style="max-width: 100.0%;max-height: 100.0%;" />
The steps were numbered from one to infinity. As we know, tigers are very
fond of all striped things, it is possible that it has something to do
with their color. So on some interval of her way she calculated two values
— the number of steps with even and odd numbers.
You need to check whether there is an interval of steps from the l-th to
the r-th (1 ≤ l ≤ r), for which values that Dasha has found are correct.
*/
void run(){
int a,b;scanf("%d%d",&a,&b);
if(a==b&&a==0){
printf("NO\n");
return;
}
if(abs(a-b)<2)printf("YES\n");
else printf("NO\n");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
40. Codeforces Global Round 6 B. Dice Tower
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1266/B
Codeforces Global Round 6 B. Dice Tower
Bob is playing with 6-sided dice. A net of such standard cube is shown
below.
<img class="tex-graphics"
src="https://espresso.codeforces.com/0065ec3465bffc3d36eefbdb4a5cab1e259814
6d.png" style="max-width: 100.0%;max-height: 100.0%;" />
He has an unlimited supply of these dice and wants to build a tower by
stacking multiple dice on top of each other, while choosing the
orientation of each dice. Then he counts the number of visible pips on the
faces of the dice.
For example, the number of visible pips on the tower below is 29 — the
number visible on the top is 1, from the south 5 and 3, from the west 4
and 2, from the north 2 and 4 and from the east 3 and 5.
<img class="tex-graphics"
src="https://espresso.codeforces.com/8b7b0bd353a0dc7abd2f410cbb90999b99b2a2
a7.png" style="max-width: 100.0%;max-height: 100.0%;" />
The one at the bottom and the two sixes by which the dice are touching are
not visible, so they are not counted towards total.
Bob also has t favourite integers x_i, and for every such integer his goal
is to build such a tower that the number of visible pips is exactly x_i.
For each of Bob's favourite integers determine whether it is possible to
build a tower that has exactly that many visible pips.
*/
void run(){
ll x;scanf("%lld",&x);
ll y=x/14;
ll r=x%14;
if(y>=1&&(r>=1&&r<=6))printf("YES\n");
else printf("NO\n");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
41. Codeforces Round #830 (Div. 2) A. Bestie
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1732/A
Codeforces Round #830 (Div. 2) A. Bestie
You are given an array a consisting of n integers a_1, a_2, \ldots, a_n.
Friends asked you to make the <a
href="https://en.wikipedia.org/wiki/Greatest_common_divisor">greatest
common divisor (GCD)
of all numbers in the array equal to 1. In one operation, you can do the
following:
Select an arbitrary index in the array 1 \leq i \leq n;
Make a_i = \gcd(a_i, i), where \gcd(x, y) denotes the GCD of integers x
and y. The cost of such an operation is n - i + 1.
You need to find the minimum total cost of operations we need to perform
so that the GCD of the all array numbers becomes equal to 1.
*/
unordered_set<ll> mp={2,3,5,7,11,13,17,19};
void run(){
int n;scanf("%d",&n);
int res=INT_MAX;
int tot=-1;
vector<int> can;
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);
if(tot==-1)tot=x;
else tot=__gcd(tot,x);
}
if(tot==1)res=0;
else if(__gcd(tot,n)==1)res=1;
else if(__gcd(tot,n-1)==1)res=2;
else res=3;
printf("%d\n",res);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
42. Codeforces Round #546 (Div. 2) B. Nastya Is Playing Computer Games
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1136/B
Codeforces Round #546 (Div. 2) B. Nastya Is Playing Computer Games
Finished her homework, Nastya decided to play computer games. Passing
levels one by one, Nastya eventually faced a problem. Her mission is to
leave a room, where a lot of monsters live, as quickly as possible.
There are n manholes in the room which are situated on one line, but,
unfortunately, all the manholes are closed, and there is one stone on
every manhole. There is exactly one coin under every manhole, and to win
the game Nastya should pick all the coins. Initially Nastya stands near
the k-th manhole from the left. She is thinking what to do.
In one turn, Nastya can do one of the following:
if there is at least one stone on the manhole Nastya stands near, throw
exactly one stone from it onto any other manhole (yes, Nastya is strong).
go to a neighboring manhole;
if there are no stones on the manhole Nastya stays near, she can open it
and pick the coin from it. After it she must close the manhole immediately
(it doesn't require additional moves).
<img class="tex-graphics"
src="https://espresso.codeforces.com/d67a584d94f164baaa23c9f6ada7b629599b01
b9.png" style="max-width: 100.0%;max-height: 100.0%;" /> The figure
shows the intermediate state of the game. At the current position Nastya
can throw the stone to any other manhole or move left or right to the
neighboring manholes. If she were near the leftmost manhole, she could
open it (since there are no stones on it).
Nastya can leave the room when she picks all the coins. Monsters are
everywhere, so you need to compute the minimum number of moves Nastya has
to make to pick all the coins.
Note one time more that Nastya can open a manhole only when there are no
stones onto it.
*/
void run(){
int n,k;scanf("%d%d",&n,&k);
printf("%d\n",6+3*(n-2)+min(n-k,k-1));
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
43. Pinely Round 1 (Div. 1 + Div. 2) B. Elimination of a Ring
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1761/B
Pinely Round 1 (Div. 1 + Div. 2) B. Elimination of a Ring
Define a cyclic sequence of size n as an array s of length n, in which s_n
is adjacent to s_1.
Muxii has a ring represented by a cyclic sequence a of size n.
However, the ring itself hates equal adjacent elements. So if two adjacent
elements in the sequence are equal at any time, one of them will be erased
immediately. The sequence doesn't contain equal adjacent elements
initially.
Muxii can perform the following operation until the sequence becomes empty:
Choose an element in a and erase it.
For example, if ring is [1, 2, 4, 2, 3, 2], and Muxii erases element 4,
then ring would erase one of the elements equal to 2, and the ring will
become [1, 2, 3, 2].
Muxii wants to find the maximum number of operations he could perform.
Note that in a ring of size 1, its only element isn't considered adjacent
to itself (so it's not immediately erased).
*/
void run(){
int n;scanf("%d",&n);
unordered_map<int,int> mp;
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
mp[x]++;
}
if(mp.size()==2)printf("%d\n",n/2+1);
else printf("%d\n",n);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
44. Codeforces Round #401 (Div. 2) A. Shell Game
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/777/A
Codeforces Round #401 (Div. 2) A. Shell Game
Bomboslav likes to look out of the window in his room and watch lads
outside playing famous shell game. The game is played by two persons:
operator and player. Operator takes three similar opaque shells and places
a ball beneath one of them. Then he shuffles the shells by swapping some
pairs and the player has to guess the current position of the ball.
Bomboslav noticed that guys are not very inventive, so the operator always
swaps the left shell with the middle one during odd moves (first, third,
fifth, etc.) and always swaps the middle shell with the right one during
even moves (second, fourth, etc.).
Let's number shells from 0 to 2 from left to right. Thus the left shell is
assigned number 0, the middle shell is 1 and the right shell is 2.
Bomboslav has missed the moment when the ball was placed beneath the
shell, but he knows that exactly n movements were made by the operator and
the ball was under shell x at the end. Now he wonders, what was the
initial position of the ball?
*/
int a[][3]={
{0,1,2},
{1,0,2},
{1,2,0},
{2,1,0},
{2,0,1},
{0,2,1},
{0,1,2},
};
void run(){
int n,x;scanf("%d%d",&n,&x);
printf("%d\n",a[n%6][x]);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
45. Codeforces Round #493 (Div. 2) A. Balloons
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/998/A
Codeforces Round #493 (Div. 2) A. Balloons
There are quite a lot of ways to have fun with inflatable balloons. For
example, you can fill them with water and see what happens.
Grigory and Andrew have the same opinion. So, once upon a time, they went
to the shop and bought n packets with inflatable balloons, where i-th of
them has exactly a_i balloons inside.
They want to divide the balloons among themselves. In addition, there are
several conditions to hold:
Do not rip the packets (both Grigory and Andrew should get unbroken
packets);
Distribute all packets (every packet should be given to someone);
Give both Grigory and Andrew at least one packet;
To provide more fun, the total number of balloons in Grigory's packets
should not be equal to the total number of balloons in Andrew's packets.
Help them to divide the balloons or determine that it's impossible under
these conditions.
*/
#define MAXN 20
int a[MAXN];
void run(){
int n;scanf("%d",&n);
int mi=INT_MAX,idx=-1;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
if(a[i]<mi){
mi=a[i];
idx=i;
}
}
if(n==1||(n==2&&a[0]==a[1])){
printf("-1\n");
return;
}
printf("1\n%d\n",idx+1);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
46. Codeforces Round #402 (Div. 2) A. Pupils Redistribution
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/779/A
Codeforces Round #402 (Div. 2) A. Pupils Redistribution
In Berland each high school student is characterized by academic
performance — integer value between 1 and 5.
In high school 0xFF there are two groups of pupils: the group A and the
group B. Each group consists of exactly n students. An academic
performance of each student is known — integer value between 1 and 5.
The school director wants to redistribute students between groups so that
each of the two groups has the same number of students whose academic
performance is equal to 1, the same number of students whose academic
performance is 2 and so on. In other words, the purpose of the school
director is to change the composition of groups, so that for each value of
academic performance the numbers of students in both groups are equal.
To achieve this, there is a plan to produce a series of exchanges of
students between groups. During the single exchange the director selects
one student from the class A and one student of class B. After that, they
both change their groups.
Print the least number of exchanges, in order to achieve the desired equal
numbers of students for each academic performance.
*/
#define MAXN 110
int a[MAXN],b[MAXN];
void run(){
int n;scanf("%d",&n);
unordered_map<int,vector<int>> mp1;
unordered_map<int,vector<int>> mp2;
unordered_map<int,int> exp;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
mp1[a[i]].push_back(i);
exp[a[i]]++;
}
for(int i=0;i<n;i++){
scanf("%d",&b[i]);
mp2[b[i]].push_back(i);
exp[b[i]]++;
}
bool flag=false;
for(const auto&[k,v]:exp){
if(v%2){
flag=true;
break;
}
exp[k]=v/2;
}
if(flag){
printf("-1\n");
return;
}
int res=0;
for(const auto&[k,v]:mp1){
int sz=v.size();
if(exp[k]<sz)res+=sz-exp[k];
}
printf("%d\n",res);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
47. Codeforces Round #209 (Div. 2) A. Table
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/359/A
Codeforces Round #209 (Div. 2) A. Table
Simon has a rectangular table consisting of n rows and m columns. Simon
numbered the rows of the table from top to bottom starting from one and
the columns — from left to right starting from one. We'll represent the
cell on the x-th row and the y-th column as a pair of numbers (x, y). The
table corners are cells: (1, 1), (n, 1), (1, m), (n, m).
Simon thinks that some cells in this table are good. Besides, it's known
that no good cell is the corner of the table.
Initially, all cells of the table are colorless. Simon wants to color all
cells of his table. In one move, he can choose any good cell of table
(x_1, y_1), an arbitrary corner of the table (x_2, y_2) and color all
cells of the table (p, q), which meet both inequations: min(x_1, x_2) ≤ p
≤ max(x_1, x_2), min(y_1, y_2) ≤ q ≤ max(y_1, y_2).
Help Simon! Find the minimum number of operations needed to color all
cells of the table. Note that you can color one cell multiple times.
*/
#define MAXN 100
int a[MAXN][MAXN];
void run(){
int n,m;scanf("%d%d",&n,&m);
bool flag=false;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
scanf("%d",&a[i][j]);
if(a[i][j]){
if(i==0||i==n-1||j==0||j==m-1)flag=true;
}
}
}
if(flag)printf("2\n");
else printf("4\n");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
// int T;scanf("%d",&T);
// while(T--){
run();
// }
}
48. VK Cup 2016 - Qualification Round 1 A. Voting for Photos
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/637/A
VK Cup 2016 - Qualification Round 1 A. Voting for Photos
After celebrating the midcourse the students of one of the faculties of
the Berland State University decided to conduct a vote for the best photo.
They published the photos in the social network and agreed on the rules to
choose a winner: the photo which gets most likes wins. If multiple photoes
get most likes, the winner is the photo that gets this number first.
Help guys determine the winner photo by the records of likes.
*/
void run(){
int n;scanf("%d",&n);
int mx=0,idx=-1;
unordered_map<int,int> mp;
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);
mp[x]++;
if(mp[x]>mx){
mx=mp[x];
idx=x;
}
}
printf("%d\n",idx);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
49. CROC 2016 - Qualification A. Parliament of Berland
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/644/A
CROC 2016 - Qualification A. Parliament of Berland
There are n parliamentarians in Berland. They are numbered with integers
from 1 to n. It happened that all parliamentarians with odd indices are
Democrats and all parliamentarians with even indices are Republicans.
New parliament assembly hall is a rectangle consisting of a × b chairs — a
rows of b chairs each. Two chairs are considered neighbouring if they
share as side. For example, chair number 5 in row number 2 is neighbouring
to chairs number 4 and 6 in this row and chairs with number 5 in rows 1
and 3. Thus, chairs have four neighbours in general, except for the chairs
on the border of the hall
We know that if two parliamentarians from one political party (that is two
Democrats or two Republicans) seat nearby they spent all time discussing
internal party issues.
Write the program that given the number of parliamentarians and the sizes
of the hall determine if there is a way to find a seat for any
parliamentarian, such that no two members of the same party share
neighbouring seats.
*/
void run(){
int n,a,b;scanf("%d%d%d",&n,&a,&b);
if(a*b<n){
printf("-1\n");
return;
}
vector<vector<int>> v(a+1,vector<int>(b+1,0));
int odd=1,even=2,cnt=0;;
for(int i=1;i<=a;i++){
for(int j=1;j<=b;j++){
if(cnt<n){
if(i%2==j%2){
if(odd<=n){
v[i][j]=odd;
odd+=2;
cnt++;
}
}else{
if(even<=n){
v[i][j]=even;
even+=2;
cnt++;
}
}
}
printf("%d%c",v[i][j]," \n"[j==b]);
}
}
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
50. Testing Round #11 A. Up the hill
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/491/A
Testing Round #11 A. Up the hill
Hiking club "Up the hill" just returned from a walk. Now they are trying
to remember which hills they've just walked through.
It is known that there were N stops, all on different integer heights
between 1 and N kilometers (inclusive) above the sea level. On the first
day they've traveled from the first stop to the second stop, on the second
day they've traveled from the second to the third and so on, and on the
last day they've traveled from the stop N - 1 to the stop N and
successfully finished their expedition.
They are trying to find out which heights were their stops located at.
They have an entry in a travel journal specifying how many days did they
travel up the hill, and how many days did they walk down the hill.
Help them by suggesting some possible stop heights satisfying numbers from
the travel journal.
*/
void run(){
int a,b;scanf("%d%d",&a,&b);
int n=a+b+1;
vector<int> v;
for(int i=1;i<=n;i++)v.push_back(i);
reverse(v.begin()+a,v.end());
for(int i=0;i<n;i++)printf("%d%c",v[i]," \n"[i==n-1]);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
51. Codeforces Round #267 (Div. 2) B. Fedor and New Game
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/467/B
Codeforces Round #267 (Div. 2) B. Fedor and New Game
After you had helped George and Alex to move in the dorm, they went to
help their friend Fedor play a new computer game «Call of Soldiers 3».
The game has (m + 1) players and n types of soldiers in total. Players
«Call of Soldiers 3» are numbered form 1 to (m + 1). Types of soldiers are
numbered from 0 to n - 1. Each player has an army. Army of the i-th player
can be described by non-negative integer x_i. Consider binary
representation of x_i: if the j-th bit of number x_i equal to one, then
the army of the i-th player has soldiers of the j-th type.
Fedor is the (m + 1)-th player of the game. He assume that two players can
become friends if their armies differ in at most k types of soldiers (in
other words, binary representations of the corresponding numbers differ in
at most k bits). Help Fedor and count how many players can become his
friends.
*/
#define MAXN 1100
int x[MAXN];
void run(){
int n,m,k;scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=m+1;i++){
scanf("%d",&x[i]);
}
int res=0;
for(int i=1;i<=m;i++){
if(__builtin_popcount(x[i]^x[m+1])<=k)res++;
}
printf("%d\n",res);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
52. Codeforces Round #644 (Div. 3) C. Similar Pairs
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1360/C
Codeforces Round #644 (Div. 3) C. Similar Pairs
We call two numbers x and y similar if they have the same parity (the same
remainder when divided by 2), or if |x-y|=1. For example, in each of the
pairs (2, 6), (4, 3), (11, 7), the numbers are similar to each other, and
in the pairs (1, 4), (3, 12), they are not.
You are given an array a of n (n is even) positive integers. Check if
there is such a partition of the array into pairs that each element of the
array belongs to exactly one pair and the numbers in each pair are similar
to each other.
For example, for the array a = [11, 14, 16, 12], there is a partition into
pairs (11, 12) and (14, 16). The numbers in the first pair are similar
because they differ by one, and in the second pair because they are both
even.
*/
#define MAXN 55
int a[MAXN];
void run(){
int n;scanf("%d",&n);
int odd=0,even=0;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
if(a[i]%2)odd++;
else even++;
}
sort(a,a+n);
int adj=0;
for(int i=0;i<n-1;i++){
if(abs(a[i]-a[i+1])==1){
adj++;
i++;
}
}
odd-=adj;
even-=adj;
if((odd%2+even%2)>adj*2){
printf("NO\n");
return;
}
printf("YES\n");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
53. Educational Codeforces Round 86 (Rated for Div. 2) B. Binary Period
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1342/B
Educational Codeforces Round 86 (Rated for Div. 2) B. Binary Period
Let's say string s has period k if s_i = s_{i + k} for all i from 1 to |s|
- k (|s| means length of string s) and k is the minimum positive integer
with this property.
Some examples of a period: for s="0101" the period is k=2, for s="0000"
the period is k=1, for s="010" the period is k=2, for s="0011" the period
is k=4.
You are given string t consisting only of 0's and 1's and you need to find
such string s that:
String s consists only of 0's and 1's;
The length of s doesn't exceed 2 \cdot |t|;
String t is a subsequence of string s;
String s has smallest possible period among all strings that meet
conditions 1—3.
Let us recall that t is a subsequence of s if t can be derived from s by
deleting zero or more elements (any) without changing the order of the
remaining elements. For example, t="011" is a subsequence of s="10101".
*/
void run(){
string s;cin>>s;
int n=s.length();
int z=0,o=0;
for(int i=0;i<n;i++){
if(s[i]=='0')z++;
else o++;
}
if(!z||!o){
cout<<s<<"\n";
return;
}
string t;
for(int i=0;i<n;i++){
if(i==n-1||s[i]!=s[i+1])t+=s[i];
else {
t+=s[i];
t+='0'+(s[i]=='0');
}
}
cout<<t<<"\n";
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
54. Codeforces Round #651 (Div. 2) B. GCD Compression
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1370/B
Codeforces Round #651 (Div. 2) B. GCD Compression
Ashish has an array a of consisting of 2n positive integers. He wants to
compress a into an array b of size n-1. To do this, he first discards
exactly 2 (any two) elements from a. He then performs the following
operation until there are no elements left in a:
Remove any two elements from a and append their sum to b.
The compressed array b has to have a special property. The greatest common
divisor (\mathrm{gcd}) of all its elements should be greater than 1.
Recall that the \mathrm{gcd} of an array of positive integers is the
biggest integer that is a divisor of all integers in the array.
It can be proven that it is always possible to compress array a into an
array b of size n-1 such that gcd(b_1, b_2..., b_{n-1}) > 1.
Help Ashish find a way to do so.
*/
#define MAXN 10001
int a[MAXN];
void run(){
int n;scanf("%d",&n);
vector<int> odd,even;
for(int i=1;i<=2*n;i++){
scanf("%d",&a[i]);
if(a[i]%2)odd.push_back(i);
else even.push_back(i);
}
int cnt=0;
for(int i=0;i<odd.size();i+=2){
if(cnt>=2*n-2)break;
if(i+1<odd.size()){
printf("%d %d\n",odd[i],odd[i+1]);
cnt+=2;
}
}
for(int i=0;i<even.size();i+=2){
if(cnt>=2*n-2)break;
if(i+1<even.size()){
printf("%d %d\n",even[i],even[i+1]);
cnt+=2;
}
}
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
55. Codeforces Round #764 (Div. 3) C. Division by Two and Permutation
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1624/C
Codeforces Round #764 (Div. 3) C. Division by Two and Permutation
You are given an array a consisting of n positive integers. You can
perform operations on it.
In one operation you can replace any element of the array a_i with \lfloor
\frac{a_i}{2} \rfloor, that is, by an integer part of dividing a_i by 2
(rounding down).
See if you can apply the operation some number of times (possible 0) to
make the array a become a permutation of numbers from 1 to n —that is, so
that it contains all numbers from 1 to n, each exactly once.
For example, if a = [1, 8, 25, 2], n = 4, then the answer is yes. You
could do the following:
Replace 8 with \lfloor \frac{8}{2} \rfloor = 4, then a = [1, 4, 25, 2].
Replace 25 with \lfloor \frac{25}{2} \rfloor = 12, then a = [1, 4, 12,
2].
Replace 12 with \lfloor \frac{12}{2} \rfloor = 6, then a = [1, 4, 6, 2].
Replace 6 with \lfloor \frac{6}{2} \rfloor = 3, then a = [1, 4, 3, 2].
*/
#define MAXN 100
int a[MAXN];
void run(){
int n;scanf("%d",&n);
int res=0;
unordered_map<int,int> mp;
bool flag=false;
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
while(a[i]>n){
a[i]/=2;
res++;
}
while(a[i]!=0&&mp.find(a[i])!=mp.end()){
a[i]/=2;
res++;
}
if(a[i]==0)flag=true;
else if(mp.find(a[i])==mp.end()){
res++;
mp[a[i]]=1;
}
}
if(flag)printf("NO\n");
else printf("YES\n");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
56. Codeforces Round #665 (Div. 2) B. Ternary Sequence
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1401/B
Codeforces Round #665 (Div. 2) B. Ternary Sequence
You are given two sequences a_1, a_2, \dots, a_n and b_1, b_2, \dots, b_n.
Each element of both sequences is either 0, 1 or 2. The number of elements
0, 1, 2 in the sequence a is x_1, y_1, z_1 respectively, and the number of
elements 0, 1, 2 in the sequence b is x_2, y_2, z_2 respectively.
You can rearrange the elements in both sequences a and b however you like.
After that, let's define a sequence c as follows:
c_i = \begin{cases} a_i b_i & \mbox{if }a_i > b_i \\ 0 & \mbox{if
}a_i = b_i \\ -a_i b_i & \mbox{if }a_i < b_i \end{cases}
You'd like to make \sum_{i=1}^n c_i (the sum of all elements of the
sequence c) as large as possible. What is the maximum possible sum?
*/
void run(){
int x1,y1,z1,x2,y2,z2;
scanf("%d%d%d%d%d%d",&x1,&y1,&z1,&x2,&y2,&z2);
// x1 0 y1 1 z1 2
// x2 0 y2 1 z2 2
// 00000 11111 22222
// 22111 11111 11100
ll res=0;
int p02=min(x1,z2);
x1-=p02;
z2-=p02;
// 000 11111 22222
// 111 11111 11100
if(z2==0){
printf("%d\n",min(z1,y2)*2);
return;
}
// 111 11111 22222
// 222 11111 11100
// 11111 22222
// 22222 11100
int p21=min(z1,y2);
z1-=p21;
y2-=p21;
res+=p21*2;
// 111 11111
// 222 11100
int p22=min(z1,z2);
z1-=p22;
z2-=p22;
// 111 22222
// 222 22200
res-=min(y1,z2)*2;
printf("%lld\n",res);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
57. Educational Codeforces Round 107 (Rated for Div. 2) B. GCD Length
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1511/B
Educational Codeforces Round 107 (Rated for Div. 2) B. GCD Length
You are given three integers a, b and c.
Find two positive integers x and y (x > 0, y > 0) such that:
the decimal representation of x without leading zeroes consists of a
digits;
the decimal representation of y without leading zeroes consists of b
digits;
the decimal representation of gcd(x, y) without leading zeroes consists
of c digits.
gcd(x, y) denotes the <a
href="https://en.wikipedia.org/wiki/Greatest_common_divisor">greatest
common divisor (GCD)
of integers x and y.
Output x and y. If there are multiple answers, output any of them.
*/
void run(){
int a,b,c;scanf("%d%d%d",&a,&b,&c);
printf("1");
for(int i=0;i<a-1;i++)printf("0");
printf(" ");
for(int i=0;i<b-c+1;i++)printf("1");
for(int i=0;i<c-1;i++)printf("0");
printf("\n");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
58. Codeforces Round #669 (Div. 2) A. Ahahahahahahahaha
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1407/A
Codeforces Round #669 (Div. 2) A. Ahahahahahahahaha
Alexandra has an even-length array a, consisting of 0s and 1s. The
elements of the array are enumerated from 1 to n. She wants to remove at
most \frac{n}{2} elements (where n — length of array) in the way that
alternating sum of the array will be equal 0 (i.e. a_1 - a_2 + a_3 - a_4 +
\dotsc = 0). In other words, Alexandra wants sum of all elements at the
odd positions and sum of all elements at the even positions to become
equal. The elements that you remove don't have to be consecutive.
For example, if she has a = [1, 0, 1, 0, 0, 0] and she removes 2nd and 4th
elements, a will become equal [1, 1, 0, 0] and its alternating sum is 1 -
1 + 0 - 0 = 0.
Help her!
*/
void run(){
int n;scanf("%d",&n);
int c0=0,c1=0;
for(int i=0;i<n;i++){
int x;scanf("%d",&x);
if(x)c1++;
else c0++;
}
if(c1<=n/2){
printf("%d\n",n/2);
for(int i=0;i<n/2;i++)printf("0%c"," \n"[i==n/2-1]);
return;
}
printf("%d\n",c1-c1%2);
for(int i=0;i<c1-c1%2;i++)printf("1%c"," \n"[i==n/2-1]);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
59. Codeforces Round #181 (Div. 2) A. Array
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/300/A
Codeforces Round #181 (Div. 2) A. Array
Vitaly has an array of n distinct integers. Vitaly wants to divide this
array into three non-empty sets so as the following conditions hold:
The product of all numbers in the first set is less than zero ( < 0).
The product of all numbers in the second set is greater than zero ( > 0).
The product of all numbers in the third set is equal to zero.
Each number from the initial array must occur in exactly one set.
Help Vitaly. Divide the given array.
*/
void run(){
int n;scanf("%d",&n);
vector<int> v1,v2,v3;
for(int i=0;i<n;i++){
int x;scanf("%d",&x);
if(x<0)v1.push_back(x);
if(x==0)v3.push_back(x);
if(x>0)v2.push_back(x);
}
if(v2.empty()){
v2.push_back(v1.back());v1.pop_back();
v2.push_back(v1.back());v1.pop_back();
}
if(v1.size()%2==0){
v3.push_back(v1.back());v1.pop_back();
}
printf("%d ",v1.size());for(const auto& x:v1)printf("%d ",x);printf("\n");
printf("%d ",v2.size());for(const auto& x:v2)printf("%d ",x);printf("\n");
printf("%d ",v3.size());for(const auto& x:v3)printf("%d ",x);printf("\n");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
60. Educational Codeforces Round 99 (Rated for Div. 2) C. Ping-pong
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1455/C
Educational Codeforces Round 99 (Rated for Div. 2) C. Ping-pong
Alice and Bob play ping-pong with simplified rules.
During the game, the player serving the ball commences a play. The server
strikes the ball then the receiver makes a return by hitting the ball
back. Thereafter, the server and receiver must alternately make a return
until one of them doesn't make a return.
The one who doesn't make a return loses this play. The winner of the play
commences the next play. Alice starts the first play.
Alice has x stamina and Bob has y. To hit the ball (while serving or
returning) each player spends 1 stamina, so if they don't have any
stamina, they can't return the ball (and lose the play) or can't serve the
ball (in this case, the other player serves the ball instead). If both
players run out of stamina, the game is over.
Sometimes, it's strategically optimal not to return the ball, lose the
current play, but save the stamina. On the contrary, when the server
commences a play, they have to hit the ball, if they have some stamina
left.
Both Alice and Bob play optimally and want to, firstly, maximize their
number of wins and, secondly, minimize the number of wins of their
opponent.
Calculate the resulting number of Alice's and Bob's wins.
*/
void run(){
// The best strategy for Bob is to not hit the ball for the
// first x-1 turn.
int x,y;scanf("%d%d",&x,&y);
printf("%d %d\n",x-1,y);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
61. Codeforces Round #674 (Div. 3) C. Increase and Copy
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1426/C
Codeforces Round #674 (Div. 3) C. Increase and Copy
Initially, you have the array a consisting of one element 1 (a = [1]).
In one move, you can do one of the following things:
Increase some (single) element of a by 1 (choose some i from 1 to the
current length of a and increase a_i by one);
Append the copy of some (single) element of a to the end of the array
(choose some i from 1 to the current length of a and append a_i to the end
of the array).
For example, consider the sequence of five moves:
You take the first element a_1, append its copy to the end of the array
and get a = [1, 1].
You take the first element a_1, increase it by 1 and get a = [2, 1].
You take the second element a_2, append its copy to the end of the array
and get a = [2, 1, 1].
You take the first element a_1, append its copy to the end of the array
and get a = [2, 1, 1, 2].
You take the fourth element a_4, increase it by 1 and get a = [2, 1, 1,
3].
Your task is to find the minimum number of moves required to obtain the
array with the sum at least n.
You have to answer t independent test cases.
*/
void run(){
// I: increase
// A: append
// The pattern must be like: IIII..IIIAAAA.AAAA
// The resule array must be like: [v,v,v,v,v...,v,v] (all the same)
// Let k be the final length of the array
// Then v = \lceil \frac{n}{k} \rceil
// # of I = v - 1
// # of A = k - 1
// # of I+A = v + k - 2 = \lceil n/k \rceil + k - 2
// Observe that the min is reached when k = \sqrt{n} for f(k) = n/k+k
// Therefore we can try a few values around \sqrt{n}
ll n;scanf("%lld",&n);
auto f=[&](ll k){
if(k<=0||k>n)return ll(2e9);
return 1ll*((n+k-1)/k+k-2); // v + k - 2
};
ll k=sqrt(n);
ll res=2e9;
res=min(res,1ll*f(k));
res=min(res,1ll*f(k-1));
res=min(res,1ll*f(k+1));
printf("%lld\n",res);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
62. Educational Codeforces Round 136 (Rated for Div. 2) B. Array Recovery
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1739/B
Educational Codeforces Round 136 (Rated for Div. 2) B. Array Recovery
For an array of non-negative integers a of size n, we construct another
array d as follows: d_1 = a_1, d_i = |a_i - a_{i - 1}| for 2 \le i \le n.
Your task is to restore the array a from a given array d, or to report
that there are multiple possible arrays.
*/
#define MAXN 110
int d[MAXN];
void run(){
int n;scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&d[i]);
}
int x=d[0];
vector<int> res;
res.push_back(x);
for(int i=1;i<n;i++){
if(d[i]==0){
res.push_back(x);
continue;
}
if(x-d[i]>=0){
printf("-1\n");
return;
}
x+=d[i];
res.push_back(x);
}
for(const auto& x:res)printf("%d ",x);
printf("\n");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
63. Codeforces Global Round 9 A. Sign Flipping
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1375/A
Codeforces Global Round 9 A. Sign Flipping
You are given n integers a_1, a_2, \dots, a_n, where n is odd. You are
allowed to flip the sign of some (possibly all or none) of them. You wish
to perform these flips in such a way that the following conditions hold:
At least \frac{n - 1}{2} of the adjacent differences a_{i + 1} - a_i for
i = 1, 2, \dots, n - 1 are greater than or equal to 0.
At least \frac{n - 1}{2} of the adjacent differences a_{i + 1} - a_i for
i = 1, 2, \dots, n - 1 are less than or equal to 0.
Find any valid way to flip the signs. It can be shown that under the given
constraints, there always exists at least one choice of signs to flip that
satisfies the required condition. If there are several solutions, you can
find any of them.
*/
void run(){
int n;scanf("%d",&n);
for(int i=0;i<n;i++){
int x;scanf("%d",&x);
if(i%2&&x>0)x=-x;
if(i%2==0&&x<0)x=-x;
printf("%d ",x);
}
printf("\n");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
64. Codeforces Round 358 (Div. 2) A. Alyona and Numbers
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/682/A
Codeforces Round 358 (Div. 2) A. Alyona and Numbers
After finishing eating her bun, Alyona came up with two integers n and m.
She decided to write down two columns of integers — the first column
containing integers from 1 to n and the second containing integers from 1
to m. Now the girl wants to count how many pairs of integers she can
choose, one from the first column and the other from the second column,
such that their sum is divisible by 5.
Formally, Alyona wants to count the number of pairs of integers (x, y)
such that 1 ≤ x ≤ n, 1 ≤ y ≤ m and <img align="middle" class="tex-formula"
src="https://espresso.codeforces.com/172ce45a535a02e9d636dcf4c462a2a1df6c32
15.png" style="max-width: 100.0%;max-height: 100.0%;" /> equals 0.
As usual, Alyona has some troubles and asks you to help.
*/
void run(){
int n,m;scanf("%d%d",&n,&m);
int r=n%5;
int k=n/5;
ll res=0;
for(int i=0;i<5;i++){
if(i==0){
res+=1ll*k*((i+m)/5);
}else{
res+=1ll*((i<=r?1:0)+k)*((i+m)/5);
}
}
printf("%lld\n",res);
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}
65. Codeforces Round 808 (Div. 2) B. Difference of GCDs
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1708/B
Codeforces Round 808 (Div. 2) B. Difference of GCDs
You are given three integers n, l, and r. You need to construct an array
a_1,a_2,\dots,a_n (l\le a_i\le r) such that \gcd(i,a_i) are all distinct
or report there's no solution.
Here \gcd(x, y) denotes the <a
href="https://en.wikipedia.org/wiki/Greatest_common_divisor">greatest
common divisor (GCD)
of integers x and y.
*/
void run(){
int n,l,r;scanf("%d%d%d",&n,&l,&r);
vector<int> res;
for(int i=1;i<=n;i++){
int k=((l-1)/i+1)*i;
if(k>r){
puts("No\n");
return;
}
res.push_back(k);
}
puts("Yes\n");
for(auto x:res)printf("%d ",x);
puts("");
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
int T;scanf("%d",&T);
while(T--){
run();
}
}
66. Codeforces Round 620 (Div. 2) B. Longest Palindrome
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
/*
https://codeforces.com/problemset/problem/1304/B
Codeforces Round 620 (Div. 2) B. Longest Palindrome
Returning back to problem solving, Gildong is now studying about
palindromes. He learned that a palindrome is a string that is the same as
its reverse. For example, strings "pop", "noon", "x", and "kkkkkk" are
palindromes, while strings "moon", "tv", and "abab" are not. An empty
string is also a palindrome.
Gildong loves this concept so much, so he wants to play with it. He has n
distinct strings of equal length m. He wants to discard some of the
strings (possibly none or all) and reorder the remaining strings so that
the concatenation becomes a palindrome. He also wants the palindrome to be
as long as possible. Please help him find one.
*/
void run(){
int n,m;scanf("%d%d",&n,&m);
string center;
deque<string> dq;
unordered_map<string,int> mp;
for(int i=0;i<n;i++){
string s;cin>>s;
mp[s]++;
}
for(auto [k,v]:mp){
int x=v;
string t=k;
reverse(t.begin(),t.end());
if(t!=k){
int y=mp[t];
int d=min(x,y);
mp[k]-=d;
mp[t]-=d;
for(int i=0;i<d;i++){
dq.push_front(k);
dq.push_back(t);
}
}
if(k==t){
if(mp[k]>1){
int d=mp[k]/2;
mp[k]-=d;
mp[t]-=d;
for(int i=0;i<d;i++){
dq.push_front(k);
dq.push_back(t);
}
}
if(mp[k])center=k,mp[k]--;
else if(mp[t])center=t,mp[t]--;
}
}
int z=dq.size();
cout<<z*m+center.size()<<"\n";
for(int i=0;i<z/2;i++){
cout<<dq.front();
dq.pop_front();
}
cout<<center;
for(int i=z/2;i<z;i++){
cout<<dq.front();
dq.pop_front();
}
cout<<"\n";
}
int main(){
#ifdef WINE
freopen("data.in","r",stdin);
#endif
run();
}