Идея: Vladosiya
Разбор
Tutorial is loading...
Решение
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
Разбор
Tutorial is loading...
Решение
#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
Разбор
Tutorial is loading...
Решение
#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
Разбор
Tutorial is loading...
Решение
#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
Разбор
Tutorial is loading...
Решение
#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
Разбор
Tutorial is loading...
Решение
#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<int> 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
Разбор
Tutorial is loading...
Решение
#include<cstdio>
#include<cstring>
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;
}