Розбір завдань першого етапу відбору в школу програмістів HeadHunter 2016

У вересні 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,простих чисел){
for (var j=0, len=простих чисел.length; j<len; j++){
if (x%простих чисел[j]==0) return false;
}
return true;
}

Підсумкова функція підрахунку S(n):

function task2(n) {
for (var i=4, count=2, простих=[2,3]; i < =n; i++){
// якщо число - парне
if (i%2==0) {
count+=i/2-1;
} else {
// непарне
count+=(i-1)/2-1;
// якщо не можна представити як суму двох простих чисел
if (i!=(простих чисел[простих чисел.length-1]+2)) {
count--;
}
// якщо число - просте
if (isPrime(i,простих чисел)) {
count++;
// додаємо новий просте число в загальний ряд
простих чисел[простих чисел.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 простих = [2,3,5,7,11];
// перебираючи ряд простих чисел, визначаємо, чи можна уявити число ступенем
for (var i=0; i < простих чисел.length; i++) {
power = isPowerOf(a,простих чисел[i]);
if (power>1) {
break;
}
}
for (var b=b1+1, idx="; b<b2; b++){
// задамо черговий асоціативний індекс для масиву всіх варіацій a в b ступеня
idx = (power>1)? "a"+простих чисел[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.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.