Идея: Vladosiya
t = int(input())
for _ in range(t):
a, b, c = map(int, input().split())
d1 = a — 1
d2 = abs(b — c) + c — 1
ans = 0
if d1 <= d2:
ans += 1
if d1 >= d2:
ans += 2
print(ans)
Идея: MikeMirzayanov
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
using namespace std;
char get(int i) {
return 'a' + i - 1;
}
void solve() {
int n;
string s;
cin >> n >> s;
int i = n - 1;
string res;
while (i >= 0) {
if (s[i] != '0') {
res += get(s[i] - '0');
i--;
} else {
res += get(stoi(s.substr(i - 2, 2)));
i -= 3;
}
}
reverse(res.begin(), res.end());
cout << res << '\n';
}
int main() {
int t = 1;
cin >> t;
for (int it = 0; it < t; ++it) {
solve();
}
return 0;
}
Идея: MikeMirzayanov, Aris
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define forn(i, n) for (int i = 0; i < int(n); i++)
void solve() {
string s;
cin >> s;
int n = s.size();
map<char, vector<int>> let_to_ind;
for (int i = 0; i < n; ++i) {
let_to_ind[s[i]].push_back(i);
}
int direction = (s[0] < s[n - 1]) ? 1 : -1;
vector<int> ans;
for (char c = s[0]; c != s[n - 1] + direction; c += direction) {
for (auto now : let_to_ind[c]) {
ans.push_back(now);
}
}
int cost = 0;
for (int i = 1; i < ans.size(); i++)
cost += abs(s[ans[i]] - s[ans[i - 1]]);
cout << cost << " " << ans.size() << '\n';
for (auto now : ans) {
cout << now + 1 << " ";
}
cout << '\n';
}
int main() {
int tests;
cin >> tests;
forn(tt, tests) {
solve();
}
}
1729D - Friends and the Restaurant
Идея: MikeMirzayanov, Aris, myav
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
void solve(){
int n;
cin >> n;
vector<ll>x(n), y(n);
vector<pair<ll, int>>dif(n);
for(auto &i : x) cin >> i;
for(auto &i: y) cin >> i;
for(int i = 0; i < n; i++){
dif[i].first = y[i] - x[i];
dif[i].second = i;
}
sort(dif.begin(), dif.end());
reverse(dif.begin(), dif.end());
int j = n - 1, cnt = 0;
for(int i = 0; i < n; i++){
while(j > i && dif[i].first + dif[j].first < 0) j--;
if(j <= i) break;
cnt++; j--;
}
cout << cnt << endl;
}
int main() {
int t;
cin >> t;
while(t--){
solve();
}
}
Идея: Gornak40, MikeMirzayanov
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define eb emplace_back
long long ask(int a, int b) {
cout << "? " << a << ' ' << b << endl;
long long x; cin >> x;
return x;
}
long long solve() {
for (int i = 2; i <= 26; i++) {
long long x = ask(1, i);
long long y = ask(i, 1);
if (x == -1) return i-1;
if (x != y) return x + y;
}
assert(false);
}
int main() {
long long ans = solve();
cout << "! " << ans << endl;
}
1729F - Kirei and the Linear Function
Идея: Gornak40
~~~~~
include <bits/stdc++.h>
define endl '\n'
using namespace std;
typedef pair<int, int> ipair;
const int MAXSZ = 200200; const int INF = 2e9;
inline int add(int a, int b) { return (a + b >= 9 ? a + b — 9 : a + b); }
inline int sub(int a, int b) { return (a < b ? a + 9 — b : a — b); }
inline int mul(int a, int b) { return a * b % 9; }
int sz, n, m; string s; int ps[MAXSZ]; vector D[9];
void build() { sz = s.size(); for (int md = 0; md < 9; ++md) D[md].clear(); for (int i = 0; i < sz; ++i) ps[i + 1] = ps[i] + (s[i] — '0'); for (int i = 0; i + n <= sz; ++i) D[(ps[i + n] — ps[i]) % 9].push_back(i); }
ipair solve(int l, int r, int k) { int x = (ps[r] — ps[l]) % 9; ipair ans {INF, INF}; for (int a = 0; a < 9; ++a) { int b = sub(k, mul(a, x)); if (D[a].empty() || D[b].empty()) continue; if (a != b) ans = min(ans, make_pair(D[a].front(), D[b].front())); else if (D[a].size() >= 2) ans = min(ans, make_pair(D[a].front(), D[a][1])); } if (ans == make_pair(INF, INF)) return {-2, -2}; return ans; }
int main() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); int t; cin >> t; while (t--) { cin >> s >> n >> m; build(); for (int i = 0; i < m; ++i) { int l, r, k; cin >> l >> r >> k, --l; auto [ans1, ans2] = solve(l, r, k); cout << ++ans1 << ' ' << ++ans2 << endl; } } }~~~~~
Идея: senjougaharin, MikeMirzayanov
~~~~~
include
include
const int N=505; const int Mod=1e9+7; char s[N],t[N]; int n,m; int f[N],g[N]; int p[N],tot; inline void Init(){ scanf("%s",s+1); scanf("%s",t+1); n=strlen(s+1); m=strlen(t+1); tot=0; for(int i=1;i+m-1<=n;i++){ bool flg=1; for(int j=1;j<=m;j++) if(s[i+j-1]!=t[j]) flg=0; if(flg) p[++tot]=i; } return ; } inline int addv(int x,int y){ int s=x+y; if(s>=Mod) s-=Mod; return s; } inline int subv(int x,int y){ int s=x-y; if(s<0) s+=Mod; return s; } inline void add(int&x,int y){ x=addv(x,y); return ; } inline void sub(int&x,int y){ x=subv(x,y); return ; } inline void Solve(){ memset(f,0x3f,sizeof(f)); memset(g,0,sizeof(g)); p[0]=-N; f[0]=0; g[0]=1; p[++tot]=n+m; for(int i=0;i<tot;i++){ int j=i+1; while(j<=tot&&p[j]<=p[i]+m-1) j++; for(int k=j;p[j]+m-1>=p[k]&&k<=tot;k++){ if(f[i]+1<f[k]){ f[k]=f[i]+1; g[k]=g[i]; } else if(f[i]+1==f[k]) add(g[k],g[i]); } } printf("%d %d\n",f[tot]-1,g[tot]); return ; } int T; int main(){ for(scanf("%d",&T);T;T--){ Init(); Solve(); } return 0; }~~~~~