Идея: BledDest
Разбор
Tutorial is loading...
Решение (Ne0n25)
for i in range(int(input())):
print(len(input()))
Идея: adedalic
Разбор
Tutorial is loading...
Решение (adedalic)
#include<bits/stdc++.h>
using namespace std;
int main() {
int t; cin >> t;
while (t--) {
int x; cin >> x;
int steps = 0;
while (steps * (steps + 1) < 2 * x)
steps++;
if (steps * (steps + 1) / 2 == x + 1)
steps++;
cout << steps << endl;
}
}
Идея: Neon
Разбор
Tutorial is loading...
Решение (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
void solve() {
int x, y;
cin >> x >> y;
cout << x - 1 << " " << y << endl;
}
int main() {
int t;
cin >> t;
while (t--) solve();
}
1455D - Последовательность и обмены
Идея: BledDest
Разбор
Tutorial is loading...
Решение 1 (BledDest)
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
for(int i = 0; i < t; i++)
{
int n, x;
cin >> n >> x;
vector<int> a(n);
for(int i = 0; i < n; i++)
cin >> a[i];
if(is_sorted(a.begin(), a.end()))
{
cout << 0 << endl;
continue;
}
vector<vector<int>> dp(n, vector<int>(501, int(1e9)));
for(int i = 0; i < n; i++)
{
if(a[i] > x && (i == 0 || a[i - 1] <= x))
dp[i][x] = 1;
if(i < n - 1 && a[i] > a[i + 1])
break;
}
int ans = int(1e9);
for(int i = 0; i < n; i++)
for(int j = 0; j <= 500; j++)
{
if(dp[i][j] == int(1e9))
continue;
if(i == n || (j <= a[i + 1] && is_sorted(a.begin() + i + 1, a.end())))
ans = min(ans, dp[i][j]);
bool good = true;
for(int k = i + 1; k < n; k++)
{
int pr = k == i + 1 ? j : a[k - 1];
if(good && a[i] >= pr && a[i] < a[k])
dp[k][a[i]] = min(dp[k][a[i]], dp[i][j] + 1);
good &= a[k] >= pr;
}
}
if(ans == int(1e9))
ans = -1;
cout << ans << endl;
}
}
Решение 2 (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())
#define x first
#define y second
typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << ", " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
out << "[";
fore(i, 0, sz(v)) {
if(i) out << ", ";
out << v[i];
}
return out << "]";
}
const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
int n, x;
vector<int> a;
inline bool read() {
if(!(cin >> n >> x))
return false;
a.resize(n);
fore (i, 0, n)
cin >> a[i];
return true;
}
inline void solve() {
vector<int> sf(n + 1, 0);
sf[n] = sf[n - 1] = 1;
for (int i = n - 2; i >= 0; i--) {
if (a[i] <= a[i + 1])
sf[i] = sf[i + 1];
}
int ans = 0;
int uk = 0;
while (true) {
int np = uk;
while (np < n && a[np] <= x)
np++;
fore (i, uk, np) {
if (i == 0) continue;
if (a[i - 1] > a[i]) {
cout << -1 << endl;
return;
}
}
if (sf[np])
break;
assert(a[np] > x);
swap(a[np], x);
ans++;
uk = np;
}
cout << ans << endl;
}
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;
}
Идея: adedalic
Разбор
Tutorial is loading...
Решение 1 (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())
#define x first
#define y second
typedef long long li;
typedef pair<li, li> pt;
const li INF64 = li(1e18);
pt p[4];
inline bool read() {
fore (i, 0, 4) {
if(!(cin >> p[i].x >> p[i].y))
return false;
}
return true;
}
inline void solve() {
li ans = INF64;
fore (st, 0, 2) {
fore (idx1, 0, 4) fore (idx2, 0, 4) fore (idy1, 0, 4) {
li x1 = p[idx1].x;
li x2 = p[idx2].x;
li y1 = p[idy1].y;
if (x1 > x2)
continue;
for (int k = -1; k <= 1; k += 2) {
li y2 = y1 + k * abs(x1 - x2);
vector<pt> fp = { {x1, y1}, {x2, y1}, {x2, y2}, {x1, y2} };
sort(fp.begin(), fp.end());
do {
li cur = 0;
fore (i, 0, 4)
cur += abs(fp[i].x - p[i].x) + abs(fp[i].y - p[i].y);
ans = min(ans, cur);
} while(next_permutation(fp.begin(), fp.end()));
}
}
fore (i, 0, 4)
swap(p[i].x, p[i].y);
}
cout << ans << endl;
}
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--) {
assert(read());
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Решение 2 (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())
#define x first
#define y second
typedef long long li;
typedef pair<li, li> pt;
const li INF64 = li(1e18);
pt p[4];
inline bool read() {
fore (i, 0, 4) {
if(!(cin >> p[i].x >> p[i].y))
return false;
}
return true;
}
li len(const pt &a) {
assert(a.y >= a.x);
return a.y - a.x;
}
pt getSeg(li a, li b) {
return { min(a, b), max(a, b) };
}
pt getOpt(const pt &a, const pt &b) {
return {
max({ a.x - b.y, b.x - a.y, 0LL }),
max({ b.y - a.x, a.y - b.x, 0LL })
};
}
inline void solve() {
li ans = INF64;
vector<int> id = { 0, 1, 2, 3 };
do {
li cur = 0;
auto x1 = getSeg(p[id[0]].x, p[id[3]].x);
auto x2 = getSeg(p[id[1]].x, p[id[2]].x);
cur += len(x1) + len(x2);
pt xSeg = getOpt(x1, x2);
auto y1 = getSeg(p[id[0]].y, p[id[1]].y);
auto y2 = getSeg(p[id[2]].y, p[id[3]].y);
cur += len(y1) + len(y2);
pt ySeg = getOpt(y1, y2);
li is = min(xSeg.y, ySeg.y) - max(xSeg.x, ySeg.x);
cur += 2 * max(0LL, -is);
ans = min(ans, cur);
}
while (next_permutation(id.begin(), id.end()));
cout << ans << endl;
}
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--) {
assert(read());
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
Идея: Neon
Разбор
Tutorial is loading...
Решение (Ne0n25)
#include <bits/stdc++.h>
using namespace std;
const int N = 505;
int n, k;
string s;
string dp[N];
void solve() {
cin >> n >> k >> s;
for (int i = 1; i <= n; i++)
dp[i] = char('z' + 1);
for (int i = 0; i < n; i++) {
int c = s[i] - 'a';
int nc = min({c, (c + 1) % k, (c + k - 1) % k});
dp[i + 1] = min(dp[i + 1], dp[i] + char('a' + nc));
if (i > 0) {
dp[i + 1] = min(dp[i + 1], dp[i - 1] + char('a' + nc) + s[i - 1]);
dp[i + 1] = min(dp[i + 1], dp[i].substr(0, i - 1) + s[i] + dp[i].back());
}
if (i > 1) {
dp[i + 1] = min(dp[i + 1], dp[i - 1].substr(0, i - 2) + s[i] + dp[i - 1].back() + s[i - 1]);
}
}
cout << dp[n] << endl;
}
int main() {
int t;
cin >> t;
while (t--) solve();
}
Идея: MrPaul_TUser и BledDest
Разбор
Tutorial is loading...
Решение (pikmike)
#include <bits/stdc++.h>
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define x first
#define y second
using namespace std;
const long long INF = 1e18;
struct op{
string tp;
int y, v, to;
};
struct addmap{
long long add;
map<int, long long> val;
multiset<long long> mn;
};
void reset(addmap &a, int x, long long val){
if (a.val.count(x))
a.mn.erase(a.mn.find(a.val[x]));
a.val[x] = val - a.add;
a.mn.insert(val - a.add);
}
int main() {
int n, s;
scanf("%d%d", &n, &s);
static char buf[10];
op a;
vector<addmap> st;
st.push_back({});
st.back().val[0] = 0;
st.back().add = 0;
st.back().mn.insert(0);
forn(i, n){
scanf("%s", buf);
a.tp = buf;
if (a.tp == "set"){
scanf("%d%d", &a.y, &a.v);
assert(!st.back().mn.empty());
long long mn = st.back().add + *st.back().mn.begin();
st.back().add += a.v;
if (a.y != s) reset(st.back(), a.y, mn);
}
else if (a.tp == "if"){
scanf("%d", &a.y);
long long val = INF;
if (st.back().val.count(a.y)){
val = st.back().val[a.y] + st.back().add;
st.back().mn.erase(st.back().mn.find(st.back().val[a.y]));
st.back().val.erase(a.y);
}
st.push_back({});
reset(st.back(), a.y, val);
st.back().add = 0;
}
else{
if (st[int(st.size()) - 1].val.size() > st[int(st.size()) - 2].val.size())
swap(st[int(st.size()) - 1], st[int(st.size()) - 2]);
addmap& v = st[int(st.size()) - 2];
for (auto it : st.back().val){
if (!v.val.count(it.x) || v.val[it.x] + v.add > it.y + st.back().add){
if (v.val.count(it.x))
v.mn.erase(v.mn.find(v.val[it.x]));
v.val[it.x] = it.y + st.back().add - v.add;
v.mn.insert(it.y + st.back().add - v.add);
}
}
st.pop_back();
}
}
printf("%lld\n", *st.back().mn.begin() + st.back().add);
return 0;
}