В задаче достаточно сделать то, что написано в условии - перебрать все числа от 1 до n, если число i счастливое (а проверку можно сделать если просто пройтись по цифрам числа), то проверить, делиться ли нацело n на i. Если такое i существует, то вывести "YES", иначе "NO".
Заметим, что ответ всегда либо одна цифра, либо -1. Если нет ни одного вхождения 4 или 7, то выводим -1, иначе, ели 4 встречается больше раз чем 7 (или такое самое количество), то ответ 4, иначе 7.
Сгенерируем все счастливые числа на промежутке [1;1010]. Рассмотрим промежутки вида [1;L0], [L0 + 1;L1], [L1 + 1;L2] ... Результатом тогда будет размер произведение пересечения отрезков [1;L0] и [1;n] на L0 плюс размер пересечения [L0 + 1;L1] и [1;n] на L1 и т.д.
Заметим, что если есть такое i (imod2 = 0), что di = 4, di + 1 = 7, di - 1 = 4, то после этого будет зацикливание. Действительно, 447 → 477 → 447 → 477 → ... То есть нужно идти слева на право и делать то, что написано в условии, а когда появиться такое зацикливание, то просто вывести то что уже есть (только изменяя i-й элемент в зависимости от четности количества операций что остались) и закончить исполнение.
Если n ≤ 14, то проверим, будет ли -1 в ответе или нет. Теперь нам нужно найти размер суффикса перестановки, которая будет изменяться за те k операций. То есть такое максимальное i, что i! ≤ k. Остальные элементы до этого суффикса не будут изменяться, поэтому, сгенерировав счастливые числа до 109 узнаем результат для префикса что не изменяется. После этого осталось найти k-ю перестановку чисел от 1 до i, пройтись по ней и посчитать что она - это суффикс перестановки чисел от 1 до n и посчитать результат.
Будем держать массивы L и R. Для каждого счастливого i, L[i] - количество операций нужных для того, что-бы перенести все промежутки, правый конец которых левее i до i; R[i] - количество операций для переноса всех промежутков, левый конец которых правее i до i. Например, L можно посчитать, создав массив, в котором будем держать пару из числа и 0, если это очередное счастливое число, 1, если это первый конец некоторого промежутка. То есть просто для каждого счастливого числа закинем в массив пару (Luckyi;0), для всех промежутков закинем в массив пару (Righti;1). Теперь лексикографически отсортируем этот массив. Будем идти слева на право, держа количество концов промежутков, которые уже встретились c и сумму si, si = si - 1 + (Ai - Ai - 1) * c. Тогда если Ai счастливое, то Li = si. Аналогично для R. Теперь, используя метод двух указателей (или бинарный поиск) найдем результат - пару индексов i и j, такой, что i ≤ j, Lj + Ri ≤ k, Luckyj - Luckyi + 1 ≤ минимальный_размер_входного_отрезка. Также здесь нужно было отдельно сделать процедуру умножение, которая должна была возвращать min(a * b, INF). Это можно было сделать, если считать результат по модулю 264 или используя double.
В этой задаче можно использовать различные методы, рассмотрим один из них. Очевидно, что так как числа не будут превышать 104, то количество различных счастливых чисел будет 30. Давайте будем держать массив D, Di ровно разнице минимального счастливого числа большего или ровного Ai и Ai. Теперь, нам нужно динамически поддерживать этот массив. Для этого нам понадобятся 5 (но можно и меньше) операции: Subtract(l, r, d) - отнять от всех чисел Di (l ≤ i ≤ r) число d, Minimum(l, r) - минимальное Di (l ≤ i ≤ r), Count(l, r) - сколько раз встречается минимум на этом промежутке [l;r], Left(l, r) - самое левое вхождение минимума на этом промежутке, Set(i, d) - присвоить Di число d. Теперь, будем исполнять операции. Если есть операция "count", то нам нужно вызвать Minimum(l, r), если этот минимум не ровен нулю, то ответ 0, иначе ответ ровен Count(l, r). Если есть операция "add", то нам нужно вызвать Subtract(l, r, d). После этого некоторые числа в D могли стать < 0, поэтому, пока минимум на этом промежутке меньше нуля, нам нужно взять этот минимум (а именно минимум под индексом j=Left(l, r)) и заменить его на новое Di (которое можно посчитать за O(1)), то есть сделать Set(j, d').
Сложность такого алгоритма - O(m * log(n) + n * log(n) * C), где C константа, ровна количеству счастливых чисел (30).
Проблема в этом условии -
if (k % 2) s[t] = '7';else s[t] = '4';
так как если k % 2 == 0, то изменять в числе, по идее, вообще ничего не надо. Если я не ошибаюсь, то должно работать такое:
if (k % 2) {
if (t % 2)
s[t] = '7';
else
s[t + 1] = '4';
}
Можно еще очередью, тогда эти числа сразу будут отсортированы:
не, ну если уж так не хочется использовать дополнительные структуры, то
Кстати, в Е заходит все подряд. Например, эпичная обработка сложения одним из участников.
for (int i=l;i<r;i++)
{
int k=a[b[i]+w]-a[b[i]];
if (k!=0) up(i,k);
b[i]+=w;
}
up - это отдать Фенвику
How to implement Subtract(l, r, d) and Count(l, r) operations?
Segment_Tree?
Who can explain the solution in detail ?
How is the TC of this step "while, Min(l,r) < 0, Set(j, Dj)" under Log(n) and overall TC of add/count operations m*Log(n)?
Entire sub-array might become < 0 after an add operation and this can happen for multiple/many add operations.
I see that someone has O(n*m*log) (in worst case) but AC. How? example : 19299244
In Problem 122A, A. Lucky Division, what is the meaning of evenly divided, because this has been accepting the answers for 49 as YES. I don't understand why it should be a YES?
Because 49 is divided by 7
Yeah, I do understand that, but what is the meaning of term evenly divided in the problem statement. I didn't understand the context of this word because 7 divides 49, 7 times which isn't even.
"Evenly" means "exactly" here
Lucky Array 121E — 72 testcases and still passes O(n*m*log(10^4)) :0 Code
It's actually faster than $$$O(n\cdot m\cdot log(n))$$$ because you only update the BIT when a number becomes or "unbecomes" lucky, this can only happen at most 60 times per number, so it's actually $$$O(n(m+60 \log n))$$$.
Still more than 4 sec. :D
It's a perfectly valid solution, the heaviest part $$$O(nm)$$$ has a small constant because it's very simple and cache-friendly. I have just written a blog post about this, I believe people will find it useful.
I have implemented the same code and it passed all test cases, and worst time was around 2 secs.
Submission
IN problem Div1(A) or Div2(c) how to create those lucky numbers from 1 to 10^10?
For each length of number L, the are only 2^L possible lucky numbers (since there are 2 possibilities for each digit: 4 or 7).
Generate instead all possible bitmasks of length L (for L = 1 to 10), and replace 0s with 4s, 1s with 7s. Note that you need to include bitmasks with leading zeros.
Python implementation: https://paste2.org/YfMYvaXe
Test Case 26: Input is 799 and output should be "NO" but the answer is "YES", can anyone explain?
Yesh because 799 % 47 == 0 and 47 is lucky number