А было бы возможно подключить еще один язык - Go?
Интересный язык, и практиковаться на нем было бы полезно.
UPDATE: Задача решена быстрее, чем за два часа. Первое правильное решение получено от Artemev Vasiliy.
Разного рода "ненормальное" программирование весьма популярно среди любителей поломать голову над разными задачками. Порой программу для очередной "ненормальной" среды программирования уже нереально написать вручную, а надо писать генератор, создающий код.
В задаче, что предлагаю я, программы все еще можно писать вручную на некотором высокоуровневом макроассемблере.
Итак, имеется модель некоторого виртуального процессора, выполняющего только одну логическую операцию - Стрелку Пирса.
На этом процессоре написана программа, на вход которой подается некоторый пароль. Если пароль неверный, то в ответ выдается строка "Wrong password!". Если верный, то выдается определенное волшебное сообщение.
Задача: любым образом выяснить это волшебное сообщение. Как вариант, можно, например, угадать пароль, и программа сама выдаст секрет.
Логика написана таким образом, что разобравшись в алгоритме, можно без труда расшифровать волшебное сообщение.
Раньше я описывал использованный подход во всех деталях.
Оригинальный подход, на котором основан мой эксперимент, был не совсем "чистым", так как команда сложения был вынесена за логику процессора. В моей версии все до единой команды реализованы на самом процессоре. Для этого потребовалось немного изменить интерпретатор, добавив в него сдвиговый регистр.
Для желающих попробовать взломать мой эксперимент, я сделал страничку, на которой на JavaScript'e реализован выше описанный виртуальный процессор с одной командой и программа для него, проверяющая пароль.
Итак, ссылка на задачу: http://demin.ws/norcpu/norcpu.html
Удачи.
P.S. Для первого взломавшего - небольшой приз! Информация по ссылке.
Мое решение (ниже) - это ДП, в котором для каждой клумбы перебираются все предыдующие клумбы, из которых можно прийдти в текущую. Для каждой такой пары (текущая <-> какая-то сзади) перебираются все возможные варианты деревьев. Итого, решение O(M*M*N*N). Но, увы, на каком-то из непервых тестов получаю WA. То есть решение вроде бы верно, но не совсем ;-).
Подскажите проблему, кто видит.
int M;
is >> M;
vector<int> w(M), e(M);
for (int i = 0; i < M; ++i)
is >> w[i] >> e[i];
int N;
is >> N;
vector<int> p(N);
for (int i = 0; i < N; ++i)
is >> p[i];
vector<vector<int> > dp(M, vector<int>(N, 0));
for (int i = 0; i < M; ++i)
dp[i][0] = 1;
for (int i = 1; i < N; ++i) {
for (int j = 0; j < M; ++j) {
for (int i0 = 0; i0 < i; ++i0) {
for (int j0 = 0; j0 < M; ++j0) {
if (p[i0] + e[j0] <= p[i] && p[i] - w[j] >= p[i0])
dp[j][i] = max(dp[j][i], dp[j0][i0] + 1);
}
}
}
}
int ans = 0;
for (int i = 0; i < M; ++i)
ans = max(ans, dp[i][N - 1]);
os << ans << endl;
}
http://acmp.ru/index.asp?main=task&id_task=433
Подскажите идею динамики. Судя по ограничению в 10^6 там требуется максимум n*log(n) решение.
У меня пока, увы, только квадратичное, которые, ясное дело, падает с TLE:
void solve(istream& is, ostream& os) {
int n;
string s;
is >> n >> s;
vector<int> dp(n, 0);
unsigned long long ans = 0;
for (int i = 0; i < n; ++i) {
dp[i] = s[i] == 'a' ? +1 : -1;
for (int j = 0; j < i; ++j) {
dp[j] += dp[i];
if (dp[j] == 0)
ans += 1;
}
}
os << ans << endl;
}
Не пойму, как делать половинное деление, чтобы получить log(n), ведь приходится проверять подстроки не только в кусках с границами в 1/2, 1/4, 1/8 и т.д., но пересекающие их.
Есть задача про Фотографа-зануду
Лично я осилил ее несколько "с фланга", а не составлением динамики, то есть сбрутфорсил полным перебором решения для размерностей до 5-6, и через известную базу данных последовательностей получил формулу (к счастью, такая последовательность там была).
Вопрос номер 1: вообще, для мира спортивного решения "канает" такое решение? Я имею ввиду использование этой базы данных для решение задач, вместо честного вывода формулы.
Вопрос номер 2: в обсуждении этой задачи на Тимусе даются две динамики, смысл которых мне не удается пока постичь.
№1
a[i][1] = a[i - 1][1] + a[i - 1][2],
a[i][2] = a[i - 1][2] + a[i - 3][2]
a[i][2] = a[i - 1][2] + a[i - 3][2]
№2
a[i][1] = a[i-1][1] + a[i-2][2]
a[i][2] = a[i-2][1] + 1
a[i][2] = a[i-2][1] + 1
Может кто-нибудь просто словами проговорить физический смысл a[i,t] в обоих случаях? Ясно, что i - это длина ряда в текущей подзадаче, а вот что такое t?
Подскажите начинающему: есть базовая динамика для задач про правильные скобочные последовательности (ПСП).
F(n, k) = F(n-1, k-1) + F(n-1, k+1).
Многие задачи про скобки к ней сводятся. Но есть такой вариант, когда надо найти количество правильных скобочных последовательностей из n открывающихся скобок, причем максимальная глубина на всей строке (разница между открывающимися и закрывающимися скобками) должна быть равна k. Например, для n=3 и k=2 последовательность ()(()) верная (глубина 2), а ((())) нет (глубина 3).
F(n, k) - количество ПСП длиной n и разницей между количеством открывающихся и закрывающихся скобок (глубиной) k:
F(n, k) = F(n-1, k-1) + F(n-1, k+1).
Многие задачи про скобки к ней сводятся. Но есть такой вариант, когда надо найти количество правильных скобочных последовательностей из n открывающихся скобок, причем максимальная глубина на всей строке (разница между открывающимися и закрывающимися скобками) должна быть равна k. Например, для n=3 и k=2 последовательность ()(()) верная (глубина 2), а ((())) нет (глубина 3).
Подскажите идею динамики тут. Если удасться подтолкнуть в нужном направлении, но без приведения непосредственно решения, будет еще лучше.
Спасибо.
А было бы реально удобно, если б в профайле можно было бы вставлять ссылки на профайлы в других системах (например, ТопКодере). А если б еще и рейтинг автоматически брался, было бы вообще нереально. ;-)
А есть ли в планах проводить матчи не только в 19:00 по Москве? Не могу, правда, сказать, что представляю большое количество людей (только двоих ;-). У нас тут время GMT+0, и московские семь часов вечера нам приходятся аккурат в четыре часа вечера, конец рабочего дня, даже не середина. Вобщем, было бы здорово, если б иногда были матчи в иное время, хотя бы по топкодеровской сетке со смещением в день-два.
Спасибо.