周练19.11.24
积薄而为厚，积少而为多。
CodeForces - 1180A
While playing with geometric figures Alex has accidentally invented a concept of a nn-th order rhombus in a cell grid.
A 11-st order rhombus is just a square 1×11×1 (i.e just a cell).
A nn-th order rhombus for all n≥2n≥2 one obtains from a n−1n−1-th order rhombus adding all cells which have a common side with it to it (look at the picture to understand it better).
Alex asks you to compute the number of cells in a nn-th order rhombus.
Input
The first and only input line contains integer nn (1≤n≤1001≤n≤100) — order of a rhombus whose numbers of cells should be computed.
Output
Print exactly one integer — the number of cells in a nn-th order rhombus.
Examples
Input
1Output
1Input
2Output
5Input
3Output
13Note
Images of rhombus corresponding to the examples are given in the statement.
#include<stdio.h>
#include<iostream>
using namespace std;
typedef long long ll;
ll n;
ll num;
int main()
{
while(cin>>n)
{
num = 2*(n-1)*(n-1)+2*n-1;
cout<<num<<endl;
}
return 0;
}CodeForces - 1180B
Nick had received an awesome array of integers a=[a1,a2,…,an]a=[a1,a2,…,an] as a gift for his 55 birthday from his mother. He was already going to explore its various properties but after unpacking he was disappointed a lot because the product a1⋅a2⋅…ana1⋅a2⋅…an of its elements seemed to him not large enough.
He was ready to throw out the array, but his mother reassured him. She told him, that array would not be spoiled after the following operation: choose any index ii (1≤i≤n1≤i≤n) and do ai:=−ai−1ai:=−ai−1.
For example, he can change array [3,−1,−4,1][3,−1,−4,1] to an array [−4,−1,3,1][−4,−1,3,1] after applying this operation to elements with indices i=1i=1 and i=3i=3.
Kolya had immediately understood that sometimes it’s possible to increase the product of integers of the array a lot. Now he has decided that he wants to get an array with the maximal possible product of integers using only this operation with its elements (possibly zero, one or more times, as many as he wants), it is not forbidden to do this operation several times for the same index.
Help Kolya and print the array with the maximal possible product of elements a1⋅a2⋅…ana1⋅a2⋅…an which can be received using only this operation in some order.
If there are multiple answers, print any of them.
Input
The first line contains integer nn (1≤n≤1051≤n≤105) — number of integers in the array.
The second line contains nn integers a1,a2,…,ana1,a2,…,an (−106≤ai≤106−106≤ai≤106) — elements of the array
Output
Print nn numbers — elements of the array with the maximal possible product of elements which can be received using only this operation in some order from the given array.
If there are multiple answers, print any of them.
Examples
Input
4
2 2 2 2Output
-3 -3 -3 -3Input
1
0Output
0Input
3
-3 -3 2Output
-3 -3 2#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n;
ll a[200000],b[200000];
ll Max1,Max2;
int main()
{
while(cin>>n)
{
ll Min = 0;
for(int i =0;i<n;++i)
{
cin>>a[i];
}
for(int i =0;i<n;++i)
{
if(a[i]>=0)
a[i] = -a[i] - 1;
if(a[i]<0)
Min= min(a[i],Min);
}
if(n%2==1)
{
for(int i=0;i<n;++i)
{
if(a[i]==Min)
{ a[i] = -a[i] - 1;
break;
}
}
}
for(int i =0;i<n;++i)
{
cout<<a[i]<<" ";
}
cout<<endl;
}
return 0;
}CodeForces - 1169B
Toad Ivan has mm pairs of integers, each integer is between 11 and nn, inclusive. The pairs are (a1,b1),(a2,b2),…,(am,bm)(a1,b1),(a2,b2),…,(am,bm).
He asks you to check if there exist two integers xx and yy (1≤x<y≤n1≤x<y≤n) such that in each given pair at least one integer is equal to xx or yy.
Input
The first line contains two space-separated integers nn and mm (2≤n≤3000002≤n≤300000, 1≤m≤3000001≤m≤300000) — the upper bound on the values of integers in the pairs, and the number of given pairs.
The next mm lines contain two integers each, the ii-th of them contains two space-separated integers aiaiand bibi (1≤ai,bi≤n,ai≠bi1≤ai,bi≤n,ai≠bi) — the integers in the ii-th pair.
Output
Output “YES” if there exist two integers xx and yy (1≤x<y≤n1≤x<y≤n) such that in each given pair at least one integer is equal to xx or yy. Otherwise, print “NO”. You can print each letter in any case (upper or lower).
Examples
Input
4 6
1 2
1 3
1 4
2 3
2 4
3 4Output
NOInput
5 4
1 2
2 3
3 4
4 5Output
YESInput
300000 5
1 2
1 2
1 2
1 2
1 2Output
YESNote
In the first example, you can’t choose any xx, yy because for each such pair you can find a given pair where both numbers are different from chosen integers.
In the second example, you can choose x=2x=2 and y=4y=4.
In the third example, you can choose x=1x=1 and y=2y=2.
The circle line of the Roflanpolis subway has nn stations.
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll n,m;
ll a[400000],b1[400000],b2[400000];
struct node
{
ll x,y;
}mm[300006];
ll con,num,flag;
int main()
{
cin>>n>>m;
num = 0;
flag = 0;
for(int i =1;i<=m;++i)
{
cin>>mm[i].x>>mm[i].y;
}
for(int i =2;i<=m;++i)
{
if(mm[i].x!=mm[1].x&&mm[i].y!=mm[1].x)
{
a[num++] = i;
}
}
for(int i =0;i<num;++i)
{
b1[mm[a[i]].x]++;
b1[mm[a[i]].y]++;
if(b1[mm[a[i]].x] == num||b1[mm[a[i]].y]==num)
flag = 1;
}
if(num ==0)
flag = 1;
num = 0;
for(int i =2;i<=m;++i)
{
if(mm[i].x!=mm[1].y&&mm[i].y!=mm[1].y)
{
a[num++] = i;
}
}
for(int i =0;i<num;++i)
{
b2[mm[a[i]].x]++;
b2[mm[a[i]].y]++;
if(b2[mm[a[i]].x] == num||b2[mm[a[i]].y]==num)
flag = 1;
}
if(num == 0)
flag = 1;
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
return 0;
}CodeForces - 1169A
There are two parallel routes in the subway. The first one visits stations in order 1→2→…→n→1→2→…1→2→…→n→1→2→… (so the next stop after station xx is equal to (x+1)(x+1) if x<nx<n and 11otherwise). The second route visits stations in order n→(n−1)→…→1→n→(n−1)→…n→(n−1)→…→1→n→(n−1)→…(so the next stop after station xx is equal to (x−1)(x−1) if x>1x>1 and nn otherwise). All trains depart their stations simultaneously, and it takes exactly 11 minute to arrive at the next station.
Two toads live in this city, their names are Daniel and Vlad.
Daniel is currently in a train of the first route at station aa and will exit the subway when his train reaches station xx.
Coincidentally, Vlad is currently in a train of the second route at station bb and he will exit the subway when his train reaches station yy.
Surprisingly, all numbers a,x,b,ya,x,b,y are distinct.
Toad Ilya asks you to check if Daniel and Vlad will ever be at the same station at the same time during their journey. In other words, check if there is a moment when their trains stop at the same station. Note that this includes the moments when Daniel or Vlad enter or leave the subway.
Input
The first line contains five space-separated integers nn, aa, xx, bb, yy (4≤n≤1004≤n≤100, 1≤a,x,b,y≤n1≤a,x,b,y≤n, all numbers among aa, xx, bb, yy are distinct) — the number of stations in Roflanpolis, Daniel’s start station, Daniel’s finish station, Vlad’s start station and Vlad’s finish station, respectively.
Output
Output “YES” if there is a time moment when Vlad and Daniel are at the same station, and “NO” otherwise. You can print each letter in any case (upper or lower).
Examples
Input
5 1 4 3 2Output
YESInput
10 2 1 9 10Output
NONote
In the first example, Daniel and Vlad start at the stations (1,3)(1,3). One minute later they are at stations (2,2)(2,2). They are at the same station at this moment. Note that Vlad leaves the subway right after that.
Consider the second example, let’s look at the stations Vlad and Daniel are at. They are:
- initially (2,9)(2,9),
- after 11 minute (3,8)(3,8),
- after 22 minutes (4,7)(4,7),
- after 33 minutes (5,6)(5,6),
- after 44 minutes (6,5)(6,5),
- after 55 minutes (7,4)(7,4),
- after 66 minutes (8,3)(8,3),
- after 77 minutes (9,2)(9,2),
- after 88 minutes (10,1)(10,1),
- after 99 minutes (1,10)(1,10).
After that, they both leave the subway because they are at their finish stations, so there is no moment when they both are at the same station.
#include<iostream>
using namespace std;
typedef long long ll;
ll aa[105];
ll n;
ll a,x,b,y;
int main()
{
while(cin>>n)
{
int flag = 0;
cin>>a>>x>>b>>y;
for(ll i =a,j = b;;i++,j--)
{
if(i>n) i = 1;
if(j==0) j=n;
if(i==j)
flag = 1;
if(i==x||j==y)
break;
}
if(flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}
return 0;
}