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

[qw1]

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]

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

[oleg_agapov]

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

[anandr]

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

[kpcb]

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

[reci]

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

[filazopovich]

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

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

[qw1]

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

[filazopovich]

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

[qw1]

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

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

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

[zabadal]

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

[qw1]

Я догадался, что при запрете использования условий и циклов, условную логику можно осуществить, используя значение массива (тем более, там 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]

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

В 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]

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

Раскрыть

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

[KYKYH]

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

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

[qw1]

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

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

[KYKYH]

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

[reci]

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

[claygod]

2 kind of pills

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

[smer44]

тут интересна только задача на комбинации, ибо вторая задача — на сокращённое 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]

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]

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

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

По сути имеем 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]

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

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]

Таблетки

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

Зарплата

Сначала я подумал что каждому надо добавить случайное число, затем сложиться, и вычесть все три числа. Но тогда получается что сумму можно вычислить постфактум. Значит, им надо ещё и обменяться теми случайными числами по кругу. Пусть 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)
Теперь сс вычитает своё число и делит на три.

1

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

2

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 задание ещё ничего не было) Что значит дополнение? В оригинале более интересный термин, дополнить до укомплектовки. Что есть укомплектованное число?