TCO 2009 Round 1
Прошел и пожелтел :) Не знаю, как вам, а мне созерцать 6 желтых букв SharpC, пусть даже полученных не честным решением 500, а просто сказочно быстрыми пальцами ©, невыразимо приятно. Cut-off составил 231 балл и, увы, оказался не по силам камрадам 
shuffle_c и dfyz. Поэтому когда я буду сливать round 2, оные товарищи будут скрипеть зубами и желать мне gl :)
Не смог поучаствовать tomek, разом лишив финал интриги, случившейся в прошлом году.
↑1529
250 (автор — legakis)
Найти кратчайшую последовательность последовательных неотрицательных чисел не короче L, но и не длиннее 100, дающую в сумме N (до 109), если, конечно, такая существует.
Перебирая длину последовательности l, находим средний элемент последовательности m, из него начальный s, а потом проверяем, является ли он неотрицательным, и равна ли сумма последовательности длины l, начинающейся с s, числу N.
500 (автор — Nickolas)
Равномерно выбирают M целых чисел из [lb; ub]. Нужно найти вероятность того, что K-й элемент в отсортированном полученном списке равен N.
Очевидная динамика выглядит так: [число_чисел_меньших_N][равных][больших]
1000 (автор — misof)
Фигура «единорог» ходит так же, как конь, за тем исключением, что сначала он ходит больше, чем на 2 клетки, а затем, перпендикулярно, больше чем на 1 клетку. Дана доска (до 300x300), заполненная буквами (в условии дан ГСЧ для этого), нужно найти, сколькими вариантами можно, прыгая по доске единорогом, собрать заданное слово (длина до 50), по модулю 109+7.
Динамика [строка][столбец][длина_префикса] = число способов, собирающих этот префикс и кончающихся в этой клетке тоже достаточно очевидна, но небольшое размышление показывает, что, перебирая на каждом шаге стартовую и конечную позицию, мы рискуем получить 50*3004 итераций цикла в худшем случае. Для каждого шага и клетки нам нужна сумма с предыдущего шага хитрой комбинации клеток (что следует из условия достижимости для единорога):
Если предрассчитать сумму dp[][][step−1] для строк, столбцов и целиком, то сумму зеленой области можно будет считать за O(1), сводя тем самым худший случай к 50*3002.
Стоит отметить, что расход памяти можно существенно уменьшить, если хранить только массивы ДП для текущего и предыдущего префикса.
Немного о других контестах. Sapka Contest перенесли на 13-20 марта (на главной странице стоит увлекательное замечание, что «Sapka — это контест для настоящих программистов. По-настоящему, а не так, как на олимпиадах.» — «по-настоящему» мне и на работе хватает :)).
Олимпиада по нанотехнологиям-2009, которая идет сейчас и продлится до 15 марта, содержит в себе 12 категорий и 120 PDFников с задачами. При этом правила зачета крайне хитры, а сами задачи делятся на три категории: «вы читали эту статью», «вы умеете копипастить википедию» и «вы знаете арифметику». Впрочем, круг затрагиваемых явлений достаточно широк: цеолиты, органическая молекулярная электроника, люминесценция, квантовые точки, коллоиды, нанотрубки, нанопленки, бетоны, цементы и керамики (их наноструктура оказывает значительное влияние на их прочность), наноимплантанты, наноподшипники, деконволюция (обращение свертки) изображения сканирующего зондового микроскопа, термоэлектрики, сверхпроводимость 2-го рода, фотонные кристаллы, метод оптического пинцета, АТФ-синтазные наномоторы, гигантское комбинационное рассеяние, вирусы и бактерии. Есть мнение, что в виде книжки с картинками (а ля «Такой одинаковый и разный мир» Хоффмана) все это читалось бы на ура, но прочитать, а тем более прорешать 120 задач — настоящий подвиг. Из мелких замечаний: задачи бы лучше смотрелись, будучи оформленными в одном файле. И хорошо бы не хранить кроссворд в сильно пожатом JPG :) Избранная цитата: «Представьте себе, что бригада неутомимых и неуловимых (а также невидимых) демонов Максвелла топотактически превращает бриллиант (30 карат) в наноалмазы».
shuffle_c и dfyz. Поэтому когда я буду сливать round 2, оные товарищи будут скрипеть зубами и желать мне gl :)Не смог поучаствовать tomek, разом лишив финал интриги, случившейся в прошлом году.
↑1529
250 (автор — legakis)
Найти кратчайшую последовательность последовательных неотрицательных чисел не короче L, но и не длиннее 100, дающую в сумме N (до 109), если, конечно, такая существует.
Перебирая длину последовательности l, находим средний элемент последовательности m, из него начальный s, а потом проверяем, является ли он неотрицательным, и равна ли сумма последовательности длины l, начинающейся с s, числу N.
int sum(int n, int l)
{
return n * l + l * (l-1) / 2;
}
class SequenceSums {
public:
vector <int> sequence(int N, int L) {
vector<int> res;
for (int l = L; l <= 100; ++l) {
int m = N / l, s = m - (l % 2 ? l/2 : l/2-1);
if (s < 0) continue;
if (sum(s, l) == N) {
for (int i = 0; i < l; ++i) res.push_back(s + i);
return res;
}
}
return res;
}
};
{
return n * l + l * (l-1) / 2;
}
class SequenceSums {
public:
vector <int> sequence(int N, int L) {
vector<int> res;
for (int l = L; l <= 100; ++l) {
int m = N / l, s = m - (l % 2 ? l/2 : l/2-1);
if (s < 0) continue;
if (sum(s, l) == N) {
for (int i = 0; i < l; ++i) res.push_back(s + i);
return res;
}
}
return res;
}
};
500 (автор — Nickolas)
Равномерно выбирают M целых чисел из [lb; ub]. Нужно найти вероятность того, что K-й элемент в отсортированном полученном списке равен N.
Очевидная динамика выглядит так: [число_чисел_меньших_N][равных][больших]
double p[101][101][101];
class KthProbableElement {
public:
double probability(int M, int lb, int ub, int N, int K) {
int z = ub - lb + 1;
memset(p, 0, sizeof(p));
double pless, peq, pmore;
p[1][0][0] = pless = (double) (N - lb) / z;
p[0][1][0] = peq = 1.0 / z;
p[0][0][1] = pmore = (double) (ub - N) / z;
for (int s = 1; s < M; ++s) {
for (int less = 0; less <= s; ++less) {
for (int more = 0, more_end = s - less; more <= more_end; ++more) {
int eq = s - less - more;
double cp = p[less][eq][more];
p[less + 1][eq][more] += cp * pless;
p[less][eq + 1][more] += cp * peq;
p[less][eq][more + 1] += cp * pmore;
}
}
}
double res = 0.0;
for (int less = 0; less < K; ++less) {
for (int eq = K - less; eq <= M - less; ++eq) {
res += p[less][eq][M - less - eq];
}
}
return res;
}
};
class KthProbableElement {
public:
double probability(int M, int lb, int ub, int N, int K) {
int z = ub - lb + 1;
memset(p, 0, sizeof(p));
double pless, peq, pmore;
p[1][0][0] = pless = (double) (N - lb) / z;
p[0][1][0] = peq = 1.0 / z;
p[0][0][1] = pmore = (double) (ub - N) / z;
for (int s = 1; s < M; ++s) {
for (int less = 0; less <= s; ++less) {
for (int more = 0, more_end = s - less; more <= more_end; ++more) {
int eq = s - less - more;
double cp = p[less][eq][more];
p[less + 1][eq][more] += cp * pless;
p[less][eq + 1][more] += cp * peq;
p[less][eq][more + 1] += cp * pmore;
}
}
}
double res = 0.0;
for (int less = 0; less < K; ++less) {
for (int eq = K - less; eq <= M - less; ++eq) {
res += p[less][eq][M - less - eq];
}
}
return res;
}
};
1000 (автор — misof)
Фигура «единорог» ходит так же, как конь, за тем исключением, что сначала он ходит больше, чем на 2 клетки, а затем, перпендикулярно, больше чем на 1 клетку. Дана доска (до 300x300), заполненная буквами (в условии дан ГСЧ для этого), нужно найти, сколькими вариантами можно, прыгая по доске единорогом, собрать заданное слово (длина до 50), по модулю 109+7.
Динамика [строка][столбец][длина_префикса] = число способов, собирающих этот префикс и кончающихся в этой клетке тоже достаточно очевидна, но небольшое размышление показывает, что, перебирая на каждом шаге стартовую и конечную позицию, мы рискуем получить 50*3004 итераций цикла в худшем случае. Для каждого шага и клетки нам нужна сумма с предыдущего шага хитрой комбинации клеток (что следует из условия достижимости для единорога):
Если предрассчитать сумму dp[][][step−1] для строк, столбцов и целиком, то сумму зеленой области можно будет считать за O(1), сводя тем самым худший случай к 50*3002.
const int M = 1000000007;
int cb[300][300];
int dp[300][300][50];
int dpr[300][50], dpc[300][50], dps[50];
class Unicorn {
public:
void fill(int R, int C, int L, int seed)
{
int x = seed;
int d = (65535 / L) + 1;
for (int r = 0; r < R; ++r) {
for (int c = 0; c < C; ++c) {
x = (x * 25173 + 13849) % 65536;
cb[r][c] = 'A' + x / d;
}
}
}
int countWays(int R, int C, int L, int seed, string word) {
// Заливка поля с помощью ГСЧ
fill(R, C, L, seed);
// Инициализируем массивы для ДП
int n = (int) word.length();
memset(dp, 0, sizeof(dp));
memset(dpr, 0, sizeof(dpr));
memset(dpc, 0, sizeof(dpc));
memset(dps, 0, sizeof(dps));
for (int i = 0; i < R; ++i) for (int j = 0; j < C; ++j) {
if (cb[i][j] == word[0]) dp[i][j][0] = 1;
dpr[i][0] = (dpr[i][0] + dp[i][j][0]) % M;
dpc[j][0] = (dpc[j][0] + dp[i][j][0]) % M;
dps[0] = (dps[0] + dp[i][j][0]) % M;
}
for (int l = 1; l < n; ++l) {
for (int i = 0; i < R; ++i) for (int j = 0; j < C; ++j) {
if (cb[i][j] == word[l]) {
// Берем сумму всех клеток на предыдущем шаге
int cell = dps[l - 1];
// Вычитаем 3 строки и 3 столбца
for (int sh = -1; sh <= 1; ++sh) {
if (i + sh >= 0 && i + sh < R) cell -= dpr[i + sh][l - 1]; if (cell < 0) cell += M; else cell %= M;
if (j + sh >= 0 && j + sh < C) cell -= dpc[j + sh][l - 1]; if (cell < 0) cell += M; else cell %= M;
}
// Добавляем 9 клеток, вычтенных дважды
for (int shi = -1; shi <= 1; ++shi) for (int shj = -1; shj <= 1; ++shj) {
if (i + shi >= 0 && i + shi < R && j + shj >= 0 && j + shj < C) {
cell = (cell + dp[i + shi][j + shj][l - 1]) % M;
}
}
// Вычитаем 4 оставшихся серых клетки
for (int shi = -2; shi <= 2; shi += 4) for (int shj = -2; shj <= 2; shj += 4) {
if (i + shi >= 0 && i + shi < R && j + shj >= 0 && j + shj < C) {
cell -= dp[i + shi][j + shj][l - 1]; if (cell < 0) cell += M; else cell %= M;
}
}
// Обновляем массивы ДП
dp[i][j][l] = cell;
dpr[i][l] = (dpr[i][l] + cell) % M;
dpc[j][l] = (dpc[j][l] + cell) % M;
dps[l] = (dps[l] + cell) % M;
}
}
}
int s = 0;
for (int i = 0; i < R; ++i) for (int j = 0; j < C; ++j) {
s = (s + dp[i][j][n-1]) % M;
}
return s;
}
};
int cb[300][300];
int dp[300][300][50];
int dpr[300][50], dpc[300][50], dps[50];
class Unicorn {
public:
void fill(int R, int C, int L, int seed)
{
int x = seed;
int d = (65535 / L) + 1;
for (int r = 0; r < R; ++r) {
for (int c = 0; c < C; ++c) {
x = (x * 25173 + 13849) % 65536;
cb[r][c] = 'A' + x / d;
}
}
}
int countWays(int R, int C, int L, int seed, string word) {
// Заливка поля с помощью ГСЧ
fill(R, C, L, seed);
// Инициализируем массивы для ДП
int n = (int) word.length();
memset(dp, 0, sizeof(dp));
memset(dpr, 0, sizeof(dpr));
memset(dpc, 0, sizeof(dpc));
memset(dps, 0, sizeof(dps));
for (int i = 0; i < R; ++i) for (int j = 0; j < C; ++j) {
if (cb[i][j] == word[0]) dp[i][j][0] = 1;
dpr[i][0] = (dpr[i][0] + dp[i][j][0]) % M;
dpc[j][0] = (dpc[j][0] + dp[i][j][0]) % M;
dps[0] = (dps[0] + dp[i][j][0]) % M;
}
for (int l = 1; l < n; ++l) {
for (int i = 0; i < R; ++i) for (int j = 0; j < C; ++j) {
if (cb[i][j] == word[l]) {
// Берем сумму всех клеток на предыдущем шаге
int cell = dps[l - 1];
// Вычитаем 3 строки и 3 столбца
for (int sh = -1; sh <= 1; ++sh) {
if (i + sh >= 0 && i + sh < R) cell -= dpr[i + sh][l - 1]; if (cell < 0) cell += M; else cell %= M;
if (j + sh >= 0 && j + sh < C) cell -= dpc[j + sh][l - 1]; if (cell < 0) cell += M; else cell %= M;
}
// Добавляем 9 клеток, вычтенных дважды
for (int shi = -1; shi <= 1; ++shi) for (int shj = -1; shj <= 1; ++shj) {
if (i + shi >= 0 && i + shi < R && j + shj >= 0 && j + shj < C) {
cell = (cell + dp[i + shi][j + shj][l - 1]) % M;
}
}
// Вычитаем 4 оставшихся серых клетки
for (int shi = -2; shi <= 2; shi += 4) for (int shj = -2; shj <= 2; shj += 4) {
if (i + shi >= 0 && i + shi < R && j + shj >= 0 && j + shj < C) {
cell -= dp[i + shi][j + shj][l - 1]; if (cell < 0) cell += M; else cell %= M;
}
}
// Обновляем массивы ДП
dp[i][j][l] = cell;
dpr[i][l] = (dpr[i][l] + cell) % M;
dpc[j][l] = (dpc[j][l] + cell) % M;
dps[l] = (dps[l] + cell) % M;
}
}
}
int s = 0;
for (int i = 0; i < R; ++i) for (int j = 0; j < C; ++j) {
s = (s + dp[i][j][n-1]) % M;
}
return s;
}
};
Стоит отметить, что расход памяти можно существенно уменьшить, если хранить только массивы ДП для текущего и предыдущего префикса.
Немного о других контестах. Sapka Contest перенесли на 13-20 марта (на главной странице стоит увлекательное замечание, что «Sapka — это контест для настоящих программистов. По-настоящему, а не так, как на олимпиадах.» — «по-настоящему» мне и на работе хватает :)).
Олимпиада по нанотехнологиям-2009, которая идет сейчас и продлится до 15 марта, содержит в себе 12 категорий и 120 PDFников с задачами. При этом правила зачета крайне хитры, а сами задачи делятся на три категории: «вы читали эту статью», «вы умеете копипастить википедию» и «вы знаете арифметику». Впрочем, круг затрагиваемых явлений достаточно широк: цеолиты, органическая молекулярная электроника, люминесценция, квантовые точки, коллоиды, нанотрубки, нанопленки, бетоны, цементы и керамики (их наноструктура оказывает значительное влияние на их прочность), наноимплантанты, наноподшипники, деконволюция (обращение свертки) изображения сканирующего зондового микроскопа, термоэлектрики, сверхпроводимость 2-го рода, фотонные кристаллы, метод оптического пинцета, АТФ-синтазные наномоторы, гигантское комбинационное рассеяние, вирусы и бактерии. Есть мнение, что в виде книжки с картинками (а ля «Такой одинаковый и разный мир» Хоффмана) все это читалось бы на ура, но прочитать, а тем более прорешать 120 задач — настоящий подвиг. Из мелких замечаний: задачи бы лучше смотрелись, будучи оформленными в одном файле. И хорошо бы не хранить кроссворд в сильно пожатом JPG :) Избранная цитата: «Представьте себе, что бригада неутомимых и неуловимых (а также невидимых) демонов Максвелла топотактически превращает бриллиант (30 карат) в наноалмазы».
