SRM 438
Автор сета — vexorian. Сет получился жутко челленджабельным, и, пожалуй, слишком технически сложным. В div1 все три задачи порвал только Petr, во div2 третью задачу не сдал вообще никто. К слову, div2 1000 была такая же, как и div1 500, от сдачи которой я был всего в одном пропущенном касте, что лишний раз доказывает, что даже бледно-желтый топкодер круче 856 обычных серо-зеленых программистов :) Не могу не поздравить своих френдов 
e_maxx_wasm и renatm со вторым и третьим абсолютным местом соответственно.
↓1631 (сдал две задачи, что для меня редкость, но мою радость слегка омрачило то, что первую заЧили, а вторая упала)
div2 250
Дан набор счастливых чисел. Несчастливый интервал — интервал [A;B] (A < B), не содержащий ни одного счастливого числа. Дано число N (не больше максимума из набора счастливых чисел), найти количество несчастливых интервалов, которые его содержат.
Отсортируем набор счастливых чисел. Если N в него входит, то ответ равен 0. Если нет, тогда рассмотрим интервал между двумя ближайшими счастливыми числами, который содержит N. Левую границу интервала можно поставить на любое из N−L чисел ≤N, правую — на любое из R−N чисел ≥N, но вот поставить одновременно их на N нельзя: по условию A < B.
div1 300
Число тем счастливее, чем 1) в меньшем количестве несчастливых интервалов оно содержится; 2) оно меньше. Найти N самых счастливых чисел.
В 0 несчастливых интервалов содержатся сами счастливые числа, и числа, находящиеся в дырках размера 1, поэтому сразу поместим их в ответ, отсортируем, и вернем его префикс, если этого хватило (про дырки размера 1 я на контесте забыл). Затем для каждой оставшейся дырки будем хранить ее левую и правую границу (очевидно, что чем ближе число в дырке к счастливому числу, тем в меньшее число несчастливых интервалов оно попадает — минимум произведения чисел равной суммы). Пока в дырках есть элементы, а ответ неполон, будем искать самое счастливое число среди границ, найдя, сдвинем соответствующую границу и добавим число в ответ. Если все дырки исчерпаны, а ответ все еще неполон, доведем его до кондиции «бесконечно несчастными» числами больше максимума счастливого набора.
div2 1000 & div1 500
Строкой INPUT (изначально до 50 символов) заменяют каждый символ $ в другой строке PROGRAM (до 50 символов, первый всегда $), с полученной строкой поступают так же, и так S (до 109) раз. Найти подстроку полученной строки (не длиннее 100 символов, начало не дальше 109, если результат итерирования недостаточно длинен, дополнить дефисами).
Будем искать каждый символ результата отдельно. Заметим, что если $ в строке один, то все итерации сводятся к добавлению в конец INPUT оставшейся PROGRAM S раз. Если $ не один, то каждая итерация, как минимум, удваивает длину строки, а значит, меньше чем за 32 шага мы получаем более не изменяющийся префикс длины S+100. Найти длину строки после STEP итераций легко, а значит, посимвольно просматривая PROGRAM, мы можем найти, какой символ строки на предыдущем шаге или какой символ самой программы у нас просят. Обратите внимание на условие if (m + (long long) times * k > idx). Из-за этого каста я получил бублик!
div2 500 & div1 1000
Это не ошибка, div2 500 решалась тем же самым кодом, но содержало коренное отличие в ограничениях, что позволяло даже руками разобрать отдельные случаи.
Шахта может запускать неограниченное количество ракет, они вылетают из нее за takeOffTime секунд, а затем нужно еще rechargeTime минут, чтобы подготовить запуск следующей. Ракета летит до цели distance/missileSpeed минут, после чего цель полностью уничтожается. Даны координаты шахт (до 50) и целей (до 50), надо найти минимальное время, через которое все цели могут быть уничтожены.
...В воздухе отчетливо запахло женским плачем из DefCon... Задачу можно решить бинарным поиском по ответу. Строим двудольный граф, где в одной доле нумерованные ракеты (по числу целей в каждой шахте), а в другой цели; отношение связности — успеет ли ракета уничтожить цель за предполагаемое время (отметим подлость в условии: шахту ракета покидает за секунды, а готовится и летит в минутах!). Чтобы решение не получило TL, в двудольный граф будем помещать только те ракеты, которые хоть куда-то успеют, а перед алгоритмом Куна вставим жадное предзаполнение. Обратите внимание на каст к double перед каждым слагаемым в расчете расстояния. Если хотя бы один будет пропущен, произойдет переполнение. 1.987 секунд. Еще никогда Штирлиц не был так близко к провалу...
Не забудьте, что завтра (вторник, 21 апреля), в 11:00 по Москве, в Стокгольме начнется финал чемпионата мира по командному программированию ACM ICPC. Возможно, тут будет трансляция, как в прошлом году.
e_maxx_wasm и renatm со вторым и третьим абсолютным местом соответственно.↓1631 (сдал две задачи, что для меня редкость, но мою радость слегка омрачило то, что первую заЧили, а вторая упала)
div2 250
Дан набор счастливых чисел. Несчастливый интервал — интервал [A;B] (A < B), не содержащий ни одного счастливого числа. Дано число N (не больше максимума из набора счастливых чисел), найти количество несчастливых интервалов, которые его содержат.
Отсортируем набор счастливых чисел. Если N в него входит, то ответ равен 0. Если нет, тогда рассмотрим интервал между двумя ближайшими счастливыми числами, который содержит N. Левую границу интервала можно поставить на любое из N−L чисел ≤N, правую — на любое из R−N чисел ≥N, но вот поставить одновременно их на N нельзя: по условию A < B.
class UnluckyNumbers {
public:
int f(int l, int a, int r) { return (a - l) * (r - a) - 1; }
int getCount(vector <int> luckySet, int n) {
int m = (int) luckySet.size();
sort(luckySet.begin(), luckySet.end());
for (int i = 0; i < m; ++i) {
if (n == luckySet[i]) return 0;
if (n < luckySet[i]) {
return f(i == 0 ? 0 : luckySet[i-1], n, luckySet[i]);
}
}
return -1;
}
};
public:
int f(int l, int a, int r) { return (a - l) * (r - a) - 1; }
int getCount(vector <int> luckySet, int n) {
int m = (int) luckySet.size();
sort(luckySet.begin(), luckySet.end());
for (int i = 0; i < m; ++i) {
if (n == luckySet[i]) return 0;
if (n < luckySet[i]) {
return f(i == 0 ? 0 : luckySet[i-1], n, luckySet[i]);
}
}
return -1;
}
};
div1 300
Число тем счастливее, чем 1) в меньшем количестве несчастливых интервалов оно содержится; 2) оно меньше. Найти N самых счастливых чисел.
В 0 несчастливых интервалов содержатся сами счастливые числа, и числа, находящиеся в дырках размера 1, поэтому сразу поместим их в ответ, отсортируем, и вернем его префикс, если этого хватило (про дырки размера 1 я на контесте забыл). Затем для каждой оставшейся дырки будем хранить ее левую и правую границу (очевидно, что чем ближе число в дырке к счастливому числу, тем в меньшее число несчастливых интервалов оно попадает — минимум произведения чисел равной суммы). Пока в дырках есть элементы, а ответ неполон, будем искать самое счастливое число среди границ, найдя, сдвинем соответствующую границу и добавим число в ответ. Если все дырки исчерпаны, а ответ все еще неполон, доведем его до кондиции «бесконечно несчастными» числами больше максимума счастливого набора.
class UnluckyIntervals {
public:
// Количество несчастливых интервалов
long long f(int l, int a, int r)
{
return (long long) (a - l) * (r - a) - 1;
}
vector <int> getLuckiest(vector <int> luckySet, int n) {
int m = (int) luckySet.size();
sort(luckySet.begin(), luckySet.end());
int rem = luckySet.back() - m;
vector<int> sl(m + 1), sr(m + 1);
vector<int> res;
// Все элементы luckySet и из дырок размера 1 в ответ
res = luckySet;
for (int i = 0; i < m; ++i) {
if (luckySet[i] - (i == 0 ? 0 : luckySet[i-1]) == 2) {
res.push_back(luckySet[i] - 1);
--rem;
}
}
sort(res.begin(), res.end());
if (res.size() >= n) return vector<int>(res.begin(), res.begin() + n);
// Заполняем массивы левыми и правыми элементами дырок
sl[0] = 1;
for (int i = 0; i < m; ++i) {
if (luckySet[i] - (i == 0 ? 0 : luckySet[i-1]) == 2) sr[i] = luckySet[i] - 2;
else sr[i] = luckySet[i] - 1;
sl[i+1] = luckySet[i] + 1;
}
sr[m] = 2100000000;
for (int i = (int) res.size(); i < n; ++i) {
// Пока в дырках остаются элементы, ищем лучший
if (rem) {
long long bestz = 1LL << 62, z;
int best = -1; char bests;
for (int j = 0; j < m; ++j) if (sl[j] <= sr[j]) {
z = f(j == 0 ? 0 : luckySet[j-1], sl[j], luckySet[j]);
if (z < bestz) { bestz = z; best = j; bests = 'l'; }
z = f(j == 0 ? 0 : luckySet[j-1], sr[j], luckySet[j]);
if (z < bestz) { bestz = z; best = j; bests = 'r'; }
}
--rem;
if (bests == 'l') {
res.push_back(sl[best]); ++sl[best];
} else if (bests == 'r') {
res.push_back(sr[best]); --sr[best];
}
} else break;
}
// Забиваем ответ оставшимся бесконечным хвостом
for (int i = (int) res.size(), num = luckySet[m-1] + 1; i < n; ++i, ++num) res.push_back(num);
return res;
}
};
public:
// Количество несчастливых интервалов
long long f(int l, int a, int r)
{
return (long long) (a - l) * (r - a) - 1;
}
vector <int> getLuckiest(vector <int> luckySet, int n) {
int m = (int) luckySet.size();
sort(luckySet.begin(), luckySet.end());
int rem = luckySet.back() - m;
vector<int> sl(m + 1), sr(m + 1);
vector<int> res;
// Все элементы luckySet и из дырок размера 1 в ответ
res = luckySet;
for (int i = 0; i < m; ++i) {
if (luckySet[i] - (i == 0 ? 0 : luckySet[i-1]) == 2) {
res.push_back(luckySet[i] - 1);
--rem;
}
}
sort(res.begin(), res.end());
if (res.size() >= n) return vector<int>(res.begin(), res.begin() + n);
// Заполняем массивы левыми и правыми элементами дырок
sl[0] = 1;
for (int i = 0; i < m; ++i) {
if (luckySet[i] - (i == 0 ? 0 : luckySet[i-1]) == 2) sr[i] = luckySet[i] - 2;
else sr[i] = luckySet[i] - 1;
sl[i+1] = luckySet[i] + 1;
}
sr[m] = 2100000000;
for (int i = (int) res.size(); i < n; ++i) {
// Пока в дырках остаются элементы, ищем лучший
if (rem) {
long long bestz = 1LL << 62, z;
int best = -1; char bests;
for (int j = 0; j < m; ++j) if (sl[j] <= sr[j]) {
z = f(j == 0 ? 0 : luckySet[j-1], sl[j], luckySet[j]);
if (z < bestz) { bestz = z; best = j; bests = 'l'; }
z = f(j == 0 ? 0 : luckySet[j-1], sr[j], luckySet[j]);
if (z < bestz) { bestz = z; best = j; bests = 'r'; }
}
--rem;
if (bests == 'l') {
res.push_back(sl[best]); ++sl[best];
} else if (bests == 'r') {
res.push_back(sr[best]); --sr[best];
}
} else break;
}
// Забиваем ответ оставшимся бесконечным хвостом
for (int i = (int) res.size(), num = luckySet[m-1] + 1; i < n; ++i, ++num) res.push_back(num);
return res;
}
};
div2 1000 & div1 500
Строкой INPUT (изначально до 50 символов) заменяют каждый символ $ в другой строке PROGRAM (до 50 символов, первый всегда $), с полученной строкой поступают так же, и так S (до 109) раз. Найти подстроку полученной строки (не длиннее 100 символов, начало не дальше 109, если результат итерирования недостаточно длинен, дополнить дефисами).
Будем искать каждый символ результата отдельно. Заметим, что если $ в строке один, то все итерации сводятся к добавлению в конец INPUT оставшейся PROGRAM S раз. Если $ не один, то каждая итерация, как минимум, удваивает длину строки, а значит, меньше чем за 32 шага мы получаем более не изменяющийся префикс длины S+100. Найти длину строки после STEP итераций легко, а значит, посимвольно просматривая PROGRAM, мы можем найти, какой символ строки на предыдущем шаге или какой символ самой программы у нас просят. Обратите внимание на условие if (m + (long long) times * k > idx). Из-за этого каста я получил бублик!
class EndlessStringMachine {
public:
int m, n, k;
string in, pr;
char get(int times, int idx)
{
// Нас просят отдать символ из начального входа
if (times == 0) return m > idx ? in[idx] : '-';
// В программе всего один доллар
if (n == 1) {
if (m + (long long) times * k > idx) return idx >= m ? pr[(idx - m) % k + 1] : in[idx];
else return '-';
// В программе много долларов
} else {
long long cm = m * n + k, cmp = m, read; int step;
// Ищем количество шагов, достаточное для выдачи ответа
for (step = 1; cm <= idx; cmp = cm, cm = cm * n + k, ++step);
// До этого индекса процесс не дотянется
if (step > times) return '-';
for (int i = 0, read = 0; i < n + k; ++i) {
// Здесь выход предыдущей итерации
if (pr[i] == '$') {
read += cmp;
if (read > idx) return get(min(step, times - 1), idx - (read - cmp));
// Здесь символ текущей программы
} else {
++read;
if (read > idx) return pr[i];
}
}
}
}
string getFragment(string input, string program, int s, int min, int max) {
m = (int) input.length();
n = count(program.begin(), program.end(), '$');
k = (int) program.length() - n;
in = input; pr = program;
string res;
for (int i = min; i <= max; ++i) {
res.push_back(get(s, i - 1));
}
return res;
}
};
public:
int m, n, k;
string in, pr;
char get(int times, int idx)
{
// Нас просят отдать символ из начального входа
if (times == 0) return m > idx ? in[idx] : '-';
// В программе всего один доллар
if (n == 1) {
if (m + (long long) times * k > idx) return idx >= m ? pr[(idx - m) % k + 1] : in[idx];
else return '-';
// В программе много долларов
} else {
long long cm = m * n + k, cmp = m, read; int step;
// Ищем количество шагов, достаточное для выдачи ответа
for (step = 1; cm <= idx; cmp = cm, cm = cm * n + k, ++step);
// До этого индекса процесс не дотянется
if (step > times) return '-';
for (int i = 0, read = 0; i < n + k; ++i) {
// Здесь выход предыдущей итерации
if (pr[i] == '$') {
read += cmp;
if (read > idx) return get(min(step, times - 1), idx - (read - cmp));
// Здесь символ текущей программы
} else {
++read;
if (read > idx) return pr[i];
}
}
}
}
string getFragment(string input, string program, int s, int min, int max) {
m = (int) input.length();
n = count(program.begin(), program.end(), '$');
k = (int) program.length() - n;
in = input; pr = program;
string res;
for (int i = min; i <= max; ++i) {
res.push_back(get(s, i - 1));
}
return res;
}
};
div2 500 & div1 1000
Это не ошибка, div2 500 решалась тем же самым кодом, но содержало коренное отличие в ограничениях, что позволяло даже руками разобрать отдельные случаи.
Шахта может запускать неограниченное количество ракет, они вылетают из нее за takeOffTime секунд, а затем нужно еще rechargeTime минут, чтобы подготовить запуск следующей. Ракета летит до цели distance/missileSpeed минут, после чего цель полностью уничтожается. Даны координаты шахт (до 50) и целей (до 50), надо найти минимальное время, через которое все цели могут быть уничтожены.
...В воздухе отчетливо запахло женским плачем из DefCon... Задачу можно решить бинарным поиском по ответу. Строим двудольный граф, где в одной доле нумерованные ракеты (по числу целей в каждой шахте), а в другой цели; отношение связности — успеет ли ракета уничтожить цель за предполагаемое время (отметим подлость в условии: шахту ракета покидает за секунды, а готовится и летит в минутах!). Чтобы решение не получило TL, в двудольный граф будем помещать только те ракеты, которые хоть куда-то успеют, а перед алгоритмом Куна вставим жадное предзаполнение. Обратите внимание на каст к double перед каждым слагаемым в расчете расстояния. Если хотя бы один будет пропущен, произойдет переполнение. 1.987 секунд. Еще никогда Штирлиц не был так близко к провалу...
class FeudaliasWar {
public:
double dist(int x1, int y1, int x2, int y2)
{
return sqrt((double) (x1-x2) * (x1-x2) + (double) (y1-y2) * (y1-y2));
}
bool kuhn_dfs(int v, const vector< vector<int> >& g, vector<int>& mt, vector<bool>& used)
{
if (used[v]) return false;
used[v] = true;
for (int i = 0, len = (int) g[v].size(); i < len; ++i) {
int to = g[v][i];
if (mt[to] == -1 || kuhn_dfs(mt[to], g, mt, used)) {
mt[to] = v;
return true;
}
}
return false;
}
int kuhn(const vector< vector<double> >& g, double t)
{
// В двудольный граф добавляются ракеты, которые могут куда-нибудь успеть
int n = (int) g.size(), k = (int) g[0].size(), missiles = 0;
vector< vector<int> > graph;
for (int i = 0; i < n; ++i) {
vector<int> link;
for (int j = 0; j < k; ++j) {
if (g[i][j] <= t) link.push_back(j);
}
if (!link.empty()) {
graph.push_back(link);
++missiles;
}
}
// Жадное предзаполнение паросочетания
vector<int> mt(k, -1);
vector<bool> used, used1(missiles);
for (int i = 0; i < missiles; ++i) {
for (int j = 0, len = (int) graph[i].size(); j < len; ++j) {
if (mt[graph[i][j]] == -1) {
mt[graph[i][j]] = i;
used1[i] = true;
break;
}
}
}
// Поиск максимального паросочетания
for (int i = 0; i < missiles; ++i) {
if (used1[i]) continue;
used.assign(missiles, false);
kuhn_dfs(i, graph, mt, used);
}
// Число пораженных баз
return count_if(mt.begin(), mt.end(), bind2nd(not_equal_to<int>(), -1));
}
double getMinimumTime(vector <int> baseX, vector <int> baseY, vector <int> siloX, vector <int> siloY,
int takeOffTime, int rechargeTime, int missileSpeed)
{
int siloses = (int) siloX.size(), bases = (int) baseX.size();
// Время полета bases ракет из siloses шахт к bases базам
vector< vector<double> > g(siloses * bases, vector<double>(bases));
for (int silo = 0; silo < siloses; ++silo) for (int missile = 0; missile < bases; ++missile) {
for (int base = 0; base < bases; ++base) {
g[silo * bases + missile][base] =
(double) (missile + 1) * takeOffTime / 60 + missile * rechargeTime +
dist(siloX[silo], siloY[silo], baseX[base], baseY[base]) / missileSpeed;
}
}
// Бинарный поиск по времени
double l = 0.0, r = 1e7, eps = 1e-9, c;
while (r - l > eps) {
c = (r + l) / 2;
if (kuhn(g, c) == bases) r = c;
else l = c;
}
return c;
}
};
public:
double dist(int x1, int y1, int x2, int y2)
{
return sqrt((double) (x1-x2) * (x1-x2) + (double) (y1-y2) * (y1-y2));
}
bool kuhn_dfs(int v, const vector< vector<int> >& g, vector<int>& mt, vector<bool>& used)
{
if (used[v]) return false;
used[v] = true;
for (int i = 0, len = (int) g[v].size(); i < len; ++i) {
int to = g[v][i];
if (mt[to] == -1 || kuhn_dfs(mt[to], g, mt, used)) {
mt[to] = v;
return true;
}
}
return false;
}
int kuhn(const vector< vector<double> >& g, double t)
{
// В двудольный граф добавляются ракеты, которые могут куда-нибудь успеть
int n = (int) g.size(), k = (int) g[0].size(), missiles = 0;
vector< vector<int> > graph;
for (int i = 0; i < n; ++i) {
vector<int> link;
for (int j = 0; j < k; ++j) {
if (g[i][j] <= t) link.push_back(j);
}
if (!link.empty()) {
graph.push_back(link);
++missiles;
}
}
// Жадное предзаполнение паросочетания
vector<int> mt(k, -1);
vector<bool> used, used1(missiles);
for (int i = 0; i < missiles; ++i) {
for (int j = 0, len = (int) graph[i].size(); j < len; ++j) {
if (mt[graph[i][j]] == -1) {
mt[graph[i][j]] = i;
used1[i] = true;
break;
}
}
}
// Поиск максимального паросочетания
for (int i = 0; i < missiles; ++i) {
if (used1[i]) continue;
used.assign(missiles, false);
kuhn_dfs(i, graph, mt, used);
}
// Число пораженных баз
return count_if(mt.begin(), mt.end(), bind2nd(not_equal_to<int>(), -1));
}
double getMinimumTime(vector <int> baseX, vector <int> baseY, vector <int> siloX, vector <int> siloY,
int takeOffTime, int rechargeTime, int missileSpeed)
{
int siloses = (int) siloX.size(), bases = (int) baseX.size();
// Время полета bases ракет из siloses шахт к bases базам
vector< vector<double> > g(siloses * bases, vector<double>(bases));
for (int silo = 0; silo < siloses; ++silo) for (int missile = 0; missile < bases; ++missile) {
for (int base = 0; base < bases; ++base) {
g[silo * bases + missile][base] =
(double) (missile + 1) * takeOffTime / 60 + missile * rechargeTime +
dist(siloX[silo], siloY[silo], baseX[base], baseY[base]) / missileSpeed;
}
}
// Бинарный поиск по времени
double l = 0.0, r = 1e7, eps = 1e-9, c;
while (r - l > eps) {
c = (r + l) / 2;
if (kuhn(g, c) == bases) r = c;
else l = c;
}
return c;
}
};
Не забудьте, что завтра (вторник, 21 апреля), в 11:00 по Москве, в Стокгольме начнется финал чемпионата мира по командному программированию ACM ICPC. Возможно, тут будет трансляция, как в прошлом году.
