Тут короткие разборы и решения задач второго тура отборочного этапа Олимпиады Университета Иннополис, который прошел 14 декабря 2019 года. Порешать задачи можно в тренировках: Innopolis Open 2019-2020, qualification, contest 2. Здесь еще был анонс и некоторые обсуждения.
Разборы не всегда полные, иногда описаны только некоторые идеи. Не стесняйтесь обсуждать задачи, может кто-нибудь из сообщества расскажет более подробно, как решать задачу.
102461A - Expression Formatting
Разбор
Tutorial is loading...
Решение на Python
s = input()
ans = ''
for c in s:
if c == '+' or c == '-' or c == '*' or c == '/':
ans += ' '
ans += c
ans += ' '
else:
ans += c
print(ans)
Авторы задачи: niyaznigmatul, pashka
102461B - Contest Rescheduling
Разбор
Tutorial is loading...
Решение на C++
#include <bits/stdc++.h>
using namespace std;
struct answer {
int move;
int start1;
int start2;
answer flip() const {
return {move, start2, start1};
}
bool operator<(answer const &a) const {
return move < a.move;
}
};
int const INF = 1 << 30;
answer fixFirst(int l1, int r1, int l2, int r2, int s1, int len1, int s2, int len2) {
if (s1 + len1 <= s2 || s2 + len2 <= s1)
return {0, s1, s2};
answer ret = {INF, -1, -1};
for (int x : {l1, s1, r1 - len1}) {
for (int y : {x - len2, x + len1}) {
if (y < l2 || y + len2 > r2)
continue;
answer cur = {abs(x - s1) + abs(y - s2), x, y};
ret = min(ret, cur);
}
}
return ret;
}
void solve() {
int l1, r1, l2, r2;
int s1, s2, len1, len2;
cin >> l1 >> r1 >> l2 >> r2;
cin >> s1 >> len1 >> s2 >> len2;
answer ans = min(fixFirst(l1, r1, l2, r2, s1, len1, s2, len2),
fixFirst(l2, r2, l1, r1, s2, len2, s1, len1).flip());
if (ans.move == INF) {
cout << "-1 -1\n";
} else {
cout << ans.start1 << ' ' << ans.start2 << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++)
solve();
}
Авторы задачи: niyaznigmatul, pashka
102461C - Advertisement Profit
Разбор
Tutorial is loading...
Решение на C++
#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
typedef pair<int, int> pii;
int const INF = (int)1e9 + 1e3;
void upd(int& a, int b) {
a = max(a, b);
}
const int init_subscr = 10000;
void solve() {
int n;
cin >> n;
vector<int> good;
for (int i = 0; i < n; ++i) {
int num;
cin >> num;
good.push_back(num);
}
sort(good.rbegin(), good.rend());
int m;
cin >> m;
vector<pii> bad;
int sum_bad = 0;
for (int i = 0; i < m; ++i) {
int num, cost;
cin >> cost >> num;
bad.push_back({num, cost});
sum_bad += cost;
}
sort(bad.begin(), bad.end(), [&](pii a, pii b) {
return a.ff * b.ss > b.ff * a.ss;
});
vector<int> pref = {0};
for (int num : good) {
pref.push_back(pref.back() + num);
}
vector<vector<vector<int>>> dp(2, vector<vector<int>>(m + 1, vector<int>(sum_bad + 1, -INF)));
dp[0][0][0] = 0;
for (int i = 0; i < m; ++i) {
for (int j = 0; j <= m; ++j) {
fill(dp[1][j].begin(), dp[1][j].end(), -INF);
}
for (int took = 0; took <= m; ++took) {
for (int sum = 0; sum <= sum_bad; ++sum) {
if (dp[0][took][sum] == -INF) {
continue;
}
upd(dp[1][took][sum], dp[0][took][sum]);
upd(dp[1][took + 1][sum + bad[i].ss], dp[0][took][sum] - bad[i].ff * sum);
}
}
swap(dp[0], dp[1]);
}
vector<int> ans(n + m + 1);
for (int i = 1; i <= n + m; ++i) {
ans[i] = -INF;
for (int j = max(0, i - m); j <= min(n, i); ++j) {
int start_subscr = pref[j] + init_subscr;
int left = i - j;
assert(0 <= left && left <= m);
for (int k = 0; k <= sum_bad; ++k) {
if (dp[0][left][k] == -INF) {
continue;
}
upd(ans[i], dp[0][left][k] + k * start_subscr);
}
}
}
int q;
cin >> q;
for (int i = 0; i < q; ++i) {
int num;
cin >> num;
cout << ans[num] << "\n";
}
}
int main() {
cout << setprecision(15) << fixed;
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
Авторы задачи: budalnik, Aksenov239, VArtem, niyaznigmatul
102461D - RSA factoring
Разбор
Tutorial is loading...
Решение на Kotlin
import java.math.BigInteger
import java.math.BigInteger.ONE
import java.math.BigInteger.ZERO
fun main() {
val (bits, k) = readLine()!!.split(" ").map { it.toInt() }
val n = BigInteger(readLine()!!, 16)
var sqrt = sqrt(n)
val divs = mutableSetOf<BigInteger>()
while (divs.size < k) {
sqrt++
val diff = sqrt * sqrt - n
val diffSqrt = sqrt(diff)
if (diffSqrt * diffSqrt == diff) {
divs.add(sqrt - diffSqrt)
divs.add(sqrt + diffSqrt)
}
}
val primeDivs = mutableSetOf<BigInteger>()
for (d1 in divs) {
for (d2 in divs) {
val gcd = d1.gcd(d2)
if (gcd.isProbablePrime(40)) {
primeDivs.add(gcd)
}
}
}
for (d in primeDivs) {
println(d.toString(16))
}
}
private fun sqrt(n: BigInteger): BigInteger {
var x = n
var y = (x + ONE) shr 1
while (y < x) {
x = y
y = (x + n / x) shr 1
}
return x
}
Автор задачи: VArtem
102461E - Black Friday
Разбор
Tutorial is loading...
Решение на C++
#include <bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 100;
int n;
ll S;
pair<pair<ll, ll>, int> q[maxn];
bool tak[maxn];
void print() {
vector<int> g;
ll ls = 0, rans = 0;
for (int i = 0; i < n; i++)
if (tak[i]) {
g.push_back(i);
ls += q[i].fr.fr;
rans = min(S, rans + q[i].fr.sc);
if (ls > S)
break;
}
reverse(g.begin(), g.end());
while (ls > S) {
ls -= q[g.back()].fr.fr;
g.pop_back();
}
cout << rans << '\n';
vector<ll> ans(n - 2);
for (int i : g) {
int id = q[i].sc;
if (id != -1) {
ls -= q[i].fr.fr;
ans[id] = min(q[i].fr.sc, rans - ls);
rans -= ans[id];
}
}
for (ll i : ans)
cout << i << ' ';
cout << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> S;
for (int i = 0; i < n; i++) {
q[i].sc = i;
cin >> q[i].fr.fr >> q[i].fr.sc;
}
sort(q, q + n);
int cnt = 0;
q[n++] = {{0, 0}, -1};
q[n++] = {{0, 0}, -1};
while (cnt < n && q[cnt].fr.fr * 7 <= S * 2)
cnt++;
if (cnt + 4 < n && q[cnt].fr.fr + q[cnt + 1].fr.fr + q[cnt + 2].fr.fr <= S) {
tak[cnt] = tak[cnt + 1] = tak[cnt + 2] = 1;
} else {
for (int i = 0; i < cnt; i++)
tak[i] = 1;
pair<ll, pair<int, int> > found = {-1, {0, 0}};
rotate(q + cnt, q + n - 2, q + n);
int id = cnt, pos = id + 1;
for (int i = n - 1; i >= cnt; i--) {
while (pos < i && q[i].fr.fr + q[pos].fr.fr <= S) {
if (q[pos].fr.sc > q[id].fr.sc)
id = pos;
pos++;
}
if (q[i].fr.fr <= S)
found = max(found, {q[i].fr.sc + q[id].fr.sc, {i, id}});
if (pos == i)
break;
}
tak[found.sc.fr] = tak[found.sc.sc] = 1;
}
print();
}
Авторы задачи: never_giveup, Burunduk1
Если решать задачу Е, поддерживая множество непересекающихся отрезков, то как тогда восстановить ответ?
При добавлении отрезка нужно не удалять старое множество отрезков, а перезаписывать его заного и обновлять новым отрезком. В конце у нас получится N множеств, каждое размером не более 90, поэтому уложится по памяти.
Теперь будем идти с конца по отрезкам, каждый раз либо включая текущий отрезок в ответ, либо нет. Множества, сохранённые вначале, помогут нам понять, можем/должны ли мы взять текущий отрезок в ответ или нет.