Комментарии 42
Вопрос N2:
Ответ: Уровень воды уменьшится.
1) Как легко понять, неважно, где камень, в лодке на дне или привязан за веревку и находится полностью в воде. Ну, заменим камень песком или тяжелой жидкостью...
2) Т.е. если утопить камень (или перерезать веревку) сумма объема воды в озере плюс объем камня не изменится.
3) Но лодка всплывет.
4) Значит уровень воды упадет.
Честно говоря, я сначала формулы в Maple написал, удивился результату, а уже потом через некоторое время понял, как без них объяснить.
— камень в лодке на плаву, значит вытеснен объем воды по массе равный массе камня;
— камень на дне, значит вытеснен объем самого камня.
Из того, что плотность камня больше плотности воды (камень тонет), следует, что при одинаковой массе вода имеет больший объем чем камень.
Те. V_озера+V_воды_массой_камня > V_озера+V_камня.
P.S. У меня может быть не совсем понятен только первый пункт. Ну, могу подробнее. Считаем лодку плоскодонкой. Далее давайте условно расплавим камень, потом, сделаем поверх новое дно лодки а низ отрежем — пусть тонет. Понятно, что мы имеем право считать дно лодки невесомым — неважно, где вес сосредоточен.
Путешественник А перевозит все деньги на другой берег. Далее перевозит путешественника Б, но на обратном пути забирает свою тысячу. Забирает путешественника C, оставив свою тысячу на изначальном берегу, после возвращается за ними.
Путешественник А перевозит все деньги на другой берег.
И сбегает с ними…
The problem is that in this process of crossing the river if a traveller is left with an amount of coins more than his own then he will run away with that.
Не совсем понятно условие.
Если число представлено в десятичной записи, то достаточно проверить сумму его цифр на делимость на 3.
Если число десятичное, то школьное правило, если троичное, то ноль в конце, если шестнадцатеричное, то поскольку 16^N mod 3 == 1, то тоже самое школьное правило, для прочих систем счисления тоже можно найти подобные правила (типа как для двоичной — см. google):
На самом деле последовательность вида M^k mod 3, k=1,2,3… где M — основание системы счисления бывает, вроде бы, всего лишь трех типов:
0, 0, 0, 0,…
1, 1, 1, 1…
1, 2, 1, 2,… (или с двойки начинается).
Если первый вариант, то систем «троичная» и надо, чтобы был ноль в конце. Если второй — то «школьное» правило, а вот если третий вариант, то тот же способ, что и для двоичной системы — надо, что бы сумма цифр, стоящих на четных местах, минус сумма, стоящих на нечетных, делилась на три.
A вот если N число задано, например, последовательностью из N единиц, а потом нулем, и неизвестно, на какой системе счисления основан компьютер (или даже просто неизвестно про систему счисления — ну, типа в римских числах), то все становится интереснее.
Обозначение: берег — {лодка} --> берег
B,C, 1000 — {A,1000} --->> 0
B,C, 1000 << — {A} — 1000
A, 1000 — { B,C} --->> 1000
A, 1000 << — {C, 300} — B, 700
C, 300 — {A,1000} -->> B, 700
C, 300 << — {B, 700} — A, 1000
1000 — {B,C} --->> A, 1000
1000 << — {A} — B,C, 1000
0 — {A, 1000} -->> B,C, 1000
Минимум без условий:
min = (a + b – (a – b) & 0x7FFFFFFF) / 2
Задача про деление на три: если разница между суммой четных и нечетных битов делится на три. Сумму считаем примерно как в классическом примере о подсчёте битов.
Разница может быть только меньше 16 для x32 числа и меньше 32 для x64 числа, поэтому для неё можно сделать лукап- таблицу.
попозже может мину исходники: дерево решений для первой и код для других задач.
#define yMIN(a,b) (b- ((a-b) & 0x7FFFFFFF) +a )>>1
#define yMAX(a,b) (b+ ((a-b) & 0x7FFFFFFF) +a )>>1
#define SWAP_NO_IF(a,b,type) { type t = (a^b) & -(a > b); a = a^t; b = b^t;}
uint32_t lookupDiv3[] = {1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0};
int div3(uint32_t x){
uint32_t evens = (x & 0xAAAAAAAA) >> 1;
evens = ((evens>>2) & 0x33333333) + (evens & 0x33333333);
evens = ((evens>>4)+evens) & 0x0F0F0F0F;
evens = ((evens>>8)+evens) & 0x00FF00FF;
evens = ((evens>>16)+evens) & 0xFF;
uint32_t odds = x & 0x55555555;
odds = ((odds>>2) & 0x33333333) + (odds & 0x33333333);
odds = ((odds>>4)+odds) & 0x0F0F0F0F;
odds = ((odds>>8)+odds) & 0x00FF00FF;
odds = ((odds>>16)+odds)& 0xFF;
SWAP_NO_IF(evens, odds, uint32_t);
return lookupDiv3[odds - evens]; //lookupDiv3[odds - evens];
}
2. Туда: B + C, обратно B + 700
3. Туда: A + 1000, обратно C + 300
4. Туда: B + C, обратно A
5. Туда: A + 1000
Когда камень опустился на дно озера, то лодка вытесняет объём воды, равный по массе лодке + человеку, а погрузившийся камень вытесняет меньше, чем раньше, иначе он бы не утонул.
Таким образом, уровень воды снизится.
bool isMultiplyOf3(int number) {
int sum = 0;
while (number) {
sum += (number & 1);
number >>= 1;
sum -= (number & 1);
number >>= 1;
}
return !sum;
}
r = (a+b-abs(a-b))/2;
надеюсь взятие модуля числа и деление на 2 сдвигом недороги на неуказанной абстрактной платформе, где будет исполняться кот
зависит от представления отрицательных чисел — в обратном, дополнительном до 1 или дополнительном до 2 коде. где-то достаточно просто занулить знаковый бит по И по маске, где-то просто прибавить максимальное число разрядной сетки умноженное на знаковый бит, сдвинутый вправо на ту же величину разрядной сетки — получается мы прибавляем макс_сигнед_инт умноженный на 1 если число отрицательное и на 0 если положительное — и получаем модуль числа.
но это уже детали реализации. стравлю 200 денег, что составители задачи хотели увидеть именно такое решение, как написано выше
del
Вопрос 2 — на физфаке нас учили проверять формулы и модели устремляя какие-либо величины к крайним значениям. Допустим, у нас камень из страшного вещества с огромной плотностью, диаметром сантиметр и массой тонну. Пока он лежит в лодке — лодка сильно погружена в воду и вытесняет существенный объем. Когда мы выкинем камень, его объем почти не скажется на результате, за то лодка существенно поднимается и уровень воды опустится. Варианты когда плотность камня меньше плотности воды или воздуха рассматривать лень — думаю ответа выше вполне достаточно.
Варианты когда плотность камня меньше плотности воды или воздуха рассматривать лень
Камень плотность которого меньше воздуха — взлетит), камень плотность которого меньше воды — всплывет)). За условием задачи камень упал на дно — значит его плотность больше плотности воды.
Его можно силой затащить на дно, привязав веревкой к коряге )) И тогда уровень воды поднимется — по той же логике крайних значений — представьте что вы везли в лодке огромный воздушный шар )) И это стройно укладывается в модель — при плотности камня больше плотности воды уровень опустится, при меньше — поднимется. А если камень деревянный, и не затаскивать его на дно, а позволить плавать свободно после выкидывания за борт — то вангую что уровень не изменится — но надо аккуратнее разобрать этот вариант для уверенности )
А если камень плавучий, то действительно не изменится.
Квайн:
1
проверяется в любом РЕПЛе
я не думаю, что составители задачи будут в восторге от такого ответа, но квайнопись сильно зависит от языка — а он не был озвучен. Или это интервью в ту компанию, где кроме С языков не знают? ))
Дальше что угодно.
-2 уезжает со своими 700 и оставляет там, возвращаясь
-3 берёт 300 и отвозит на тот берег, возвращается (ведь у него и своих столько же)
-отбывают 1 и 2, кто-то из них возвращается со своим, чтобы его место на том берегу занял 3 (со своим)
-отбывает второй со своим, теперь оба переезжают без мешков, все три путника на другом берегу
-3 плывёт назад за 700 и возвращается
-1 плывёт назад за 300 и возвращается
a = []
a.append("a")
a.append(" = []")
a.append(".append")
a.append("(")
a.append("\"")
a.append(")")
a.append("\\")
a.append("a")
a.append("print(a[0] + a[1])")
a.append("for i in range(13):")
a.append(" print(a[0] + a[2] + a[3] + a[4] + a[6] + a[i] + a[4] + a[5] if (i==4 or i ==6) else a[0] + a[2] + a[3] + a[4] + a[i] + a[4] + a[5])")
a.append("for i in range(8, 13):")
a.append(" print(a[i])")
print(a[0] + a[1])
for i in range(13):
print(a[0] + a[2] + a[3] + a[4] + a[6] + a[i] + a[4] + a[5] if (i==4 or i ==6) else a[0] + a[2] + a[3] + a[4] + a[i] + a[4] + a[5])
for i in range(8, 13):
print(a[i])
Выпуск#11: ITренировка — актуальные вопросы и задачи от ведущих компаний