Подсчет количества «ПЛОХИХ» значений
Я решал проблему и наткнулся на эту.
Предположим, у нас есть глиняные шарики. Каждый шар имеет определенное значение; значение каждого шара может быть любым положительным целым числом. Изначально для каждого значения от X до X+Y−1 (включительно) у нас есть бесконечный запас шаров с этими значениями.
У шаров есть особое свойство: любые два из них можно смешать, чтобы получился новый шар. Если исходные шары имели значения a и b (возможно, a=b), новый шар имеет значение a+b. Созданные таким образом шары можно использовать и для смешивания других шаров. Мы вольны смешивать шары любым способом, который выберем, и любое количество раз.
Назовем значение v (v>0) ПЛОХИМ, если нет возможности получить мяч со значением v; в противном случае значение v является ХОРОШИМ. Мы хотим сделать мячи со всеми ХОРОШИМИ значениями, и мы хотели бы знать количество ПЛОХИХ значений.
Примечание. Существует бесконечное количество ХОРОШИХ значений шаров, но можно доказать, что количество ПЛОХИХ значений всегда конечно для Y≥2.
Для заданных X и Y разработайте процедуру для нахождения количества значений BAD.
Например.
X = 1 ; Y = 2
Нам дарят [1, 1 + 2 - 1] == [1, 2] == {1, 2} мячей. Ответ 0 ; Так как можно получить шары со всеми возможными значениями по X и Y.
X = 3 ; Y = 3
Нам дарят [3, 3 + 3 - 1] == [3, 5] == {3, 4, 5} мячей.
Ответ 2 ; Поскольку шары со значениями 1 и 2 нельзя сделать.
Я думал, что значения меньше X нельзя сделать, но, похоже, это неправильно, может быть, я что-то упускаю.
Я не думаю, что количество плохих значений конечно. Если у вас есть два шара с четными номерами, скажем, 2 и 4, как вы получите шар с нечетным номером?
@ChatterOne: это невозможно: вам дается спектр, например. если X = 2, Y = 3 значит у тебя [2, 2 + 3 - 1] - {2, 3, 4} мячи
@DmitryBychenko О, я неправильно понял, что у вас просто два значения вместо диапазона. Хорошо, тогда.
@DmitryBychenko Теперь я понял, но как мы сможем посчитать эти значения?
@Steve: При решении таких проблем начните с играть с цифрами, позвольте мне не предоставлять вам полное решение, но идея с 1st случаем (Y = 2) объяснена
Ответы 1
При решении таких задач начинайте с игра с цифрами. Допустим, нам дано 2 мячей (Y = 2), пусть это будут 11 и 12 (X = 11). Мы можем создать
- Из
1мяча:11,12 - Из
2шаров:22,23,24 - Из
3шаров:33,34,35,36 - Из
4шаров:44,45,46,47,48
....
Однако у нас есть отверстия (неверные числа): 1..10 размера 10, затем 13..21 размера 9, затем 25..32 размера 8. Можете ли вы увидеть образец? Сумма отверстий (количество неверных чисел) равна
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 == 55
Теперь мы можем решить задачу, если Y = 2: это сумма артиметическая прогрессия
X - 1 + X - 2 + ... + 2 + 1 == (X - 1) * (X - 2) / 2
Продолжайте делать Y = 3, например. нам дают 3 мячей (Y = 3) 11, 12, 13 (X = 11). Мы можем создать:
- Из
1мяча:11,12,13 - Из
2шаров:22,23,24,25,26 - Из
3шаров:33,34,35,36,37,38,39 - Из
4шаров:44,45,46,47,48,49,50,51,52
Давайте посчитаем отверстия: 1..10, затем 14..21, затем 26..33, а затем 40..43:
10 + 8 + 6 + 4 + 2 == 30
Можете ли вы увидеть образец? Можете ли вы решить для Y = 3? Пожалуйста, обратите внимание на разницу:
X = 11; Y = 2 -> 10 + 9 + 8 + 7 + ... + 1
X = 11; Y = 3 -> 10 + 8 + 6 + 4 + 2
Можешь сейчас написать формулу Y = 3? Для Y = 4, Y = 5?
X = 11; Y = 4 -> 10 + 7 + 4 + 1
x = 11; Y = 5 -> 10 + 6 + 2
Для произвольного Y?
X = 11; Y -> 10 + (10 - 1 * (Y - 1)) + (10 - 2 * (Y - 1)) + ...
Для произвольных X и Y (мы должны суммировать все члены положительный)?
X; Y -> (X - 1) + (X - 1 - 1 * (Y - 1)) + (X - 1 - 2 * (Y - 1)) + ...
Код: Пусть будет С#:
private static int MySum(int X, int Y) {
int d = Y - 1; // difference
int n = (X - 1) / (Y - 1) + 1; // number of items to sum
int A1 = X - 1; // 1st item
int An = X - 1 - (n - 1) * d; // last item
return (A1 + An) * n / 2; // sum of arithmetic progression
}
Некоторые тесты (или демо):
(int, int)[] tests = new (int, int)[] {
(X : 11, Y : 2),
(X : 11, Y : 3),
(X : 11, Y : 4),
(X : 11, Y : 5),
(X : 1, Y : 2),
(X : 3, Y : 3),
};
string demo = string.Join(Environment.NewLine, tests
.Select(test => $"X = {test.Item1,2}, Y = {test.Item2} => {MySum(test.Item1, test.Item2),2}"));
Console.Write(demo);
Исход:
X = 11, Y = 2 => 55
X = 11, Y = 3 => 30
X = 11, Y = 4 => 22
X = 11, Y = 5 => 18
X = 1, Y = 2 => 0 // test from the question
X = 3, Y = 3 => 2 // test from the question
Это так элегантно! Большое спасибо за объяснение.
Не могли бы вы проверить stackoverflow.com/questions/56503879/…. Я попробовал реализацию в ответе, но в некоторых случаях это не удается.
@Steve: максимизация суммы gcd кажется совсем другой проблемой; здесь у нас есть артиметическая прогрессия к сумме (a1 = X - 1, разность = Y - 1 и т. д.)
Я согласен, что это совершенно другая проблема, просто хотел немного разобраться в этом.
Еще одно сомнение относительно того, как мы найдем «N», то есть количество терминов для использования суммы формулы AP? Sn = [n*(2*a + (n-1)*d)]/2
@Steve: Ну, когда у нас есть прогресс, все детали кажутся довольно простыми. Хорошо, я добавил немного кода (C#) с тестами.
Этот код работает! Только для одного теста он не проходит, так как ввод X и Y имеет порядок 10 ^ 18, и нам нужно вычислить его по модулю 1000000007. Так что не могли бы вы помочь мне включить это в каждый промежуточный шаг, потому что если мы возьмите его в конце, он дает неправильный ответ.
@Steve: измените int на BigInt или long, чтобы поддерживать диапазон до 1e18
Я использовал long int. Но им нужен ответ по модулю 1e9 + 7. Так что я ошибаюсь, беря по модулю на промежуточных шагах.
@Steve: для вычисления по модулю в случае оператора С# поставить %. return (...) % 1000000007;
Это именно то, что я сделал! Тем не менее, это терпит неудачу для одного случая. Я немного почитал в Интернете, и там говорится, что для больших выражений мы должны взять% 1000000007 на промежуточных этапах, тогда он дает правильный ответ. (Распределительное свойство оператора mod.) Я взял по модулю промежуточные шаги, но дал неправильный ответ.
@Steve: арифметика по модулю не так проста. Вероятно, лучший выход — вычислить результат через BigInteger, который может быть произвольно длинным, а затем вычислить остаток
BigInt - это ответ! Приняли наконец. Большое спасибо за помощь.
Представьте,
X = 11, Y = 2вам даны шарики11и12: вы не можете создать13,14, ...21,25и т. д.