Разбор задач первого этапа отбора в школу программистов HeadHunter 2016

в 10:21, , рубрики: headhunter, javascript, Алгоритмы, задачи для программистов, Занимательные задачки, простые числа

В сентябре 2016 прошел очередной ежегодный отбор молодых специалистов, студентов и выпускников инженерных и математических специальностей в школу программистов HeadHunter.

Для поступления предлагалось пройти несколько этапов, решая логические/математические задачи.
Варианты решения некоторых типовых задач первого этапа я и попытаюсь разобрать в данной статье.
PS: Для удобства быстрого написания и отладки кода подсчетов использовался JavaScript.

Пока писал статью, смотрю, в песочнице меня уже опередили по теме. Однако, у меня рассмотрены другие типы задач, только одна совпала про степени (но, судя по комментариям, не в обиду автору — решение неверное).

Комментарии и предложения альтернативных вариантов решения только приветствуются.

Задача 1

Рассмотрим спираль, в которой, начиная с 1 в центре, последовательно расставим числа по часовой стрелке, пока не получится спираль 5 на 5:

spiral

Можно проверить, что сумма всех чисел на диагоналях равна 101.
Чему будет равна сумма чисел на диагоналях, для спирали размером 1195 на 1195?

Решение 1

Будем идти от самого центра по спирали и просто суммировать числа на углах: 1 + 3 + 5 + 7 + 9 + 13 + 17 + 21 + 25 +…

Можно заметить, что в этой последовательности каждое следующее число отличается на дельту d (вначале равную 2: 3, 5, 7, 9). При этом с каждым переходом на следующий виток спирали дельта между четырьмя угловыми числами увеличивается еще на 2: 13, 17, 21, 25.

Получается сумма значений угловых чисел одного витка рассчитывается по формуле: (v+d) + (v+2*d) + (v+3*d) + (v+4*d), где v — последнее число предыдущего витка (1, 9, 25, ...), d — дельта. Построим цикл, увеличивая дельту d до размера спирали size.

function task1(size) {
	for (var v=1, d=2, sum=v; d<size; v+=4*d, d+=2) {
		sum += 4*v+10*d;
	}
	return sum;	
}

Для спирали размером size = 1195 сумма чисел на диагоналях равна 1138375521.

Задача 2

Определим функцию P(n,k) следующим образом: P(n,k) = 1, если n может быть представлено в виде суммы k простых чисел (простые числа в записи могут повторяться, 1 не является простым числом) и P(n,k) = 0 в обратном случае.

К примеру, P(10,2) = 1, т.к. 10 может быть представлено в виде суммы 3 + 7 или 5 + 5, а P(11,2) = 0, так как никакие два простых числа не могут дать в сумме 11.

Определим функцию S(n) как сумму значений функции P(i,k) для всех i и k, таких что 1<=i<=n, 1<=k<=n.

Таким образом, S(2) = P(1,1) + P(2,1) + P(1,2) + P(2,2) = 1, S(10) = 20, S(1000) = 248838.
Найдите S(17688).

Решение 2

Воспользуемся свойствами простых чисел:

Для k>3 значения функции P(i,k) заполняются как следствия из предыдущих утверждений. При этом все четные числа i>=4 можно разложить максимум на k=i/2 простых чисел (k=i/2-1 для нечетных).

Составим наглядную матрицу, где i — числа от 1 до n, которые можно разложить на сумму k простых чисел:

matrix

Можно заметить, что существуют такие нечетные числа, которые не являются простыми, и при этом их нельзя представить как сумму двух простых чисел — в данном случае это, например, 27.

Ряд простых чисел можем подсчитать, проверяя каждое нечетное число на деление по модулю без остатка на все полученные ранее простые числа:

// функция определения простых чисел
function isPrime(x,primes){
	for (var j=0, len=primes.length; j<len; j++){
		if (x%primes[j]==0) return false;
	}
	return true;
}

Итоговая функция подсчета S(n):

function task2(n) {
	for (var i=4, count=2, primes=[2,3]; i<=n; i++){
		// если число - четное
		if (i%2==0) {
			count+=i/2-1;
		} else {
			// нечетное
			count+=(i-1)/2-1;
			// если нельзя представить как сумму двух простых чисел
			if (i!=(primes[primes.length-1]+2)) {
				count--;
			}
			// если число - простое
			if (isPrime(i,primes)) {
				count++;
				// добавляем новое простое число в общий ряд
				primes[primes.length]=i;
			}
		}
	}
	return count;
}

S(17688) = 78193870.

Задача 3

Число 125874 и результат умножения его на 2 — 251748 можно получить друг из друга перестановкой цифр. Найдите наименьшее положительное натуральное x такое, что числа 2*x, 3*x можно получить друг из друга перестановкой цифр.

Решение 3

Для простого сравнения чисел путем перестановки цифр будем приводить числа в строки с упорядоченными по возрастанию символами:

// получение строки упорядоченных символов
function sortVal(val) {
	var str=val.toString();
	if (str.length>1){
		return str.split("").sort().join("");
	} else {
		return str;
	}
}

И сравнивать эти строки с "упорядоченным" x:

function task3(a,b) {
	for (var x=1, xSorted=''; x<=1000000; x++){
		// сортируем цифры в текущем x
		xSorted=sortVal(x);
		// сравниваем с сортированными результатами перемножений x на a и b
		if (xSorted==sortVal(a*x) && xSorted==sortVal(b*x)) {
			var founded=x;
			break;
		}
	}
	return founded;
}

Наименьшее положительное натуральное x = 142857 (где для a = 2 и b = 3: a*x = 285714 и b*x = 428571).

Задача 4

Если мы возьмем 47, перевернем его и сложим, получится 47 + 74 = 121 — число-палиндром.
Если взять 349 и проделать над ним эту операцию три раза, то тоже получится палиндром:

349 + 943 = 1292
1292 + 2921 = 4213
4213 + 3124 = 7337

Найдите количество положительных натуральных чисел меньших 13110 таких, что из них нельзя получить палиндром за 50 или менее применений описанной операции (операция должна быть применена хотя бы один раз).

Решение 4

Переворачивать числа будем, как массив символов, объединяемый в строку:

// получение перевернутой строки
function rev(val){
	val=val.toString();
	if (val.length>1){
		return val.split("").reverse().join("");
	} else {
		return val;
	}
}

Для проверки на палиндром достаточно перевернуть полученную сумму и сравнить значение с самим собой: rev(7337) == 7337.

function task4(maxNum) {
	for (var num=1, count=0; num<maxNum; num++){
		// производим 50 операций суммирования с переворачиванием
		for (var i = 1, val=num, palindrome=false; i<=50; i++) {
			val = parseInt(val,10)+parseInt(rev(val),10);
			// если перевернутая сумма равна сама себе
			if (rev(val) == val) {
				// получили палиндром - прерываем
				palindrome = true;
				break;
			}
		}
		// если до палиндрома так и не дошло - считаем
		if (!palindrome) {
			count++;
		}
	}
	return count;
}

В итоге, количество положительных натуральных чисел меньших maxNum = 13110 таких, что из них нельзя получить палиндром за 50 операций: 368.

Задача 5

Рассмотрим все возможные числа ab для 1<a<6 и 1<b<6:
22=4, 23=8, 24=16, 25=32 32=9, 33=27, 34=81, 35=243, 42=16, 43=64, 44=256, 45=1024, 52=25, 53=125, 54=625, 55=3125
Если убрать повторения, то получим 15 различных чисел.
Сколько различных чисел ab для 2<a<149 и 2<b<121?

Решение 5

В приведенном выше примере совпали варианты 24=16 и 42=16, т.к. 42 можно представить, как (2*2)2 => 22*2 => 24. Поэтому, чтобы не возводить все в степени, можно просто привести все a к степени простого числа, например: 16 = 24, 27 = 33, 125 = 53 и т.д.

// функция определения степени числа
function isPowerOf(val,prime){
	var power = 0;
	// если число делится без остатка на простое число
	if (val%prime == 0) {
		// делим пока 
		while ((val/=prime)>=1) {
			power++;
			if (val==1) return power;
		}
	}
	return 0;
}

Требуемый для вычислений ряд простых чисел можно определить функцией из выше рассмотренной Задачи 2, но для упрощения в данном случае возьмем готовые значения. При чем, достаточно взять первые несколько чисел (2, 3, 5, 7, 11), где максимальное простое число будет не более квадратного корня из a, т.к. для данного случая мы не сможем разложить a < 149 на степени 13: 132 > 149.

Перебирая ряд простых чисел, определяем, можно ли представить число a степенью. А полученную степень просто перемножаем с соответствующими b. Из результата задаем очередной ассоциативный индекс idx для массива всех вариаций ab (arr), например:

3100 => a3b100
и 950 => 32*50 => 3100 => a3b100

Соответственно, проверяем наличие элемента с данным индексом в массиве arr.

Итоговая функция подсчета, где a1, b1 — соответствующие минимумы входных значений, и a2, b2 — максимумы входных значений:

// a1, b1 - соответствующие минимумы входных значений, и a2, b2 - максимумы входных значений
function task5(a1,a2,b1,b2) {
	for (var a=a1+1, arr=[], power=1, count=0; a<a2; a++){
		// определим ряд простых чисел
		var primes = [2,3,5,7,11];
		// перебирая ряд простых чисел, определяем, можно ли представить число степенью
		for (var i=0; i < primes.length; i++) {
			power = isPowerOf(a,primes[i]);
			if (power>1) {
				break;
			}
		}
		for (var b=b1+1, idx=''; b<b2; b++){
			// зададим очередной ассоциативный индекс для массива всех вариаций a в степени b
			idx = (power>1)? "a"+primes[i]+"b"+power*b : "a"+a+"b"+b ;
			// если такого индекса в массиве еще не было
			if (!arr[idx]) {
				// заполняем новый элемент значением
				arr[idx]=1;
				// считаем итоговые уникальные индексы
				count++;
			}
		}
	}
	return count;
}

Для 2<a<149 и 2<b<121 различных чисел ab: 16529.

Задача 6

В некоторых числах можно найти последовательности цифр, которые в сумме дают 10. К примеру, в числе 3523014 целых четыре таких последовательности:

3523014
3523014
3523014
3523014
Можно найти и такие замечательные числа, каждая цифра которых входит в по крайней мере одну такую последовательность.

Например, 3523014 является замечательным числом, а 28546 — нет (в нём нет последовательности цифр, дающей в сумме 10 и при этом включающей 5).

Найдите количество этих замечательных чисел в интервале [1, 1900000] (обе границы — включительно).

Решение 6

Единственное решение для этой задачи, которое мне пришло в голову — прямой перебор. Но я постарался его максимально оптимизировать.

Каждое число num будем разбивать на массив цифр arrPrep, исключая из него все нули, т.к. они никакой роли не играют.

Для начала можем проверить сумму сразу всех цифр sum:

  • если равна 10 — т.е. число представляет из себя максимальную последовательность и его можно сразу отнести к замечательным;
  • если меньше 10 — число не имеет ни одной последовательности и не является замечательным;

Далее можем сразу проверить первые две и последние две цифры. Если хотя бы одна из пар в сумме больше 10 — число точно не является замечательным, например: 56112, 127379.
Теперь можно приступить к перебору всех последовательностей.

Суммы последовательностей будут записываться в двумерный массив s. Основную диагональ которого предварительно заполним всеми цифрами из arrPrep.

Если найдена удачная последовательность — заполняем проверочный массив arrCheck цифрами, входящими в данную последовательность.

В конце сравним строчные представления массива arrPrep и проверочного массива arrCheck. Если равны — все цифры числа использованы хотя бы в одной удачной последовательности — т.е. число замечательное.

// функция определения "замечательного" числа
function isWonderful(num) {
	var arrRaw=[], arrPrep=[], len=0, sum=0;
	// разберем число на массив цифр
	arrRaw = num.toString().split("");
	for (var i=0, digit=0; i<arrRaw.length; i++){
		digit=parseInt(arrRaw[i]);
		// исключаем нули
		if (digit>0) {
			arrPrep[arrPrep.length]=digit;
			// сумма всех цифр числа
			sum+=digit;
		}
	}
	// длина обработанного массива цифр
	len=arrPrep.length;
	// если сумма всех цифр числа равна 10, число - "замечательное"
	if (sum==10) {
		return true;
	// сумма всех цифр числа меньше 10 - не является "замечательным"
	} else if (sum<10) {
		return false;
	} else {
		// если первые 2 или последние 2 цифры в сумме больше 10 - не является "замечательным"
		if ((arrPrep[0]+arrPrep[1])>10 || (arrPrep[len-1]+arrPrep[len-2])>10) {
			return false;
		}
		for (var i=0, s=[]; i<len; i++){
			// задаем двумерный массив для хранения сумм последовательностей
			s[i]=[];
			// заполняем диагональ массива цифрами числа
			s[i][i]=arrPrep[i];
		}
		// перебираем последовательности цифр
		for (var i=0, arrCheck=[]; i<len-1; i++){
			for (var j=i; j<len-1; j++){
				// сумма очередной последовательности
				s[i][j+1]=s[i][j]+s[j+1][j+1];
				// нашли удачную последовательность
				if (s[i][j+1]==10){
					for (var k=i;k<=j+1;k++){
						// заполняем проверочный массив цифрами, уже использованные хотя бы в одной удачной последовательности
						arrCheck[k]=s[k][k];
					}
					break;
				// перебор - ищем следующую последовательность
				} else if (s[i][j+1]>10) {
					break;
				}
			}
		}
		// сравниваем строчные представления обработанного массива цифр и проверочного массива
		if (arrPrep.join('')==arrCheck.join('')) {
			// все цифры числа использованы хотя бы в одной удачной последовательности - число "замечательное"
			return true;
		}
	}
	return false;
}


// функция подсчета "замечательных" чисел в интервале x1, x2
function task6(x1,x2) {
	for (var x=x1, count=0; x<=x2; x++){
		// если число "замечательное" - считаем
		if (isWonderful(x)) {
			count++;
		}
	}
	return count;
}

Количество замечательных чисел в интервале [1, 1900000]: 152409.

Автор: wizarts

Источник

* - обязательные к заполнению поля

Главная   |  Архив новостей  |   Android  |   Google  |   Apple  |   Microsoft  |   Информационная безопасность  |   Веб – разработка
Публикации RSS  |  Комментарии RSS
https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js