Комментарии 42
Вопрос 1 не совсем понятен. Заменяются пары на 1 шар. Этот один шар откуда? Из мешка тоже? Или отдельно?
Вопрос 2 - простым показался
78 яиц = $7.80
Да, шар на замену достаётся из мешка, потом пара добирается оттуда же.
Вопрос 2 еще вариант
18
Решается в один цикл
Код на js
let result;
for(let i = 50; i <= 100; i++) {
if(
(i % 2 === 0) &&
(i % 3 === 0) &&
(i % 5 === 3)
) {
result = i
}
}
console.log(result)
> Input: N = 200, D = 9
Про шары:
Ответ
(999-99)/9*(9+9)/9
Про шары:
Ответ
Черного, так как при каждой операции число черных шаров меняется на 0 или 2, а начальное число — 13 (нечетное).
Input: N = 200, D = 9: (9*9+9+9+9/9)*(9+9)/9
Если я правильно понял задание с массивом, то нам нужно просто посчитать индексы значений, которые меньше k, получим массив (пример) [0, 1, 3, 4], а потом пройдем циклом по элементам и если следующий индекс больше предыдущего на 2 и больше, значит нужна перестановка.
Код на js
const array = [2, 7, 9, 5, 8, 7, 4]
const k = 5
const groupNearK = function (arr, k) {
const length = arr.length
const idx = []
let moveCount = 0
for(let i = 0; i < length; i++) {
if(arr[i] <= k) idx.push(i)
}
for(let i = 1; i < idx.length; i++) {
if((idx[i] - idx[i - 1]) > 1) moveCount++
}
return moveCount
}
console.log(groupNearK(array, k))Решение за один цикл
const array = [2, 1, 5, 6, 3]
const k = 3
const groupNearK = function (arr, k) {
const length = arr.length
let moveCount = 0
let lastIndex = -1
for(let i = 0; i < length; i++) {
if(arr[i] <= k) {
if(lastIndex >= 0 && (i - lastIndex) > 1) {
moveCount++
}
lastIndex = i
}
}
return moveCount
}
console.log(groupNearK(array, k))
Одной перестановкой на каждый пропуск не отделаешься, за ней целый паровоз перестановок поползёт. Надо просто сначала посчитать количество "хороших" значений <= k, а потом пройтись окном размера k по всему массиву, считая количество попаданий "плохих" значений в каждое окно. Минимум и будет ответом — это значит, что в данном окне нужно перестановками заменить "плохие" значения "хорошими" снаружи окна.
Ну да, лучше такого алгоритма придумать не смог.
Код на java
private int GetTranspositions(int[] array, int k)
{
int count = 0;
for (int i = 0; i < array.length; i++)
{
if (array[i] <= k)
{
count++;
}
}
int result = array.length;
for (int i = 0; i<= array.length - count; i++)
{
int iteration = 0;
for (int j = 0; j<= count; j++)
{
if (array[i+j] > k)
{
iteration++;
}
}
if (iteration < result)
{
result = iteration;
}
}
return result;
}
3-вопрос
(9+9+9/9+9/9+9/9+9/9)*9+9/9+9/9
(9+9+9/9+9/9+9/9+9/9)*9+9/9+9/9
Шары
Белый шар останется. Есть комбинации где извлекая пары чёрных можно потратить все белые, но тогда не может остаться одного шара (всегда минимум 2 чёрных останется, а надо ответить про цвет последнего шара). Вывод — чёрные необходимо исчерпать раньше белых, чтобы была возможность оставить только один шар. Соответственно, шар будет белым.
яйца
780 центов, по признаку делимости на 6.
Шары
А ничего, что в начале есть 13 черных, а извлечь их можно только попарно?
Вовсе нет. Шары всегда извлекаются по одному. Вот взяли два чёрных — заменили на белый (т.е. оба чёрных остались в коробке, вместо них ушёл белый), взяли чёрный и белый — ушёл чёрный (один, белый остался в коробке).
200
поскольку () в допустимых операциях нет:
99+99+9/9+9/9
99+99+9/9+9/9
Вопрос 1
Изначально у нас в мешке нечётное количество чёрных шаров.
Если мы достали два чёрных шара, то заменяем их одним белым, чётность количества чёрных шаров не меняется.
Если мы достали два белых шара, то заменяем их одним белым, количество (и чётность) чёрных не меняется.
Если мы достали белый и чёрный шары, то заменяем их одним чёрным, количество (и чётность) чёрных не меняется.
Таким образом, в мешке всегда нечётное количество чёрных шаров, а значит, когда там останется всего один шар — он будет чёрным.
Если мы достали два чёрных шара, то заменяем их одним белым, чётность количества чёрных шаров не меняется.
Если мы достали два белых шара, то заменяем их одним белым, количество (и чётность) чёрных не меняется.
Если мы достали белый и чёрный шары, то заменяем их одним чёрным, количество (и чётность) чёрных не меняется.
Таким образом, в мешке всегда нечётное количество чёрных шаров, а значит, когда там останется всего один шар — он будет чёрным.
Вопрос 2
Обозначим количество яиц как N.
50 ≤ N ≤ 100
N % 5 = 3, этому условию соответствуют числа 53, 58, 63, 68, 73, 78, 83, 88, 93, 98
N % 2 = 0, значит последняя цифра числа чётная, остаются числа 58, 68, 78, 88, 98
N % 3 = 0, остаётся 78.
50 ≤ N ≤ 100
N % 5 = 3, этому условию соответствуют числа 53, 58, 63, 68, 73, 78, 83, 88, 93, 98
N % 2 = 0, значит последняя цифра числа чётная, остаются числа 58, 68, 78, 88, 98
N % 3 = 0, остаётся 78.
Задачи понравились.
Мои решения:
Задачу 1 ещё обдумываю.
Мои решения:
1 Вопрос
При всех вариантах сохраняется четность черных шаров. Значит, черных шаров не может из 13 стать 0. Последним будет черный шар.
Вопрос 2
78. Так, как n%5=3 и значение четное, то остается 58, 68, 78, 88, 98. Из них только 78 делится на 3 без остатка.
Задача 3
Считает количество нужных значений в массиве. За второй раз сканируем окном массив, и считаем количество значений, которые больше k. Минимум этого значения и будет равен кол-ву перестановок.
public static int nearMix(int[] _array, int _k){
int s =0;
for(int i: _array){
if(i<=_k){
s++;
}
}
int itemIntoWindow = 0;
for(int i=0; i<s; i++){
if(_array[i]>_k){
itemIntoWindow++;
}
}
int minOther = itemIntoWindow;
for(int i=s; s<_array.length; i++){
if(_array[i]>_k){
itemIntoWindow++;
}
if(_array[i-s]>_k){
itemIntoWindow--;
}
if(itemIntoWindow<minOther){
minOther = itemIntoWindow;
}
}
return minOther;
}
public static void main(String[] _a){
int array[] = {1,4,3,7,8};
System.out.println(nearMix(array,3));
}Считает количество нужных значений в массиве. За второй раз сканируем окном массив, и считаем количество значений, которые больше k. Минимум этого значения и будет равен кол-ву перестановок.
Задача 2
Пусть у нас есть цифра 9. Выражение длиной в 1 цифру может быть только одно, это сама цифра (первый набор). Выражений из 2-х цифр 9 может быть 4. Запомним все числа, которые при этом получились(второй набор). Чтобы найти все значения, которые состоят из трех цифр нужно взять все числа из первого набора и применить все операции по отношению ко всем числами из второго набора, а также все числа из второго набора на все числа из первого набора. Каждое вновь найденное значение проверяем в хеше, если его нет, то вносим туда(в виде ключа). По этому ключу ложим те значения из которых это число получилось в виде кода «первое число + код операции».
Таким образом пробегаем, пока не заполняем все 10 наборов. А дальше смотрим из Хэша как искомое число получилось и рекурсивно повторяем весь процесс, пока не дойдем до самой цифры.
Данный код подразумевает, что скобки не влияют на длину значения. И ещё, считаем, что во время выполнения операций полученные значения всегда целые. Доказать это не могу, но думаю, что если в середине получено дробное число, то существует другая комбинация с длинной не большей, чем исходная комбинация.
Таким образом пробегаем, пока не заполняем все 10 наборов. А дальше смотрим из Хэша как искомое число получилось и рекурсивно повторяем весь процесс, пока не дойдем до самой цифры.
public static String StringOfOperations(int _n, int _d){
if(_n==_d){return ""+_d;}
Object[] arrayInt = new Object[11];
HashMap<Integer,Integer> common = new HashMap<>();
Integer[] first = new Integer[1];
first[0]=_d;
arrayInt[1]=first;
common.put(_d, 0);
for(int i=2; i<=10; i++){
System.out.println("Stage: "+i);
HashSet<Integer> set = new HashSet<>();
for(int j=1; j<i; j++){
Integer[] list1 = (Integer[])arrayInt[j];
Integer[] list2 = (Integer[])arrayInt[i-j];
for(int a: list1){
for(int b: list2){
int c = a+b;
if(common.containsKey(c)!=true){
common.put(c, a*4+0);
set.add(c);
}
c = a-b;
if(common.containsKey(c)!=true){
common.put(c, a*4+1);
set.add(c);
}
c = a*b;
if(common.containsKey(c)!=true){
common.put(c, a*4+2);
set.add(c);
}
if(b==0){
continue;
}
c = a/b;
if((common.containsKey(c)!=true)&&(b*c==a)){
common.put(c, a*4+3);
set.add(c);
}
}
}
}
Integer[] next = new Integer[set.size()];
next = set.toArray(next);
arrayInt[i] = next;
set.clear();
}
if(common.containsKey(_n)){
int g = common.get(_n);
return subPrint(_n, common, _d);
}
return "Error";
}
public static String subPrint(int _value, HashMap<Integer,Integer> _common, int _base){
if(_value==_base){
return String.valueOf(_base);
}
int a = _common.get(_value);
int b = a>>2;
int c = a&0x3;
int d = 0;
char operation = 0;
switch(c){
case 0:
operation = '+';
d = _value - b;
break;
case 1:
operation = '-';
d = b - _value;
break;
case 2:
operation = '*';
d = _value / b;
break;
case 3:
operation = '/';
d = b/_value;
break;
}
return "("+subPrint(b, _common, _base)+operation+subPrint(d, _common, _base)+")";
}
public static void main(String[] _a){
System.out.print(StringOfOperations(200, 9));
}Данный код подразумевает, что скобки не влияют на длину значения. И ещё, считаем, что во время выполнения операций полученные значения всегда целые. Доказать это не могу, но думаю, что если в середине получено дробное число, то существует другая комбинация с длинной не большей, чем исходная комбинация.
Задачу 1 ещё обдумываю.
Решение задачи 1. Пока без кода
Можно отсортировать весь массив и взять центральный элемент. Это означает r*c*Log(r*c).
Можно постараться найти решение за r*c. Но r*c — это предел для данных без структуры. У нас же есть порядок по строкам, поэтому можно искать решения вида r*Log( c), или что-то типа того.
Если коротко, как в бинарном поиске храним верхнюю и нижнюю границы по значению. Кроме того, храним правую и левую границы для каждой строки. Каждый раз берем медиану по каждой строке (с учетом границ), находим среди этих медиан новую медиану и пробуем её, как искомое значение. Находим для каждой строчки положение этого значения бинарным поиском (с учетом границ). Для левой границы ищем положение значения меньше или равно, а для правой больше или равно. Если сумма по каждой строке больше половины всех элементов массива с обоих сторон, значит значение и есть искомое. Если нет, то в каждой строке передвигаем границу.
Нам нужно, чтобы за каждую итерацию отсеивать некий процент (у меня он =25%) оставшихся элементов. Поэтому медиану медиан нужно искать с учётом весов, где вес медианы равен кол-ву оставшихся значений в строке.
Т.е. пусть у нас остались следующие строки (16) (11, 15, 20) (17, 21,33,48,50,77,78) и соотвественно медианы 16, 15, 48 с весами 1-3-7. Если мы возмем просто медиану медиан, т.е. число 16, то отсеем малое значение элементов, т.к. оно произойдет в строках с малым количеством. Это нам не нужно. с другой стороны 3+1+7=11, и медиана приходится на значение 7, т.е. медиану, которая равна 48.
Поиск такой медианы можно делать через сортировку медиан с последующим проходом.
Сложность поиска такой медианы с весом равна r*Log( r). Внутри строк нужен бинарный поиск, и так как зона бинарного поиска сокращается на 25%, то Log( c)+Log(0.75*c)+Log(0.75*0.75*c)+… = O(Log( c)*Log( c)), как сумма арифметической прогрессии.
Итого, сложность всего алгоритма это O(r*Log( r)*Log( c)^2)
Можно постараться найти решение за r*c. Но r*c — это предел для данных без структуры. У нас же есть порядок по строкам, поэтому можно искать решения вида r*Log( c), или что-то типа того.
Если коротко, как в бинарном поиске храним верхнюю и нижнюю границы по значению. Кроме того, храним правую и левую границы для каждой строки. Каждый раз берем медиану по каждой строке (с учетом границ), находим среди этих медиан новую медиану и пробуем её, как искомое значение. Находим для каждой строчки положение этого значения бинарным поиском (с учетом границ). Для левой границы ищем положение значения меньше или равно, а для правой больше или равно. Если сумма по каждой строке больше половины всех элементов массива с обоих сторон, значит значение и есть искомое. Если нет, то в каждой строке передвигаем границу.
Нам нужно, чтобы за каждую итерацию отсеивать некий процент (у меня он =25%) оставшихся элементов. Поэтому медиану медиан нужно искать с учётом весов, где вес медианы равен кол-ву оставшихся значений в строке.
Т.е. пусть у нас остались следующие строки (16) (11, 15, 20) (17, 21,33,48,50,77,78) и соотвественно медианы 16, 15, 48 с весами 1-3-7. Если мы возмем просто медиану медиан, т.е. число 16, то отсеем малое значение элементов, т.к. оно произойдет в строках с малым количеством. Это нам не нужно. с другой стороны 3+1+7=11, и медиана приходится на значение 7, т.е. медиану, которая равна 48.
Поиск такой медианы можно делать через сортировку медиан с последующим проходом.
Сложность поиска такой медианы с весом равна r*Log( r). Внутри строк нужен бинарный поиск, и так как зона бинарного поиска сокращается на 25%, то Log( c)+Log(0.75*c)+Log(0.75*0.75*c)+… = O(Log( c)*Log( c)), как сумма арифметической прогрессии.
Итого, сложность всего алгоритма это O(r*Log( r)*Log( c)^2)
#3 — вроде как, тоже простой (решение за O(n)):
counter = 0
for i =0; i < array.size; i++
if array[i] <= k
counter = 0
for i =0; i < array.size; i++
if array[i] <= k
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Выпуск#12: ITренировка — актуальные вопросы и задачи от ведущих компаний