C. Traffic Light
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
You find yourself on an unusual crossroad with a weird traffic light. That traffic light has three possible colors: red (r), yellow (y), green (g). It is known that the traffic light repeats its colors every nn seconds and at the ii-th second the color sisi is on.
That way, the order of the colors is described by a string. For example, if s=s=”rggry”, then the traffic light works as the following: red-green-green-red-yellow-red-green-green-red-yellow- … and so on.
More formally, you are given a string s1,s2,…,sns1,s2,…,sn of length nn. At the first second the color s1s1 is on, at the second — s2s2, …, at the nn-th second the color snsn is on, at the n+1n+1-st second the color s1s1 is on and so on.
You need to cross the road and that can only be done when the green color is on.
You know which color is on the traffic light at the moment, but you don’t know the current moment of time. You need to find the minimum amount of time in which you are guaranteed to cross the road.
You can assume that you cross the road immediately.
For example, with s=s=”rggry” and the current color r there are two options: either the green color will be on after 11 second, or after 33. That way, the answer is equal to 33 — that is the number of seconds that we are guaranteed to cross the road, if the current color is r.
Input
The first line contains a single integer tt (1≤t≤104(1≤t≤104) — the number of test cases.
Then the description of the test cases follows.
The first line of each test case contains an integer nn and a symbol cc (1≤n≤2⋅1051≤n≤2⋅105, cc is one of allowed traffic light colors r, y or g)— the length of the string ss and the current color of the traffic light.
The second line of each test case contains a string ss of the length nn, consisting of the letters r, y and g.
It is guaranteed that the symbol g is in the string ss and the symbol cc is in the string ss.
It is guaranteed, that the sum of nn over all test cases does not exceed 2⋅1052⋅105.
Output
For each test case output the minimal number of second in which you are guaranteed to cross the road.
Example
input
6
5 r
rggry
1 g
g
3 r
rrg
5 y
yrrgy
7 r
rgrgyrg
9 y
rrrgyyygy
output
3 0 2 4 1 4
Note
The first test case is explained in the statement.
In the second test case the green color is on so you can cross the road immediately.
In the third test case, if the red color was on at the second second, then we would wait for the green color for one second, and if the red light was on at the first second, then we would wait for the green light for two seconds.
In the fourth test case the longest we would wait for the green color is if we wait for it starting from the fifth second.
题目大意：
红绿灯有三种颜色，只有g代表可以通行。给一个长度为n的字符串，给一个字符c，问从颜色c的灯开始等几秒能够同行，输出需要等待的最长时间。
思路：
记下颜色为c的下标为数组a，再记下颜色为g的下标为数组b，遍历a数组，对于每一个a[i],upper_bound b数组中第一个大于a[i]的b[j]，如果搜索结果是b.size,说明没有，则最大等待时间为n-a[i]+b[0],否则为b[j] – a[i].
代码如下：
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin >> T;
while(T--)
{
vector<int>v1,v2;
int n;
cin >> n;
char op;
cin >> op;
string s;
cin >> s;
if(op == 'g')
{
cout << 0 << '\n';
continue;
}
for(int i = 0; i < n; i ++)
{
if(s[i] == 'g')
{
v1.push_back(i);
}
if(s[i] == op)
{
v2.push_back(i);
}
}
int ans = 0;
for(int i = 0; i < v2.size(); i++)
{
int x = upper_bound(v1.begin(),v1.end(),v2[i]) - v1.begin();
if(x == v1.size())
{
ans = max(ans,n - v2[i] + v1[0]);
}
else
{
ans = max(ans,v1[x] - v2[i]);
}
}
cout << ans << '\n';
}
}
D. Divisibility by 2^n
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
You are given an array of positive integers a1,a2,…,ana1,a2,…,an.
Make the product of all the numbers in the array (that is, a1⋅a2⋅…⋅ana1⋅a2⋅…⋅an) divisible by 2n2n.
You can perform the following operation as many times as you like:
- select an arbitrary index ii (1≤i≤n1≤i≤n) and replace the value aiai with ai=ai⋅iai=ai⋅i.
You cannot apply the operation repeatedly to a single index. In other words, all selected values of ii must be different.
Find the smallest number of operations you need to perform to make the product of all the elements in the array divisible by 2n2n. Note that such a set of operations does not always exist.
Input
The first line of the input contains a single integer tt (1≤t≤104(1≤t≤104) — the number test cases.
Then the descriptions of the input data sets follow.
The first line of each test case contains a single integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the length of array aa.
The second line of each test case contains exactly nn integers: a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109).
It is guaranteed that the sum of nn values over all test cases in a test does not exceed 2⋅1052⋅105.
Output
For each test case, print the least number of operations to make the product of all numbers in the array divisible by 2n2n. If the answer does not exist, print -1.
Example
input
6
1
2
2
3 2
3
10 6 11
4
13 17 1 1
5
1 1 12 1 1
6
20 7 14 18 3 5
output
0 1 1 -1 2 1
Note
In the first test case, the product of all elements is initially 22, so no operations needed.
In the second test case, the product of elements initially equals 66. We can apply the operation for i=2i=2, and then a2a2 becomes 2⋅2=42⋅2=4, and the product of numbers becomes 3⋅4=123⋅4=12, and this product of numbers is divided by 2n=22=42n=22=4.
In the fourth test case, even if we apply all possible operations, we still cannot make the product of numbers divisible by 2n2n — it will be (13⋅1)⋅(17⋅2)⋅(1⋅3)⋅(1⋅4)=5304(13⋅1)⋅(17⋅2)⋅(1⋅3)⋅(1⋅4)=5304, which does not divide by 2n=24=162n=24=16.
In the fifth test case, we can apply operations for i=2i=2 and i=4i=4.
题目大意:
给定一个长度为n的数组a，可以对a[i]进行如下操作：
a[i] *= i;(i从1开始)；
问最后得到的数组a中每个元素的乘积能不能被2的n次方整除，如果可以，输出需要的操作次数，不可以则输出-1
思路：
n是2e5，所以不能暴力。由于需要整除2的n次方，所以每次操作必须乘2的倍数，而且先乘含2多的数，这样能让操作次数最少。可以先预处理出1-2e5中是2的倍数的数，并记下有几个2。输入的时候，对于每个i，如果i中有2，则把i含2的个数加入vector中，最后从大到小排序。如果需要操作，遍历vector，直到v[i] + 原乘积中含2的个数 >= n，输出操作次数即可，否则输出-1
代码如下：
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
int a[N];
int c[N];
int cmp(int a,int b)
{
return a > b;
}
int main() {
for(int i = 2; i <= 2e5; i += 2)
{
int x = i;
int p = 0;
while(x % 2 == 0)
{
p++;
x /= 2;
}
c[i] = p;
}
int T;
cin >> T;
while(T--)
{
int n;
cin >> n;
int cnt = 0;
vector<int>v;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
int res = a[i];
while(res % 2 == 0)
{
cnt ++;
res /= 2;
}
if(c[i])
{
v.push_back(c[i]);
}
}
if(cnt >= n)
{
cout << 0 << '\n';
}
else
{
sort(v.begin(),v.end(),cmp);
int res = 0;
int f = 0;
for(int i = 0; i < v.size(); i++)
{
cnt += v[i];
res++;
if(cnt >= n)
{
f = 1;
break;
}
}
if(f)
{
cout << res << '\n';
}
else
{
cout << -1 << '\n';
}
}
}
return 0;
}
E1. Divisible Numbers (easy version)
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
This is an easy version of the problem. The only difference between an easy and a hard version is the constraints on aa, bb, cc and dd.
You are given 44 positive integers aa, bb, cc, dd with a<ca<c and b<db<d. Find any pair of numbers xx and yy that satisfies the following conditions:
- a<x≤ca<x≤c, b<y≤db<y≤d,
- x⋅yx⋅y is divisible by a⋅ba⋅b.
Note that required xx and yy may not exist.
Input
The first line of the input contains a single integer tt (1≤t≤10(1≤t≤10), the number of test cases.
The descriptions of the test cases follow.
The only line of each test case contains four integers aa, bb, cc and dd (1≤a<c≤1051≤a<c≤105, 1≤b<d≤1051≤b<d≤105).
Output
For each test case print a pair of numbers a<x≤ca<x≤c and b<y≤db<y≤d such that x⋅yx⋅y is divisible by a⋅ba⋅b. If there are multiple answers, print any of them. If there is no such pair of numbers, then print -1 -1.
Example
input
5
1 1 2 2
3 4 5 7
8 9 15 18
12 21 14 24
36 60 48 66
output
2 2 4 6 12 12 -1 -1 -1 -1
题目大意:
每次询问给四个数a,b,c,d,问是否有两个数a<x<=c,b<y<=d,使得x * y 能够被a*b整除，有则输出xy，没有则输出-1 -1。
思路：
直接暴力会TL。我们可以求x和a*b的最小公倍数记为sum，让y = d / sum * sum。一方面，直接避免y大于d，另一方面，让y尽量大，可以让y大于b，满足条件就输出。
代码如下：
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
long long int a,b,c,d;
scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
long long int m = a * b;
int f = 0;
for(long long int i = a + 1; i <= c; i++)
{
long long int t = m / __gcd(m,i) * i / i;
long long ans = d / t * t;
if(ans > b)
{
printf("%lld %lld\n",i,ans);
f = 1;
break;
}
}
if(!f)
{
printf("-1 -1\n");
}
}
return 0;
}