Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
t = int(input())
for i in range(t):
print(eval(input()))
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for(int _ = 0; _ < t; _++)
{
vector<int> a(4);
for(int i = 0; i < 4; i++)
cin >> a[i];
int maxpos = max_element(a.begin(), a.end()) - a.begin();
int minpos = min_element(a.begin(), a.end()) - a.begin();
if(maxpos + minpos == 3)
puts("YES");
else
puts("NO");
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
def construct(f, k):
return [(i + 2 if i < f - 1 else 1) for i in range(k)]
t = int(input())
for i in range(t):
k, n = map(int, input().split())
ans = 1
for f in range(1, k):
d = construct(f, k - 1)
if sum(d) <= n - 1:
ans = f
res = [1]
d = construct(ans, k - 1)
for x in d:
res.append(res[-1] + x)
print(*res)
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int n;
cin >> n;
vector<int> a(n);
for(int j = 0; j < n; j++)
cin >> a[j];
int mn = 0, mx = int(1e9);
for(int j = 0; j + 1 < n; j++)
{
int x = a[j];
int y = a[j + 1];
int midL = (x + y) / 2;
int midR = (x + y + 1) / 2;
if(x < y)
mx = min(mx, midL);
if(x > y)
mn = max(mn, midR);
}
if(mn <= mx) cout << mn << endl;
else cout << -1 << endl;
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (Neon)
for tc in range(int(input())):
n = int(input())
p = list(map(int, input().split()))
a, b, c = 0, 0, 0
for i in range(n):
if p[i] != i + 1 and p[i] != n - i:
c += 1
elif p[i] != i + 1:
a += 1
elif p[i] != n - i:
b += 1
if a + c <= b:
print("First")
elif b + c < a:
print("Second")
else:
print("Tie")
1772F - Copy of a Copy of a Copy
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (awoo)
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < int(n); i++)
struct op{
int t, x, y, i;
};
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int main(){
int n, m, k;
cin >> n >> m >> k;
vector<vector<string>> a(k + 1, vector<string>(n));
forn(z, k + 1) forn(i, n)
cin >> a[z][i];
vector<int> cnt(k + 1);
forn(z, k + 1){
for (int i = 1; i < n - 1; ++i){
for (int j = 1; j < m - 1; ++j){
bool ok = true;
forn(t, 4)
ok &= a[z][i][j] != a[z][i + dx[t]][j + dy[t]];
cnt[z] += ok;
}
}
}
vector<int> ord(k + 1);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&cnt](int x, int y){
return cnt[x] > cnt[y];
});
vector<op> ops;
forn(z, k){
forn(i, n) forn(j, m) if (a[ord[z]][i][j] != a[ord[z + 1]][i][j]){
a[ord[z]][i][j] ^= '0' ^ '1';
ops.push_back({1, i + 1, j + 1, -1});
}
ops.push_back({2, -1, -1, ord[z + 1] + 1});
}
cout << ord[0] + 1 << '\n';
cout << ops.size() << '\n';
for (auto it : ops){
cout << it.t << " ";
if (it.t == 1)
cout << it.x << " " << it.y << '\n';
else
cout << it.i << '\n';
}
}
Idea: BledDest
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
typedef long long li;
int n;
li x, y;
vector<li> a;
inline bool read() {
if(!(cin >> n >> x >> y))
return false;
a.resize(n);
fore (i, 0, n)
cin >> a[i];
return true;
}
li ceil(li a, li b) {
assert(a >= 0 && b >= 0);
return (a + b - 1) / b;
}
inline void solve() {
sort(a.begin(), a.end());
vector<li> t(n), b(n);
fore (i, 0, n) {
if (i > 0 && b[i - 1] >= a[i]) {
t[i] = t[i - 1];
b[i] = b[i - 1] + 1;
} else {
t[i] = a[i] - i;
b[i] = a[i] + 1;
}
}
li ans = 0;
while (x < y) {
int pos = int(upper_bound(t.begin(), t.end(), x) - t.begin());
li p = pos, m = n - pos;
if (x + p >= y) {
cout << ans + (y - x) << endl;
return;
}
if (p <= m) {
cout << -1 << endl;
return;
}
//1. x + k(p - m) + p >= y
li k = ceil(y - x - p, p - m);
if (pos < n) {
//2. x + k(p - m) >= t[pos]
k = min(k, ceil(t[pos] - x, p - m));
}
ans += k * n;
//x + k(p - m) < y, since 1. and p >= p - m
x += k * (p - m);
}
assert(false);
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
int t; cin >> t;
while (t--) {
read();
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
By the way, a more "natural" way to deduce the relations for D (without doing a lot of casework) is to square both sides of the inequality, because if $$$|x| \leqslant |y| \Rightarrow x^2 \leqslant y^2$$$. This gives $$$(a_i - x)^2 \leqslant (a_{i + 1} - x)^2$$$ for all valid $$$i$$$. This implies that $$$a_i^2 - 2a_ix + x^2 \leqslant a_{i + 1}^2 - 2a_{i + 1}x + x^2 \Rightarrow (a_i^2 - a_{i + 1}^2) - 2(a_i - a_{i + 1})x \leqslant 0 \Rightarrow (a_i - a_{i + 1})(a_i + a_{i + 1} - 2x) \leqslant 0$$$, and then we can continue in the same way as editorial.
It's more natural to just binary search the answer 185850639 (I suppose)
interesting, could you explain your approach a bit in detail?
First, let's denote min(a) as L, max(a) as H and M as (L + H) / 2, it's pointless to look for a solution where x > H or x < L because they will give array of the same (sortness) as H and L. try x = 5, 6 and x = 3, 2 on a = [5, 3, 5] for example, it'll give [0, 2, 0], [1, 3, 1] and [2, 0, 2], [3, 1, 3], respectively. every binary search loop iteration you loop through the array and check for any abs(M — a[i]) < abs(M — a[i — 1]) (which makes the result unsorted obviously), in case we found it we need to prolong the distance between M, a[i] and shorten it between M, a[i — 1] so we updaet H = M — 1 in case a[i] > a[i — 1] or L = M + 1 in case a[i] < a[i — 1]
how do we know when to do h=m-1 or l=m+1
absolute value means distance so if abs(m-a[i]) < abs(m-a[i-1]) that means m was closer to a[i] than a[i — 1] when it should have been further or equal, so we we make it closer to a[i-1]. if a[i] > a[i — 1] we need to make m smaller by doing h=m-1 and vice versa
so we should check all abs(a[i]-m)
my question is in this case what should i do : a[1]-m<a[2]-m at the same time a[3]-m>a[4]-m
If you want to do it more natural, you can apply difference of squares identity: $$$a^2 - b^2 = (a - b)(a + b)$$$ i.e. $$$(a_i−x)^2\le(a_{i+1}−x)^2 \Leftrightarrow (a_i−x)^2 - (a_{i+1}−x)^2 \le 0 \Leftrightarrow (a_i - a_{i + 1})(a_i + a_{i + 1} - 2x) \le 0$$$
I still don't understand the strategy used in Permutation Game. For me at least, the only possible outcome was a tie, because the other player can mess with the correct ordered ones. For example: 1 2 3 5 4 The first one colors 5 1 2 3 B5 4 The second colors any other to not let the first payer win B1 2 3 B5 4 The first color the last element B1 2 3 B5 B4 The second starts to mess the order of elements B5 2 3 B1 B4 And we have at least two elements out of order for player one, and it will require at least two first movements, but for any of them the other player will undo that movement. So what's the strategy?
You can swap more than two blue elements in one turn. You can reorder them as you want, the only condition is that all red elements stay on their positions.
I thought the swap was meant for only two elements, thanks.
Why cant 2nd player win in [2,3,1] . Why the answer is Tie.
first player [2B,3,1]
2nd player[2B,3B,1]
1st player skips
2nd player exchanges [3B,2B,1]
If the starting configuration is [2,3,1], 1st player wouldn't start by making the 2 blue. The game would go like this:
1st player [2,3,1B]
2nd player [2B,3,1B]
1st player skips
2nd player skips
1st player skips
2nd player skips . . .
Neither player can arramge the numbers in their goal orders, and making the 3 blue would allow the opponent to win, so bot players just skip turns and it's a tie.
For Problem G, why can we assume that we require a whole cycle in the reasoning for $$$x+k(p-m) \geq t_p$$$? What if $$$x$$$ exceeds $$$t_p$$$ mid-cycle? Then the number of wins in this particular cycle iteration would be $$$p+1$$$ and not $$$p$$$.
The $$$t_p$$$ is the rating you need at the start of the cycle to be able to win the $$$p$$$-th opponent (i.e. first $$$p+1$$$ opponents). If your $$$x < t_p$$$ at the start of the cycle — you can't win against the $$$p$$$-opponent.
Nope, suppose array $$$a = [5, 5, 5, 6]$$$. Arrays $$$t = [5, 4, 3, 3]$$$ and $$$b = [6, 6, 6, 7]$$$ don't make any sense.
The checker got me wrong answer to have the array which is not in ascending order in question C. Is this a bug? 186207153
can someone confirm How many operations can we make in one second in codeforces ?
I have tested cf servers once and it was approximately $$$3*10^9$$$ per second for simple operations like memset which is actually enormously fast (blog with the same question)
1172A- A+B is very easy solution in python 227321207
The tutorial for D, the conditions are x <= a[i], and x <= (a[i] + a[i + 1]) / 2 so the union isn't
a[i] <= x <= (a[i] + a[i + 1) / 2.
It had me confused so I'm writing for anybody that might come across the same thing.