### [problem:665A]↵
↵
Задачау предложена пользователемил Сергей Эрлих [user:unprost,2016-04-20].↵
↵
Рассмотрим интервал времени, когда Симион будет находиться на трассе строго между городами $(x_1, y_1)$, ($x_1=60h+m, y_1=x_1+t_a$).↵
Переберём встречный автобус. Пусть $(x_2, y_2)$ — это интервал времени, когда встречный автобус будет находиться строго между городами.↵
Если пересечение этих интервалов $(x=max(x_1, x_2), y=min(y_1, y_2))$ не пусто, то Симион посчитает этот автобус.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Решение на С++">↵
~~~~~↵
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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
Сложность: $O(1)$.↵
↵
### [problem:665B]↵
↵
Задачу предложил Ayush Anand [user:FanOfTourist,2016-04-20].↵
↵
В этой задаче нужно было сделать ровно то, что написано в условии. Никаких хитростей и↵
подвохов.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Решение на 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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
Сложность: $O(nmk)$.↵
↵
### [problem:665C]↵
↵
Задачу предложил Zi Song Yeoh [user:zscoder,2016-04-20].↵
↵
Для решения этой задачи есть два подхода: жадность и динамическое программирование.↵
↵
Первый подход: Рассмотрим некоторый отрезок из подряд идущих одинаковых букв. Пусть длина отрезка $k$.↵
Очевидно мы должны изменить хотя бы $\lfloor \frac k2 \rfloor$ букв в ней, чтобы не было одинаковых↵
букв подряд. С другой стороны мы можем изменить второй, четвёртый и т.д. символы на букву, которая не равна↵
букве слева и справа от нашего отрезка.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Жадность на 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);↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
Второй подход: Пусть $z_{ka}$ — наименьшее количество изменений, чтобы на префиксе длины $k$ не было двух↵
подряд идущих одинаковых букв и при этом символ $s'_k$ был равен букве $a$. Переберём букву, которую поставим↵
на $k+1$-й позиции и если она не равна $a$ сделаем переход. Цена перехода равна $0$, если мы поставили ту же↵
букву, что стояла в исходной строке $s$ на $k+1$-й позиции. В противном случае цена равна $1$.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Динамика на 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);↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
Сложность: $O(n)$.↵
↵
↵
### [problem:665D]↵
↵
Задачу предложил Zi Song Yeoh [user:zscoder,2016-04-20].↵
↵
Рассмотрим подмножество $A$, являющееся ответом на задачу. Пусть $a, b, c$ — три произвольных элемента↵
из $A$ и пусть не более чем один из них равен $1$. По принципу Дирихле среди этих трёх чисел обязательно найдется↵
пара чисел с одинаковой чётностью. Поскольку в этой паре только одно может быть равно $1$, то их сумма чётна↵
и больше $2$. Значит подмножество $A$ не является простым. Таким образом, $A$ состоит либо из двух чисел больших единицы (с простой суммой), либо из некоторого количества единиц и возможно одной не единицы (если она равна простому минус один).↵
Первый случай легко обработать за $O(n^2)$. Второй случай легко обрабатывается за линейное время. Среди двух↵
ответов, конечно, нужно просто выбрать лучший.↵
↵
Проверять на простоту числа порядка $2\cdot 10^6$ за $O(1)$ можно с помощью обычного или линейного решета Эратосфена.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Решение на 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]);↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
Сложность: $O(n^{2}+X)$, где $X$ — максимальное среди заданных чисел.↵
↵
Задач
↵
Рассмотрим интервал времени, когда Симион будет находиться на трассе строго между городами $(x_1, y_1)$, ($x_1=60h+m, y_1=x_1+t_a$).↵
Переберём встречный автобус. Пусть $(x_2, y_2)$ — это интервал времени, когда встречный автобус будет находиться строго между городами.↵
Если пересечение этих интервалов $(x=max(x_1, x_2), y=min(y_1, y_2))$ не пусто, то Симион посчитает этот автобус.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Решение на С++">↵
~~~~~↵
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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
Сложность: $O(1)$.↵
↵
### [problem:665B]↵
↵
Задачу предложил Ayush Anand [user:FanOfTourist,2016-04-20].↵
↵
В этой задаче нужно было сделать ровно то, что написано в условии. Никаких хитростей и↵
подвохов.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Решение на 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;↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
Сложность: $O(nmk)$.↵
↵
### [problem:665C]↵
↵
Задачу предложил Zi Song Yeoh [user:zscoder,2016-04-20].↵
↵
Для решения этой задачи есть два подхода: жадность и динамическое программирование.↵
↵
Первый подход: Рассмотрим некоторый отрезок из подряд идущих одинаковых букв. Пусть длина отрезка $k$.↵
Очевидно мы должны изменить хотя бы $\lfloor \frac k2 \rfloor$ букв в ней, чтобы не было одинаковых↵
букв подряд. С другой стороны мы можем изменить второй, четвёртый и т.д. символы на букву, которая не равна↵
букве слева и справа от нашего отрезка.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Жадность на 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);↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
Второй подход: Пусть $z_{ka}$ — наименьшее количество изменений, чтобы на префиксе длины $k$ не было двух↵
подряд идущих одинаковых букв и при этом символ $s'_k$ был равен букве $a$. Переберём букву, которую поставим↵
на $k+1$-й позиции и если она не равна $a$ сделаем переход. Цена перехода равна $0$, если мы поставили ту же↵
букву, что стояла в исходной строке $s$ на $k+1$-й позиции. В противном случае цена равна $1$.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Динамика на 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);↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
Сложность: $O(n)$.↵
↵
↵
### [problem:665D]↵
↵
Задачу предложил Zi Song Yeoh [user:zscoder,2016-04-20].↵
↵
Рассмотрим подмножество $A$, являющееся ответом на задачу. Пусть $a, b, c$ — три произвольных элемента↵
из $A$ и пусть не более чем один из них равен $1$. По принципу Дирихле среди этих трёх чисел обязательно найдется↵
пара чисел с одинаковой чётностью. Поскольку в этой паре только одно может быть равно $1$, то их сумма чётна↵
и больше $2$. Значит подмножество $A$ не является простым. Таким образом, $A$ состоит либо из двух чисел больших единицы (с простой суммой), либо из некоторого количества единиц и возможно одной не единицы (если она равна простому минус один).↵
Первый случай легко обработать за $O(n^2)$. Второй случай легко обрабатывается за линейное время. Среди двух↵
ответов, конечно, нужно просто выбрать лучший.↵
↵
Проверять на простоту числа порядка $2\cdot 10^6$ за $O(1)$ можно с помощью обычного или линейного решета Эратосфена.↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
<spoiler summary="Решение на 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]);↵
}↵
~~~~~↵
</spoiler>↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
↵
Сложность: $O(n^{2}+X)$, где $X$ — максимальное среди заданных чисел.↵
