Задачу предложил Сергей Эрлих unprost.
Рассмотрим интервал времени, когда Симион будет находиться на трассе строго между городами (x1, y1), (x1 = 60h + m, y1 = x1 + ta). Переберём встречный автобус. Пусть (x2, y2) — это интервал времени, когда встречный автобус будет находиться строго между городами. Если пересечение этих интервалов (x = max(x1, x2), y = min(y1, y2)) не пусто, то Симион посчитает этот автобус.
Решение на С++int a, ta;
int b, tb;
int h, m;
bool read() {
if (!(cin >> a >> ta)) return false;
assert(cin >> b >> tb);
assert(scanf("%d:%d", &h, &m) == 2);
return true;
}
void solve() {
int x1 = h * 60 + m;
int y1 = x1 + ta;
int ans = 0;
for (int x2 = 5 * 60 + 0; x2 < 24 * 60; x2 += b) {
int y2 = x2 + tb;
int x = max(x1, x2), y = min(y1, y2);
if (x < y)
ans++;
}
cout << ans << endl;
}
Сложность: O(1).
Задачу предложил Ayush Anand JeanValjean01.
В этой задаче нужно было сделать ровно то, что написано в условии. Никаких хитростей и подвохов.
Решение на C++const int N = 111;
int n, m, k;
int p[N];
int a[N][N];
bool read() {
if (!(cin >> n >> m >> k)) return false;
forn(i, k) {
assert(scanf("%d", &p[i]) == 1);
p[i]--;
}
forn(i, n)
forn(j, m) {
assert(scanf("%d", &a[i][j]) == 1);
a[i][j]--;
}
return true;
}
void solve() {
int ans = 0;
forn(i, n)
forn(j, m) {
int pos = int(find(p, p + k, a[i][j]) - p);
ans += pos + 1;
nfor(l, pos) p[l + 1] = p[l];
p[0] = a[i][j];
}
cout << ans << endl;
}
Сложность: O(nmk).
Задачу предложил Zi Song Yeoh zscoder.
Для решения этой задачи есть два подхода: жадность и динамическое программирование.
Первый подход: Рассмотрим некоторый отрезок из подряд идущих одинаковых букв. Пусть длина отрезка k. Очевидно мы должны изменить хотя бы 
букв в ней, чтобы не было одинаковых букв подряд. С другой стороны мы можем изменить второй, четвёртый и т.д. символы на букву, которая не равна букве слева и справа от нашего отрезка.
Жадность на C++const int N = 200200;
int n;
char s[N];
bool read() {
if (!gets(s)) return false;
n = int(strlen(s));
return true;
}
void solve() {
for (int i = 0, j = 0; i < n; i = j) {
while (j < n && s[j] == s[i]) j++;
char c = 'a';
while (c == s[i] || (i > 0 && c == s[i - 1]) || (j < n && c == s[j]))
c++;
fore(k, i, j)
if ((i + k) & 1)
s[k] = c;
}
puts(s);
}
Второй подход: Пусть zka — наименьшее количество изменений, чтобы на префиксе длины k не было двух подряд идущих одинаковых букв и при этом символ s'k был равен букве a. Переберём букву, которую поставим на k + 1-й позиции и если она не равна a сделаем переход. Цена перехода равна 0, если мы поставили ту же букву, что стояла в исходной строке s на k + 1-й позиции. В противном случае цена равна 1.
Динамика на C++const int N = 1200300, A = 27;
int n;
char s[N];
bool read() {
if (!gets(s)) return false;
n = int(strlen(s));
return true;
}
int z[N][A];
int p[N][A];
char ans[N];
void solve() {
memset(z, 63, sizeof(z));
z[0][A - 1] = 0;
forn(i, n) {
int c = int(s[i] - 'a');
forn(j, A) {
int dv = z[i][j];
if (dv > INF / 2) continue;
forn(nj, A - 1) {
if (nj == j) continue;
int ct = nj != c;
if (z[i + 1][nj] > dv + ct) {
z[i + 1][nj] = dv + ct;
p[i + 1][nj] = j;
}
}
}
}
int idx = int(min_element(z[n], z[n] + A) - z[n]);
for (int i = n, j = idx; i > 0; j = p[i][j], i--)
ans[i - 1] = char('a' + j);
ans[n] = 0;
cerr << z[n][idx] << endl;
puts(ans);
}
Сложность: O(n).
Задачу предложил Zi Song Yeoh zscoder.
Рассмотрим подмножество A, являющееся ответом на задачу. Пусть a, b, c — три произвольных элемента из A и пусть не более чем один из них равен 1. По принципу Дирихле среди этих трёх чисел обязательно найдется пара чисел с одинаковой чётностью. Поскольку в этой паре только одно может быть равно 1, то их сумма чётна и больше 2. Значит подмножество A не является простым. Таким образом, A состоит либо из двух чисел больших единицы (с простой суммой), либо из некоторого количества единиц и возможно одной не единицы (если она равна простому минус один). Первый случай легко обработать за O(n2). Второй случай легко обрабатывается за линейное время. Среди двух ответов, конечно, нужно просто выбрать лучший.
Проверять на простоту числа порядка 2·106 за O(1) можно с помощью обычного или линейного решета Эратосфена.
Решение на C++const int N = 1010, X = 2100300;
int n, a[N];
bool read() {
if (!(cin >> n)) return false;
forn(i, n) assert(scanf("%d", &a[i]) == 1);
return true;
}
int szp, p[X];
int mind[X];
void prepare() {
fore(i, 2, X) {
if (!mind[i]) {
p[szp++] = i;
mind[i] = i;
}
for (int j = 0; j < szp && p[j] <= mind[i] && i * p[j] < X; j++)
mind[i * p[j]] = p[j];
}
}
void printAns(int cnt1, int a = -1, int b = -1) {
vector<int> ans;
forn(i, cnt1) ans.pb(1);
if (a != -1) ans.pb(a);
if (b != -1) ans.pb(b);
assert(!ans.empty());
random_shuffle(all(ans));
cout << sz(ans) << endl;
forn(i, sz(ans)) {
if (i) putchar(' ');
printf("%d", ans[i]);
}
puts("");
}
void solve() {
int cnt1 = (int) count(a, a + n, 1);
function<bool(int)> isPrime = [](int p) { return mind[p] == p; };
if (cnt1 > 0)
forn(i, n)
if (a[i] != 1 && isPrime(a[i] + 1)) {
printAns(cnt1, a[i]);
return;
}
if (cnt1 > 1) {
printAns(cnt1);
return;
}
forn(i, n)
forn(j, i)
if (isPrime(a[i] + a[j])) {
printAns(0, a[i], a[j]);
return;
}
printAns(0, a[0]);
}
Сложность: O(n2 + X), где X — максимальное среди заданных чисел.
