1) В силу небольших ограничений в задаче можно в цикле перебирать значения
n и проверять условие
for (int n = 1; n <= Tn; n++)
{
if (n * (n + 1) / 2 == Tn)
{
cout << "YES\n";
return;
}
}
cout << "NO\n";
2) Определим граф, где буквы
A,
B,
C - вершины, и если выполняется
x < y, то существует ребро
y - > x. Далее проведем
топологическую сортировку. Если при выборе следующей вершины при поиске мы можем перейти в помеченную, но не использованную вершину, значит найден цикл, и надо вывести "Impossible".
3) Задача решается переборо
6! = 720 перестановок. Для каждой перестановки первые 3 слова будем располагать горизонтально, остальные - вертикально. Будем располагать слова так:
- hor[0], ver[0] - влево-вверх
- hor[2], ver[2] - вправо-вниз
- hor[1]: (len(ver[0]) - 1, 0)
- ver[1]: (0, len(hor[0]) - 1)
Пусть теперь N = len(ver[1]), M = len(hor[1]).
Для того, чтобы существовало решение, необходимы следующие условия:
- len(hor[0]) + len(hor[2]) == M + 1 // углы восьмерки
- len(ver[0]) + len(ver[2]) == N + 1 // углы восьмерки
- len(hor[0]) >= 3 && len(hor[2]) >= 3 && len(ver[0]) >= 3 && len(ver[2]) >= 3 // восьмерка невырождена
- буквы на началах/концах соответствующих строк совпадают
- совпадают буквы при пересечении hor[1], ver[1]
При выполнении этих условий получаем правильную доску размером N x M, обновляем ответ.
Замечание: В C++ если хранить доску в виде vector<vector<char> > или vector<string>, то для обновления ответа можно просто использовать оператор "<".
4) Рассмотрим не самый эффективный алгоритм, тем не менее проходящий по времени, со сложностью
O(mCn5log(Cn5)).
Рассмотрим 1 ответ системы: <number, v>. Общее число вариантов шифра будет
Cnv - не очень большое число, поэтому можно их просто
сгенерировать. Объявляем это множество вариантов текущим. Далее, для каждого нового ответа генерируем множество возможных шифров, пересечение текущего и нового множеств объявляем текущим.
В итоге получаем некое множество. Надо исключить из него элементы, которые уже были в ответах системы, и вывести его размер.
PS: В комментариях приветствуются более эффективные алгоритмы
5) Приведу пример решения за
O((n + m)log(n + m)).
Предварительно исключим из рассмотрения стенки до которых снаряд не может долететь ни при каких условиях:
x > v2 / gВ силу условия
α < =π / 4 выполняется следующее
- Функция дальности полета от угла монотонная
- Функция высоты при фиксированной дальности от угла монотонная
Этот факт позволяет сопоставить каждой стенке отрезок углов атаки
[α1, α2]. Если снаряд выпущен под углом из этого отрезка, то он попадает в стенку. Эти углы можно находить, решая уравнение (оно окажется биквадратным), но опять же в силу монотонности можно воспользоваться бинарным поиском.
Отсортируем стенки по координате
x. Теперь задача свелась к следующей: для каждого выстрела определить минимальный индекс стенки, при этом угол выстрела лежит между углами атаки стенки. А эту задачу можно решать деревом отрезков для минимума с возможностью обновления на интервале. Вначале заполним дерево значением KInf. Далее, для каждой стенки будем делать update(
α1,
α2, index). Потом пройдемся по запросам. Если getMin(
α) == KInf, значит снаряд благополучно приземлится на землю, иначе врежется в стенку с индексом getMin(
α).