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

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

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

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

Задача 1


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

spiral

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

Решение 1

Решение 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;	
}

Альтернативное решение, как сумма квадратичной последовательности, предложенное eandr_67 в комментариях:
function task1_alt(size) {
	return (size * size * size * 2 / 3.0 + size * size / 2.0 + size * 4 / 3.0 - 1.5);	
}


Для спирали размером 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

Решение 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

Решение 3


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

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

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

В комментариях Large предложил исключить из перебора x, в которых первая цифра 4 и более: 412, 5230, 60457…, т.к. при перемножении увеличивается длина числа — и проверять такие x не имеет смысла.
Зададим такой максимум xFirstMax первой цифры x, как результат округленного целочисленного деления 9 и максимального из a и b.

function task3(a,b) {
	// задаем предел первой цифры числа x для исключения таких x из перебора
	var xFirstMax = Math.floor(9/Math.max(a,b));
	for (var x=1, xSorted=''; x<=1000000; x++){
		// пропускаем x, если его первая цифра больше предела
		if (x.toString()[0]>xFirstMax) continue;
		// сортируем цифры в текущем 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

Решение 4


50 операций прямого суммирования, может привести к очень большим числам, что, как подсказал в комментариях Stelet, закончится непредвиденными результатами. Поэтому будем хранить числа, как строки. А вместо множественных переворачиваний будем просто суммировать попарно цифры числа начиная с концов, что в итоге равнозначно сумме числа и его перевернутой копии.
И уже для проверки на палиндром достаточно перевернуть полученную строку и сравнить значение с самим собой: 7337==reverse(7337).
function task4(maxNum) {
	for (var num=1, count=0; num<maxNum; num++){
		// производим 50 операций суммирования с переворачиванием
		for (var op = 1, val=num, palindrome=false; op<=50; op++) {
			val=val.toString();
			// перебираем число посимвольно, как строку
			for (var iMax=val.length-1, i=iMax, j=0, digSum=0, arrSum=[], carry=0; i>=0 && j<=iMax; i--, j++) {
				// складываем цифры с обоих концов + перенос из предыдущего разряда
				digSum = parseInt(val[i])+parseInt(val[j])+carry;
				// если сумма больше 9
				if (digSum>9) {
					// в массив закидываем только разряд до 10
					arrSum[arrSum.length]=digSum-10;
					// делаем перенос в следующий разряд
					carry=1;
					// финальный перенос
					if (i==0) arrSum[arrSum.length]=1;
				} else {
					arrSum[arrSum.length]=digSum;
					carry=0;
				}
			}
			val = arrSum.join("");
			// если перевернутая сумма равна сама себе
			if (val == val.split("").reverse().join("")) {
				// получили палиндром - прерываем
				palindrome = true;
				break;
			}
		}
		// если до палиндрома так и не дошло - считаем
		if (!palindrome) {
			count++;
		}
	}
	return count;
}

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

Задача 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

Решение 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

Решение 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.
Поделиться с друзьями
-->

Комментарии (30)


  1. eandr_67
    11.10.2016 13:38
    +1

    Задача N 1.

    1*d + 2*d +… + (n-1)*d + n*d = s*d, гд s — банальная сумма арифметической прогрессии, изучаемая в школе:

    s = (1+n)*n/2

    Значие n также находится простейшим вычислением.

    Вывод: задача элементарно решается вообще без циклов.


    1. wizarts
      11.10.2016 14:23

      Это было бы справедливо, если бы d не менялось на следующем витке.


      1. eandr_67
        11.10.2016 15:10
        +1

        Сумма квадратичной последовательности есть кубическая функция. Так что цикл всё равно не нужен, но формула будет чуть сложнее. Для нечётных size формула:

        Sum = size * size * size * 2 / 3.0 + size * size / 2.0 + size * 4 / 3.0 - 1.5
        


        1. wizarts
          11.10.2016 15:19

          Справедливо, «плюсую».


        1. Jojat
          12.10.2016 09:23

          Можете описать, как вы пришли к этой формуле?


          1. alexeykuzmin0
            12.10.2016 13:39

            Я в свое время в школе нашел ее примерно следующими рассуждениями:
            1. Понятно, что сумма квадратов — кубическая формула: S(n) = an^3 + bn^2 + cn + d.
            2. Запишем систему уравнений для небольших n, чтобы найти a, b, c, d:
            1 = a + b + c + d
            5 = 8a + 4b + 2c + d
            14 = 27a + 9b + 3c + d
            30 = 64a + 16b + 4c + d
            3. Решим, найдем a, b, c, d.


        1. wizarts
          12.10.2016 10:16

          Добавил как альтернативное решение. Да, хотелось бы немного подробнее описание вывода формулы.


          1. eandr_67
            13.10.2016 15:54

            Искал коэф-ты «в лоб» — методом наименьших квадратов.


  1. CrazyOpossum
    11.10.2016 14:58

    Задача 3: интересный факт, дроби n/7 имеют периоды (7-1) в десятичной записи и они получаются перестановкой цифр для разных n. Если не ошибаюсь, то же верно и для 17 с периодом (17-1). Короче, увлекающиеся подобной фигнёй решают эту задачу в уме.


    1. max0ua
      12.10.2016 10:26

      Решал без непосредственных вычислений такую задачу в школьные годы: «Найти шестизначное число которое при умножении на 2, 3, 4, 5, 6 дает в результате шестизначное число записанное теми же цифрами что и исходное но в другом порядке.»

       N = 142857
      2N = 285714
      3N = 428571
      4N = 571428
      5N = 714285
      6N = 857142
      


      1. Large
        12.10.2016 14:47

        И это более правильный подход, в решении никак не используется ограничение на первую цифру (1-3) в вашем случае она детерминировано 1.


        1. wizarts
          12.10.2016 15:57

          В решении сравниваются именно строчные значения, а не сами числа. Поэтому для гипотетического случая с 0 (далее числа выдуманы): для x = 123450 могли бы получить 2*x=254130 и 3*x=351240, где строчные значения всех этих чисел равны «012345».


          1. Large
            12.10.2016 17:14

            for (var x=1, xSorted=''; x<=1000000; x++) — тут вы зачем проверяете число которое с 4 начинается? Если число х начинается с 4, то 3*x будет большей длины чем х и проверять этот случай смысла нет (даже такие случаи 4, 34, 334 и т.д.)


            1. wizarts
              12.10.2016 19:26

              Согласен, спасибо. Т.к. 4 — частный случай для данных входных значений, добавил в решение расчет максимума первой цифры x. Т.е., например, для варианта 2*x, 4*x — xFirstMax уже будет 2, а для 3*x, 7*x — xFirstMax = 1.


  1. Stelet
    11.10.2016 17:00

    В задаче 4 где-то ошибка, возможно, в ParseInt или при сравнении строк и чисел, не знаю JS. Проверил для одного лишнего числа 10548, где-то на 30 итерации получилось число 17858768886785871. В консоли Хрома это число не присваивается переменной, при присвоении получается 17858768886785872. Возможно, ошибка в этом.
    У меня получился ответ 359, вот те 9 лишних чисел в вашем решении: [10548, 10794, 10828, 11538, 11784, 11818, 12528, 12774, 12808].


    1. wizarts
      11.10.2016 18:48

      Спасибо. Действительно упустил момент.


    1. wizarts
      14.10.2016 18:17

      Переписал решение для 4-ой задачи. Теперь суммируем не целые числа, а посимвольно строки — работает даже быстрее. Действительно, верный ответ 359.


  1. lis355
    11.10.2016 18:46

    залейте пожалуйста картинки на habrastorage.org, у меня они уже не грузятся в статье


    1. wizarts
      12.10.2016 09:34

      Перезалил.


  1. lismut
    12.10.2016 09:24

    В задаче №3 говорится про перестановку цифр чисел 2х и 3х, про цифры самого х ничего не сказано, так что предполагаю, что ответ 1782 (2*1782 = 3564, 3*1782 = 5346)


  1. dm_p2016
    12.10.2016 09:25

    В задаче 3 формулировка вводит в заблуждение. Написано, что «числа 2*x, 3*x можно получить друг из друга перестановкой цифр». Однако, судя по решению, требуется найти натуральное x такое, что числа x, 2*x, 3*x можно получить друг из друга перестановкой цифр.


    1. wizarts
      12.10.2016 10:23

      Да, формулировка действительно странновата. Просто тогда не ясен смысл умножения на 2. Можно было бы тогда просто найти x, из которого надо получить число 1.5*х перестановкой цифр.


  1. drch
    12.10.2016 09:25

    Немного не понял решение 6-ой задачи. Ведь если речь идет о последовательностях, то достаточно начать складывать все цифры числа — если на каком-то шаге у нас будет сумма больше 10 — то это не замечательное число, а если же на последнем шаге итерации у нас сумма 10 — то число замечательное.

    foo = function(n) {
    	n = n.toString();
    	n = n.slice('');
    
    	for(var i = 0, sum = 0; i<n.length; i++) {
    		sum += parseFloat(n[i], 10);
    
    		if(sum==10 && i == (n.length-1)) {
    			return true;
    		}
    
    		if(sum>10) {
    			return false;
    		}
    
    		else {
    			if(sum==10) {
    				sum = 0;
    			}
    		}
    	}
    	return false;
    }
    


    1. wizarts
      12.10.2016 09:41

      Сумма всех цифр числа, равная 10, — частный случай задачи, учитываемый в одном из этапов моего решения.
      Обратите внимание на пример в самом задании. Последовательностью является не только та, что начинается с первой цифры:
      3523014
      3523014
      3523014


      1. drch
        12.10.2016 10:04

        Но ведь в замечательном числе все цифры являются частями последовательностей, разве я не прав?


        1. wizarts
          12.10.2016 10:11

          Исходя из вашей логики, складывая последовательно цифры числа 3523014, получим 3 + 5 + 2 + 3… — уже на этом этапе получим 13, и число не попадет в список «замечательных», хотя верно обратное.


          1. drch
            12.10.2016 10:18

            Все, понял. Спасибо.


  1. SoLazy
    12.10.2016 09:25

    Совсем не по теме:
    Почему картинки не отображаются ни здесь, ни во многих других статьях? я что-то делаю не так?


    1. wizarts
      12.10.2016 09:36

      Перезалил на habrastorage.org, однако у них сегодня ошибка 500 выдавалась.


  1. urakin
    12.10.2016 11:10

    Например, решение задачи 5 (остальные пока не смотрел) — не верно. Оно не учитывает сочетания степеней простых чисел, поэтому результат завышен.
    Вот моя программа, которая не анализирует, а решает «в лоб»:

    import java.math.BigInteger;
    import java.util.LinkedList;

    public class Task3 {
    public static void main(String[] args) {
    int minA = 3;
    int maxA = 148;
    int minB = 3;
    int maxB = 120;
    LinkedList numbers = new LinkedList<>();
    for (int i = minA; i <= maxA; i++) {
    for (int b = minB; b <= maxB; b++) {
    BigInteger a = new BigInteger(String.valueOf(i));
    a = a.pow(b);
    if (!numbers.contains(a)) {
    numbers.add(a);
    }
    }
    }
    System.out.println(numbers.size());
    }
    }

    Да, не эффективно по ресурсам на вычисление, зато очень даже эффективно, чтобы понять, что 16529 — ответ не верный. Верный — 16355.