目录
A. Linear Keyboard
You are given a keyboard that consists of 2626 keys. The keys are arranged sequentially in one row in a certain order. Each key corresponds to a unique lowercase Latin letter.
You have to type the word ss on this keyboard. It also consists only of lowercase Latin letters.
To type a word, you need to type all its letters consecutively one by one. To type each letter you must position your hand exactly over the corresponding key and press it.
Moving the hand between the keys takes time which is equal to the absolute value of the difference between positions of these keys (the keys are numbered from left to right). No time is spent on pressing the keys and on placing your hand over the first letter of the word.
For example, consider a keyboard where the letters from 'a' to 'z' are arranged in consecutive alphabetical order. The letters 'h', 'e', 'l' and 'o' then are on the positions 88, 55, 1212 and 1515, respectively. Therefore, it will take |5−8|+|12−5|+|12−12|+|15−12|=13|5−8|+|12−5|+|12−12|+|15−12|=13 units of time to type the word "hello".
Determine how long it will take to print the word ss.
Input
The first line contains an integer tt (1≤t≤10001≤t≤1000) — the number of test cases.
The next 2t2t lines contain descriptions of the test cases.
The first line of a description contains a keyboard — a string of length 2626, which consists only of lowercase Latin letters. Each of the letters from 'a' to 'z' appears exactly once on the keyboard.
The second line of the description contains the word ss. The word has a length from 11 to 5050 letters inclusive and consists of lowercase Latin letters.
Output
Print tt lines, each line containing the answer to the corresponding test case. The answer to the test case is the minimal time it takes to type the word ss on the given keyboard.
Example
input
Copy
5 abcdefghijklmnopqrstuvwxyz hello abcdefghijklmnopqrstuvwxyz i abcdefghijklmnopqrstuvwxyz codeforces qwertyuiopasdfghjklzxcvbnm qqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq qwertyuiopasdfghjklzxcvbnm abacaba
output
Copy
13 0 68 0 74
题意：
给你一个有26个键的键盘和一个字符串s，26个键排成一行，使用键盘时在两个键之间移动花费的时间是两键之间的距离差，输出键入s花费的时间。
思路：
用map形成一个键和位置的映射，然后直接通过键找位置计算时间。
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<map>
#include<string>
#include<cmath>
using namespace std;
typedef long long ll;
int main()
{
ll t;
cin>>t;
while(t--)
{
string a,s;
cin>>a>>s;
map<char,ll> mp;
for(ll i=0;i<a.size();i++)
{
mp[a[i]]=i;
}
ll ans=0;
for(ll i=1;i<s.size();i++)
{
ans+=abs(mp[s[i]]-mp[s[i-1]]);
}
cout<<ans<<endl;
}
}
B. Odd Grasshopper
The grasshopper is located on the numeric axis at the point with coordinate x0x0.
Having nothing else to do he starts jumping between integer points on the axis. Making a jump from a point with coordinate xx with a distance dd to the left moves the grasshopper to a point with a coordinate x−dx−d, while jumping to the right moves him to a point with a coordinate x+dx+d.
The grasshopper is very fond of positive integers, so for each integer ii starting with 11 the following holds: exactly ii minutes after the start he makes a jump with a distance of exactly ii. So, in the first minutes he jumps by 11, then by 22, and so on.
The direction of a jump is determined as follows: if the point where the grasshopper was before the jump has an even coordinate, the grasshopper jumps to the left, otherwise he jumps to the right.
For example, if after 1818 consecutive jumps he arrives at the point with a coordinate 77, he will jump by a distance of 1919 to the right, since 77 is an odd number, and will end up at a point 7+19=267+19=26. Since 2626 is an even number, the next jump the grasshopper will make to the left by a distance of 2020, and it will move him to the point 26−20=626−20=6.
Find exactly which point the grasshopper will be at after exactly nn jumps.
Input
The first line of input contains an integer tt (1≤t≤1041≤t≤104) — the number of test cases.
Each of the following tt lines contains two integers x0x0 (−1014≤x0≤1014−1014≤x0≤1014) and nn (0≤n≤10140≤n≤1014) — the coordinate of the grasshopper's initial position and the number of jumps.
Output
Print exactly tt lines. On the ii-th line print one integer — the answer to the ii-th test case — the coordinate of the point the grasshopper will be at after making nn jumps from the point x0x0.
Example
input
Copy
9 0 1 0 2 10 10 10 99 177 13 10000000000 987654321 -433494437 87178291199 1 0 -1 1
output
Copy
-1 1 11 110 190 9012345679 -87611785637 1 0
Note
The first two test cases in the example correspond to the first two jumps from the point x0=0x0=0.
Since 00 is an even number, the first jump of length 11 is made to the left, and the grasshopper ends up at the point 0−1=−10−1=−1.
Then, since −1−1 is an odd number, a jump of length 22 is made to the right, bringing the grasshopper to the point with coordinate −1+2=1−1+2=1.
题意：
坐标轴上x处有一个蚂蚱，他要跳n次，第d次跳到x+d或者x-d上，如果起跳前的位置是偶数就往左跳到x-d，否则跳到x+d上，问最后蚂蚱的位置。
思路：
数据范围很大，模拟不行，所以找规律，会发现：如果刚开始在奇数位，在前三次之后，每四次相当于往左跳4格；如果刚开始在偶数位，在前三次之后，每四次相当于往右跳四格；计算前三次之后有多少个四次，然后再算出不足四次的部分即可。
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
ll t;
cin>>t;
while(t--)
{
ll x,n;
cin>>x>>n;
if(n>3)
{
if(x%2)
{
for(ll i=3+(n-3)/4*4+1;i<=n;i++)
{
if(i-(3+(n-3)/4*4)<=2)
x+=i;
else
x-=i;
}
cout<<x+1-2-3-4*((n-3)/4)<<endl;
}
else
{
for(ll i=3+(n-3)/4*4+1;i<=n;i++)
{
if(i-(3+(n-3)/4*4)<=2)
x-=i;
else
x+=i;
}
cout<<x-1+2+3+4*((n-3)/4)<<endl;
}
}
else
{
if(x%2)
{
ll a[3]={1,-2,-3};
for(ll i=0;i<n;i++)
{
x+=a[i];
}
cout<<x<<endl;
}
else
{
ll a[3]={-1,2,3};
for(ll i=0;i<n;i++)
{
x+=a[i];
}
cout<<x<<endl;
}
}
}
}
C. Minimum Extraction
Yelisey has an array aa of nn integers.
If aa has length strictly greater than 11, then Yelisei can apply an operation called minimum extraction to it:
- First, Yelisei finds the minimal number mm in the array. If there are several identical minima, Yelisey can choose any of them.
- Then the selected minimal element is removed from the array. After that, mm is subtracted from each remaining element.
Thus, after each operation, the length of the array is reduced by 11.
For example, if a=[1,6,−4,−2,−4]a=[1,6,−4,−2,−4], then the minimum element in it is a3=−4a3=−4, which means that after this operation the array will be equal to a=[1−(−4),6−(−4),−2−(−4),−4−(−4)]=[5,10,2,0]a=[1−(−4),6−(−4),−2−(−4),−4−(−4)]=[5,10,2,0].
Since Yelisey likes big numbers, he wants the numbers in the array aa to be as big as possible.
Formally speaking, he wants to make the minimum of the numbers in array aa to be maximal possible (i.e. he want to maximize a minimum). To do this, Yelisey can apply the minimum extraction operation to the array as many times as he wants (possibly, zero). Note that the operation cannot be applied to an array of length 11.
Help him find what maximal value can the minimal element of the array have after applying several (possibly, zero) minimum extraction operations to the array.
Input
The first line contains an integer tt (1≤t≤1041≤t≤104) — the number of test cases.
The next 2t2t lines contain descriptions of the test cases.
In the description of each test case, the first line contains an integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the original length of the array aa. The second line of the description lists nn space-separated integers aiai (−109≤ai≤109−109≤ai≤109) — elements of the array aa.
It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105.
Output
Print tt lines, each of them containing the answer to the corresponding test case. The answer to the test case is a single integer — the maximal possible minimum in aa, which can be obtained by several applications of the described operation to it.
Example
input
Copy
8 1 10 2 0 0 3 -1 2 0 4 2 10 1 7 2 2 3 5 3 2 -4 -2 0 2 -1 1 1 -2
output
Copy
10 0 2 5 2 2 2 -2
Note
In the first example test case, the original length of the array n=1n=1. Therefore minimum extraction cannot be applied to it. Thus, the array remains unchanged and the answer is a1=10a1=10.
In the second set of input data, the array will always consist only of zeros.
In the third set, the array will be changing as follows: [−1,2,0]→[3,1]→[2][−1,2,0]→[3,1]→[2]. The minimum elements are highlighted with blueblue. The maximal one is 22.
In the fourth set, the array will be modified as [2,10,1,7]→[1,9,6]→[8,5]→[3][2,10,1,7]→[1,9,6]→[8,5]→[3]. Similarly, the maximum of the minimum elements is 55.
题意：
给你一个长度为n的数组a，可以进行任意次以下操作：选一个最小的数x从数组中删除，然后剩余的数a[i]-=x;输出数组的最小值的最大值。
思路：
排个序，从头减到尾，保留最大的最小值。
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
ll a[300000];
int main()
{
ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
for(ll i=0;i<n;i++)
{
cin>>a[i];
}
ll dx=0;
sort(a,a+n);
ll ans=a[0];
for(ll i=0;i<n-1;i++)
{
dx+=-(a[i]+dx);
ans=max(ans,a[i+1]+dx);
}
cout<<ans<<endl;
}
}
D. Blue-Red Permutation
You are given an array of integers aa of length nn. The elements of the array can be either different or the same.
Each element of the array is colored either blue or red. There are no unpainted elements in the array. One of the two operations described below can be applied to an array in a single step:
- either you can select any blue element and decrease its value by 11;
- or you can select any red element and increase its value by 11.
Situations in which there are no elements of some color at all are also possible. For example, if the whole array is colored blue or red, one of the operations becomes unavailable.
Determine whether it is possible to make 00 or more steps such that the resulting array is a permutation of numbers from 11 to nn?
In other words, check whether there exists a sequence of steps (possibly empty) such that after applying it, the array aa contains in some order all numbers from 11 to nn (inclusive), each exactly once.
Input
The first line contains an integer tt (1≤t≤1041≤t≤104) — the number of input data sets in the test.
The description of each set of input data consists of three lines. The first line contains an integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the length of the original array aa. The second line contains nn integers a1a1, a2a2, ..., anan (−109≤ai≤109−109≤ai≤109) — the array elements themselves.
The third line has length nn and consists exclusively of the letters 'B' and/or 'R': iith character is 'B' if aiai is colored blue, and is 'R' if colored red.
It is guaranteed that the sum of nn over all input sets does not exceed 2⋅1052⋅105.
Output
Print tt lines, each of which contains the answer to the corresponding test case of the input. Print YES as an answer if the corresponding array can be transformed into a permutation, and NO otherwise.
You can print the answer in any case (for example, the strings yEs, yes, Yes, and YES will be recognized as a positive answer).
Example
input
Copy
8 4 1 2 5 2 BRBR 2 1 1 BB 5 3 1 4 2 5 RBRRB 5 3 1 3 1 3 RBRRB 5 5 1 5 1 5 RBRRB 4 2 2 2 2 BRBR 2 1 -2 BR 4 -2 -1 4 0 RRRR
output
Copy
YES NO YES YES NO YES YES YES
Note
In the first test case of the example, the following sequence of moves can be performed:
- choose i=3i=3, element a3=5a3=5 is blue, so we decrease it, we get a=[1,2,4,2]a=[1,2,4,2];
- choose i=2i=2, element a2=2a2=2 is red, so we increase it, we get a=[1,3,4,2]a=[1,3,4,2];
- choose i=3i=3, element a3=4a3=4 is blue, so we decrease it, we get a=[1,3,3,2]a=[1,3,3,2];
- choose i=2i=2, element a2=2a2=2 is red, so we increase it, we get a=[1,4,3,2]a=[1,4,3,2].
We got that aa is a permutation. Hence the answer is YES.
题意：
给你一个长度为n的数组a，a中的每个数都有一个属性蓝或者红，蓝色的数可以减任意个1，红色的数可以加任意个1；问是否可以让数组中每个数a[i]∈[1,n]且没有重复。
思路：
将蓝色和红色的数分别递增排序，假设有x个蓝数b[x]和y个红数r[y]，每个b[i]可以变成[1,b[i]]中的任意一个数，如果b[i]<i就无法满足条件；同理r[i]>i也无法满足条件
代码：
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<string>
#include<vector>
using namespace std;
typedef long long ll;
struct point {
ll num;
char color;
};
point p[300000];
int main() {
ll t;
cin>>t;
while(t--) {
ll n;
cin>>n;
vector<ll> b;
vector<ll> r;
for(ll i=0;i<n;i++){
cin>>p[i].num;
}
string color;
cin>>color;
for(ll i=0;i<n;i++){
p[i].color=color[i];
}
for(ll i=0;i<n;i++){
if(p[i].color=='B')
{
b.push_back(p[i].num);
}
else
{
r.push_back(p[i].num);
}
}
sort(b.begin(),b.end());
sort(r.begin(),r.end());
int flag=1;
for(ll i=1;i<=b.size();i++)
{
if(i>b[i-1])
{
flag=0;
break;
}
}
for( ll i=b.size()+1;i<=n;i++)
{
if(i<r[i-b.size()-1])
{
flag=0;
break;
}
}
if(flag)
{
cout<<"YES"<<endl;
}
else
{
cout<<"NO"<<endl;
}
}
}