Hello everyone!
Thanks for participating in TheForces Round #5 (PerfectForces).
[problem:425963A]
We must first determine the scenario in which the answer is $$$0$$$. If $$$a > c$$$, then. Following that, if $$$b <= d$$$, the answer will be $$$-1$$$. Answer for the alternative case is $$$\frac{c - a}{b - d} + 1$$$. Because every second, the distance will be reduced by $$$(d - b)$$$.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int tests;
cin >> tests;
while (tests--) {
int a, b, c, d;
cin >> a >> b >> c >> d;
if (a > c) {
cout << 0 << '\n';
continue;
}
if (b <= d) {
cout << -1 << '\n';
continue;
}
int num = c - a;
int den = b - d;
cout << num / den + 1 << '\n';
}
return 0;
}
[problem:425963B]
We can solve this problem by doing pre bruteforce with using vector and map data structures. $$$(10^6)^3$$$ = $$$10^{18}$$$
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define int ll
#define double ld
#define _FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pii pair<int , int>
#define pb emplace_back
#define endl '\n'
#define sz(x) (int)((x).size())
#define all(x) (x).begin() , (x).end()
#define rall(x) (x).rbegin() , (x).rend()
#define F first
#define S second
const int mod = 1e9 + 7;
const int MAXX = 1e6 + 5;
const int N = 1e6;
const int INF = 1e18 + 123;
int t , l , r , k , x , y , ans;
map<int , int> p;
signed main()
{
_FastIO;
vector<int> v;
vector<int>::iterator it;
v.pb(0);
p[0] = 0;
for(int i = 1; i <= N; i++){
k = i * i * i;
x = (i - 1) * (i - 1) * (i - 1);
p[k] = p[x] + k;
p[k] %= mod;
v.pb(k);
}
cin >> t;
while(t--){
cin >> l >> r;
it = lower_bound(all(v) , l);
it--;
k = *it;
x = p[k];
it = upper_bound(all(v) , r);
it--;
k = *it;
y = p[k];
ans = y - x;
ans += mod;
ans %= mod;
cout << ans << endl;
}
return 0;
}
[problem:425963C]
Basically you include or don't include some element into $$$f$$$. For example:
$$$n = 3$$$
For $$$i = 1$$$ ($$$1$$$ if $$$a_i$$$ included, $$$0$$$ otherwise):
$$${1 0 0 1 1 0 0 1 1 0 0 1}$$$
For $$$i = 2$$$ :
$$${0 1 0 1 0 1 0 1 0 1 0 1}$$$
For $$$i = 3$$$ :
$$${0 0 1 1 0 0 1 1 0 0 1 1}$$$
First $$$n$$$ values are $$$0$$$, except for $$$i_{th}$$$ element, $$$(n + 1)_{th}$$$ value obviously becomes $$$1$$$. For next $$$i - 1$$$ values, you will take two $$$1$$$ for every $$$f$$$, so next $$$i - 1$$$ values will be equal to $$$0$$$. $$$(n + 1 + i)_{th}$$$ value will be $$$1$$$, because you will take only one $$$1$$$ from previous $$$f's$$$. Then next $$$(n - i)_{th}$$$ values will be $$$0$$$, because you will take two $$$1$$$ for every $$$f$$$. And we returned back to $$$n$$$ zeros except for $$$i_{th}$$$ element, so it's just cyclic pattern of size $$$n + 1$$$ where all elements are zeros except for $$$i_{th}$$$ and last element.
So you just need to find first $$$n+1$$$ $$$f$$$ values. Then find first $$$n+1$$$ $$$s$$$ values. After first $$$n+1$$$ values, the answer is infinitely repeating.
#include <bits/stdc++.h>
using namespace std;
typedef long double LD;
typedef long long int LL;
typedef pair <int,int> pii;
#define L first
#define R second
const int maxn = 1e5 + 100;
int f[maxn], s[maxn];
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, q;
cin >> n >> q;
for (int i = 1; i <= n; i++)
cin >> f[i], f[n + 1] ^= f[i];
for (int i = 1; i <= n + 1; i++)
s[i] = s[i - 1] ^ f[i];
while (q--) {
int idx;
cin >> idx;
idx = ((idx - 1) % (n + 1)) + 1;
cout << s[idx] << '\n';
}
return 0;
}
[problem:425963D]
All switched on bits of $$$x$$$ should be switched on in every $$$a_i$$$. You can do anything you want with other bits (except you can't make some bit in every $$$a_i$$$ switched on, but anyway it's impossible in the best case, because you can just turn bits off). If we will ignore fixed bits, we can see that the best way to choose numbers, is to add bits of $$$i-1$$$ between switched on bits of $$$x$$$.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define int ll
#define _FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pii pair<int , int>
#define pb emplace_back
#define endl '\n'
#define all(x) (x).begin() , (x).end()
#define rall(x) (x).rbegin() , (x).rend()
#define F first
#define S second
const int mod = 1e9 + 7;
const int MAXX = 1e6 + 5;
const int N = 1e6;
const int INF = 1e18 + 123;
int t , x , n;
signed main()
{
_FastIO;
cin >> t;
while(t--){
cin >> x >> n;
n--;
vector<int> v;
for(int i = 0; i <= 60; i++){
if(x & (1LL << i))
continue;
v.pb(1LL << i);
}
int ans = x;
for(int i = 0; i <= 30; i++){
if(n & (1LL << i))
ans += v[i];
}
cout << ans << endl;
}
return 0;
}
[problem:425963E]
We declare $$$dp[i][0]$$$ $$$(1 \le i \le n)$$$, as the maximum chosen days between day $$$1$$$ and $$$i$$$ such that the last day we chose was Green ("G"), Also $$$dp[i][1]$$$ for Yellow ("Y") and $$$dp[i][2]$$$ for Red ("R") will be defined same as Green. So the final answer will be maximum of $$$(dp[n][0], dp[n][1], dp[n][2])$$$. For base we put $$$dp[0][0] = dp[0][1] = dp[0][2] = 0$$$, and for example for update of $$$dp[i][0]$$$, We will have :
If the $$$i_{th}$$$ day is Green ("G"), we will have :
$$$dp[i][0] = max(dp[i — 1][0], dp[i — 1][2]) + 1$$$.
and if the $i_{th} day is not Green ("G"), we will have :
$$$dp[i][0] = dp[i - 1][0]$$$.
And for the other colors, the update is with the same idea.
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;
cin >> T;
for(int test = 0; test < T; test++)
{
int n;
cin >> n;
string s;
cin >> s;
int dp[n+1][3];
dp[0][0] = dp[0][1] = dp[0][2] = 0;
for(int i = 0; i < n; i++)
{
dp[i+1][0] = dp[i][0];
dp[i+1][1] = dp[i][1];
dp[i+1][2] = dp[i][2];
if(s[i] == 'G')dp[i+1][0] = max(dp[i][0],dp[i][2])+1;
else if(s[i] == 'Y')dp[i+1][1] = max(dp[i][0],dp[i][1])+1;
else dp[i+1][2] = max(dp[i][1],dp[i][2])+1;
}
cout << max(dp[n][0], max(dp[n][1], dp[n][2])) << '\n';
}
}
[problem:425963F]
With this constraints, we can write brute force. For being fast we need sieve.
If $$$N=p^a*q^b*r^c$$$ .
Number of divisors = $$$(a+1)*(b+1)*(c+1)$$$,
#include <bits/stdc++.h>
using namespace std;
#define _FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define pb emplace_back
const int MAXX = 1e4 + 5;
const int N = 1e4;
const int NUM = 4000000;
int t , n , i , j , k , s , m , cnt;
bool p[MAXX];
int ans[MAXX];
vector<int> v;
void sieve(){
p[2] = true;
for(i = 3; i < N; i += 2){
p[i] = true;
}
for(i = 3; (i * i) < N; i += 2){
if(p[i]){
for(j = (i + i + i); j < N; j += (i + i))
p[j] = false;
}
}
v.pb(2);
for(i = 3; i < N; i += 2){
if(p[i])
v.pb(i);
}
}
signed main()
{
_FastIO;
sieve();
for(i = 1; i <= NUM; i++){
k = i;
s = 1;
for(j = 0; (v[j] * v[j]) <= k; j++){
if(k % v[j])
continue;
cnt = 0;
while(k % v[j] == 0){
k /= v[j];
cnt++;
}
s *= (cnt + 1);
}
if(k > 1)
s *= 2;
while(m < s){
m++;
ans[m] = i;
}
}
scanf("%d" , &t);
while(t--){
scanf("%d" , &n);
printf("%d" , ans[n]);
putchar('\n');
}
return 0;
}
[problem:425963G]
At first, we assume that the answer is not $$$-1$$$, the state that the answer is $$$-1$$$ will be easily found.
From the constraints we can realize that any number from $$$1$$$ to $$$10^{13}$$$ has at most $$$M = \frac{log(10^{13})}{log(3)}$$$ which is less than $$$30$$$ digits.
So sum of the digits will be at most $$$2 * 30 = 60$$$, then we calculate the answer with recursion, for this way, we declare function $$$f(k, cntdigits, before)$$$ which calculates the $$$k_{th}$$$ smallest semi-prime-lover that has at most $$$cntdigits$$$ digits in $$$base_{3}$$$. We call a number semi-prime-lover if it's sum of digits + $$$before$$$ becomes a prime number.
Note that if $$$before = 0$$$ we will have the prime-lover number so the answer is $$$f(k, M, 0)$$$. Also for solving the problem we need :
$$$cnt[i][j] (0 \leq i \leq M, 0 \leq j \leq S)$$$, that calculates the number of numbers with at most $$$i$$$ digits (obviously in $$$base_3$$$) with sum of digits equal to $$$j$$$, which can be calculated in this way : $$$cnt[0][0] = 1, cnt[i][j] = cnt[i-1][j] + cnt[i-1][j-1] + cnt[i-1][j-2]$$$.
for calculating $$$f(k, cntdigit, before)$$$ we always try to determine the value of the most valuable digit of the answer.
More specifically, suppose the number of semi-prime-lover numbers while the most valuable digit is $$$0$$$ be $$$x$$$, when it's $$$1$$$ be $$$y$$$ and when it's $$$2$$$ be $$$z$$$, now if $$$(0 \le k \le x)$$$ then the most valuable digit is $$$0$$$, and if $$$(x < k \le x + y)$$$ then the most valuable digit is $$$1$$$, and when $$$(x + y < k \le x + y + z)$$$ the most valuable digit is $$$2$$$ (otherwise the answer is $$$-1$$$).
In order to know how many semi-prime-lover numbers with most valuable digit $$$w$$$ we have, it's enough to calculate the following formula :
$$$\sum_{p_i \in P} cnt[cntdigits-1][p_i-w-before]$$$.
That $$$P$$$ means the set of prime numbers from $$$0$$$ to $$$S$$$.
Now the answer can be calculated in this way :
$$$f(k, cntdigits, before) = f(k, cntdigits-1,before)$$$.
$$$f(k, cntdigits, before) = 3^{cntdigits-1} + f(k-x, cntdigits-1,before+1)$$$.
$$$f(k, cntdigits, before) = 2*3^{cntdigits-1} + f(k-x-y, cntdigits-1,before+2)$$$.
Time Complexity : $$$\mathcal{O}(\log {MAX_N}^2 + T \times \log MAX_N \times \frac{\log {MAX_N}}{\log \log MAX_N})$$$.
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 30; // N = MAX_DIGIT_IN_BASE_3
vector<ll> primes = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59};
ll dp[N][N*2], n, k, ans;
ll Find(ll k, ll digit, ll before)
{
if(digit == -1)
return 0;
ll last_sum = 0, sum = 0;
for(ll d = 0; d < 3; d++)
{
for(auto p: primes)if(p >= d+before)
sum += dp[digit][p-d-before];
if(sum >= k)
return d*pow(3, digit)+Find(k-last_sum, digit-1, before+d);
last_sum = sum;
}
return -1LL;
}
int main()
{
memset(dp, 0, sizeof(dp));
dp[1][0] = dp[1][1] = dp[1][2] = 1;
for(int i = 0; i < N; i++)dp[i][0] = 1;
for(int i = 0; i < N; i++)dp[i][1] = i;
for(int i = 2; i < N; i++)
for(int j = 2; j < 2*N; j++)
dp[i][j] = dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j-2];
int T;
cin >> T;
for(int test = 0; test < T; test++)
{
cin >> n >> k;
ans = Find(k, N-1, 0);
if(ans > n)
ans = -1;
cout << ans << '\n';
}
}
For problem F we can use a sieve to precalculate the number of divisors of each number from 1 to N.
My submission
can anyone explain D question i m not getting editorial
First sentence of editorial means that: $$$a_1$$$ & $$$\ldots$$$ & $$$a_n=x\implies\forall i:a_i=x$$$ | $$$smth_i$$$
& will keep only the bit which is present in all operands. You, probably, got it.
Second sentence of editorial means that: $$$smth_1$$$ & $$$\ldots$$$ & $$$smth_n = 0$$$
There is no benefit of having some bit in all $$$smth_i$$$. And the other reason is that the first equality will not hold (smth is smth, but smth is not any). I quess, you fiqured it out during a contest. Now:
Third sentence: We want minimum $$$a_n$$$. Bits that are set in x also are set in $$$a_i$$$. What is the minimum possible $$$a_1$$$? Well, we can take $$$a_1=x$$$. What is minimum possible $$$a_2$$$? we can take $$$a_1$$$ and set 'the least significant' zero-bit in it to one. What is minimum possible $$$a_3$$$? We take $$$a_1$$$ and set 'the next least significant' zero-bit to one. What is minimum possible $$$a_4$$$? We take $$$a_1$$$ and set both 'the least significant' and 'the next least significant' zero-bit to one. Now you need to notice that $$$a_i$$$ are constructed in a way of filling empty slots (zero-bits) of $$$a_1$$$. So if we want to make $$$m$$$ steps from $$$x$$$ we need to look at a binary representation of $$$m$$$ and fill this representation in empty slots of $$$x$$$.
For example:
$$$x=100101_2$$$
$$$m=4=100_2$$$
Then:
$$$a_1=x$$$
Empty slots of $$$x$$$ are $$$1[0][0]1[0]1_2$$$
And $$$a_{1+m}=a_5$$$ will be $$$1[1][0]1[0]1_2$$$
what will be the values of a for x u have taken in example
Your guess..
100101 100111 101101 101111 110101
i got much of the solution but checking on binary representation of m how will this help?
So you know what to do on paper, but don't know how to instruct a machine to do the same? I think the more problems on bit manipulation you encounter, the more 'manipulative' in regard to bits you will become. You can look at program text, if you wish. I don't think my explanation will be more clear then the code.
Binary representation of m is needed to know what to insert in empty slots of $$$x$$$. In initial problem we need to find $$$a_n$$$ that means that we need to make $$$n-1$$$ steps from $$$a_1=x$$$. We can say that to solve initial problem we consider $$$m=n-1$$$. To implement this we traverse index on $$$m$$$ and for it we search for empty slot of $$$x$$$ with the help of while-loop.
The intuition is simply we write $$$m$$$ inside $$$x$$$.