SRM 432
↑1420
Автор сета — nika.
FractalInfinity, с дебютом ;)
div2 250
Условие
В правильном слове нет не подряд идущих одинаковых букв. Сколько слов из входного вектора правильные?
div2 500 & div1 250
Условие
Дана прямоугольная бинарная матрица, за ход можно инвертировать произвольный столбец. Какого максимального числа единичных строк можно добиться за ровно K ходов?
Очевидно, что все единичные (одинаковые) строки могут быть получены только из одинаковых строк, число нулей в которых ≤K и совпадает с ним по четности.
div2 1000
Условие
На плоскости до 50 точек с разными ценами. Провести прямую так, чтобы абсолютная разность стоимостей двух полуплоскостей была наименьшей.
Достаточно проводить прямые через каждую пару точек. Пусть на прямой оказалось несколько точек. Очень маленькими сдвигами прямой мы можем добиться того, чтобы часть точек с одной стороны принадлежала одной полуплоскости, а часть — другой.
В качестве критерия принадлежности полуплоскостям и прямой можно использовать знак канонического уравнения прямой Ax+By+C при подстановке координат точки. Точки, лежащие на прямой, упорядочим по первой непостоянной координате.
div1 500
Условие
Нужно сконкатенировать строки, чтобы получилось правильное слово, либо указать, что это невозможно, либо возможно несколькими способами.
Переберем все буквы и склеим все кусочки, содержащие эту букву в конце, начале, или целиком состоящие из нее. При этом склеивание могло не привести к одной строке — нужно дополнительно проверить, можно ли тогда вообще получить правильное слово (MANY) или нельзя (IMPOSSIBLE). Кроме того, даже если осталась одна строка, она все равно может быть неправильной.
Автор сета — nika.
FractalInfinity, с дебютом ;)
div2 250
Условие
В правильном слове нет не подряд идущих одинаковых букв. Сколько слов из входного вектора правильные?
bool valid(const string& s) {
int was[26]; for (int i = 0; i < 26; ++i) was[i] = 0;
for (int i = 0, len = (int)s.length(); i < len; ++i) {
if ((i == 0 || s[i] != s[i-1]) && was[s[i] - 'a']) return false;
was[s[i] - 'a'] = 1;
}
return true;
}
class GroupedWordChecker
{
public:
int howMany(vector <string> words)
{
return count_if(words.begin(), words.end(), valid);
}
};
int was[26]; for (int i = 0; i < 26; ++i) was[i] = 0;
for (int i = 0, len = (int)s.length(); i < len; ++i) {
if ((i == 0 || s[i] != s[i-1]) && was[s[i] - 'a']) return false;
was[s[i] - 'a'] = 1;
}
return true;
}
class GroupedWordChecker
{
public:
int howMany(vector <string> words)
{
return count_if(words.begin(), words.end(), valid);
}
};
div2 500 & div1 250
Условие
Дана прямоугольная бинарная матрица, за ход можно инвертировать произвольный столбец. Какого максимального числа единичных строк можно добиться за ровно K ходов?
Очевидно, что все единичные (одинаковые) строки могут быть получены только из одинаковых строк, число нулей в которых ≤K и совпадает с ним по четности.
class LampsGrid
{
public:
int mostLit(vector <string> a, int K)
{
int n = a.size(), res = 0;
for (int i = 0; i < n; ++i) {
int z = count(a[i].begin(), a[i].end(), '0');
if (z <= K && z % 2 == K % 2) {
int cres = count(a.begin(), a.end(), a[i]);
if (cres > res) res = cres;
}
}
return res;
}
};
{
public:
int mostLit(vector <string> a, int K)
{
int n = a.size(), res = 0;
for (int i = 0; i < n; ++i) {
int z = count(a[i].begin(), a[i].end(), '0');
if (z <= K && z % 2 == K % 2) {
int cres = count(a.begin(), a.end(), a[i]);
if (cres > res) res = cres;
}
}
return res;
}
};
div2 1000
Условие
На плоскости до 50 точек с разными ценами. Провести прямую так, чтобы абсолютная разность стоимостей двух полуплоскостей была наименьшей.
Достаточно проводить прямые через каждую пару точек. Пусть на прямой оказалось несколько точек. Очень маленькими сдвигами прямой мы можем добиться того, чтобы часть точек с одной стороны принадлежала одной полуплоскости, а часть — другой.
В качестве критерия принадлежности полуплоскостям и прямой можно использовать знак канонического уравнения прямой Ax+By+C при подстановке координат точки. Точки, лежащие на прямой, упорядочим по первой непостоянной координате.
vector<int> x, y;
bool sortbyt(int i1, int i2)
{
return x[i1] != x[i2] ? x[i1] < x[i2] : y[i1] < y[i2];
}
class TreesDivision
{
public:
int minDifference(vector <int> X, vector <int> Y, vector <int> income)
{
x = X; y = Y; int n = (int)x.size(), res = 1000000000;
for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) {
int diff = 0;
int a = y[i] - y[j], b = x[j] - x[i], c = -(a * x[i] + b * y[i]);
vector<int> online;
int ls = 0, rs = 0;
for (int k = 0; k < n; ++k) {
int t = a * x[k] + b * y[k] + c;
if (t == 0) { online.push_back(k); rs += income[k]; }
else diff += t > 0 ? income[k] : -income[k];
}
sort(online.begin(), online.end(), sortbyt);
int no = (int)online.size();
if (res > abs(diff + rs)) res = abs(diff + rs);
if (res > abs(diff - rs)) res = abs(diff - rs);
for (int k = 0; k < no; ++k) {
ls += income[online[k]]; rs -= income[online[k]];
if (res > abs(diff - ls + rs)) res = abs(diff - ls + rs);
if (res > abs(diff + ls - rs)) res = abs(diff + ls - rs);
}
}
return res;
}
};
bool sortbyt(int i1, int i2)
{
return x[i1] != x[i2] ? x[i1] < x[i2] : y[i1] < y[i2];
}
class TreesDivision
{
public:
int minDifference(vector <int> X, vector <int> Y, vector <int> income)
{
x = X; y = Y; int n = (int)x.size(), res = 1000000000;
for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) {
int diff = 0;
int a = y[i] - y[j], b = x[j] - x[i], c = -(a * x[i] + b * y[i]);
vector<int> online;
int ls = 0, rs = 0;
for (int k = 0; k < n; ++k) {
int t = a * x[k] + b * y[k] + c;
if (t == 0) { online.push_back(k); rs += income[k]; }
else diff += t > 0 ? income[k] : -income[k];
}
sort(online.begin(), online.end(), sortbyt);
int no = (int)online.size();
if (res > abs(diff + rs)) res = abs(diff + rs);
if (res > abs(diff - rs)) res = abs(diff - rs);
for (int k = 0; k < no; ++k) {
ls += income[online[k]]; rs -= income[online[k]];
if (res > abs(diff - ls + rs)) res = abs(diff - ls + rs);
if (res > abs(diff + ls - rs)) res = abs(diff + ls - rs);
}
}
return res;
}
};
div1 500
Условие
Нужно сконкатенировать строки, чтобы получилось правильное слово, либо указать, что это невозможно, либо возможно несколькими способами.
Переберем все буквы и склеим все кусочки, содержащие эту букву в конце, начале, или целиком состоящие из нее. При этом склеивание могло не привести к одной строке — нужно дополнительно проверить, можно ли тогда вообще получить правильное слово (MANY) или нельзя (IMPOSSIBLE). Кроме того, даже если осталась одна строка, она все равно может быть неправильной.
bool valid(const string& s) {
int was[26]; for (int i = 0; i < 26; ++i) was[i] = 0;
for (int i = 0, len = (int)s.length(); i < len; ++i) {
if ((i == 0 || s[i] != s[i-1]) && was[s[i] - 'a']) return false;
was[s[i] - 'a'] = 1;
}
return true;
}
class GroupedWord
{
public:
bool onechar(const string& s) {
for (int i = 0, len = (int)s.length(); i < len - 1; ++i) if (s[i] != s[i+1]) return false;
return true;
}
string restore(vector <string> a)
{
for (char c = 'a'; c <= 'z'; ++c) {
vector<string> na; string le, mi, ri;
for (size_t i = 0, len = a.size(); i < len; ++i) {
char f = *a[i].begin(), l = *a[i].rbegin();
if (f == c) {
if (onechar(a[i])) mi += a[i];
else ri += a[i];
} else if (l == c) le += a[i];
else na.push_back(a[i]);
}
if (le + mi + ri != "") na.push_back(le + mi + ri);
a = na;
}
string sum = accumulate(a.begin(), a.end(), string());
if (!valid(sum)) return "IMPOSSIBLE";
if (a.size() > 1) return "MANY";
return a[0];
}
};
int was[26]; for (int i = 0; i < 26; ++i) was[i] = 0;
for (int i = 0, len = (int)s.length(); i < len; ++i) {
if ((i == 0 || s[i] != s[i-1]) && was[s[i] - 'a']) return false;
was[s[i] - 'a'] = 1;
}
return true;
}
class GroupedWord
{
public:
bool onechar(const string& s) {
for (int i = 0, len = (int)s.length(); i < len - 1; ++i) if (s[i] != s[i+1]) return false;
return true;
}
string restore(vector <string> a)
{
for (char c = 'a'; c <= 'z'; ++c) {
vector<string> na; string le, mi, ri;
for (size_t i = 0, len = a.size(); i < len; ++i) {
char f = *a[i].begin(), l = *a[i].rbegin();
if (f == c) {
if (onechar(a[i])) mi += a[i];
else ri += a[i];
} else if (l == c) le += a[i];
else na.push_back(a[i]);
}
if (le + mi + ri != "") na.push_back(le + mi + ri);
a = na;
}
string sum = accumulate(a.begin(), a.end(), string());
if (!valid(sum)) return "IMPOSSIBLE";
if (a.size() > 1) return "MANY";
return a[0];
}
};
