reci Mar 2 2018 at 19:38

Выпуск#13: ITренировка — актуальные вопросы и задачи от ведущих компаний

4 min

6.5K

Spice IT Recruitment corporate blogEntertaining tasksProgramming*

+12

Comments 26

qw1 Mar 2 2018 at 22:07

Avg Salary

Пусть участники A, B, C имеют зарплаты a, b, c.
Каждый участник загадывает случайное число от 1 до 1.000.000.000.
Участник A передаёт своё загаданное число ar участнику C (в тайне от B).
Участник B передаёт своё загаданное число br участнику A (в тайне от C).
Участник C передаёт своё загаданное число cr участнику B (в тайне от A).
Затем A передаёт x1=(a+ar) участнику B.
B прибавляет b, br и вычитает cr, передаёт x2=x1+b+br-cr=a+ar+b+br-cr участнику C.
C передаёт x3=x2+c+cr-ar=a+ar+b+br-cr+c+cr-ar участнику A.
A вычисляет x4=x3-br=a+ar+b+br-cr+c+cr-ar-br=a+b+c и объявляет x4 всем.
Средняя зарплата — это x4/3 = (a+b+c)/3

AlexTest Mar 3 2018 at 03:32

Можно гораздо проще. Они скрыто друг от друга берут игровые фишки от любой игры в эквиваленте своей зарплаты и так, чтобы никто другой не видел (например зажав жменю фишек в руке) кладут их в непрозрачный мешок, встряхивают его для надежности, пересчитывают содержимое мешка и делят на 3.

oleg_agapov Mar 3 2018 at 07:41

Хм, интересно. Я подумал про вариант, когда каждый пишет на свою з\п на листочке и кладет в шапку. Потом достаем и считаем среднее. Вроде условия задачи выполняются.
Интересно, прокатило бы на собеседовании?

anandr Mar 3 2018 at 11:28

Пусть все N работников скинутся каждый по 1/N своей зарплаты в непрозрачную банку. Останется посчитать.

Swiftarrow7 Mar 3 2018 at 13:47

Например, с помощью программы

Можно написать программу сервер, которая принимает значения от участников (может быть N количеством), в данном случае они максимум смогут узнать о среднем! Да и зная средняя и положения сотрудников в компании можно приблизительно вычислить среднее, а таким методом можно скрыть и среднее =)

kpcb Mar 3 2018 at 19:12

Первый говорит второму случайное число, второй говорит третьему это число + своя з.п, третий говорит первому то, что услышал от второго + своя з.п. Первый добавляет к услышанному свою з.п, вычитает своё случайное число и делит результат на 3

reci Mar 5 2018 at 09:14

Если это в открытом помещении — то первый может вычислить зарплату второго и третьего.

filazopovich Mar 4 2018 at 09:00

Можно немного упростить.

Первый сотрудник должен выбрать случайное число и запомнить его. К нему прибавить свою зарплату, записать на бумажку и передать следующему сотруднику.
Следующий, в свою очередь, должен прибавить свою зарплату к числу на бумажке и заменить его результатом.
Повторяем процесс пока не закончатся сотрудники и передаём бумажку с результатом первому
первый вычитает заполненное им случайное число из результата и делит получившееся на количество сотрудников.
То бишь:
((Seed + x1 + x2 +… + xn) — Seed ) / n

qw1 Mar 4 2018 at 18:07

Только для безопасности нельзя «передавать» одну бумажку, нужно каждый раз заменять её новой.
Если все промежуточные суммы окажутся на одной бумажке, следующему легко будет понять, сколько прибавил предыдущий сотрудник.

filazopovich Mar 4 2018 at 18:41

Как я и написал, число на бумажке каждый раз заменяется. И да! Бумажка должна иметь возможность полного удаления надписи и её следов :)

qw1 Mar 2 2018 at 22:23

Boolean Array Puzzle
Я так полагаю, что дополнение — это инверсия: !x, или (1-x) для чисел {0,1}
В таком случае, решение:

Скрытый текст

arr[!arr[0]] = arr[!arr[1]]

zabadal Mar 3 2018 at 07:41

А вы действительно решили или знали решение? Если решили — не могли бы вы описать ход мысли?

qw1 Mar 3 2018 at 16:54

Я догадался, что при запрете использования условий и циклов, условную логику можно осуществить, используя значение массива (тем более, там 0 или 1), как индекс.
Я ожидал, что решение будет элементарным, типа a[!a[1]] = a[0], но точно не знал, каким.
Затем я накатал маленькую программку:

#include <stdio.h>

int main()
{
        for (int i = 0; i < 3; i++) {
                int a[2] = { i >> 1, i & 1 };
                a[a[0]] = !a[1];
                printf("%d %d -> %d %d\n", i >> 1, i & 1, a[0], a[1]);
        }
        return 0;
}

И подставлял туда разные формулы, пока не получил два столбца нулей. Это заняло 10-20 итераций, и как оказалось, формула получилась сложнее, чем я ожидал )))

Возможно, есть более простая формула, эту я нашёл слепым подбором.

KYKYH Mar 6 2018 at 20:18

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

В Roslyn C#, например, прямой конвертации булевых значений в числа нет: вместо этого в функции `Convert.ToInt32(bool value)` используется условная операция, что нарушает условия задачи.

А вывести формулу можно разложив массивы на бумаге. У нас всего три варианта: [1,0] [0,1] [0,0]. Сразу ясно, что нужно использовать структуру a[x], где x = a[y], поскольку заполняя x заранее выбранным значением мы условную логику не сможем симулировать, только перестановку. Дальше разложим наши варианты a[a[y]]: всего четыре штуки на каждый массив. Из них два примечательных: a[a[0]] всегда указывает на значение 0, a[!a[0]] всегда указывает на значение 1, если оно присутствует. Стало быть a[!a[0]] = a[a[0]] заменит 1 на 0 в тех случаях, когда 1 есть, а когда его нет — заменит 0 на 0.

qw1 Mar 10 2018 at 16:31

На C# эта задача тоже решается.

Раскрыть

arr[arr[1]] = arr[arr[0]];

KYKYH Mar 11 2018 at 04:14

Вот именно это решение будет работать только при условии что исходные элементы числового типа. В языке нет неявного преобразования типа bool в int, поэтому всё в конце концов упрётся в декларацию arr.

`int[] arr = {0, 1};` вполне сработает, а `bool[] arr = {false, true};` уже нет. Так что постановка задачи как «Boolean array puzzle» в конкретно этом случае подходит не вполне. Пример.

qw1 Mar 11 2018 at 11:04

Заголовок задачи можно считать лирическим отсуплением, но в условии написано конкретно

A array arr[] of two elements having value 0 and 1

KYKYH Mar 11 2018 at 18:06

Признаюсь занудой.

reci Mar 3 2018 at 17:41

Да, «инверсия», пожалуй лучше подходит по смыслу

claygod Mar 2 2018 at 23:19

2 kind of pills

Просто добавить ещё одну таблетку А в стакан, перемешать и выпить полстакана..?
Если важна концентрация, то можно ещё добавить воды, но вроде про концентрацию ничего не сказано.

Swiftarrow7 Mar 3 2018 at 13:44

Почти тоже

Я подумал, что можно просто стакан разделить на 2 по половинке, далее разбавить А таблетку в новом и влить по половине в два полученный из исходного, тогда и концентрация, по идеи, также останется.

smer44 Mar 3 2018 at 04:54

тут интересна только задача на комбинации, ибо вторая задача — на сокращённое x mod 10, а в третьей не корректное условие и с такими ограничениями не хочется решать.
вот корявый псевдокод:
обозначим combo(x,n) количество комбинаций для числа x с n цифрами.
например combo(4,2) = count ((1,3), (2,2), (3,1)) = 3
очевидно что combo(x,2) = x-1
тогда combo (x,n ) = summ(i = 1..(x-n+1)), combo(x-i,n-1)
например
combo (5,3 ) = (1,1,3 ), (1,2,2) (1,3,1), (2,1,2), (2,2,1), (3,1,1) = combo(4,2) + combo(3,2), + combo(2,2))) = 3 + 2 + 1
или
combo(6,4) = combo(5,3)+combo(4,3)+combo(3,3) = 6 + 3+1
все комбинации для числа x:
combo(x) = combo(x,1)+ combo(x,2) +… + combo(x,x)

smer44 Mar 3 2018 at 05:13

import java.util.Arrays;

public class SummCombos {

	public static int count(int x) {
		calls = 0;
		int[][] lookup = new int[x+1][x+1];

		for (int i = 0; i < lookup.length; i++) {
			Arrays.fill(lookup[i], -1);
		}

		int summ = 0;
		for (int n = 1; n <= x; n++) {
			summ += count(x, n, lookup);
		}

		return summ;
	}

	public static int calls = 0;

	public static int count(int x, int n, int[][] lookup) {
		calls++;
		int summ;
		if ((summ = lookup[x][n]) > 0) {
			return summ;
		}
		if (n == x || n == 1)
			summ = 1;

		if (n == 2)
			summ = x - 1;
		if (summ < 0) {
			summ = 0;
			int limit = x - n + 1;
			int nm1 = n - 1;
			for (int i = 1; i <= limit; i++) {
				summ += count(x - i, nm1, lookup);
			}
		}
		lookup[x][n] = summ;
		return summ;

	}
	
	public static void main(String[] args) {
				
		int maxX = 30;
		
		for (int i = 1; i < maxX; i++) {
			System.out.println("i: " + i + " count : " + count(i) + " calls " + calls);
		}
		
		
		
	}
}

и тогда видим что:

i: 1 count : 1 calls 1

i: 2 count : 2 calls 2

i: 3 count : 4 calls 3

i: 4 count : 8 calls 6

i: 5 count : 16 calls 12

i: 6 count : 32 calls 22

i: 7 count : 64 calls 37

i: 8 count : 128 calls 58

i: 9 count : 256 calls 86

i: 10 count : 512 calls 122

i: 11 count : 1024 calls 167

i: 12 count : 2048 calls 222

i: 13 count : 4096 calls 288

i: 14 count : 8192 calls 366

i: 15 count : 16384 calls 457

i: 16 count : 32768 calls 562

i: 17 count : 65536 calls 682

i: 18 count : 131072 calls 818

i: 19 count : 262144 calls 971

i: 20 count : 524288 calls 1142

i: 21 count : 1048576 calls 1332

i: 22 count : 2097152 calls 1542

i: 23 count : 4194304 calls 1773

i: 24 count : 8388608 calls 2026

i: 25 count : 16777216 calls 2302

i: 26 count : 33554432 calls 2602

i: 27 count : 67108864 calls 2927

i: 28 count : 134217728 calls 3278

i: 29 count : 268435456 calls 3656

и код можэно сократить до 2^(x-1) или 1 << (x-1)

KYKYH Mar 7 2018 at 07:47

На самом деле, задача на основы мат анализа.

Если записать выражение через сигму, то постановка задачи станет яснее.

По сути имеем n,n-1+1, n-2+1+1… 1+n-1, n-2+2, n-3+2+1...2+n-2...1/2n+1/2n. Остаётся только решить сигму.

kardan2 Mar 4 2018 at 09:02

Выпуск не понравился, половину заданий я не понял.

1 Вопрос

В чем суть вопроса? В том, чтобы добавить ещё одну таблетку для равновесия, и потом разделить коктель на 2 дозы вертикальной перегородкой (лекарства могут быть слоями с разными плотностями)

Вопрос 2

Не понятно зачем, и не понятно что можно делать. Для себя я понял вопрос так: нужно узнать среднюю, но чтобы никто не узнал ЗП другого работника. Первый человек говорит второму случайное число(и запоминает его). Второй прибавляет свою ЗП к числу и говорит сумму третьему. Третий также прибавляет свою ЗП и говорит первому. Первый с данному значению прибавляет свою ЗП и отнимает запомненное число. Делит на 3 и говорит всем среднюю ЗП.

Задача 1

2^(n-1). Почему так? Возмем число 7, разобьем его на семь единиц. 7 = 1 1 1 1 1 1 1. Между 7-ю единицами есть 6 промежутков. В каждом из промежутков может либо быть "+", либо не быть. Единицы, между которыми нет плюса объединяем в одно число. 7=11+1+1+111=2+1+1+3. Каждая комбинация плюсов дает 1 последовательность, и каждая последовательность дает ровно 1 комбинацию. Поэтому число их вариантов одинаково.

Задача 2

Логично такую задачу решать рекурсией. Но рекурсия обрабатывает разряды со старшего, при этом, если в старших разрядах есть 3, то от младших ничего не зависит. т.е. 35 и 38 дадут одинаковое кол-во. Поэтому, если найдена 3, то делаем число отрицательным и передаем его вверх. Не сложно заметить, что 10 — это 9 комбинаций, 100-это 9*9=81 комбинаций, 1000-это 9*9*9 комбинаций.
Код не причесан, но решение должно быть понятно.

public static boolean isRight(int _i){
        int h = _i;
        while(h>0){
            int hh = h/10;
            if(h-hh*10==3){
                return false;
            }
            h = hh;
        }
        return true;
    }
    
    public static void main(String[] _a){
        for(int i=1; i<100000; i++){
            int z1 = bruteforce(i);
            int z2 = Math.abs(shum(i, 1));
            if(z1!=z2){
                System.out.println(" "+i+"   "+z1+"   "+z2);
            }
        }
    }
    
    public static int bruteforce(int _h){
        int s = 0;
        for(int i=1; i<=_h; i++){
            if(isRight(i)){
                s++;
            }
        }
        return s;
    }
    
    public static int shum(int _h, int _power){
        if(_h==0){return 0;}
        int g = _h/10;
        int c = _h-g*10;
        int d = shum(g, 9*_power);
        if(d<0){return d;}
        if(c<3){return d+c*_power;}
        if(c>3){return d+(c-1)*_power;}
        return (shum(g, 9*_power)+c*_power-1)*-1;
    }

В коде идет проверка моего способа с полным перебором.

Задачу 3 не понял.

Nick_mentat Mar 6 2018 at 14:50

Таблетки

Растворить ещё одну А и выпить полстакана, тщательно перемешав. Вторую половину на завтра.

Зарплата

Сначала я подумал что каждому надо добавить случайное число, затем сложиться, и вычесть все три числа. Но тогда получается что сумму можно вычислить постфактум. Значит, им надо ещё и обменяться теми случайными числами по кругу. Пусть a, b, c — зарплаты; A, B, C — их личные случайные числа. aa<< — информация, которую получил aa.
bb<< (a+A)
cc<< (a+A+b+B)
aa<< (a+A+b+B+c+C)
bb<< (a+b+B+c+C)
cc<< (a+b+c+C)
Теперь сс вычитает своё число и делит на три.

Можно написать слегка оптимизированный перебор — перебрать упорядоченные наборы, умножая каждый новый на количество перестановок.

def not3(x):
    if x < 3:
        return x
    b = 1
    a = -1
    while b < x:
        b *= 10
        a += 1
    b //= 10
    res = x//b
    if res > 3: res -= 1
    res2 = 0
    for i in range(a):
        res2 *= 9
        res2 += 10**i
    res = res * b - res * res2 + not3(x % b)
    return res

Более непонятного чем 3 задание ещё ничего не было) Что значит дополнение? В оригинале более интересный термин, дополнить до укомплектовки. Что есть укомплектованное число?