Тут короткие разборы и решения задач первого тура отборочного этапа Олимпиады Университета Иннополис, который прошел 24 ноября 2019 года. Порешать задачи можно в тренировках: Innopolis Open 2019-2020, qualification, contest 1
По некоторым задачам разбора нет, и мы еще не знаем, появится ли. Не стесняйтесь обсуждать задачи, может кто-нибудь из сообщества расскажет, как решать задачу.
102436A - Cool Water
Разбор
Tutorial is loading...
Решение перебором
a = int(input())
b = int(input())
x = int(input())
T = 100
V = 1000
if x == T:
print((V // a) * a)
elif x == 0:
print((V // b) * b)
else:
for i in range(1,V+1):
for j in range(1,V+1):
if a*i*100 / (a*i + b*j) == x:
mn = a*i + b*j
print((V // mn) * mn)
return
print(0)
Решение формулой
from math import gcd
a = int(input())
b = int(input())
x = int(input())
T = 100
V = 1000
mn = a * b * 100 // gcd(b * x, a * (100 - x))
print((V // mn) * mn)
Авторы задачи: Aksenov239 и dusja.ds
102436B - Trie Minimization
Разбор
Tutorial is loading...
Решение на C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false), cin.tie(0);
int n;
cin >> n;
vector<map<int, int>> letters;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
for (int j = 0; j < (int) s.size(); j++) {
if (j >= (int) letters.size()) letters.emplace_back();
letters[j][s[j] - 'a']++;
}
}
int ans = 0;
for (auto &e: letters) {
int all = 0;
int best = 0;
for (auto &f : e) {
all += f.second;
best = max(best, f.second);
}
ans += all - best;
}
cout << ans << endl;
}
Авторы задачи: Aksenov239 и iilnar
102436C - Painting Plan
Разбор
Tutorial is loading...
Решение на C++
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector <int> v(2 * n, 0);
for (int i = 0; i < 2 * n; i++) {
cin >> v[i];
}
vector < pair <int, int> > w;
for (int i = 0; i < n; i++) {
if (i + 1 < n) {
w.push_back(make_pair(v[2 * i + 2] - v[2 * i + 1], i));
}
k -= v[2 * i + 1] - v[2 * i];
}
if (k < 0) {
cout << "No\n";
return 0;
}
vector <bool> dp(k + 1, false);
vector <pair <int, int>> parent(k + 1);
dp[0] = true;
for (size_t j = 0; j < w.size(); j++) {
for (int i = k; i >= 0; i--) {
if (i + w[j].first <= k && dp[i]) {
if (!dp[i + w[j].first]) {
dp[i + w[j].first] = true;
parent[i + w[j].first] = w[j];
}
}
}
}
if (!dp[k]) {
cout << "No\n";
return 0;
}
cout << "Yes\n";
vector <int> ans;
for (int cur = k; cur > 0; cur -= parent[cur].first) {
ans.push_back(2 * parent[cur].second + 1);
ans.push_back(2 * parent[cur].second + 2);
}
vector <pair <int, int>> res;
sort(ans.begin(), ans.end());
size_t id = 0;
vector <int> not_used;
for (int i = 0; i < 2 * n; i++) {
while (id < ans.size() && ans[id] < i) id++;
if (id == ans.size() || i != ans[id]) {
not_used.push_back(i);
}
}
for (size_t i = 0; i < ans.size(); i += 2) {
res.push_back({ans[i], ans[i + 1]});
}
for (size_t i = 0; i < not_used.size(); i += 2) {
res.push_back({not_used[i], not_used[i + 1]});
}
for (auto &i : res) {
cout << i.first + 1 << ' ' << i.second + 1 << '\n';
}
return 0;
}
Автор задачи: disa
102436D - Subset ``AND''
Разбор
Tutorial is loading...
Решение на Kotlin
import java.io.PrintWriter
import java.util.*
fun main() {
val `in` = Scanner(System.`in`)
val out = PrintWriter(System.out)
val k = `in`.nextInt()
val (result, bits) = solve(k)
out.println(result.size)
out.println(result.joinToString(separator = " ") { it.toString() })
out.close()
}
fun solve(k: Int): Pair<List<Long>, Int> {
if (k == 1) {
return Pair(mutableListOf<Long>(1), 0);
}
if (k % 2 == 0) {
var (result, bits) = solve(k / 2)
bits++
result = result.map { it * 2 + 1 }.toMutableList()
result.add((1.toLong() shl bits) - 2)
return Pair(result, bits)
} else {
var (result, bits) = solve(k - 1)
bits++
result = result.map { it * 2 + 1}.toMutableList()
result.add(0)
return Pair(result, bits)
}
}
Авторы задачи: VArtem и Aksenov239
102436E - Stamp
Решение за линейное время на C++
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
vector<string> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
vector<int> mx(2 * n, m);
const int INF = 1e9;
int minm = m;
int x = 0;
for (int j = 0; j < m; j++) {
if (a[n - 1][j] == '.') {
x++;
} else {
x = 0;
}
minm = max(minm, m + x);
}
mx[2 * n - 1] = minm;
vector<int> up(m), l(m), r(m);
for (int i = 0; i < m; i++) {
up[i] = -1;
l[i] = 0;
r[i] = m - 1;
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (a[i][j] == 'X') {
up[j] = i;
l[j] = 0;
r[j] = m - 1;
int k = j - 1;
while (k >= 0 && a[i][k] == '.') {
r[k] = min(r[k], j - 1);
k--;
}
k = j + 1;
while (k < m && a[i][k] == '.') {
l[k] = max(l[k], j + 1);
k++;
}
}
}
for (int j = 0; j < m; j++) {
if (a[i][j] == 'X') continue;
int mm = m + (r[j] - l[j] + 1);
int nn = up[j] == -1 ? 2 * n - 1 : n + (i - up[j]) - 1;
if (l[j] == 0 || r[j] == m - 1) mm = INF;
mx[nn] = max(mx[nn], mm);
}
}
for (int i = 2 * n - 1; i > 0; i--) {
mx[i - 1] = max(mx[i - 1], mx[i]);
}
int bestn = 2 * n;
int bestm = 2 * m;
int best = bestn * bestm;
for (int i = n; i < 2 * n; i++) {
if (mx[i] < INF) {
if (i * mx[i] < best) {
best = i * mx[i];
bestn = i;
bestm = mx[i];
}
}
}
cout << bestn << " " << bestm << "\n";
return 0;
}
В задаче C код, который был сдан во время контеста на 66 баллов, при сдаче в тренировках получает МЛ1..
Вы же знаете, почему так, правда?
Как можно развить следующую идею: давайте предположим, что конечным множеством всех чисел будет множество чисел от $$$0$$$ до $$$k-1$$$. Скажем, что варианта лучше мы найти не можем: взяв в данном множестве любое побитовое И для чисел мы не получим числа меньше нуля, и не получим числа больше $$$k-1$$$. В таком случае, давайте скажем, сколькими способами мы можем получить некоторое число $$$z$$$, где $$$z=a&b$$$, а $$$a$$$ и $$$b$$$ — два числа из нашего множества, при чем $$$z < a$$$ и $$$z < b$$$. В таком случае, каждое $$$z$$$ полученное не более, чем одним способом будет являться ответом на задачу. https://codeforces.me/gym/102436/submission/65681890
Я написал оптимальную версию этого кода. $$$d_i$$$ это сколько чисел меньше $$$k$$$, которые надмножество $$$i$$$ в битовом представлении. $$$f_i$$$ это сколько пар $$$x$$$ и $$$y$$$ ($$$x, y < k$$$), что их and это $$$i$$$.
На тесте
519010 60выдает больше 125 чисел.Я нашел баг в прошлом решении, который не проявлялся. Вместо
f[i] - d[i]должно бытьf[i] - (2 * d[i] - 1), что подсказало, как еще быстрее сгенерить этот список. Если захотеть, можно еще быстрее, мне кажется.До такого решения, как у вас, мы не дошли. Жалко, что лимит только 125 поставили, очень неплохая получилась идея для конструкции.