Нет, если у вас в руках молоток, то вы и болты забивать будете. Были у энтузиастов деньки в блокчейне, придумали контракты, захотелось как-то использовать, ничего другого не придумали. Но искусственность и натянтость этого решения никуда не делись. Это задача, придуманная под решение.
Опять криптоанархисты о своих мечтах рассказывают. Это все хорошо, но вообще не применимо в реальном физическом мире.
Пример с инвестиционным фондом вообще не реалестичный. Сколько у вас денег есть, вы столько сами и можете вкладывать куда хотите. Нет смысла собираться с толпой других людей, складывать деньги в кучу, чтобы потом согласно голосам выбирать куда их вкладывать.
Инвестиционными фондами пользуются, потому что не хотят сами решать, куда деньги вкладывать и доверяют это профессионалам. Ну или не хотят с бюрократией или другими препятствиями связываться.
Но вообще, фундаментальная проблема в том, что код не влияет на реальность. На реальность влияют люди, государство и институты. Они могут решить использовать блокчейн и смарт-котнтракты, если это окажется удобнее. Но на практике, это не удобнее, потому что распределенность сама по себе несет кучу проблем.
Разница в масштабах, трудозатратах и монетизации. Люди "обучают свою нейронку" очень медленно, долго, и только одной книге в каждый момент времени. И почти всегда платят за это. Библиотеки - это оплаченные государством места для чтения книг, потому что это приносит ощутимую пользу обществу, как и все-общее образование.
Люди с очень большим трудом дословно запоминают, и прочитав книгу - они вспомнят лишь основной сюжет и пару моментов. Чтобы дословно воспроизвести что-то, человеку надо очень усиленно заучивать материал, что происходит еще медленнее и еще сложнее. Даже если человек прочтет книгу и "вдохновятся" ею, чтобы написать свою точно такую же, то это будет очень медленный и долгий процесс, в результате получится вообще не такая же книга, и там очень-очень много отсебятены будет. И к людям тут не придраться с точки зрения закона. С другой стороны, если человек возьмет чью-то книгу, отсканирует ее, через Edit-find and replace заменит имена основных персонажей и некоторых мест на какие-то свои, то его вполне заслуженно засудят за плагиат, его книгу запретят и заставят платить много-много денег. Хотя процесс точно такой же: взял за основу чужую книгу и написал что-то свое пытаясь ее копировать.
Так вот, благодаря простоте работы, дешевезне и точности воспроизведения, ГПТ и компания гораздо ближе к плагиату через find and replace, чем к запоминанию и попытке воспроизвести копию.
Тоже самое и с генераторами картинок. Вы можете посмотреть на чужую картинку и попытаться нарисовать свое, и вас обвинят в отстутствии совести, но не в плагиате. Но если вы возьмете чужую картинку и в фотошопе ее тупо обведете, тут у вас уже будет плагиат. И вот эти генераторы картинок часто воспроизовдят чье-то произведение настолько точно, что это ближе к срисовыванию.
Хоть у нас в голове тоже нейронка, но она работает настолько медленно и дорого, что не было нужды запрещать копирование чужой работы через обучение этой нейронки. Современный же ИИ на порядки быстрее и дешевле, поэтому надо с этим что-то делать.
Задача решается довольно простым динамическим программированием: F(k,r) - сколько вариантов взять какие-то из первых k чисел, сконкатенировать их и получить число с остатком r.
Пересчет: F(k,r) = F(k-1,r) + F(k-1, r'), где r' такое, что если приписать k-ое число к остатку r', то получится остаток r. При приписывании мы берем каждую цифру числа со старших, умножаем остаток на 10, прибавляем цифру и берем по модулю 13. Удобно это реализовывать снизу вверх итеративно.
Ответ будет в F(n, 0). База: F(0,0) = 1, F(0, r) = 0.
Все решение будет за O(N), Где N - общаяя длина всех чисел. Для произвольного делителя R это будет O(NR). Памяти тут требуется O(R).
Основная идея: если вы к числу припишите цифру c, то остаток от деления на 13 станет (10*r+c) mod 13. Поэтому вам не надо следить за тем, какое у вас конкретно сейчас число сконкатенировано, вам важен лишь его остаток от деления на 13.
Удобно это все реализовать в итеративно:
код
int Count(vector<string> numbers) {
int dp[13] = {0};
dp[0] = 1;
for (string x: numbers) {
int next[13] = {0};
for (int i = 0; i < 13; ++i) {
int r = i;
for (char c : x) {
r = (10*r + c - '0') % 13;
}
next[r] = dp[i];
}
for (int i = 0; i < 13; ++i) {
dp[i] += next[i];
}
}
return dp[0];
}
Про дейкстру сначала правильно пишите, что отрицательные ребра его ломают. Потом, почему-то пишите:
Обратите внимание: наш алгоритм умеет работать с графами, содержащими ребра отрицательного веса.
Это тоже не правда. И еще даже тест приводите. Так что это не опечатка. То, что алгоритм на одном каком-то тесте отработал - не доказывает что она работает на всех возможных графах.
Про Флойда Урошелла тоже напутали:
Алгоритм Флойда-Уоршелла сравнивает все возможные пути через граф между каждой парой вершин.
Нет, алгоритм считает динамическое программирование d[k][i][j] - минимальное расстояние из вершины i в вершину j если промежуточные вершины могут быть 0..k-1. При чем, считается только последняя 2d матрица в этой 3d матрице.
У вас там дальше даже что-то вроде правильного объяснения дается, только формула не отображается целиком.
Разница между обходом дерева и обходом графа состоит в том, что в случае графа начальный узел выбирается произвольно. Это обуславливает необходимость отслеживания посещенных узлов:
Ну это же не правда вообще. Разница в том, что в дереве нет циклов и в любую вершину можно прийти только одним способом. Поэтому во время обхода из вершины есть ровно одно ребро к уже посещенному предку, а все остальные ребра ведут в новые вершины. Поэтому, кроме предка ничего запоминать не надо. В произвольном же графе могут быть разные пути в вершину, поэтому надо содержать множество уже посещенных вершин.
Еще раз, задачи утекают. Троечники еще могут зазубренный цикл написать, но если задача другая - нет. Поэтому задачи постоянно меняются. Когда-то давали задачи прям с прода, насколько это возможно. Потом скатились к немного искуственным задачам.
Аналогия с водительскими правами вам не понятна? Вы же не ругаетесь на инспектаров, что они заставляют вас ездить по тем дорогам, по которым вы ездить вообще никогда не собираетесь? Но вы при этом демонстрируете те же навыки, что вам понадоятся в настоящей езде. Так и тут, на этой, может и не самой классной, задаче кандидат показывает навыки, которые от него хотят увидеть - решает что-то не совсем тривиальное.
Или не удивляйтесь, что работник будет через пень-колоду вымучивать странные алгоритмы там, где троечник сложит 2 числа через bigInt.
Ваш аргумент звучит как: никогда не берите бегунов марафонцев в качестве курьеров. Там, где можно просто спокойно дойти до двери, он будет бежать! Нет же. Наличие сложных навыков не исключает наличие простых. И, продолжая аналогию, если у вас в городе иногда попадаются бродячие собаки, а всякие перцовые балончики запрещены из-за активистов, требовать от кандидата в курьеры способностьи хоть 20 метров до машины добежать - необходимость.
Какая же каша. У вас там то множества множеств, то множества элементов.
И потом, математики же не потому что вредные такие или от скуки понапридумывали всякое. Ваша "теория" неконсистента и противоречива, а значит и бесполезна на практике.
Во-первых, не всегда степени двойки. Во-вторых, скачет как ему вздумается. Для большего количества скобочек там еще более запутанная ситуация будет. Начало и конец, действительно более менее регулярны, потому что там весьма локальные изменения около центра происходят. Но потом они разрастаются и изменения происходят по всей строке.
Закономерность я описал выше, но ее не описать так просто в терминах битов. Там надо найти последний 0, где баланс левее положителен. Тут фигурирует что-то вроде popcnt от части числа.
Тут что-то вроде алгоритма Найораны можно получить, чтобы по одной битовой последовательности получать следующую. Но там весьма сложная операция: последний ноль, перед которым больше 0, чем 1, заменяем на 1, и в конце ставим все оставшиеся 1 в конец. Но уж закономерность по битам получать номер и обратно - это что-то совсем незаписываемое.
Если делать с длинной арифметикой, то тут будет O(n^2) по времени и O(n) по памяти. Ибо там умножения/деления на короткие и n сравнений длинных чисел. И, если уж делать с длинной арифметикой, то можно первую половину решения выкинуть. Там мы считаем, сколько надо поставить '(' сначала, и таким образом выбрасываем огромное количество последовательностей, чтобы количество оставшихся с данным префиксом было мелким. Но, если мы большие числа считаем, этого делать не надо. Тогда выбрасываем первый цикл, считаем вместо него число каталана (общее количество последовательностей из n пар). А потом остается основной цикл while (n > num_opening). Выбрасываем все Safe функции и там остается только IncreaseK и Replace.
Это вообще абсолютно другая ситуация. Были чуваки, кажется с визами, но у них что-то не так с другими документами. Если бы у них не было визы, то они бы просили убежище и писали бы, что им отказали в убежище, а не во въезде. Кроме визы надо еще как-то доказать цель поездки и все такое: вроде брони на гостиницу, письма с приглашением, билетов назад. Вот с этим у них оказались проблемы.
Потом, это 6 человек в день. Не 1000. С недостаточными документами, а не вообще без документов.
Не знаю, почему российсикие власти такую же атаку на эстонию не проводят. Может, хотят оставить тонкую щелку для выпуска пара, чтобы всякие недовольные могли свалить. Может, чьему-то бизнесу важно, чтобы граница работала и грузы ходили.
Гарантирую вам, как только там на границе появятся тысяча чуваков на велосипедах, границу закроют очень быстро.
Основаная идея даже проще вашего решения. Не надо искать закономерности и структуру последовательностей, это простой и универсальный принцып, как поиск в словаре. Вы знаете, сколько слов начинается на 'А'. Если их больше рано искомому k вы знаете, что ваше слово начинается на 'А' Иначе вы все эти строки вычеркиваете из расмотрения и пересчитваете k. Продолжаете с 'Б' и т.д. пока не найдете первую букву. Потом вы фиксируете ее и смотрите на вторую. Все что вам надо уметь, это считать сколько у вас бывает последовательностей с таким началом.
Дальше чуть-чуть логики и математики, чтобы научиться считать сколько последовательностей есть с кажым началом.
Вот если вы хотите сделать без длинной арифметики, да за O(N) с O(1) памяти (как у меня ниже, посмотрите, если интересно), вот там придется уже побольше математики нагородить, чтобы пересчитывать количество объектов быстро и без переполнения. Переполенение потому, что объектов-то экспоненциально много, и если вы попросите 10000000-ую последовательность из 100 скобок, то можно неаккуратно попробовать подсчитать, например, сколько их всего, а это ни в какое 64-битное число не влезет никак.
Вот сделал свое решение O(n) c O(1) памяти. БОльшая часть кода для счета без переполнения. Если входной номер большое число, то все придется считать в длинной арифметике и будет O(n^2), но кода может чуть поменьше. Моя F - это сколько последовательностей с n пар скобками с k открвающимеся в начале. Думаю, что-то подобное с пересчетом через домножение можно сделать и с вашими F.
код
// F(n,k) = Сколько последовательностей из n пар начинаются с k '('
// F(n,k) = F(n, k+1) + F(n-1, k-1)
// 1
// 1 1
// 2 2 1
// 5 5 3 1
// 14 14 9 4 1
//
// Это же числа каталана! Только отраженные.
// Вот формула
// F(n, k) = (2*n-k)!(k+1)/((n-k)!(n+1)!)
//
// Научимся пересчитывать внутри строки:
// k++ => mult by (k+2)*(n-k)/(2*n-k)/(k+1)
// k-- => mult by (2*n-k+1)*k/(k+1)/(n-k+1)
//
// А если мы заменяем последнюю '(' на ')':
// k-=2 --n => mult by /(k+1) /(n-k+1) *(n+1) *(k-1)
// Считаем a*n/d без переполнения (мы знаем, что влезет).
int64_t SafeMult(int64_t a, int n, int d) {
// a = (q*d + r)
// a / d * n = q*n + r*n/d
int64_t q = a / d;
return q * n + (a - q * d) * n / d;
}
// Проверка a*n/d < b без переполнения.
bool SafeCompare(int64_t a, int n, int d, int64_t b) {
// Проверяем a/d < k/n
// Сначала целые части
if (d == 0) return false;
if (n == 0) return 0 < b;
int64_t int_l = a / d;
int64_t int_r = b / n;
if (int_l < int_r) return true;
if (int_l > int_r) return false;
// Целые равны, проверим дробные
// a % d / d < b % n / n
// Числа маленькие, можно перемножить.
return (a % d) * n < (b % n) * d;
}
// Можно ли сдвинуться влево в строке не перескочив через t?
bool CanDecreaseK(int64_t count, int n, int k, int64_t t) {
int den = (k+1)*(n-k+1);
int num = (2*n-k+1)*k;
return SafeCompare(count, num, den, t);
}
// Замена последней '(' на ')'.
void Replace(int64_t &count, int &n, int &k) {
int den = (k+1)*(n-k+1);
int num = (n+1)*(k-1);
k -= 2;
n--;
count = SafeMult(count, num, den);
}
// Поставили '('.
void IncreaseK(int64_t &count, int n, int &k) {
int num = (k+2)*(n-k);
int den = (2*n-k)*(k+1);
++k;
count = SafeMult(count, num, den);
}
// Убрали последнюю '('.
void DecreaseK(int64_t &count, int n, int &k) {
int den = (k+1)*(n-k+1);
int num = (2*n-k+1)*k;
--k;
count = SafeMult(count, num, den);
}
// Построить k-ую (считая с 1) последовательность из n пар скобок.
string Generate(int n, int64_t k) {
string answer;
if (k == 1) {
for (int i = 0; i < n; ++i) {
answer += '(';
}
for (int i = 0; i < n; ++i) {
answer += ')';
}
return answer;
}
// Поддерживаем инваринант:
// answer содержит начало искомой строки.
// count - сколько всего строк с таким началом есть.
// Сколько '(' будет в начале?
// Начинаем с максимального количества.
int64_t count = 1;
int num_opening = n;
while (CanDecreaseK(count, n, num_opening, k)) {
DecreaseK(count, n, num_opening);
}
for (int i = 0; i < num_opening; ++i) {
answer += '(';
}
// Сейчас у нас минимальное количество '(', которых еще мало.
// Надо последнюю убрать.
// Все такие строки мы пропускаем, значит надо вычесть из номера.
k -= count;
// Заменяем '(' на ')'
answer.back() = ')';
Replace(count, n, num_opening);
while (n > num_opening) {
// Пробуем сначала поставить '('
IncreaseK(count, n, num_opening);
answer += '(';
// Если таких строк мало, надо их пропустить и ставить ')'
if (count < k) {
k -= count;
Replace(count, n, num_opening);
answer.back() = ')';
}
}
for (int i = 0; i < num_opening; ++i) {
answer += ')';
}
return answer;
}
Но при чем тут северная корея, если вы говорите про обязанность турагентства пасти туристов в России?
Это вы сказали, что вы много где ездили и не видели. Вот я вам и посоветовал посмотреть на страны, более близкие к россии по государственному строю.
Ну или попробуйте пригласить к себе какого-нибудь иностранца в россию.
То есть есть железобетонные доказательства что все это было сделано умышленно и именно государством?
Не все так однозначно! Всей правды мы не узнаем! Даже если это выглядит, крякает и плавает как утка, может быть это все-таки медведь! /s
Но даже если власти это не организовывали, прикрыть этот поток человечины могли бы запросто в один день. Но закрытие границы со стороны ЕС российские власти вполне устраивает.
так автобусы прямо к пограничному пункту ходили.. купил билет и..
Так их на подъезде останавливают и проверяют. Ладно, допустим первая волна у пункта в ленобласти сама образовалась. А какие автобусы оттуда ездят к пограничным пунктам в Карелии и Мурманской область? А мигранты массово добирались и туда.
И да, вас за рубежом хоть когда-нибудь хоть одно турагентство пасло? Сколько ни бывал - ни разу не было замечено..
Попробуйте в северную корею сгонять. Заметите. Россия - не далеко от нее ушла.
но как?
В смысле, как? Как прекратить свое умышленное и активное действие по гибридной атаке на соседнее государство? Тут не просят как-то прекратить действия третьих лиц, тут просят прекратить свои собственные действия.
Например, выслать указание консульствам перестать массово выдавать визы в специальном порядке под операцию по перевозке мигрантов. Перестать организовывать чартерные рейсы, отменить указ об организации перевозки их с аэропорта до границы. Отменить указание погранцам игнорировать это безобразие и даже способствовать ему.
То можно заметить, что все числа тут - это числа каталана, только выписаные по диагоналям и с кучей лишних 0. Четность n, k для не нулевых значений всегда будет совпадать и F(n,k) = Cat((n+k)/2, n-k). Если обозначить m=(n+k)/2, t =n-k, то F(n,k) = (m+t)!(m-t+1)/(t!(m+1)).
Для самого начала мы можем это число подсчитать за линию умножений и делений, а потом при постановке символа у нас m и t уменьшаются на 1 или остаются прежними. В любом случае, можно пересчитать новое число каталана просто домножив и поделив на что-то за константу.
Это все, конечно, если считать что у нас значения помещаются в целые числа. Тут нельзя ничего считать по модулю, потому что нам нужно точное значение количества последовательностей. Если считать с длинной арифметикой, тут числа порядка O(n) и решение будет за O(n^2) и O(n) памяти. Но если у вас считать с длинной арифметикой, то у вас будет O(n^3) предподсчет и само решение за O(n^2 log n).
Но минус у этого решения тоже есть: нельзя все считать в маленьких числах, даже если искомый номер последовательности в целые числа влезает. Но в этом случае можно просто считать все F через сложения, не считая левый нижний угол, ибо там слишком большие числа будут.
Нет, если у вас в руках молоток, то вы и болты забивать будете. Были у энтузиастов деньки в блокчейне, придумали контракты, захотелось как-то использовать, ничего другого не придумали. Но искусственность и натянтость этого решения никуда не делись. Это задача, придуманная под решение.
Опять криптоанархисты о своих мечтах рассказывают. Это все хорошо, но вообще не применимо в реальном физическом мире.
Пример с инвестиционным фондом вообще не реалестичный. Сколько у вас денег есть, вы столько сами и можете вкладывать куда хотите. Нет смысла собираться с толпой других людей, складывать деньги в кучу, чтобы потом согласно голосам выбирать куда их вкладывать.
Инвестиционными фондами пользуются, потому что не хотят сами решать, куда деньги вкладывать и доверяют это профессионалам. Ну или не хотят с бюрократией или другими препятствиями связываться.
Но вообще, фундаментальная проблема в том, что код не влияет на реальность. На реальность влияют люди, государство и институты. Они могут решить использовать блокчейн и смарт-котнтракты, если это окажется удобнее. Но на практике, это не удобнее, потому что распределенность сама по себе несет кучу проблем.
Разница в масштабах, трудозатратах и монетизации. Люди "обучают свою нейронку" очень медленно, долго, и только одной книге в каждый момент времени. И почти всегда платят за это. Библиотеки - это оплаченные государством места для чтения книг, потому что это приносит ощутимую пользу обществу, как и все-общее образование.
Люди с очень большим трудом дословно запоминают, и прочитав книгу - они вспомнят лишь основной сюжет и пару моментов. Чтобы дословно воспроизвести что-то, человеку надо очень усиленно заучивать материал, что происходит еще медленнее и еще сложнее. Даже если человек прочтет книгу и "вдохновятся" ею, чтобы написать свою точно такую же, то это будет очень медленный и долгий процесс, в результате получится вообще не такая же книга, и там очень-очень много отсебятены будет. И к людям тут не придраться с точки зрения закона. С другой стороны, если человек возьмет чью-то книгу, отсканирует ее, через Edit-find and replace заменит имена основных персонажей и некоторых мест на какие-то свои, то его вполне заслуженно засудят за плагиат, его книгу запретят и заставят платить много-много денег. Хотя процесс точно такой же: взял за основу чужую книгу и написал что-то свое пытаясь ее копировать.
Так вот, благодаря простоте работы, дешевезне и точности воспроизведения, ГПТ и компания гораздо ближе к плагиату через find and replace, чем к запоминанию и попытке воспроизвести копию.
Тоже самое и с генераторами картинок. Вы можете посмотреть на чужую картинку и попытаться нарисовать свое, и вас обвинят в отстутствии совести, но не в плагиате. Но если вы возьмете чужую картинку и в фотошопе ее тупо обведете, тут у вас уже будет плагиат. И вот эти генераторы картинок часто воспроизовдят чье-то произведение настолько точно, что это ближе к срисовыванию.
Хоть у нас в голове тоже нейронка, но она работает настолько медленно и дорого, что не было нужды запрещать копирование чужой работы через обучение этой нейронки. Современный же ИИ на порядки быстрее и дешевле, поэтому надо с этим что-то делать.
Задача решается довольно простым динамическим программированием: F(k,r) - сколько вариантов взять какие-то из первых k чисел, сконкатенировать их и получить число с остатком r.
Пересчет: F(k,r) = F(k-1,r) + F(k-1, r'), где r' такое, что если приписать k-ое число к остатку r', то получится остаток r. При приписывании мы берем каждую цифру числа со старших, умножаем остаток на 10, прибавляем цифру и берем по модулю 13. Удобно это реализовывать снизу вверх итеративно.
Ответ будет в F(n, 0). База: F(0,0) = 1, F(0, r) = 0.
Все решение будет за O(N), Где N - общаяя длина всех чисел. Для произвольного делителя R это будет O(NR). Памяти тут требуется O(R).
Основная идея: если вы к числу припишите цифру c, то остаток от деления на 13 станет (10*r+c) mod 13. Поэтому вам не надо следить за тем, какое у вас конкретно сейчас число сконкатенировано, вам важен лишь его остаток от деления на 13.
Удобно это все реализовать в итеративно:
код
Про дейкстру сначала правильно пишите, что отрицательные ребра его ломают. Потом, почему-то пишите:
Это тоже не правда. И еще даже тест приводите. Так что это не опечатка. То, что алгоритм на одном каком-то тесте отработал - не доказывает что она работает на всех возможных графах.
Про Флойда Урошелла тоже напутали:
Нет, алгоритм считает динамическое программирование d[k][i][j] - минимальное расстояние из вершины i в вершину j если промежуточные вершины могут быть 0..k-1. При чем, считается только последняя 2d матрица в этой 3d матрице.
У вас там дальше даже что-то вроде правильного объяснения дается, только формула не отображается целиком.
Ну это же не правда вообще. Разница в том, что в дереве нет циклов и в любую вершину можно прийти только одним способом. Поэтому во время обхода из вершины есть ровно одно ребро к уже посещенному предку, а все остальные ребра ведут в новые вершины. Поэтому, кроме предка ничего запоминать не надо. В произвольном же графе могут быть разные пути в вершину, поэтому надо содержать множество уже посещенных вершин.
А почему тогда 2+3=5 а не {2, 3}?
Еще раз, задачи утекают. Троечники еще могут зазубренный цикл написать, но если задача другая - нет. Поэтому задачи постоянно меняются. Когда-то давали задачи прям с прода, насколько это возможно. Потом скатились к немного искуственным задачам.
Аналогия с водительскими правами вам не понятна? Вы же не ругаетесь на инспектаров, что они заставляют вас ездить по тем дорогам, по которым вы ездить вообще никогда не собираетесь? Но вы при этом демонстрируете те же навыки, что вам понадоятся в настоящей езде. Так и тут, на этой, может и не самой классной, задаче кандидат показывает навыки, которые от него хотят увидеть - решает что-то не совсем тривиальное.
Ваш аргумент звучит как: никогда не берите бегунов марафонцев в качестве курьеров. Там, где можно просто спокойно дойти до двери, он будет бежать! Нет же. Наличие сложных навыков не исключает наличие простых. И, продолжая аналогию, если у вас в городе иногда попадаются бродячие собаки, а всякие перцовые балончики запрещены из-за активистов, требовать от кандидата в курьеры способностьи хоть 20 метров до машины добежать - необходимость.
Не всегда. Во множестве натуральных чисел лежат натуральные числа.
Какая же каша. У вас там то множества множеств, то множества элементов.
И потом, математики же не потому что вредные такие или от скуки понапридумывали всякое. Ваша "теория" неконсистента и противоречива, а значит и бесполезна на практике.
Это только для маленьких чисел. Вот вам "приращения" для всех скобочных последовательностей длины 10:
Скрытый текст
Во-первых, не всегда степени двойки. Во-вторых, скачет как ему вздумается. Для большего количества скобочек там еще более запутанная ситуация будет. Начало и конец, действительно более менее регулярны, потому что там весьма локальные изменения около центра происходят. Но потом они разрастаются и изменения происходят по всей строке.
Закономерность я описал выше, но ее не описать так просто в терминах битов. Там надо найти последний 0, где баланс левее положителен. Тут фигурирует что-то вроде popcnt от части числа.
Тут что-то вроде алгоритма Найораны можно получить, чтобы по одной битовой последовательности получать следующую. Но там весьма сложная операция: последний ноль, перед которым больше 0, чем 1, заменяем на 1, и в конце ставим все оставшиеся 1 в конец. Но уж закономерность по битам получать номер и обратно - это что-то совсем незаписываемое.
Если делать с длинной арифметикой, то тут будет O(n^2) по времени и O(n) по памяти. Ибо там умножения/деления на короткие и n сравнений длинных чисел. И, если уж делать с длинной арифметикой, то можно первую половину решения выкинуть. Там мы считаем, сколько надо поставить '(' сначала, и таким образом выбрасываем огромное количество последовательностей, чтобы количество оставшихся с данным префиксом было мелким. Но, если мы большие числа считаем, этого делать не надо. Тогда выбрасываем первый цикл, считаем вместо него число каталана (общее количество последовательностей из n пар). А потом остается основной цикл
while (n > num_opening). Выбрасываем все Safe функции и там остается только IncreaseK и Replace.Обратите внимание, сирии и юар в списке стран для которых это спец-предложение действует - нет.
Это вообще абсолютно другая ситуация. Были чуваки, кажется с визами, но у них что-то не так с другими документами. Если бы у них не было визы, то они бы просили убежище и писали бы, что им отказали в убежище, а не во въезде. Кроме визы надо еще как-то доказать цель поездки и все такое: вроде брони на гостиницу, письма с приглашением, билетов назад. Вот с этим у них оказались проблемы.
Потом, это 6 человек в день. Не 1000. С недостаточными документами, а не вообще без документов.
Не знаю, почему российсикие власти такую же атаку на эстонию не проводят. Может, хотят оставить тонкую щелку для выпуска пара, чтобы всякие недовольные могли свалить. Может, чьему-то бизнесу важно, чтобы граница работала и грузы ходили.
Гарантирую вам, как только там на границе появятся тысяча чуваков на велосипедах, границу закроют очень быстро.
Основаная идея даже проще вашего решения. Не надо искать закономерности и структуру последовательностей, это простой и универсальный принцып, как поиск в словаре. Вы знаете, сколько слов начинается на 'А'. Если их больше рано искомому k вы знаете, что ваше слово начинается на 'А' Иначе вы все эти строки вычеркиваете из расмотрения и пересчитваете k. Продолжаете с 'Б' и т.д. пока не найдете первую букву. Потом вы фиксируете ее и смотрите на вторую. Все что вам надо уметь, это считать сколько у вас бывает последовательностей с таким началом.
Дальше чуть-чуть логики и математики, чтобы научиться считать сколько последовательностей есть с кажым началом.
Вот если вы хотите сделать без длинной арифметики, да за O(N) с O(1) памяти (как у меня ниже, посмотрите, если интересно), вот там придется уже побольше математики нагородить, чтобы пересчитывать количество объектов быстро и без переполнения. Переполенение потому, что объектов-то экспоненциально много, и если вы попросите 10000000-ую последовательность из 100 скобок, то можно неаккуратно попробовать подсчитать, например, сколько их всего, а это ни в какое 64-битное число не влезет никак.
Вот сделал свое решение O(n) c O(1) памяти. БОльшая часть кода для счета без переполнения. Если входной номер большое число, то все придется считать в длинной арифметике и будет O(n^2), но кода может чуть поменьше. Моя F - это сколько последовательностей с n пар скобками с k открвающимеся в начале. Думаю, что-то подобное с пересчетом через домножение можно сделать и с вашими F.
код
Это вы сказали, что вы много где ездили и не видели. Вот я вам и посоветовал посмотреть на страны, более близкие к россии по государственному строю.
Ну или попробуйте пригласить к себе какого-нибудь иностранца в россию.
Не все так однозначно! Всей правды мы не узнаем! Даже если это выглядит, крякает и плавает как утка, может быть это все-таки медведь! /s
Но даже если власти это не организовывали, прикрыть этот поток человечины могли бы запросто в один день. Но закрытие границы со стороны ЕС российские власти вполне устраивает.
Не имею доступа к секретным указам.
Так их на подъезде останавливают и проверяют. Ладно, допустим первая волна у пункта в ленобласти сама образовалась. А какие автобусы оттуда ездят к пограничным пунктам в Карелии и Мурманской область? А мигранты массово добирались и туда.
Попробуйте в северную корею сгонять. Заметите. Россия - не далеко от нее ушла.
В смысле, как? Как прекратить свое умышленное и активное действие по гибридной атаке на соседнее государство? Тут не просят как-то прекратить действия третьих лиц, тут просят прекратить свои собственные действия.
Например, выслать указание консульствам перестать массово выдавать визы в специальном порядке под операцию по перевозке мигрантов. Перестать организовывать чартерные рейсы, отменить указ об организации перевозки их с аэропорта до границы. Отменить указание погранцам игнорировать это безобразие и даже способствовать ему.
Добавлю про оптимизацию до O(n). Если выписать F:
То можно заметить, что все числа тут - это числа каталана, только выписаные по диагоналям и с кучей лишних 0. Четность n, k для не нулевых значений всегда будет совпадать и F(n,k) = Cat((n+k)/2, n-k). Если обозначить m=(n+k)/2, t =n-k, то F(n,k) = (m+t)!(m-t+1)/(t!(m+1)).
Для самого начала мы можем это число подсчитать за линию умножений и делений, а потом при постановке символа у нас m и t уменьшаются на 1 или остаются прежними. В любом случае, можно пересчитать новое число каталана просто домножив и поделив на что-то за константу.
Это все, конечно, если считать что у нас значения помещаются в целые числа. Тут нельзя ничего считать по модулю, потому что нам нужно точное значение количества последовательностей. Если считать с длинной арифметикой, тут числа порядка O(n) и решение будет за O(n^2) и O(n) памяти. Но если у вас считать с длинной арифметикой, то у вас будет O(n^3) предподсчет и само решение за O(n^2 log n).
Но минус у этого решения тоже есть: нельзя все считать в маленьких числах, даже если искомый номер последовательности в целые числа влезает. Но в этом случае можно просто считать все F через сложения, не считая левый нижний угол, ибо там слишком большие числа будут.