Задачи : Вопрос 1 : 61

Есть таблица результатов команд в футбольных чемпионатах вида:

Championship - Table(Liga, Team, Scores), ключами являются первые два поля. В каждом чемпионате больше 1 команды.
Необходимо вывести чемпионов и аутсайдеров(посл.место) каждой лиги. Обойтись без под запросов.

Таблица:

   Liga            Team           Scores 
1   England        Arsenal          83 
2   England        Chelsea          85 
3   Germany        Bayern           90 
4   Germany        Dortmund         99 
5   Germany        Gerta            91 
6   Italy          Inter            80 
7   Italy          Milan            75 
8   Spain          Barcelona        70 
9   Spain          Real-Madrid      90 

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Классическое решение с подзапросом выглядело бы следующим образом:

select Liga, Team, [Scores]  
from Championship ch1 
where [Scores] = (select max([Scores])    -- Max - для 'чемпионов' / Min - для 'аутсайдеров' -- 
  from Championship ch2  
  where ch1.Liga = ch2.Liga) 


Разберем как можно выполнить эту задачу без использования под запросов:
1. Нам необходимо c 'join'ить одну и ту же таблицу по определенному условию

    select * from Championship ch1 
    left join Championship ch2 on ch1.Scores < ch2.Scores and ch1.Liga = ch2.Liga 
 
    Liga          Team        Scores      Liga         Team         Scores 
1    England      Arsenal       83       England      Chelsea         85 
2    England      Chelsea       85       NULL         NULL           NULL 
3    Germany      Bayern        90       Germany      Dortmund        99 
4    Germany      Bayern        90       Germany      Gerta           91 
5    Germany      Dortmund      99       NULL         NULL           NULL 
6    Germany      Gerta         91       Germany      Dortmund        99 
7    Italy        Inter         80       NULL         NULL           NULL 
8    Italy        Milan         75       Italy        Inter           80 
9    Spain        Barcelona     70       Spain        Real-Madrid     90 
10    Spain       Real-Madrid   90       NULL         NULL           NULL 


Фактически мы взяли каждую строку из первой таблицы ch1 и каждую строку из второй таблицы ch2, но с условием, что очки из таблицы ch1 должны быть строго меньше, чем очки из второй таблицы, и при условии, что проверятся должны команды только одного чемпионата.

Соответственно это условие не выполнится только для тех команд, которые являются лидерами в своих лигах (ch1.MaxScoreByLiga < ch2.MaxScoreByLiga), в этом случае в этих строках будет Null для элементов из таблицы ch2.

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


select * from Championship ch1 
left join Championship ch2 on ch1.Scores > ch2.Scores and ch1.Liga = ch2.Liga 


2. Подправим запрос и выведем итоговый запрос

2.а Для вывода чемпионов всех лиг

select ch1.Liga, ch1.Team, ch1.Scores from Championship ch1 
left join Championship ch2 on ch1.Scores < ch2.Scores and ch1.Liga = ch2.Liga 
where ch2.Scores is NULL 
 
     Liga            Team         Scores 
1    England        Chelsea        85 
2    Germany        Dortmund       99 
3    Italy          Inter          80 
4    Spain          Real-Madrid    90 


2.b Для вывода аутсайдеров всех лиг

select ch1.Liga, ch1.Team, ch1.Scores from Championship ch1 
left join Championship ch2 on ch1.Scores > ch2.Scores and ch1.Liga = ch2.Liga 
where ch2.Scores is NULL 
     
     Liga            Team         Scores 
1    England        Arsenal        83 
2    Germany        Bayern         90 
3    Italy          Milan          75 
4    Spain          Barcelona      70 

Есть таблица результатов команд в футбольных чемпионатах вида:

Championship - Table(Liga, Team, Scores), ключами являются первые два поля. В каждом чемпионате больше 1 команды.
Необходимо вывести чемпионов и аутсайдеров(посл.место) каждой лиги. Обойтись без под запросов.

Таблица:

   Liga            Team           Scores 
1   England        Arsenal          83 
2   England        Chelsea          85 
3   Germany        Bayern           90 
4   Germany        Dortmund         99 
5   Germany        Gerta            91 
6   Italy          Inter            80 
7   Italy          Milan            75 
8   Spain          Barcelona        70 
9   Spain          Real-Madrid      90 

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Классическое решение с подзапросом выглядело бы следующим образом:

select Liga, Team, [Scores]  
from Championship ch1 
where [Scores] = (select max([Scores])    -- Max - для 'чемпионов' / Min - для 'аутсайдеров' -- 
  from Championship ch2  
  where ch1.Liga = ch2.Liga) 


Разберем как можно выполнить эту задачу без использования под запросов:
1. Нам необходимо c 'join'ить одну и ту же таблицу по определенному условию

    select * from Championship ch1 
    left join Championship ch2 on ch1.Scores < ch2.Scores and ch1.Liga = ch2.Liga 
 
    Liga          Team        Scores      Liga         Team         Scores 
1    England      Arsenal       83       England      Chelsea         85 
2    England      Chelsea       85       NULL         NULL           NULL 
3    Germany      Bayern        90       Germany      Dortmund        99 
4    Germany      Bayern        90       Germany      Gerta           91 
5    Germany      Dortmund      99       NULL         NULL           NULL 
6    Germany      Gerta         91       Germany      Dortmund        99 
7    Italy        Inter         80       NULL         NULL           NULL 
8    Italy        Milan         75       Italy        Inter           80 
9    Spain        Barcelona     70       Spain        Real-Madrid     90 
10    Spain       Real-Madrid   90       NULL         NULL           NULL 


Фактически мы взяли каждую строку из первой таблицы ch1 и каждую строку из второй таблицы ch2, но с условием, что очки из таблицы ch1 должны быть строго меньше, чем очки из второй таблицы, и при условии, что проверятся должны команды только одного чемпионата.

Соответственно это условие не выполнится только для тех команд, которые являются лидерами в своих лигах (ch1.MaxScoreByLiga < ch2.MaxScoreByLiga), в этом случае в этих строках будет Null для элементов из таблицы ch2.

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


select * from Championship ch1 
left join Championship ch2 on ch1.Scores > ch2.Scores and ch1.Liga = ch2.Liga 


2. Подправим запрос и выведем итоговый запрос

2.а Для вывода чемпионов всех лиг

select ch1.Liga, ch1.Team, ch1.Scores from Championship ch1 
left join Championship ch2 on ch1.Scores < ch2.Scores and ch1.Liga = ch2.Liga 
where ch2.Scores is NULL 
 
     Liga            Team         Scores 
1    England        Chelsea        85 
2    Germany        Dortmund       99 
3    Italy          Inter          80 
4    Spain          Real-Madrid    90 


2.b Для вывода аутсайдеров всех лиг

select ch1.Liga, ch1.Team, ch1.Scores from Championship ch1 
left join Championship ch2 on ch1.Scores > ch2.Scores and ch1.Liga = ch2.Liga 
where ch2.Scores is NULL 
     
     Liga            Team         Scores 
1    England        Arsenal        83 
2    Germany        Bayern         90 
3    Italy          Milan          75 
4    Spain          Barcelona      70 

Вы находитесь на скале высотой 100 метров. На высоте в 50 метров из скалы торчит сук, на который можно встать. У вас есть канат длиной 75 метров. Используя канат можно спуститься со скалы. Канат можно разрезать.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Режем канат на две части - 50 метров и 25 метров. На конце 25-метрового каната делаем маленькую петлю, и через нее продеваем 50-метровый канат, сложенный пополам (т.е. через петлю проходит середина 50-метрового каната). Получаем общую длину 25 + (50 /2) = 50 метров. Спускаемся на сук, вытягиваем 50-метровый канат, и теперь можем спуститься с сука вниз.

Вы находитесь на скале высотой 100 метров. На высоте в 50 метров из скалы торчит сук, на который можно встать. У вас есть канат длиной 75 метров. Используя канат можно спуститься со скалы. Канат можно разрезать.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Режем канат на две части - 50 метров и 25 метров. На конце 25-метрового каната делаем маленькую петлю, и через нее продеваем 50-метровый канат, сложенный пополам (т.е. через петлю проходит середина 50-метрового каната). Получаем общую длину 25 + (50 /2) = 50 метров. Спускаемся на сук, вытягиваем 50-метровый канат, и теперь можем спуститься с сука вниз.

Дан массив. Требуется найти подмассив максимальной суммы.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Понятно, что это можно сделать множеством способов: и тривиальным перебором, и методом разделяй и властвуй, но как сделать это легко и эффективно?
В первом случает сложность O(n^3), во втором O(n*log(n)), хотя его можно допилить до линейного по времени.
Но задачу можно решить за один проход с использованием константной дополнительной памяти!

Обозначим массив A[1, n], а задачу - M.
Рассмотрим префикс A[1, i] и решим задачу MR[i]: у каждого суффикса A[i, j] (0 <= i <= j), есть сумма, требуется выбрать из них максимум.
Понятно, что M = max(MR[i]), i = 1..n.
Для решения задачи MR[i] решим задачу mL[i] - найдём минимум сумм всех префиксов A[1, j], где 0 <= j <= i.
Эта задача решается элементарно: считаем кумулятивные суммы S[i] и помним минимум среди них s[i].
Понятно, что MR[i] = S[i] - s[i].
Итак, за один проход можно найти все S[i] и s[i], а значит и MR[i].
Далее можно вторым проходом найти максимум MR[i] и решить исходную задачу.
Но можно сделать ещё лучше: необязательно помнить все MR[i] достаточно поддерживать только их максимум.

Дан массив. Требуется найти подмассив максимальной суммы.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Понятно, что это можно сделать множеством способов: и тривиальным перебором, и методом разделяй и властвуй, но как сделать это легко и эффективно?
В первом случает сложность O(n^3), во втором O(n*log(n)), хотя его можно допилить до линейного по времени.
Но задачу можно решить за один проход с использованием константной дополнительной памяти!

Обозначим массив A[1, n], а задачу - M.
Рассмотрим префикс A[1, i] и решим задачу MR[i]: у каждого суффикса A[i, j] (0 <= i <= j), есть сумма, требуется выбрать из них максимум.
Понятно, что M = max(MR[i]), i = 1..n.
Для решения задачи MR[i] решим задачу mL[i] - найдём минимум сумм всех префиксов A[1, j], где 0 <= j <= i.
Эта задача решается элементарно: считаем кумулятивные суммы S[i] и помним минимум среди них s[i].
Понятно, что MR[i] = S[i] - s[i].
Итак, за один проход можно найти все S[i] и s[i], а значит и MR[i].
Далее можно вторым проходом найти максимум MR[i] и решить исходную задачу.
Но можно сделать ещё лучше: необязательно помнить все MR[i] достаточно поддерживать только их максимум.

Трём хирургам необходимо последовательно прооперировать в полевых условиях больного, страдающего заразным заболеванием. Сами хирурги тоже больны, причём все - разными болезнями. В распоряжении хирургов есть лишь две пары стерильных перчаток. Подскажите план операции, после которой ни хирурги, ни больной не заразятся друг от друга. (Помогать друг другу во время операций хирурги не должны. Оперировать одной рукой нельзя.)

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

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

Трём хирургам необходимо последовательно прооперировать в полевых условиях больного, страдающего заразным заболеванием. Сами хирурги тоже больны, причём все - разными болезнями. В распоряжении хирургов есть лишь две пары стерильных перчаток. Подскажите план операции, после которой ни хирурги, ни больной не заразятся друг от друга. (Помогать друг другу во время операций хирурги не должны. Оперировать одной рукой нельзя.)

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

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

На необитаемом острове живут люди только либо с голубыми, либо с карими глазами (у любого взятого наугад жителя глаза будут либо того, либо другого цвета). Если кто-то узнаёт цвет своих глаз, то он совершает обрядное самоубийство ровно в полдень на главной площади на виду у всех. Все жители очень-очень умны и обладают хорошей логикой, поэтому никто из жителей острова на эту тему друг с другом не общается.
Однажды к ним приехал путешественник, а, уезжая, после тёплого приёма, он сказал: "Я рад, что встретил на этом острове таких добрых людей и людей с такими же, как у меня, голубыми глазами." 

Что произошло после его уезда?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

По математической индукции все жители острова умерли, так как путешественник дал им базу индукции.

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

На необитаемом острове живут люди только либо с голубыми, либо с карими глазами (у любого взятого наугад жителя глаза будут либо того, либо другого цвета). Если кто-то узнаёт цвет своих глаз, то он совершает обрядное самоубийство ровно в полдень на главной площади на виду у всех. Все жители очень-очень умны и обладают хорошей логикой, поэтому никто из жителей острова на эту тему друг с другом не общается.
Однажды к ним приехал путешественник, а, уезжая, после тёплого приёма, он сказал: "Я рад, что встретил на этом острове таких добрых людей и людей с такими же, как у меня, голубыми глазами." 

Что произошло после его уезда?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

По математической индукции все жители острова умерли, так как путешественник дал им базу индукции.

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

Имеется шоколадка 100х100 плиток. Малыш и Карлсон по очереди отламывают от нее куски (один кусок за ход) вдоль углубления (т.е. прямоугольные куски). Проигрывает тот, кто не сможет сделать ход. Кто выиграет при правильной игре, если Малыш ходит первым?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Выиграет Карлсон. 

Объяснения: Малыш на своем ходу делает шоколадку прямоугольником, а Карлсон отламывает так, что бы снова был квадрат, и так до тех пор, пока у Малыша не останется шоколадка 1Х1.

Имеется шоколадка 100х100 плиток. Малыш и Карлсон по очереди отламывают от нее куски (один кусок за ход) вдоль углубления (т.е. прямоугольные куски). Проигрывает тот, кто не сможет сделать ход. Кто выиграет при правильной игре, если Малыш ходит первым?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Выиграет Карлсон. 

Объяснения: Малыш на своем ходу делает шоколадку прямоугольником, а Карлсон отламывает так, что бы снова был квадрат, и так до тех пор, пока у Малыша не останется шоколадка 1Х1.

Есть 3 ящика с фруктами (груши и сливы). В одном - только сливы, во втором - только груши, а в третьем - смесь плодов. На каждом ящике табличка, на которой написано не то, что на самом деле лежит в ящике (например, на ящике с грушами написано "смесь"). Нужно правильно перевесить таблички достав только один фрукт из любого ящика.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Доставать нужно из ящика на котором написано "смесь". Так как таблички врут, то какой плод оттуда достанем, такие фрукты там и находятся. А дальше методом исключения. Например, достали сливу - значит в ящике где написано "сливы" лежат груши, а в оставшемся - смесь.

Есть 3 ящика с фруктами (груши и сливы). В одном - только сливы, во втором - только груши, а в третьем - смесь плодов. На каждом ящике табличка, на которой написано не то, что на самом деле лежит в ящике (например, на ящике с грушами написано "смесь"). Нужно правильно перевесить таблички достав только один фрукт из любого ящика.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Доставать нужно из ящика на котором написано "смесь". Так как таблички врут, то какой плод оттуда достанем, такие фрукты там и находятся. А дальше методом исключения. Например, достали сливу - значит в ящике где написано "сливы" лежат груши, а в оставшемся - смесь.

На монетном дворе работает 101 чеканщик, каждый делает в день 100 монет по 10 грамм каждая. Но один делает 100 монет массой по 9 грамм. Имеются современные электронные весы, показывающие массу. Разрешается сделать только одно взвешивание и сказать, кто фальшивомонетчик. Как это сделать?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Берём от чеканщиков: у первого - 1 монету, у второго - 2, .... от 100го - 100. Взвешиваем монеты. На сколько грамм меньше, чем в идеале, получаем порядковый номер фальшивомонетчика. Если вес идеальный - значит последний.

На монетном дворе работает 101 чеканщик, каждый делает в день 100 монет по 10 грамм каждая. Но один делает 100 монет массой по 9 грамм. Имеются современные электронные весы, показывающие массу. Разрешается сделать только одно взвешивание и сказать, кто фальшивомонетчик. Как это сделать?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Берём от чеканщиков: у первого - 1 монету, у второго - 2, .... от 100го - 100. Взвешиваем монеты. На сколько грамм меньше, чем в идеале, получаем порядковый номер фальшивомонетчика. Если вес идеальный - значит последний.

Двое маляров встречают на дороге еще двоих маляров. У всех них перепачканы руки разными красками. Как используя всего две перчатки двум малярам обменяться рукопожатиями с другими двумя малярами, чтобы их руки не испачкались чужими красками? Перчатки можно передавать и выворачивать.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Пусть первые два маляра A и B, а другие два - C и D.
1. A и C одевают перчатки и здороваются, в итоге их перчатки запачканы с одной стороны соответствующими их цветами, а с другой стороны чистые. 
2. A не снимает перчатку и здоровается с D. Перчатка пачкается в цвет D после этого. Выворачиваем ее и отдаем маляру D.
3. аналогичная ситуация с C и B.
4. B и D здороваются через перчатки.

Двое маляров встречают на дороге еще двоих маляров. У всех них перепачканы руки разными красками. Как используя всего две перчатки двум малярам обменяться рукопожатиями с другими двумя малярами, чтобы их руки не испачкались чужими красками? Перчатки можно передавать и выворачивать.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Пусть первые два маляра A и B, а другие два - C и D.
1. A и C одевают перчатки и здороваются, в итоге их перчатки запачканы с одной стороны соответствующими их цветами, а с другой стороны чистые. 
2. A не снимает перчатку и здоровается с D. Перчатка пачкается в цвет D после этого. Выворачиваем ее и отдаем маляру D.
3. аналогичная ситуация с C и B.
4. B и D здороваются через перчатки.

На столе в тёмной комнате лежат 100 монет. 10 из них лежат решёткой вверх, остальные - орлом.
Разрешается:
1) делить кучку монет на две кучки (не обязательно равные, можно отсчитывать нужное кол-во, 1 монета - уже кучка)
2) переворачивать все монеты одной из кучек
3) совмещать кучки
Какие монеты как лежат неизвестно. Никак нельзя зафиксировать какую-то монету, чтобы определить переворачивалась она или нет.Разумеется ни на ощупь, ни как-то иначе определить состояние монеты относительно другой нельзя.
Требуется разделить эти 100 монет на две кучки, в которых равное кол-во монеток лежащих решёткой вверх.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Отделяем 10 монет от основной кучки и переворачиваем их.

Основную кучку с уже отделёнными монетами будем называть А. Кучку, в которой отделенные монеты, будет называть В.
1) Если в кучке В оказалось N монеток решёткой вверх, когда их только отделили, то, перевернув всю кучку В, получим 10-N монет решёткой вверх (так как всего в кучке В 10 монет).
2) Так как в В оказалось N монеток решёткой вверх, когда их только отделили, то в кучке А осталось 10-N монет решёткой вверх (так как было всего 10).

На столе в тёмной комнате лежат 100 монет. 10 из них лежат решёткой вверх, остальные - орлом.
Разрешается:
1) делить кучку монет на две кучки (не обязательно равные, можно отсчитывать нужное кол-во, 1 монета - уже кучка)
2) переворачивать все монеты одной из кучек
3) совмещать кучки
Какие монеты как лежат неизвестно. Никак нельзя зафиксировать какую-то монету, чтобы определить переворачивалась она или нет.Разумеется ни на ощупь, ни как-то иначе определить состояние монеты относительно другой нельзя.
Требуется разделить эти 100 монет на две кучки, в которых равное кол-во монеток лежащих решёткой вверх.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Отделяем 10 монет от основной кучки и переворачиваем их.

Основную кучку с уже отделёнными монетами будем называть А. Кучку, в которой отделенные монеты, будет называть В.
1) Если в кучке В оказалось N монеток решёткой вверх, когда их только отделили, то, перевернув всю кучку В, получим 10-N монет решёткой вверх (так как всего в кучке В 10 монет).
2) Так как в В оказалось N монеток решёткой вверх, когда их только отделили, то в кучке А осталось 10-N монет решёткой вверх (так как было всего 10).

Представим, что Земля идеальный шар без атмосферы (т.е. царит невесомость). Она обернута вплотную веревкой по экватору. Если разрезать эту веревку, вклинить потом на место разреза ещё 1 метр веревки, то пролезет ли в равномерно образовавшийся зазор обычное яблочко? Экватор = 40 000 км.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Длина окружности l = 2*PI*r;
экватор = 40 000 000 м.
2*PI*r = 40 000 000 =>
зазор будет размером l = 40 000 001/6,28 - 40 000 000/6,28;
У меня получилось около 0,16 м = 16 см. Т.е. обычное яблоко пролезет.

Представим, что Земля идеальный шар без атмосферы (т.е. царит невесомость). Она обернута вплотную веревкой по экватору. Если разрезать эту веревку, вклинить потом на место разреза ещё 1 метр веревки, то пролезет ли в равномерно образовавшийся зазор обычное яблочко? Экватор = 40 000 км.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Длина окружности l = 2*PI*r;
экватор = 40 000 000 м.
2*PI*r = 40 000 000 =>
зазор будет размером l = 40 000 001/6,28 - 40 000 000/6,28;
У меня получилось около 0,16 м = 16 см. Т.е. обычное яблоко пролезет.

Патриций решил устроить праздник и для этого приготовил 240 бочек вина. Однако к нему пробрался недоброжелатель, который подсыпал яд в одну из бочек. Злодея тут же поймали и дальнейшая его судьба больше неизвестна. Про яд стало известно, что человек, его выпивший, умирает в течение 24 часов(то есть не ровно, а может как через час, так и через 24 часа). До праздника осталось всего два дня, то есть 48 часов. У Патриция есть пять рабов, которыми он готов пожертвовать, чтобы узнать в какой именно бочке яд. 

Как Патрицию вычислить отравленную бочку?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

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

Давайте расставим рабов в ряд: ххххх
Если какой-то из рабов пробует содержимое бочки, то обозначим его как "о", получая что-то вроде: ххохх (пробует средний раб)

Сколько бочек могут точно проверить пять рабов? Построим небольшую таблицу:

№ Бочки - кто пробует 
1 - ххххх - никто не пробует 
2 - ххххо - пробует 5-ый, если он умирает, яд в этой бочке 
3 - хххох - пробует 4-ый, если он умирает, яд в этой бочке 
... 
7 - хххоо - пробует 4-ый и 5-ый, если они умирают, яд в этой бочке  
8 - ххохо - пробует 3-ый и 5-ый, если они умирают, яд в этой бочке 


И так далее. В конечном счете можно убедиться, что однозначно проверяются 32 бочки. Для тех, кто знаком с кодированием, это значение равняется двум в пятой степени(2^5=32). Построив аналогичную табличку для меньшего количества, получим такие данные:

  
2^5=32 
2^4=16 
2^3=8 
2^2=4 
2^1=2 
2^0=1 


Теперь можно перейти к первому дню.
Если в первый день никто не попробует из 32 бочек, то можно будет их полностью проверить во второй день.
Если в первый день один любой из пяти рабов попробует из 16 бочек и умрет, то можно будет полностью проверить их во второй день.
Если в первый день два из пяти рабов попробует из 8 бочек и умрет, то можно будет полностью проверить их во второй день.
Как итог получаем:

  
ххххх - 32 бочки (никто не пробует и однозначно проверяются во второй день) 
ххххо - 16 бочек (пятый пробует и однозначно проверяются во второй день) 
хххох - 16 бочек (четвертый пробует и однозначно проверяются во второй день) 
ххохх - 16 бочек (третий пробует и однозначно проверяются во второй день) 
хоххх - 16 бочек (второй пробует и однозначно проверяются во второй день) 
охххх - 16 бочек (первый пробует и однозначно проверяются во второй день) 
хххоо -  8 бочек (пятый и четвертый пробует и однозначно проверяются во второй день) 
... 
ооооо -  1 бочка (все умерли, ответ очевиден) 


Таким образом складывая из последней таблицы все бочки можно узнать, что этим способом однозначно проверяются 243 бочки, что даже больше нужного.

Патриций решил устроить праздник и для этого приготовил 240 бочек вина. Однако к нему пробрался недоброжелатель, который подсыпал яд в одну из бочек. Злодея тут же поймали и дальнейшая его судьба больше неизвестна. Про яд стало известно, что человек, его выпивший, умирает в течение 24 часов(то есть не ровно, а может как через час, так и через 24 часа). До праздника осталось всего два дня, то есть 48 часов. У Патриция есть пять рабов, которыми он готов пожертвовать, чтобы узнать в какой именно бочке яд. 

Как Патрицию вычислить отравленную бочку?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

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

Давайте расставим рабов в ряд: ххххх
Если какой-то из рабов пробует содержимое бочки, то обозначим его как "о", получая что-то вроде: ххохх (пробует средний раб)

Сколько бочек могут точно проверить пять рабов? Построим небольшую таблицу:

№ Бочки - кто пробует 
1 - ххххх - никто не пробует 
2 - ххххо - пробует 5-ый, если он умирает, яд в этой бочке 
3 - хххох - пробует 4-ый, если он умирает, яд в этой бочке 
... 
7 - хххоо - пробует 4-ый и 5-ый, если они умирают, яд в этой бочке  
8 - ххохо - пробует 3-ый и 5-ый, если они умирают, яд в этой бочке 


И так далее. В конечном счете можно убедиться, что однозначно проверяются 32 бочки. Для тех, кто знаком с кодированием, это значение равняется двум в пятой степени(2^5=32). Построив аналогичную табличку для меньшего количества, получим такие данные:

  
2^5=32 
2^4=16 
2^3=8 
2^2=4 
2^1=2 
2^0=1 


Теперь можно перейти к первому дню.
Если в первый день никто не попробует из 32 бочек, то можно будет их полностью проверить во второй день.
Если в первый день один любой из пяти рабов попробует из 16 бочек и умрет, то можно будет полностью проверить их во второй день.
Если в первый день два из пяти рабов попробует из 8 бочек и умрет, то можно будет полностью проверить их во второй день.
Как итог получаем:

  
ххххх - 32 бочки (никто не пробует и однозначно проверяются во второй день) 
ххххо - 16 бочек (пятый пробует и однозначно проверяются во второй день) 
хххох - 16 бочек (четвертый пробует и однозначно проверяются во второй день) 
ххохх - 16 бочек (третий пробует и однозначно проверяются во второй день) 
хоххх - 16 бочек (второй пробует и однозначно проверяются во второй день) 
охххх - 16 бочек (первый пробует и однозначно проверяются во второй день) 
хххоо -  8 бочек (пятый и четвертый пробует и однозначно проверяются во второй день) 
... 
ооооо -  1 бочка (все умерли, ответ очевиден) 


Таким образом складывая из последней таблицы все бочки можно узнать, что этим способом однозначно проверяются 243 бочки, что даже больше нужного.

На сковородке может одновременно жариться не более 2 котлет. Котлету необходимо прожарить с двух сторон. Для того, чтобы прожарить котлету с одной стороны требуется не менее 2 минут. Студент хочет приготовить 3 котлеты. За какое минимальное время он сможет это сделать?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Уместным будет спросить у интервьюера какие промежутки времени можно делать между переворачиваниями.
Объясняю: если переворачивать 1 раз в полминуты, то можно добиться желаемого результата за 6 минут. Для наглядности первую котлету будем обозначать как 1, вторую как 2, третью как 3, первую сторону - о, вторую сторону котлеты - х.
Тогда раз в полминуты можно наблюдать следующую картину, которую можно представить таблицей, где первый столбец - значение времени, второй - состояние 1 котлеты, третий - 2й, четвертый - 3й:

0.5 мин         1о         2о
1.0 мин         1о                     3о
1.5 мин                     2о         3о
2.0 мин         1о         2о
2.5 мин         1о                     3о
3.0 мин                     2о         3о   
3.5 мин         1х         2х
4.0 мин         1х                     3х
4.5 мин                     2х         3х
5.0 мин         1х         2х
5.5 мин         1х                     3х
6.0 мин                     2х         3х

Таким вот непростым образом можно приготовить ужин за 6 минут.

Дан массив произвольных положительных чисел. Так же дано число Х. Найти ближайшее число из массива к числу Х не более чем за один проход массива.

Например:
Массив 2, 6, 9, 4, 1, 23, 55
Число Х=10
Ближайшим является число 9

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

При прохождении массива записывать дельту - разницу между i-м значением элемента массива и числом Х. При прохождении каждого элемента массива сравнивать новую дельту со старой. Чем меньше значение дельты, тем число ближе к Х. Отсюда можно вычислить ближайшее число.

Дан массив произвольных положительных чисел. Так же дано число Х. Найти ближайшее число из массива к числу Х не более чем за один проход массива.

Например:
Массив 2, 6, 9, 4, 1, 23, 55
Число Х=10
Ближайшим является число 9

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

При прохождении массива записывать дельту - разницу между i-м значением элемента массива и числом Х. При прохождении каждого элемента массива сравнивать новую дельту со старой. Чем меньше значение дельты, тем число ближе к Х. Отсюда можно вычислить ближайшее число.

Есть 7 шаров, они одинаковой формы и неотличимы для человека, но 1 из них весит чуть-чуть (0,(0)5 г) больше, чем остальные. У вас есть идеальные двухчашечные весы (без погрешности измерений и т.д., которые могут засечь любую разницу в весе). Надо не более чем за 2 взвешивания определить, какой шарик чуть более тяжелый, чем остальные.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

1) Первое взвешивание. Кладем по 3 случайно выбранных шара на каждую чашу весов. Если весы никуда не склонятся, то оставшийся 7-ой шарик и есть самый тяжелый. Если весы качнулись в одну сторону, то отметаем 3 шарика на другой чаше весов и 7-ой оставшийся. У нас остались только 3 шарика, один из которых самый тяжелый.

2) Взвешиваем любые 2 из 3 оставшихся. В случае равенства на весах самый тяжелый шарик - оставшийся 3-ий. Если же весы качнутся в какую-либо сторону, то на той чаше и лежит самый тяжелый шарик.

Есть 7 шаров, они одинаковой формы и неотличимы для человека, но 1 из них весит чуть-чуть (0,(0)5 г) больше, чем остальные. У вас есть идеальные двухчашечные весы (без погрешности измерений и т.д., которые могут засечь любую разницу в весе). Надо не более чем за 2 взвешивания определить, какой шарик чуть более тяжелый, чем остальные.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

1) Первое взвешивание. Кладем по 3 случайно выбранных шара на каждую чашу весов. Если весы никуда не склонятся, то оставшийся 7-ой шарик и есть самый тяжелый. Если весы качнулись в одну сторону, то отметаем 3 шарика на другой чаше весов и 7-ой оставшийся. У нас остались только 3 шарика, один из которых самый тяжелый.

2) Взвешиваем любые 2 из 3 оставшихся. В случае равенства на весах самый тяжелый шарик - оставшийся 3-ий. Если же весы качнутся в какую-либо сторону, то на той чаше и лежит самый тяжелый шарик.

Компания-партнёр создала очень быстрый аллокатор, способный мгновенно выделять произвольный кусок памяти, но с заранее неизвестным выравниванием. Однако, на платформе, где он будет использоваться, выравнивание по степени двойки нужно как воздух. Перед вами стоит задача: написать функции выделения и освобождения памяти, способные предоставить вызывающему кусок памяти заданного размера с заданным выравниванием и корректно его освободить (разумеется, с использованием вышеназванного аллокатора).

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

В рамках этого ответа, пусть size будет размером, а align - требуемым выравниванием.
Для гарантированного получения достаточного объёма выравненной памяти придётся выделить чуть больше, чем требуется, а именно на align-1 байт. Тогда в худшем случае выданная нам память будет начинаться на следующий байт после выравненного, а очередная выравненная область будет находиться в самом конце куска. Во всех остальных случаях выравненная область будет где-то в середине или в начале.
Итак, newSize = size + align - 1. Пусть data = alloc( newSize ) - указатель на данные. Используя то, что align - степень двойки, находим требуемое смещение:

newData = ( data + align - 1 ) & ~(align-1) 


(newData будет указывать на data, если data уже выравнено, благодаря align-1)
После этого мы могли бы вернуть newData как требуемое значение...но не можем: при вызове нашей функции free у нас не будет данных о начале выделенного нами блока памяти. Стало быть, потребуется ещё немного памяти под указатель на начало данных:

newSize = size + sizeof( pointer ) + align - 1 


Указатель мы можем разместить только перед началом выравненного блока в силу двух причин:
1) его удастся найти, имея лишь указатель на выравненный блок
2) блок памяти, который будет занят данными, останется непрерывным, что позволит опираться на предыдущие выкладки по размеру запрашиваемого блока.
В связи с этим поиск выравненного участка превращается в цикл:

newData = data; 
do { 
  newData = ( newData + align ) & ~(align-1); 
} while ( newData - data < sizeof( pointer ) ); 


(обратите внимание на отсутствие -1 в теле цикла - это предотвратит зацикливание на 1-байтовом выравнивании)
После данного цикла по указателю newData всё равно останется кусок памяти не меньше size, а перед ним будет не меньше sizeof( pointer ) байт для указателя на начало блока, куда мы его и записываем.
Освобождение при этом проще простого: используя данный нам указатель, считываем адрес начала блока и вызываем соответствующую системную функцию.
При написании настоящего кода не забудьте проверки на то, чтобы align было степенью двойки, size был больше нуля, а аллокатор вернул валидный указатель.

Компания-партнёр создала очень быстрый аллокатор, способный мгновенно выделять произвольный кусок памяти, но с заранее неизвестным выравниванием. Однако, на платформе, где он будет использоваться, выравнивание по степени двойки нужно как воздух. Перед вами стоит задача: написать функции выделения и освобождения памяти, способные предоставить вызывающему кусок памяти заданного размера с заданным выравниванием и корректно его освободить (разумеется, с использованием вышеназванного аллокатора).

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

В рамках этого ответа, пусть size будет размером, а align - требуемым выравниванием.
Для гарантированного получения достаточного объёма выравненной памяти придётся выделить чуть больше, чем требуется, а именно на align-1 байт. Тогда в худшем случае выданная нам память будет начинаться на следующий байт после выравненного, а очередная выравненная область будет находиться в самом конце куска. Во всех остальных случаях выравненная область будет где-то в середине или в начале.
Итак, newSize = size + align - 1. Пусть data = alloc( newSize ) - указатель на данные. Используя то, что align - степень двойки, находим требуемое смещение:

newData = ( data + align - 1 ) & ~(align-1) 


(newData будет указывать на data, если data уже выравнено, благодаря align-1)
После этого мы могли бы вернуть newData как требуемое значение...но не можем: при вызове нашей функции free у нас не будет данных о начале выделенного нами блока памяти. Стало быть, потребуется ещё немного памяти под указатель на начало данных:

newSize = size + sizeof( pointer ) + align - 1 


Указатель мы можем разместить только перед началом выравненного блока в силу двух причин:
1) его удастся найти, имея лишь указатель на выравненный блок
2) блок памяти, который будет занят данными, останется непрерывным, что позволит опираться на предыдущие выкладки по размеру запрашиваемого блока.
В связи с этим поиск выравненного участка превращается в цикл:

newData = data; 
do { 
  newData = ( newData + align ) & ~(align-1); 
} while ( newData - data < sizeof( pointer ) ); 


(обратите внимание на отсутствие -1 в теле цикла - это предотвратит зацикливание на 1-байтовом выравнивании)
После данного цикла по указателю newData всё равно останется кусок памяти не меньше size, а перед ним будет не меньше sizeof( pointer ) байт для указателя на начало блока, куда мы его и записываем.
Освобождение при этом проще простого: используя данный нам указатель, считываем адрес начала блока и вызываем соответствующую системную функцию.
При написании настоящего кода не забудьте проверки на то, чтобы align было степенью двойки, size был больше нуля, а аллокатор вернул валидный указатель.

Есть односвязанный список. Каждый элемент списка содержит указатель на следующий элемент. Нам известен указатель на первый элемент списка.
Необходимо изменить направление одно-связанного списка, так чтобы список начинался с последнего элемента.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Задача простая, но есть один нюанс: необходимо хранить два указателя на текущий элемент и на предыдущий, т.к. связь между этими элементами обрывается.
Решение:
Скажем first указывает на начало списка. Каждый элемент указывает на структуру MYDATA типа

typedef struct _MYDATA { 
    _MYDATA *next; 
} MYDATA; 
 
MYDATA *current = first; 
MYDATA *prev = NULL; 
 
while(current) 
    { 
        MYDATA *temp = current->next; 
        current->next = prev; //изменяем направление 
 
        //переходим к следующему элементу 
        prev = current; 
        current = temp; 
    } 
 
//новый указатель на начало изменённого списка 
first = prev;  
 

Есть односвязанный список. Каждый элемент списка содержит указатель на следующий элемент. Нам известен указатель на первый элемент списка.
Необходимо изменить направление одно-связанного списка, так чтобы список начинался с последнего элемента.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Задача простая, но есть один нюанс: необходимо хранить два указателя на текущий элемент и на предыдущий, т.к. связь между этими элементами обрывается.
Решение:
Скажем first указывает на начало списка. Каждый элемент указывает на структуру MYDATA типа

typedef struct _MYDATA { 
    _MYDATA *next; 
} MYDATA; 
 
MYDATA *current = first; 
MYDATA *prev = NULL; 
 
while(current) 
    { 
        MYDATA *temp = current->next; 
        current->next = prev; //изменяем направление 
 
        //переходим к следующему элементу 
        prev = current; 
        current = temp; 
    } 
 
//новый указатель на начало изменённого списка 
first = prev;  
 

Сколько всего квадратов на шахматной доске размером NxN? Сколько на ней прямоугольников? (Квадрат - тоже прямоугольик)

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Для квадратов:
Квадрат 1x1 можно разместить ровно NxN раз, квадрат 2x2 уже (N-1)x(N-1) раз и т.д. до квадрата размером NxN, который размещается лишь 1 раз. В сумме будет 1^2 + 2^2 + ... + N^2.

Для прямоугольников:
Возьмём прямоугольник размерами a x b (допустим, a - по горизонтали, b - по вертикали). Посчитаем прямоугольники без учёта вертикальной составляющей - их будет ровно N - a + 1 (т.е. по количеству свободных клеток по горизонтали). Аналогично, кол-во "размещений" прямоугольника по вертикали равно N - b + 1. Стало быть, всего прямоугольников размерами a x b на доске ровно (N-a+1)x(N-b+1). Общее кол-во прямоугольников равно сумме по всем a,b от 1 до N произведения (N-a+1)x(N-b+1).
В случае a = b задача сводится к квадратам.

Сколько всего квадратов на шахматной доске размером NxN? Сколько на ней прямоугольников? (Квадрат - тоже прямоугольик)

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Для квадратов:
Квадрат 1x1 можно разместить ровно NxN раз, квадрат 2x2 уже (N-1)x(N-1) раз и т.д. до квадрата размером NxN, который размещается лишь 1 раз. В сумме будет 1^2 + 2^2 + ... + N^2.

Для прямоугольников:
Возьмём прямоугольник размерами a x b (допустим, a - по горизонтали, b - по вертикали). Посчитаем прямоугольники без учёта вертикальной составляющей - их будет ровно N - a + 1 (т.е. по количеству свободных клеток по горизонтали). Аналогично, кол-во "размещений" прямоугольника по вертикали равно N - b + 1. Стало быть, всего прямоугольников размерами a x b на доске ровно (N-a+1)x(N-b+1). Общее кол-во прямоугольников равно сумме по всем a,b от 1 до N произведения (N-a+1)x(N-b+1).
В случае a = b задача сводится к квадратам.

Порядковый номер каждой буквы алфавита русского языка, состоящего из 32 букв (Е и Ё отождествлены), представлен в двоичной системе счисления пятизначным числом, начиная с нуля. Например, букве А соответствует двоичное число 00000, а букве Ч - 10111. Передача каждой буквы сообщения осуществляется путем передачи каждой из цифр соответствующего пятизначного двоичного числа по отдельному проводу. Электрик случайно замкнул какие-то два из этих пяти проводов. В результате на других концах замкнутых проводов появляется 1, как только по одному из них передается 1. Найдите переданное слово, если получен текст ТЕЫЕУТАЦ.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Запишем полученное сообщение в двоичном виде:

Т       1    0    0    1    0
Е       0    0    1    0    1
Ы       1    1    0    1    1
Е       0    0    1    0    1
У       1    0    0    1    1
Т       1    0    0    1    0
А       0    0    0    0    0
Ц       1    0    1    1    0


Если провода замкнуты, то по ним передаются одинаковые символы (0 или 1), т.е. замкнутым проводам соответствуют одинаковые столбцы цифр. Легко видеть, что это первый и четвертый столбцы. Значит, во 2-м, 3-м и 5-м столбцах все символы правильные, кроме того, если в 1 и 4 столбцах стоят нули, то это тоже правильные знаки. Если в 1-м и 4-м столбцах стоят единицы, то возможны три варианта для знаков x и y этих столбцов:


1    0
0    1
1    1


Каждому варианту соответствует своя буква:


x    0    0    y    0
0    0    1    0    1
x    1    0    y    1
0    0    1    0    1
x    0    0    y    1
x    0    0    y    0
0    0    0    0    0
x    0    1    y    0


Заменяя каждый вариант на соответствующую букву, получим таблицу:


Т         Ы         У    Т         Ц
Р    Е    Л    Е    Г    Р    А    Ж
В         Щ         С    В         Ф


Выбирая по одной букве в каждом столбце таблицы, находим «читаемое» слово ТЕЛЕГРАФ.

Порядковый номер каждой буквы алфавита русского языка, состоящего из 32 букв (Е и Ё отождествлены), представлен в двоичной системе счисления пятизначным числом, начиная с нуля. Например, букве А соответствует двоичное число 00000, а букве Ч - 10111. Передача каждой буквы сообщения осуществляется путем передачи каждой из цифр соответствующего пятизначного двоичного числа по отдельному проводу. Электрик случайно замкнул какие-то два из этих пяти проводов. В результате на других концах замкнутых проводов появляется 1, как только по одному из них передается 1. Найдите переданное слово, если получен текст ТЕЫЕУТАЦ.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Запишем полученное сообщение в двоичном виде:

Т       1    0    0    1    0
Е       0    0    1    0    1
Ы       1    1    0    1    1
Е       0    0    1    0    1
У       1    0    0    1    1
Т       1    0    0    1    0
А       0    0    0    0    0
Ц       1    0    1    1    0


Если провода замкнуты, то по ним передаются одинаковые символы (0 или 1), т.е. замкнутым проводам соответствуют одинаковые столбцы цифр. Легко видеть, что это первый и четвертый столбцы. Значит, во 2-м, 3-м и 5-м столбцах все символы правильные, кроме того, если в 1 и 4 столбцах стоят нули, то это тоже правильные знаки. Если в 1-м и 4-м столбцах стоят единицы, то возможны три варианта для знаков x и y этих столбцов:


1    0
0    1
1    1


Каждому варианту соответствует своя буква:


x    0    0    y    0
0    0    1    0    1
x    1    0    y    1
0    0    1    0    1
x    0    0    y    1
x    0    0    y    0
0    0    0    0    0
x    0    1    y    0


Заменяя каждый вариант на соответствующую букву, получим таблицу:


Т         Ы         У    Т         Ц
Р    Е    Л    Е    Г    Р    А    Ж
В         Щ         С    В         Ф


Выбирая по одной букве в каждом столбце таблицы, находим «читаемое» слово ТЕЛЕГРАФ.

На столе лежат 50 монеток. 40 из них лежат орлом вверх, а оставшиеся 10 - решкой. Необходимо разделить монетки на 2 группы таким образом, чтобы в каждой группе было одинаковое количество монеток лежащих вверх решкой.
Комната абсолютно тёмная, т.е. мы не видим лежит монетка орлом вверх или решкой, на ощупь монеты все идентичные. Монеты можно переворачивать сколь угодно много раз.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Делим монетки на 2 группы по 40 и 10 штучек и переворачиваем каждую монетку группы с 10 монетками! Вот и всё решение! :)
Пример 1: В группе с 10 монетками попались 2 решки и 8 орлов, значит во второй группе с 40 монетками 8 решек и 32 орла. Мы переворачиваем группу с 10 монетками и получаем 8 решек и 2 орла. Т.о. в каждой группе по 8 решек!
Пример 2: Если в группу с 10 монетками попали все решки, то, перевернув эту группу, в каждой окажется равное количество решек, а именно ни одной решки ни в одной, ни в другой группе!

На столе лежат 50 монеток. 40 из них лежат орлом вверх, а оставшиеся 10 - решкой. Необходимо разделить монетки на 2 группы таким образом, чтобы в каждой группе было одинаковое количество монеток лежащих вверх решкой.
Комната абсолютно тёмная, т.е. мы не видим лежит монетка орлом вверх или решкой, на ощупь монеты все идентичные. Монеты можно переворачивать сколь угодно много раз.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Делим монетки на 2 группы по 40 и 10 штучек и переворачиваем каждую монетку группы с 10 монетками! Вот и всё решение! :)
Пример 1: В группе с 10 монетками попались 2 решки и 8 орлов, значит во второй группе с 40 монетками 8 решек и 32 орла. Мы переворачиваем группу с 10 монетками и получаем 8 решек и 2 орла. Т.о. в каждой группе по 8 решек!
Пример 2: Если в группу с 10 монетками попали все решки, то, перевернув эту группу, в каждой окажется равное количество решек, а именно ни одной решки ни в одной, ни в другой группе!

Как-то раз поймал Великан 11 гномов. Но Великан решил проявить гуманность и предложил гномам вариант при котором у каждого из них будет возможность сохранить себе жизнь. Суть такова. Гномы выстраиваются друг за другом в колонну по росту(самый высокий в конце), таким образом что они видят только головы впереди стоящих. Великан раздает всем шапки разного цвета (черные и белые), если гном угадывает какая шапка на нем, то Великан его отпускает, если нет, то Великан помещает в себя гнома. При попытках подсказать, намекнуть остальным, Великан немедленно съедает провинившегося.
За ночь гномы должны придумать способ спасти как можно больше гномов.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Гарантированное количество гномов которых можно спасти 10, но при удачном стечении обстоятельств спасутся все.
В основу принципа по которому они должны действовать, лежит проверка четности\нечетности. Последний гном считает количество черных шапок и белых, по сговору, если последний говорит: "белая шапка", значит белых шапок четное количество, если черная, то нечетное количество белых. Здесь его могут съесть, а может ему повезет 50/50. Далее следующий считает количество белых шапок впереди себя и определяет какая шапка на нем.

Как-то раз поймал Великан 11 гномов. Но Великан решил проявить гуманность и предложил гномам вариант при котором у каждого из них будет возможность сохранить себе жизнь. Суть такова. Гномы выстраиваются друг за другом в колонну по росту(самый высокий в конце), таким образом что они видят только головы впереди стоящих. Великан раздает всем шапки разного цвета (черные и белые), если гном угадывает какая шапка на нем, то Великан его отпускает, если нет, то Великан помещает в себя гнома. При попытках подсказать, намекнуть остальным, Великан немедленно съедает провинившегося.
За ночь гномы должны придумать способ спасти как можно больше гномов.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Гарантированное количество гномов которых можно спасти 10, но при удачном стечении обстоятельств спасутся все.
В основу принципа по которому они должны действовать, лежит проверка четности\нечетности. Последний гном считает количество черных шапок и белых, по сговору, если последний говорит: "белая шапка", значит белых шапок четное количество, если черная, то нечетное количество белых. Здесь его могут съесть, а может ему повезет 50/50. Далее следующий считает количество белых шапок впереди себя и определяет какая шапка на нем.

На двумерной плоскости есть многоугольник и точка. Определить находится ли точка внутри многоугольника. Многоугольник может быть любым.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

От точки провести луч в любом направлении и подсчитать количество пересечений этого луча со сторонами многоугольника. Четное количество - точка вне многоугольника, нечетное, соответственно,- в.

На двумерной плоскости есть многоугольник и точка. Определить находится ли точка внутри многоугольника. Многоугольник может быть любым.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

От точки провести луч в любом направлении и подсчитать количество пересечений этого луча со сторонами многоугольника. Четное количество - точка вне многоугольника, нечетное, соответственно,- в.

Пехотинец прячется в траншее, состоящей из 60 окопов, расположенных в линию. Каждую минуту артиллерист стреляет в один из окопов, пытаясь попасть в пехотинца. После каждого выстрела пехотинец скрытно перебегает в соседний окоп. Докажите, что артиллерист рано или поздно сможет попасть в окоп пехотинца.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Алгоритм стрельбы: 1, 2, ... , 59, 60, 60, 59, ... , 1

При последовательном обстреле цепочки (не важно, в какую сторону) расстояния между попаданиями и местом пехотинца всегда меняется или на 0, или на 2. Проскочить он сможет только в том случае, если это расстояние нечётное. Если оно чётное, то пехотинец будет убит на прямом проходе. Если нечётное и он проскочит, то после повторного выстрела в 60 и скачка пехотинца оно становится чётным, и ему уже не уйти.

Пехотинец прячется в траншее, состоящей из 60 окопов, расположенных в линию. Каждую минуту артиллерист стреляет в один из окопов, пытаясь попасть в пехотинца. После каждого выстрела пехотинец скрытно перебегает в соседний окоп. Докажите, что артиллерист рано или поздно сможет попасть в окоп пехотинца.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Алгоритм стрельбы: 1, 2, ... , 59, 60, 60, 59, ... , 1

При последовательном обстреле цепочки (не важно, в какую сторону) расстояния между попаданиями и местом пехотинца всегда меняется или на 0, или на 2. Проскочить он сможет только в том случае, если это расстояние нечётное. Если оно чётное, то пехотинец будет убит на прямом проходе. Если нечётное и он проскочит, то после повторного выстрела в 60 и скачка пехотинца оно становится чётным, и ему уже не уйти.

По среди пустыни стоит база иследователей. В которой живут четверо. Каждый иследоваетель выходя в пустыню берет с собой еду, максимальное количество еды которое он может взять с собой 10кг(тоесть максимальный вес еды который может нести один иследователь 10кг). Каждый день проведенный в пустыни он съедает 1кг еды. (тоесть он может пройти на 5 дней в перед, и вернутся обратно. Имея 10кг еды). Также иследователь может оставлять еду в пустыне, которую может подобрать другой иследователь, проходя мимо. Вопрос на какое максимально количество дней можно послать иследователя в пустыню. Если каждый из 4 иследователей может выйти один раз.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Все иследователи будут брать 10кг еды. Первый иследователь уходит в пустыню на два дня, оставляет 6кг еды и возвращается. Второй: пройдет на 3дня в пустыню, по дроге возмет 2кг еды оставленных первым и оставит на третий день 6кг еды. Вернется на базу. (и так на 2д - 4кг, на 3д - 6кг. Лежат в пустыне) третий: пойдет на пять дней в пустыню. По дороге возьмет 3кг еды в 3д пути. и на пятом дне оставит 6кг. Возвращаясь на базу на 3д заберет оставшиеся 3кг чтоб дойти до базы не умерев с голоду. (и так на 2д-4кг, и на 5д-6кг. Лежат в пустыне) четвертый: пройдет десять дней. По дороге в пустыню: Он на 2д. возьмет 2кг еды, на 3д он оставит 1кг еды. Дойдя до 5д. У него будет в рюкзаке 6кг еды и 6кг спрятаных в пустыне. Он возьмет с собой 4кг(в рюкзаке будет 10кг и останится 2кг в пустыне). И пойдет еще на 5 дней в перед и вернется с пустым рукзаком обратно, возьмет 2кг оставшиеся, на них он дойдет до 3д, заберет 1кг, дойдет до 2д, заберет 2кг, вернется на базу. Ответ. Можно отправить на 10 дней.

По среди пустыни стоит база иследователей. В которой живут четверо. Каждый иследоваетель выходя в пустыню берет с собой еду, максимальное количество еды которое он может взять с собой 10кг(тоесть максимальный вес еды который может нести один иследователь 10кг). Каждый день проведенный в пустыни он съедает 1кг еды. (тоесть он может пройти на 5 дней в перед, и вернутся обратно. Имея 10кг еды). Также иследователь может оставлять еду в пустыне, которую может подобрать другой иследователь, проходя мимо. Вопрос на какое максимально количество дней можно послать иследователя в пустыню. Если каждый из 4 иследователей может выйти один раз.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Все иследователи будут брать 10кг еды. Первый иследователь уходит в пустыню на два дня, оставляет 6кг еды и возвращается. Второй: пройдет на 3дня в пустыню, по дроге возмет 2кг еды оставленных первым и оставит на третий день 6кг еды. Вернется на базу. (и так на 2д - 4кг, на 3д - 6кг. Лежат в пустыне) третий: пойдет на пять дней в пустыню. По дороге возьмет 3кг еды в 3д пути. и на пятом дне оставит 6кг. Возвращаясь на базу на 3д заберет оставшиеся 3кг чтоб дойти до базы не умерев с голоду. (и так на 2д-4кг, и на 5д-6кг. Лежат в пустыне) четвертый: пройдет десять дней. По дороге в пустыню: Он на 2д. возьмет 2кг еды, на 3д он оставит 1кг еды. Дойдя до 5д. У него будет в рюкзаке 6кг еды и 6кг спрятаных в пустыне. Он возьмет с собой 4кг(в рюкзаке будет 10кг и останится 2кг в пустыне). И пойдет еще на 5 дней в перед и вернется с пустым рукзаком обратно, возьмет 2кг оставшиеся, на них он дойдет до 3д, заберет 1кг, дойдет до 2д, заберет 2кг, вернется на базу. Ответ. Можно отправить на 10 дней.

Есть 4 бутылки с жидкостями, в одной из них смертельный яд, так же есть 2 лабораторные мыши. Нужно определить в какой из бутылок яд за 24 часа. Известно, что яд действует в течение 18 часов (может подействовать через час, а может и через 18 часов).

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Содержимое двух бутылок дается разным мышам (каждой мыши своя бутылка). Содержимое третьей дают выпить обеим. Из четвертой бутылки никто не пьет. Таким образом, если умерла одна мышь – яд был в бутылке, из которой пила только она. Если умирают обе – отравлена 3 бутылка. И если обе мыши живы – яд в четвертой бутылке.

Есть 4 бутылки с жидкостями, в одной из них смертельный яд, так же есть 2 лабораторные мыши. Нужно определить в какой из бутылок яд за 24 часа. Известно, что яд действует в течение 18 часов (может подействовать через час, а может и через 18 часов).

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Содержимое двух бутылок дается разным мышам (каждой мыши своя бутылка). Содержимое третьей дают выпить обеим. Из четвертой бутылки никто не пьет. Таким образом, если умерла одна мышь – яд был в бутылке, из которой пила только она. Если умирают обе – отравлена 3 бутылка. И если обе мыши живы – яд в четвертой бутылке.

Дано: 25 лошадей. 
Задача: определить 3 самых быстрых за минимальное количество забегов.
Условия: За один забег может бежать только 5 лошадей. У нас нет таймера. Каждая отдельная лошадь бежит с одинаковой скоростью не зависимо от забега.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

7 забегов.

1) Надо разделить 25 лошедей на 5 групп. Делаем 5 забегов - определяем 5 победителей. 
2) Шестой забег между победителями. Его победитель - первое место.
3) Седьмой забег последний.

Учасники: 
2е и 3е место из группы победителя шестого забега
1е и 2е место из группы лошади которая пришла второй в шестом забеге
1е место из группы лошади которая пришла третьей в шестом забеге т.е. сама эта лошадь

Первое и второе место этого забега есть оставшиеся две лошади - второе и третье место в целом.

Более формально:
1) a1, a2, a3, a4, a5 - победитель а1
2) b1, b2, b3, b4, b5 - победитель b1
3) с1, с2, с3, с4, с5 - победитель с1
4) d1, d2, d3, d4, d5 - победитель d1
5) e1, e2, e3, e4, e5 - поебедитель e1
6) забег победителей. Допустим что результаты:
1 - a1, 2 - b1, 3 - c1, 4 - d1, 5 - e1
таким образом понятно что самая быстрая лошадь из всех - а1
7) учасники:
а2, а3, b1, b2, c1

Дано: 25 лошадей. 
Задача: определить 3 самых быстрых за минимальное количество забегов.
Условия: За один забег может бежать только 5 лошадей. У нас нет таймера. Каждая отдельная лошадь бежит с одинаковой скоростью не зависимо от забега.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

7 забегов.

1) Надо разделить 25 лошедей на 5 групп. Делаем 5 забегов - определяем 5 победителей. 
2) Шестой забег между победителями. Его победитель - первое место.
3) Седьмой забег последний.

Учасники: 
2е и 3е место из группы победителя шестого забега
1е и 2е место из группы лошади которая пришла второй в шестом забеге
1е место из группы лошади которая пришла третьей в шестом забеге т.е. сама эта лошадь

Первое и второе место этого забега есть оставшиеся две лошади - второе и третье место в целом.

Более формально:
1) a1, a2, a3, a4, a5 - победитель а1
2) b1, b2, b3, b4, b5 - победитель b1
3) с1, с2, с3, с4, с5 - победитель с1
4) d1, d2, d3, d4, d5 - победитель d1
5) e1, e2, e3, e4, e5 - поебедитель e1
6) забег победителей. Допустим что результаты:
1 - a1, 2 - b1, 3 - c1, 4 - d1, 5 - e1
таким образом понятно что самая быстрая лошадь из всех - а1
7) учасники:
а2, а3, b1, b2, c1

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

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

1 факт: Есть одна общая характеристика всех линий, что делят прямоугольник пополам — они проходят через центр прямоугольника (пересечение его диагоналей).

2 факт: Чтобы поделить площадь получившейся фигуры пополам можно поделить площадь целой фигуры пополам и площадь вырезаной фигуры пополам.
Из этих двух фактов следует ответ: нужно провести прямую через 2 точки: центр большого прямоугольника и центр вырезанного в нем прямоугольника.

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

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

1 факт: Есть одна общая характеристика всех линий, что делят прямоугольник пополам — они проходят через центр прямоугольника (пересечение его диагоналей).

2 факт: Чтобы поделить площадь получившейся фигуры пополам можно поделить площадь целой фигуры пополам и площадь вырезаной фигуры пополам.
Из этих двух фактов следует ответ: нужно провести прямую через 2 точки: центр большого прямоугольника и центр вырезанного в нем прямоугольника.

У петуха - 8, у коровы - 2, у кошки - 3, у собаки - 3, у овцы - 2, у свиньи - 3, у рыбы - 0. Сколько у осла?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Подсказка - не часть тела, т.к. природа любит симметрию.

У петуха - "кукареку", у коровы - "му", у кошки - "мяу", у собаки - "гав", у овцы - "ме", у свиньи - "хрю", у рыбы - "" (молчат).
У осла - "иа", т.е. 2.

У петуха - 8, у коровы - 2, у кошки - 3, у собаки - 3, у овцы - 2, у свиньи - 3, у рыбы - 0. Сколько у осла?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Подсказка - не часть тела, т.к. природа любит симметрию.

У петуха - "кукареку", у коровы - "му", у кошки - "мяу", у собаки - "гав", у овцы - "ме", у свиньи - "хрю", у рыбы - "" (молчат).
У осла - "иа", т.е. 2.

Допустим, что вы - узник, которому вдруг предоставлено право выйти на свободу, но только в том случае, если справитесь с таким заданием: перед вами две двери, одна из них ведет на волю, другая - дорога к смерти. Сидят два стражника, причем один из них - лгун, а второй всегда говорит правду; вы не знаете, кто из них кто. Вы должны, задав лишь один вопрос одному из стражников, определить дорогу на свободу. Какой вопрос вы зададите?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Существует бесконечное множество решений, однако наиболее красивы из них три: 
- Показав на конкретную дверь: "Твой товарищ сказал бы, что ЭТА дверь ведет на свободу?" Ответ "да" означает, что это дверь НЕ ведет на свободу. 

- "Перед дверью, ведущей на свободу, сидит стражник, говорящий правду?" Ответ "да" означает, что нужно войти в ту дверь, возле которой сидит стражник, которому Вы задали вопрос. 

- Показав на конкретную дверь: "Если бы я спросил тебя, ведет ли ЭТА дверь на свободу, что бы ты ответил?" Ответ "да" означает, что эта дверь ведет на свободу. Этот ответ подходит даже тогда, когда нет никакого второго стражника.

Допустим, что вы - узник, которому вдруг предоставлено право выйти на свободу, но только в том случае, если справитесь с таким заданием: перед вами две двери, одна из них ведет на волю, другая - дорога к смерти. Сидят два стражника, причем один из них - лгун, а второй всегда говорит правду; вы не знаете, кто из них кто. Вы должны, задав лишь один вопрос одному из стражников, определить дорогу на свободу. Какой вопрос вы зададите?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Существует бесконечное множество решений, однако наиболее красивы из них три: 
- Показав на конкретную дверь: "Твой товарищ сказал бы, что ЭТА дверь ведет на свободу?" Ответ "да" означает, что это дверь НЕ ведет на свободу. 

- "Перед дверью, ведущей на свободу, сидит стражник, говорящий правду?" Ответ "да" означает, что нужно войти в ту дверь, возле которой сидит стражник, которому Вы задали вопрос. 

- Показав на конкретную дверь: "Если бы я спросил тебя, ведет ли ЭТА дверь на свободу, что бы ты ответил?" Ответ "да" означает, что эта дверь ведет на свободу. Этот ответ подходит даже тогда, когда нет никакого второго стражника.

Написать тело функции bool isExp (int32_t a) которая получает положительное число и возвращает true если это число является степенью двойки, т.е. pow(2, n) = a, n- натуральное число.
Время выполнения функции не должно зависеть от a.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Тут стоит представить числа являющиеся степенью двойки в двоичном представлении, все они будут иметь один бит равный единице, а остальные нули (пример 8=0b00001000).
Если вычесть из любого числа являющегося степенью двойки 1, то все биты в этом числе будут равны 1 (пример 7=0b00000111).
Соответственно операция "побитовое И" для таких чисел даст в результате 0:

bool isExp(int32_t a) 
{ 
    return (a > 0 && (a & (a - 1)) == 0); 
} 

Написать тело функции bool isExp (int32_t a) которая получает положительное число и возвращает true если это число является степенью двойки, т.е. pow(2, n) = a, n- натуральное число.
Время выполнения функции не должно зависеть от a.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Тут стоит представить числа являющиеся степенью двойки в двоичном представлении, все они будут иметь один бит равный единице, а остальные нули (пример 8=0b00001000).
Если вычесть из любого числа являющегося степенью двойки 1, то все биты в этом числе будут равны 1 (пример 7=0b00000111).
Соответственно операция "побитовое И" для таких чисел даст в результате 0:

bool isExp(int32_t a) 
{ 
    return (a > 0 && (a & (a - 1)) == 0); 
} 

Вы находитесь в середине круглого озера и на берегу есть голодный гоблин-людоед. Гоблин может бежать в 4 раза быстрее(по земле), чем Вы можете плывете (гоблин не может плавать), так как Вам выйти из озера, не будучи съеденным? (По земле вы бежите быстрее гоблина).

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

R - радиуса озера.
П - число Пи (3,14)
1) пока Ваше удаление от центра озера < 1/4 R Ваша угловая скорость при движении по окружности выше угловой скорости гоблина.
2) если находиться на прямой, проходящей через центр озера и гоблина, и быть на противоположной от гоблина стороне на удалении 1/4 R от центра озера, то
- расстояние, необходимое Вам проплыть = 3/4 R,
- гоблину необходимо пробежать ПR
следовательно, гоблин не догонит, т.к. ему нужно будет пробежать 3,14*R, а он успеет пробежать только 3R

т.е. плыть надо так:
1) пока Ваше удаление от центра озера < 1/4 R плыть по спирали так, чтобы находиться на прямой, проходящей через центр озера и гоблина, и быть на противоположной от гоблина стороне.
2) рвануть напрямик к краю озера.

Вы находитесь в середине круглого озера и на берегу есть голодный гоблин-людоед. Гоблин может бежать в 4 раза быстрее(по земле), чем Вы можете плывете (гоблин не может плавать), так как Вам выйти из озера, не будучи съеденным? (По земле вы бежите быстрее гоблина).

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

R - радиуса озера.
П - число Пи (3,14)
1) пока Ваше удаление от центра озера < 1/4 R Ваша угловая скорость при движении по окружности выше угловой скорости гоблина.
2) если находиться на прямой, проходящей через центр озера и гоблина, и быть на противоположной от гоблина стороне на удалении 1/4 R от центра озера, то
- расстояние, необходимое Вам проплыть = 3/4 R,
- гоблину необходимо пробежать ПR
следовательно, гоблин не догонит, т.к. ему нужно будет пробежать 3,14*R, а он успеет пробежать только 3R

т.е. плыть надо так:
1) пока Ваше удаление от центра озера < 1/4 R плыть по спирали так, чтобы находиться на прямой, проходящей через центр озера и гоблина, и быть на противоположной от гоблина стороне.
2) рвануть напрямик к краю озера.

У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: "Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа".

Мудрецы задумались. Первым нарушил молчание Али.
- Я не знаю этих чисел, - сказал он, опуская голову.
- Я это знал, - подал голос Вали.
- Тогда я знаю эти числа, - обрадовался Али.
- Тогда и я знаю! - воскликнул Вали.
И мудрецы сообщили пораженному царю задуманные им числа.

Назовите эти числа.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

1. Начинать следует с первой же фразы. Мудрец Али говорит - "Я не знаю, что это за числа". Он знает произведение чисел. Это говорит нам о том, что хотя бы одно из чисел не простое. Иначе бы он единственным образом разложил произведение на множители и знал бы оба числа.

2. Смотрим на фразу второго мудреца - "Я заранее знал, что ты не знаешь, что это за числа". Этот мудрец знает сумму чисел. О чём это нам говорит? Это значит, что при всех возможных разложениях суммы на слагаемые нет случая, когда оба числа простые. Иначе бы он не мог утверждать, что мудрец Али чисел не знает.

Что за числа не раскладываются на сумму двух простых чисел? После недолгих размышлений можно заметить, что если взять число равное (2 + (нечётное не простое)), то его разложения не будут давать двух простых чисел, например:
11 = 2 + 9 (9 - не простое)
11 = 3 + 8 (8 - чётное)
11 = 4 + 7 (4 - чётное)
11 = 5 + 6 (6 - чётное)
...

При переборе видно, что чётные числа будут получаться то в одном слагаемом, то в другом и на самых крайних величинах (2+А), не простым будет как раз число А (мы ведь его и выбирали нечётным и не простым).

Кандидаты в суммы: (2+9)=11, (2+15)=17, (2+21)=23, (2+25)=27, (2+33)=35, (2+35)=37, (2+39)=41, (2+45)=47 ...

3. Смотри на третью фразу. Мудрец Али говорит - "Теперь я знаю, что это за числа". Ему становится известно, что сумма чисел обладает именно такими свойствами, как мы выяснили в предыдущем пункте.

Проверим вариант (2+9)=11.
числа 2 и 9 - (произв = 18), варианты: [2*9], (3*6).
числа 3 и 8 - (произв = 24), варианты: (2*12), [3*8], (4*6).
числа 4 и 7 - (произв = 28), варианты: (2*14), [4*7].
числа 5 и 6 - (произв = 30), варианты: [2*15], (3*10), [5*6].

Это могут быть те пары, которые в сумме равны (2+А), где А - число нечётное и не простое. Сумма д.б. равна 11 или 17 или 23 или 27 или 35 или 37 или 41 или 47 или ... Подходят комбинации отмеченные квадратными скобками.

Проверим вариант (2+15)=17.
числа 2 и 15 - (произв = 30), варианты: [2*15], (3*10), [5*6]
числа 3 и 14 - (произв = 42), варианты: [2*21], [3*14], (6*7)
числа 4 и 13 - (произв = 52), варианты: (2*26), [4*13]
числа 5 и 12 - (произв = 60), варианты: (2*30), [3*20], (4*15), [5,12], (6*10)
числа 6 и 11 - (произв = 66), варианты: [2*33], (3*22), [6*11]
числа 7 и 10 - (произв = 70), варианты: [2*35], (5*14), [7*10]
числа 8 и 09 - (произв = 72), варианты: (2*36), [3*24], (4*18), (6*12), [8*9]

Это могут быть те пары, которые в сумме равны (2+А), где А - число нечётное и не простое. Сумма д.б. равна 11 или 17 или 23 или 27 или 35 или 37 или 41 или 47 или ... Подходят комбинации отмеченные квадратными скобками.

...{ Не полезу дальше }

4. Нам подходят те строки, где только по одной квадратной скобке:
числа 2 и 9 - (произв = 18), варианты: [2*9], (3*6).
числа 3 и 8 - (произв = 24), варианты: (2*12), [3*8], (4*6).
числа 4 и 7 - (произв = 28), варианты: (2*14), [4*7].
числа 4 и 13 - (произв = 52), варианты: (2*26), [4*13]
... { мы не полезли дальше }

Это как раз те варианты которые подтверждаются мудрецу Али после высказывания мудреца Вали. И так как вариант у него один (одна квадратная скобка), то он знает ответ.

5. Теперь осталось отобрать тот вариант, который "раскрыли глаза" мудрецу Вали, после того как он узнал, что мудрец Али определился.

числа 2 и 09 = 11
числа 3 и 08 = 11
числа 4 и 07 = 11
числа 4 и 13 = 17
... { мы не полезли дальше }

Чтобы мудрец Вали понял что - это за числа, они должны давать уникальную сумму - это числа 4 и 13.

P.S. Как доказать что других чисел нет - для меня вопрос открытый.

У некоторого султана было два мудреца: Али-ибн-Вали и Вали-ибн-Али. Желая убедиться в их мудрости, султан призвал мудрецов к себе и сказал: "Я задумал два числа. Оба они целые, каждое больше единицы, но меньше ста. Я перемножил эти числа и результат сообщу Али и при этом Вали я скажу сумму этих чисел. Если вы и вправду так мудры, как о вас говорят, то сможете узнать исходные числа".

Мудрецы задумались. Первым нарушил молчание Али.
- Я не знаю этих чисел, - сказал он, опуская голову.
- Я это знал, - подал голос Вали.
- Тогда я знаю эти числа, - обрадовался Али.
- Тогда и я знаю! - воскликнул Вали.
И мудрецы сообщили пораженному царю задуманные им числа.

Назовите эти числа.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

1. Начинать следует с первой же фразы. Мудрец Али говорит - "Я не знаю, что это за числа". Он знает произведение чисел. Это говорит нам о том, что хотя бы одно из чисел не простое. Иначе бы он единственным образом разложил произведение на множители и знал бы оба числа.

2. Смотрим на фразу второго мудреца - "Я заранее знал, что ты не знаешь, что это за числа". Этот мудрец знает сумму чисел. О чём это нам говорит? Это значит, что при всех возможных разложениях суммы на слагаемые нет случая, когда оба числа простые. Иначе бы он не мог утверждать, что мудрец Али чисел не знает.

Что за числа не раскладываются на сумму двух простых чисел? После недолгих размышлений можно заметить, что если взять число равное (2 + (нечётное не простое)), то его разложения не будут давать двух простых чисел, например:
11 = 2 + 9 (9 - не простое)
11 = 3 + 8 (8 - чётное)
11 = 4 + 7 (4 - чётное)
11 = 5 + 6 (6 - чётное)
...

При переборе видно, что чётные числа будут получаться то в одном слагаемом, то в другом и на самых крайних величинах (2+А), не простым будет как раз число А (мы ведь его и выбирали нечётным и не простым).

Кандидаты в суммы: (2+9)=11, (2+15)=17, (2+21)=23, (2+25)=27, (2+33)=35, (2+35)=37, (2+39)=41, (2+45)=47 ...

3. Смотри на третью фразу. Мудрец Али говорит - "Теперь я знаю, что это за числа". Ему становится известно, что сумма чисел обладает именно такими свойствами, как мы выяснили в предыдущем пункте.

Проверим вариант (2+9)=11.
числа 2 и 9 - (произв = 18), варианты: [2*9], (3*6).
числа 3 и 8 - (произв = 24), варианты: (2*12), [3*8], (4*6).
числа 4 и 7 - (произв = 28), варианты: (2*14), [4*7].
числа 5 и 6 - (произв = 30), варианты: [2*15], (3*10), [5*6].

Это могут быть те пары, которые в сумме равны (2+А), где А - число нечётное и не простое. Сумма д.б. равна 11 или 17 или 23 или 27 или 35 или 37 или 41 или 47 или ... Подходят комбинации отмеченные квадратными скобками.

Проверим вариант (2+15)=17.
числа 2 и 15 - (произв = 30), варианты: [2*15], (3*10), [5*6]
числа 3 и 14 - (произв = 42), варианты: [2*21], [3*14], (6*7)
числа 4 и 13 - (произв = 52), варианты: (2*26), [4*13]
числа 5 и 12 - (произв = 60), варианты: (2*30), [3*20], (4*15), [5,12], (6*10)
числа 6 и 11 - (произв = 66), варианты: [2*33], (3*22), [6*11]
числа 7 и 10 - (произв = 70), варианты: [2*35], (5*14), [7*10]
числа 8 и 09 - (произв = 72), варианты: (2*36), [3*24], (4*18), (6*12), [8*9]

Это могут быть те пары, которые в сумме равны (2+А), где А - число нечётное и не простое. Сумма д.б. равна 11 или 17 или 23 или 27 или 35 или 37 или 41 или 47 или ... Подходят комбинации отмеченные квадратными скобками.

...{ Не полезу дальше }

4. Нам подходят те строки, где только по одной квадратной скобке:
числа 2 и 9 - (произв = 18), варианты: [2*9], (3*6).
числа 3 и 8 - (произв = 24), варианты: (2*12), [3*8], (4*6).
числа 4 и 7 - (произв = 28), варианты: (2*14), [4*7].
числа 4 и 13 - (произв = 52), варианты: (2*26), [4*13]
... { мы не полезли дальше }

Это как раз те варианты которые подтверждаются мудрецу Али после высказывания мудреца Вали. И так как вариант у него один (одна квадратная скобка), то он знает ответ.

5. Теперь осталось отобрать тот вариант, который "раскрыли глаза" мудрецу Вали, после того как он узнал, что мудрец Али определился.

числа 2 и 09 = 11
числа 3 и 08 = 11
числа 4 и 07 = 11
числа 4 и 13 = 17
... { мы не полезли дальше }

Чтобы мудрец Вали понял что - это за числа, они должны давать уникальную сумму - это числа 4 и 13.

P.S. Как доказать что других чисел нет - для меня вопрос открытый.

Бактерия делится пополам каждую секунду, т.е. по прошествии секунды из одной бактерии получается 2. Если в пробирку поместить одну бактерию, то она заполнится через 1 минуту. За какое время пробирка заполнится, если изначально поместить не 1, а 2 бактерии?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

По прошествии 1-й секунды получим 2 бактерии, 2-й секунды - 4 = 2 в степени 2, 3-й - 8 = 2 в степени 3. Таким образом получаем прогрессию, которая даст нам 2 в степени 60 к концу 1 минуты, как и сказано по условию.
Если же изначально поместить 2 бактерии, то к концу 1-й секунды будем иметь 4 бактерии, 2-й - 8, т.е. по окончании n секунд получим 2 в степени n+1 бактерий. Нам надо 2 в степени 60, т.е. n+1 = 60, откуда получаем, что n = 59.
Ответ: 59 секунд.

Бактерия делится пополам каждую секунду, т.е. по прошествии секунды из одной бактерии получается 2. Если в пробирку поместить одну бактерию, то она заполнится через 1 минуту. За какое время пробирка заполнится, если изначально поместить не 1, а 2 бактерии?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

По прошествии 1-й секунды получим 2 бактерии, 2-й секунды - 4 = 2 в степени 2, 3-й - 8 = 2 в степени 3. Таким образом получаем прогрессию, которая даст нам 2 в степени 60 к концу 1 минуты, как и сказано по условию.
Если же изначально поместить 2 бактерии, то к концу 1-й секунды будем иметь 4 бактерии, 2-й - 8, т.е. по окончании n секунд получим 2 в степени n+1 бактерий. Нам надо 2 в степени 60, т.е. n+1 = 60, откуда получаем, что n = 59.
Ответ: 59 секунд.

Один гладиатор прогневал римского императора. В очередной день боев Император посылал на сражения с ним на арене лучших бойцов, однако они не могли победить упорного бойца. Император во что бы то ни стало хотел немедленной смерти врага, но на глазах всего города он не хотел упреков в несправедливости. Тогда вместо очередного боя император предложил игру в две бумажки. На одной он предложил написать "Свобода". Если гладиатор вытянет ее, то ему будет дарована жизнь и свобода. Если гладиатор вытянет другую, на которой написано "Смерть", его ждет немедленная казнь.

Гладиатор прекрасно знал отношение к себе и хитрость Императора - он точно знал, что на обеих бумажках будет написано "Смерть". Однако он согласился сыграть в игру, вытянул одну бумажку - и выиграл свободу и жизнь.

Как он это сделал?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Подсказка в названии - используется логика отрицания отрицания.
Гладиатор, вытянув бумажку, не читая, тут же уничтожил ее. После чего, извинившись за неловкость, предложил для разрешения своей судьбы посмотреть вторую бумажку. Поскольку на второй было написано "Смерть", императору пришлось признать, что на первой было написано "Свобода".

Один гладиатор прогневал римского императора. В очередной день боев Император посылал на сражения с ним на арене лучших бойцов, однако они не могли победить упорного бойца. Император во что бы то ни стало хотел немедленной смерти врага, но на глазах всего города он не хотел упреков в несправедливости. Тогда вместо очередного боя император предложил игру в две бумажки. На одной он предложил написать "Свобода". Если гладиатор вытянет ее, то ему будет дарована жизнь и свобода. Если гладиатор вытянет другую, на которой написано "Смерть", его ждет немедленная казнь.

Гладиатор прекрасно знал отношение к себе и хитрость Императора - он точно знал, что на обеих бумажках будет написано "Смерть". Однако он согласился сыграть в игру, вытянул одну бумажку - и выиграл свободу и жизнь.

Как он это сделал?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Подсказка в названии - используется логика отрицания отрицания.
Гладиатор, вытянув бумажку, не читая, тут же уничтожил ее. После чего, извинившись за неловкость, предложил для разрешения своей судьбы посмотреть вторую бумажку. Поскольку на второй было написано "Смерть", императору пришлось признать, что на первой было написано "Свобода".

Сколько мест на земном шаре, где, если вы пройдете одну милю на юг, одну милю на восток и одну милю на север, вы вернетесь в то место, откуда вы отправлялись в путь?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Правильный ответ — бесконечно * бесконечно + еще одно место.

Одна точка:
На Северном полюсе любое горизонтальное направление указывает на юг. Если вы стартуете на Северном полюсе, вы можете пройти милю в любом направлении, и это будет считаться движением на юг. Более того, следующая миля пути на восток будет расположена по окружности вокруг Северного полюса. У вас получится именно так, если вы не только изначально направитесь на восток, но и будете постоянно корректировать свое направление движения, чтобы все время идти строго на восток. Тогда у вас будет возможность на финальном отрезке идти прямо к Северному полюсу и вернуться туда, откуда вы отправились.

Далее:
Представьте, что вы стартуете в точке, которая расположена на расстоянии чуть больше мили от Южного полюса. Вы пройдете одну милю на юг, потом повернете на 90 градусов и отправитесь на восток, при этом вы опишете полную окружность длиной в одну милю вокруг полюса, направляясь все время строго на восток, и, наконец, пройдете милю на север и вернетесь в исходную точку.
Такая точка не одна — таких точек бесконечное количество. Вы можете отправиться из любой точки, которая находится на подходящем расстоянии от Южного полюса. Такие точки расположены на окружности, центр которой — Южный полюс.
Что такое «подходящее расстояние»? Окружность длиной в одну милю должна иметь радиус 1/2Пи мили. Стартовая точка маршрута должна располагаться еще на одну милю дальше от полюса, то есть на расстоянии в 1+1/2Пи мили от него, или примерно в 1,159 мили.

Но и это еще не все. Допустим, вы стартуете чуть ближе к полюсу. Вы идете одну милю на юг, а потом идете строго на восток по меньшей окружности, длина которой 1/2 мили. Вы дважды совершите полный круг, а потом пройдете еще одну милю на север и вернетесь в исходную точку. Таких точек опять таки бесконечное множество, и они расположены на расстоянии в 1 + 1/4Пи мили от полюса.
Вы также можете выбрать такой маршрут, чтобы на втором этапе пройти вокруг полюса три раза, четыре раза и вообще любое целое число Пи раз. Каждый раз эти точки также будут расположены на окружности, центр которой полюс, а радиус — 1 + 1/2Пи мили. Таким образом, подобных точек — бесконечное множество, и расположены они на бесконечном количестве окружностей, расположенных концентрически вокруг полюса.

Сколько мест на земном шаре, где, если вы пройдете одну милю на юг, одну милю на восток и одну милю на север, вы вернетесь в то место, откуда вы отправлялись в путь?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Правильный ответ — бесконечно * бесконечно + еще одно место.

Одна точка:
На Северном полюсе любое горизонтальное направление указывает на юг. Если вы стартуете на Северном полюсе, вы можете пройти милю в любом направлении, и это будет считаться движением на юг. Более того, следующая миля пути на восток будет расположена по окружности вокруг Северного полюса. У вас получится именно так, если вы не только изначально направитесь на восток, но и будете постоянно корректировать свое направление движения, чтобы все время идти строго на восток. Тогда у вас будет возможность на финальном отрезке идти прямо к Северному полюсу и вернуться туда, откуда вы отправились.

Далее:
Представьте, что вы стартуете в точке, которая расположена на расстоянии чуть больше мили от Южного полюса. Вы пройдете одну милю на юг, потом повернете на 90 градусов и отправитесь на восток, при этом вы опишете полную окружность длиной в одну милю вокруг полюса, направляясь все время строго на восток, и, наконец, пройдете милю на север и вернетесь в исходную точку.
Такая точка не одна — таких точек бесконечное количество. Вы можете отправиться из любой точки, которая находится на подходящем расстоянии от Южного полюса. Такие точки расположены на окружности, центр которой — Южный полюс.
Что такое «подходящее расстояние»? Окружность длиной в одну милю должна иметь радиус 1/2Пи мили. Стартовая точка маршрута должна располагаться еще на одну милю дальше от полюса, то есть на расстоянии в 1+1/2Пи мили от него, или примерно в 1,159 мили.

Но и это еще не все. Допустим, вы стартуете чуть ближе к полюсу. Вы идете одну милю на юг, а потом идете строго на восток по меньшей окружности, длина которой 1/2 мили. Вы дважды совершите полный круг, а потом пройдете еще одну милю на север и вернетесь в исходную точку. Таких точек опять таки бесконечное множество, и они расположены на расстоянии в 1 + 1/4Пи мили от полюса.
Вы также можете выбрать такой маршрут, чтобы на втором этапе пройти вокруг полюса три раза, четыре раза и вообще любое целое число Пи раз. Каждый раз эти точки также будут расположены на окружности, центр которой полюс, а радиус — 1 + 1/2Пи мили. Таким образом, подобных точек — бесконечное множество, и расположены они на бесконечном количестве окружностей, расположенных концентрически вокруг полюса.

Дана последовательность чисел 1, 12, 123, 1234, ... , 12345678910, 1234567891011, ... , 12345...9899100; Необходимо посчитать количество чисел в этой последовательности, делящихся на 3.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3.

Возможно эвристическое решение. Если выписать первые несколько чисел, то можно найти закономерность:
1 не делится
12 делится
123 делится
1234 не делится
12345 делится
123456 делится
1234567 не делится
12345678 делится

Эту последовательность можно проверить, продолжив и дальше. Таким образом, получается последовательность - + + - + + - + +..., где "-" означает неделимость. Таких групп от 1 до 100 будет 33, в каждой группе будет по 2 делящихся числа. Таким образом ответ - 66.

Для собеседования хватит и эвристики, но избавиться от неё можно с помощью метода математической индукции. 

Далее докажем, что числа в последовательности с порядковым номером, кратным трём, делятся на 3.
первое такое число - 123 делится на 3, поскольку сумма его цифр равна 6. Пусть член последовательность под номером k (кратным трём) делится на 3. Тогда член последовательности под номером k+3 также будет делиться, поскольку к сумме цифр k-го члена прибавятся числа k+1, k+2 и k+3. Их сумма равна 3*k + 6, то есть делится на 3. Значит сумма цифр члена под номером k+3 также делится на 3.

Аналогично доказывается делимость членов с номером 3*t-1 и неделимость на 3 членов с номером 3*t-2.

Доказав обнаруженную последовательность чередования делимости/неделимости, также находим ответ - 66.

Дана последовательность чисел 1, 12, 123, 1234, ... , 12345678910, 1234567891011, ... , 12345...9899100; Необходимо посчитать количество чисел в этой последовательности, делящихся на 3.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3.

Возможно эвристическое решение. Если выписать первые несколько чисел, то можно найти закономерность:
1 не делится
12 делится
123 делится
1234 не делится
12345 делится
123456 делится
1234567 не делится
12345678 делится

Эту последовательность можно проверить, продолжив и дальше. Таким образом, получается последовательность - + + - + + - + +..., где "-" означает неделимость. Таких групп от 1 до 100 будет 33, в каждой группе будет по 2 делящихся числа. Таким образом ответ - 66.

Для собеседования хватит и эвристики, но избавиться от неё можно с помощью метода математической индукции. 

Далее докажем, что числа в последовательности с порядковым номером, кратным трём, делятся на 3.
первое такое число - 123 делится на 3, поскольку сумма его цифр равна 6. Пусть член последовательность под номером k (кратным трём) делится на 3. Тогда член последовательности под номером k+3 также будет делиться, поскольку к сумме цифр k-го члена прибавятся числа k+1, k+2 и k+3. Их сумма равна 3*k + 6, то есть делится на 3. Значит сумма цифр члена под номером k+3 также делится на 3.

Аналогично доказывается делимость членов с номером 3*t-1 и неделимость на 3 членов с номером 3*t-2.

Доказав обнаруженную последовательность чередования делимости/неделимости, также находим ответ - 66.

Какой цифрой заканчивается 777^333 + 333^777 ?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Важна последняя цифра, т.е. выражение можно упростить до
7^333 + 3^777 = 7 * (7^4)^83 + 3 * (3^4)^194 = 7 * 2401^83 + 3 * 81^194 = 7 * <что-то большое, заканчивающееся на 1> + 3 * <что-то большое, заканчивающееся на 1> = <что-то большое, заканчивающееся на 0>.

Какой цифрой заканчивается 777^333 + 333^777 ?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Важна последняя цифра, т.е. выражение можно упростить до
7^333 + 3^777 = 7 * (7^4)^83 + 3 * (3^4)^194 = 7 * 2401^83 + 3 * 81^194 = 7 * <что-то большое, заканчивающееся на 1> + 3 * <что-то большое, заканчивающееся на 1> = <что-то большое, заканчивающееся на 0>.

Жили-были 1000 лепреконов, каждый лепрекон имеет уникальный возраст и очень жадный. У лепреконов было золото и они решили его поделить. Условие дележки: если половина или более лепреконов согласна поделить, то золото делят между всеми поровну, если меньше половины согласно на раздел, то самого младшего лепрекона исключают из претендентов на золото и процесс повторяется. На сколько лепреконов поделят золото?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Ответ - на 512. 
Рассмотрим следующие ситуации: 
- если останется 2 лепрекона золото разделят на двоих; 
- если останется 3 лепрекона исключат младшего и разделят золото на двоих на следующем голосовании; 
-если останется 4 лепрекона золото разделят на четверых, т.к. третий по старшинству лепрекон будет голосовать за раздел, зная, что его тоже исключат на след. голосовании; 
-если останется 5, 6 или 7 лепреконов золото разделят на четверых; 
-если останется 8 лепреконов золото разделят на восьмерых и т.д. 
Можно сделать вывод, что золото будет разделено на кол-во лепреконов равное максимальной степени двойки в пределах от двух до начального кол-ва лепреконов.

Жили-были 1000 лепреконов, каждый лепрекон имеет уникальный возраст и очень жадный. У лепреконов было золото и они решили его поделить. Условие дележки: если половина или более лепреконов согласна поделить, то золото делят между всеми поровну, если меньше половины согласно на раздел, то самого младшего лепрекона исключают из претендентов на золото и процесс повторяется. На сколько лепреконов поделят золото?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Ответ - на 512. 
Рассмотрим следующие ситуации: 
- если останется 2 лепрекона золото разделят на двоих; 
- если останется 3 лепрекона исключат младшего и разделят золото на двоих на следующем голосовании; 
-если останется 4 лепрекона золото разделят на четверых, т.к. третий по старшинству лепрекон будет голосовать за раздел, зная, что его тоже исключат на след. голосовании; 
-если останется 5, 6 или 7 лепреконов золото разделят на четверых; 
-если останется 8 лепреконов золото разделят на восьмерых и т.д. 
Можно сделать вывод, что золото будет разделено на кол-во лепреконов равное максимальной степени двойки в пределах от двух до начального кол-ва лепреконов.

Имеется две разделенные наглухо комнаты. В первой комнате стоят 3 пронумерованных выключателя [1 2 3] провода от этих выключателей ведут в соседнюю комнату в которой стоят три пронумерованные лампы [1 2 3]. Как узнать в какой выключатель к какой лампе относится, если в каждую комнату можно зайти один раз?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Заходим в комнату с выключателями включаем первый и ждем 20 минут, выключаем. Включаем второй и уходим в комнату с лампами. Та лампа которая горит относится ко второму выключателю, та лампа которая не горит относится к третьему выключателю, та лампа которая теплая относиться к первому выключателю :)

Имеется две разделенные наглухо комнаты. В первой комнате стоят 3 пронумерованных выключателя [1 2 3] провода от этих выключателей ведут в соседнюю комнату в которой стоят три пронумерованные лампы [1 2 3]. Как узнать в какой выключатель к какой лампе относится, если в каждую комнату можно зайти один раз?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Заходим в комнату с выключателями включаем первый и ждем 20 минут, выключаем. Включаем второй и уходим в комнату с лампами. Та лампа которая горит относится ко второму выключателю, та лампа которая не горит относится к третьему выключателю, та лампа которая теплая относиться к первому выключателю :)

Календарь состоит из двух кубиков, на гранях которых нанесено по одной цифре. Располагая кубики рядом, можно составить числа 01 02 03 ... до 31. Какие цифры нанесены на грани каждого кубика?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим:
 

Верно ли наше решение?

Ответ:

012345
012678
И переворачивая 6

Календарь состоит из двух кубиков, на гранях которых нанесено по одной цифре. Располагая кубики рядом, можно составить числа 01 02 03 ... до 31. Какие цифры нанесены на грани каждого кубика?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим:
 

Верно ли наше решение?

Ответ:

012345
012678
И переворачивая 6

Напишите программу, которая будет печатать числа Фибоначчи максимально долго (без ошибок времени выполнения).

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

 /* 1 вариант */ 
public static void PrintFibonachi(int a, int b) 
{ 
int sum = a + b; 
Console.WriteLine("{0}", sum); 
 
a = b; 
b = sum; 
if (int.MaxValue - a > b) 
{ 
PrintFibonachi(a, b); 
} 
} 
 
/* 2 вариант */ 
public static void PrintFibonachi2(int a, int b) 
{ 
if (0.0 + a + b < int.MaxValue) // or (double)a or (double)b 
{ 
var sum = a + b; 
Console.WriteLine("{0}", sum); 
 
a = b; 
b = sum; 
PrintFibonachi2(a, b); 
} 
} 
static void Main() 
{ 
var a = 1; 
var b = 1; 
PrintFibonachi(a, b); 
} 

Напишите программу, которая будет печатать числа Фибоначчи максимально долго (без ошибок времени выполнения).

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

 /* 1 вариант */ 
public static void PrintFibonachi(int a, int b) 
{ 
int sum = a + b; 
Console.WriteLine("{0}", sum); 
 
a = b; 
b = sum; 
if (int.MaxValue - a > b) 
{ 
PrintFibonachi(a, b); 
} 
} 
 
/* 2 вариант */ 
public static void PrintFibonachi2(int a, int b) 
{ 
if (0.0 + a + b < int.MaxValue) // or (double)a or (double)b 
{ 
var sum = a + b; 
Console.WriteLine("{0}", sum); 
 
a = b; 
b = sum; 
PrintFibonachi2(a, b); 
} 
} 
static void Main() 
{ 
var a = 1; 
var b = 1; 
PrintFibonachi(a, b); 
} 

Какое наименьшее количество натуральных чисел надо взять, чтобы любое число от 1 до 300 можно было представить в виде суммы подходящего набора различных указанных натуральных чисел?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

9

Известно, что в двоичном представлении степеней двойки присутствует лишь одна единица: 2^0=1, 2^1=10, 2^2=100, ..., 2^8=100000000. Видим, что в двоичной записи числа 105 единицы стоят в 1-й, 4-й, 6-й и 7-й позициях (считаем слева направо). Значит, 105=2^0+2^3+2^5+2^6. Поскольку двоичное число 111111111 (девять единиц) равно 511 > 300, заключаем, что девяти чисел 1, 2, 4, 8, 16, 32, 64, 128, 256 вполне достаточно для представления любого натурального числа от 1 до 300 (и даже до 511).


Использование двоичной системы записи не является ключевым при решении этой задачи. Например, так же верны следующие девять чисел: 1, 2, 3, 7, 14, 28, 56, 112, 224.


Доказательство того, что искомый набор не может содержать менее девяти чисел:
Действительно, пусть у нас есть восемь чисел и любое число от 1 до 300 представимо в виде суммы разных чисел из этого набора. Используя наш набор, мы можем закодировать любое число от 1 до 300: пусть, например, число a равно сумме первого и третьего чисел нашего набора, тогда будем писать a=(1,0,1,0,0,0,0,0). Итак, число а получило свой код - строку из восьми символов, каждый символ или 0, или 1. Но нам надо закодировать триста чисел, а строк длины 8, как нетрудно видеть, всего 256. Значит, восьми чисел недостаточно.

Какое наименьшее количество натуральных чисел надо взять, чтобы любое число от 1 до 300 можно было представить в виде суммы подходящего набора различных указанных натуральных чисел?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

9

Известно, что в двоичном представлении степеней двойки присутствует лишь одна единица: 2^0=1, 2^1=10, 2^2=100, ..., 2^8=100000000. Видим, что в двоичной записи числа 105 единицы стоят в 1-й, 4-й, 6-й и 7-й позициях (считаем слева направо). Значит, 105=2^0+2^3+2^5+2^6. Поскольку двоичное число 111111111 (девять единиц) равно 511 > 300, заключаем, что девяти чисел 1, 2, 4, 8, 16, 32, 64, 128, 256 вполне достаточно для представления любого натурального числа от 1 до 300 (и даже до 511).


Использование двоичной системы записи не является ключевым при решении этой задачи. Например, так же верны следующие девять чисел: 1, 2, 3, 7, 14, 28, 56, 112, 224.


Доказательство того, что искомый набор не может содержать менее девяти чисел:
Действительно, пусть у нас есть восемь чисел и любое число от 1 до 300 представимо в виде суммы разных чисел из этого набора. Используя наш набор, мы можем закодировать любое число от 1 до 300: пусть, например, число a равно сумме первого и третьего чисел нашего набора, тогда будем писать a=(1,0,1,0,0,0,0,0). Итак, число а получило свой код - строку из восьми символов, каждый символ или 0, или 1. Но нам надо закодировать триста чисел, а строк длины 8, как нетрудно видеть, всего 256. Значит, восьми чисел недостаточно.

Дана матрица 
x1 x2 x3
y1 y2 y3
z1 z2 z3

Даны числа от 1 до 9. необходимо раставить эти числа так, чтобы:
x1 + x2 + x3 = y1 + y2 + y3 = z1 + z2 + z3
x1 + y1 + z1 = x2 + y2 + z2 = x3 + y3 + z3
x1 + y2 + z3 = x3 + y2 + z1

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Вы не поверите, но правильных решений 4.

Сумма всех чисел от 1 до 9 = 45. 45/3 = 15. Значит каждая вертикаль, каждая горизонталь и каждая диагональ должна давать в сумме 15.
Теперь как бы мы не представляли матрицу:
1 2 3 1 4 7 1 2 3 1 6 7
4 5 6 2 5 8 6 5 4 2 5 8
7 8 9 3 6 9 7 8 9 3 4 9 и т.д. 5 будет всегда в центре. Тоесть нужна цифра от которой мы будем отталкиватся.
Также есть математическое описание почему 5 : 15/3= 5 (среднее число любой линии матрицы).

Затем у нас не так уж и много комбинаций двух цифр которые дают в сумме 10: 1 и 9, 2 и 8, 3 и 7, 4 и 6. Теперь можно подбором (это займет минуту максимум), либо сначала в углы матрицы поставить комбинации из парных чисел (8 и 2, 4 и 6) и пытатся их подбирать (вы удивитесь но только так найдете правильный ответ), либо непарных чисел. Если вы создадите программу которая решит вам такую задачу, то увдете она выведет 4 варианта ответа:
8 1 6 2 9 4 6 1 8 4 9 2
3 5 7 7 5 3 7 5 3 3 5 7
4 9 2 6 1 8 2 9 4 8 1 6 просто меняете местами парные числа в одной паре относительно друг друга, а затем сами две пары меняете местами.

Для любознательных: есть алгоритм который позволяет решать такие матрицы (но только для не парных комбинаций - тоесть 3х3, 5х5, 7х7 ..., для парных решений нет) и подбирать числа,с помощью которых можно такое сделать. Вся суть в том, что прямым перебором обычный компьютер решает 3х3 около секунды (9! комбинаций), 4х4 - около 9 лет(16! комбинаций) - оно не решаемо, но комп будет столько пытатся решить, ну и дальше по факториалу. 

Даная задача была, на собеседовании, что бы пройти на java курсы (отводилось 5 минут на решение).

Дана матрица 
x1 x2 x3
y1 y2 y3
z1 z2 z3

Даны числа от 1 до 9. необходимо раставить эти числа так, чтобы:
x1 + x2 + x3 = y1 + y2 + y3 = z1 + z2 + z3
x1 + y1 + z1 = x2 + y2 + z2 = x3 + y3 + z3
x1 + y2 + z3 = x3 + y2 + z1

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Вы не поверите, но правильных решений 4.

Сумма всех чисел от 1 до 9 = 45. 45/3 = 15. Значит каждая вертикаль, каждая горизонталь и каждая диагональ должна давать в сумме 15.
Теперь как бы мы не представляли матрицу:
1 2 3 1 4 7 1 2 3 1 6 7
4 5 6 2 5 8 6 5 4 2 5 8
7 8 9 3 6 9 7 8 9 3 4 9 и т.д. 5 будет всегда в центре. Тоесть нужна цифра от которой мы будем отталкиватся.
Также есть математическое описание почему 5 : 15/3= 5 (среднее число любой линии матрицы).

Затем у нас не так уж и много комбинаций двух цифр которые дают в сумме 10: 1 и 9, 2 и 8, 3 и 7, 4 и 6. Теперь можно подбором (это займет минуту максимум), либо сначала в углы матрицы поставить комбинации из парных чисел (8 и 2, 4 и 6) и пытатся их подбирать (вы удивитесь но только так найдете правильный ответ), либо непарных чисел. Если вы создадите программу которая решит вам такую задачу, то увдете она выведет 4 варианта ответа:
8 1 6 2 9 4 6 1 8 4 9 2
3 5 7 7 5 3 7 5 3 3 5 7
4 9 2 6 1 8 2 9 4 8 1 6 просто меняете местами парные числа в одной паре относительно друг друга, а затем сами две пары меняете местами.

Для любознательных: есть алгоритм который позволяет решать такие матрицы (но только для не парных комбинаций - тоесть 3х3, 5х5, 7х7 ..., для парных решений нет) и подбирать числа,с помощью которых можно такое сделать. Вся суть в том, что прямым перебором обычный компьютер решает 3х3 около секунды (9! комбинаций), 4х4 - около 9 лет(16! комбинаций) - оно не решаемо, но комп будет столько пытатся решить, ну и дальше по факториалу. 

Даная задача была, на собеседовании, что бы пройти на java курсы (отводилось 5 минут на решение).

Дан линейный список. Каждый элемент содержит 2 указателя. Первый указывает на следующий элемент в списке. Второй указывает на случайный элемент в списке (может указывать на себя). Задача создать копию исходного списка за линейное число операций. Разрешено использовать память выделенную под исходный список + такой же по размеру блок памяти, выделенный под новый линейный список и блок памяти произвольного размера, который не зависит от размера исходного линейного списка. В конечном итоге должно получится 2 одинаковых линейных списка.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Пусть a , b , c ,d .... - исходный линейный список
a.1 - первый указатель первого элемента
a.2 - второй указатель первого элемента

Создадим элемент a'.
a'.1 = a.1
изменим a.1
a.1 = указатель на a'

Создадим элемент b'.
b'.1 = b.1
изменим b.1
b.1 = указатель b'

Продолжаем для всех элементов списка.

a'.2 = (a.2).1
b'.2 = (b.2).1
и т.д.

Теперь восстанавливаем первые указатели в обоих списках
a.1 = a'.1
a'.1 = b.1
b.1 = b'.1

и т.д.

Получаем 5 * n операций, где n - длина исходного списка, то есть как и требовалось линейное число операций.

Дан линейный список. Каждый элемент содержит 2 указателя. Первый указывает на следующий элемент в списке. Второй указывает на случайный элемент в списке (может указывать на себя). Задача создать копию исходного списка за линейное число операций. Разрешено использовать память выделенную под исходный список + такой же по размеру блок памяти, выделенный под новый линейный список и блок памяти произвольного размера, который не зависит от размера исходного линейного списка. В конечном итоге должно получится 2 одинаковых линейных списка.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Пусть a , b , c ,d .... - исходный линейный список
a.1 - первый указатель первого элемента
a.2 - второй указатель первого элемента

Создадим элемент a'.
a'.1 = a.1
изменим a.1
a.1 = указатель на a'

Создадим элемент b'.
b'.1 = b.1
изменим b.1
b.1 = указатель b'

Продолжаем для всех элементов списка.

a'.2 = (a.2).1
b'.2 = (b.2).1
и т.д.

Теперь восстанавливаем первые указатели в обоих списках
a.1 = a'.1
a'.1 = b.1
b.1 = b'.1

и т.д.

Получаем 5 * n операций, где n - длина исходного списка, то есть как и требовалось линейное число операций.

У вас есть рабочий, он должен работать неделю, платить ему нужно каждый день равными частями. У вас есть цельный кусок золота, его хватит как раз на семь дней, на нем засечки (шесть засечек). Разрезать кусок можно дважды только по засечкам. Как расплачиваться с рабочим?

Подсказка: рабочий жадный, и носит золото с собой.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Разрезаем кусок золота следующим образом: 

| |       | | |        | | | | | 
  1           2                4 


В первый день дать 1.
Во второй день забрать 1 и дать 2.
В третий день дать 1 (+ у него есть 2).
В четвертый все забрать и дать 4.
В пятый дать 1 (итого 5).
В шестой забрать 1 дать 2 (итого 6).
В седьмой дать 1 (итого весь кусок первоначальный у рабочего).

У вас есть рабочий, он должен работать неделю, платить ему нужно каждый день равными частями. У вас есть цельный кусок золота, его хватит как раз на семь дней, на нем засечки (шесть засечек). Разрезать кусок можно дважды только по засечкам. Как расплачиваться с рабочим?

Подсказка: рабочий жадный, и носит золото с собой.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Разрезаем кусок золота следующим образом: 

| |       | | |        | | | | | 
  1           2                4 


В первый день дать 1.
Во второй день забрать 1 и дать 2.
В третий день дать 1 (+ у него есть 2).
В четвертый все забрать и дать 4.
В пятый дать 1 (итого 5).
В шестой забрать 1 дать 2 (итого 6).
В седьмой дать 1 (итого весь кусок первоначальный у рабочего).

Есть 2 веревки разной длины. Про них известно, что каждая, будучи подожженной с одного конца, горит ровно час. Но горит неравномерно. Вопрос. Как с их помощью отмерить 45 мин. Примечание. Резать веревки нельзя.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Поджечь первую веревку с двух концов, вторую — с одного. Когда первая веревка сгорит, поджечь второй конец второй веревки.

Есть 2 веревки разной длины. Про них известно, что каждая, будучи подожженной с одного конца, горит ровно час. Но горит неравномерно. Вопрос. Как с их помощью отмерить 45 мин. Примечание. Резать веревки нельзя.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Поджечь первую веревку с двух концов, вторую — с одного. Когда первая веревка сгорит, поджечь второй конец второй веревки.

Обозначим людей 1,2,5,10 по времени, затрачиваемому на переход через мост. 
Вот последовательность переходов, гарантирующая минимальное время (время на каждый переход указано в скобках):
0. Все на исходной позиции: 1, 2, 5, 10 ⇔ — (0 мин.)
1. 1 и 2 идут на другой берег: 5, 10 ⇔ 1, 2 (2 мин.)
2. 1 возвращается: 1, 5, 10 ⇔ 2 (1 мин.)
3. 5 и 10 идут на другой берег: 1 ⇔ 2, 5, 10 (10 мин.)
4. 2 возвращается: 1, 2 ⇔ 5, 10 (2 мин.)
5. 1 и 2 идут на другой берег: — ⇔ 1, 2, 5, 10 (2 мин.)

Итого: 2 + 1 + 10 + 2 + 2 = 17 минут.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

В самом начале в арбузе был 1% сухого вещества, то есть 1 кг. Сухое вещество испариться не может. А значит, когда его стало 2%, его вес не изменился (остался 1 кг). В результате, 2% = 1кг. Соответственно, 100% = 50кг.
Ответ: 50 кг.

Обозначим людей 1,2,5,10 по времени, затрачиваемому на переход через мост. 
Вот последовательность переходов, гарантирующая минимальное время (время на каждый переход указано в скобках):
0. Все на исходной позиции: 1, 2, 5, 10 ⇔ — (0 мин.)
1. 1 и 2 идут на другой берег: 5, 10 ⇔ 1, 2 (2 мин.)
2. 1 возвращается: 1, 5, 10 ⇔ 2 (1 мин.)
3. 5 и 10 идут на другой берег: 1 ⇔ 2, 5, 10 (10 мин.)
4. 2 возвращается: 1, 2 ⇔ 5, 10 (2 мин.)
5. 1 и 2 идут на другой берег: — ⇔ 1, 2, 5, 10 (2 мин.)

Итого: 2 + 1 + 10 + 2 + 2 = 17 минут.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

В самом начале в арбузе был 1% сухого вещества, то есть 1 кг. Сухое вещество испариться не может. А значит, когда его стало 2%, его вес не изменился (остался 1 кг). В результате, 2% = 1кг. Соответственно, 100% = 50кг.
Ответ: 50 кг.

Есть множество фигурок из 4-х квадратов в форме буквы "Т". Как заполнить квадрат 10х10 такими фигурками полностью в 1 слой?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Раскрасим квадрат как шахматную доску, при этом любая фигурка закроет либо 1 белую и 3 черных клетки (тип 1) либо 1 черную и 3 белых (тип 2). Чтобы закрыть 50 черных и 50 белых клеток, нужно одинаковое число фигурок типов 1 и 2. Для заполнения будет нужно 25 фигурок (10*10/4), что пополам не делится. Заполнить квадрат указанным способом невозможно.

Есть множество фигурок из 4-х квадратов в форме буквы "Т". Как заполнить квадрат 10х10 такими фигурками полностью в 1 слой?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Раскрасим квадрат как шахматную доску, при этом любая фигурка закроет либо 1 белую и 3 черных клетки (тип 1) либо 1 черную и 3 белых (тип 2). Чтобы закрыть 50 черных и 50 белых клеток, нужно одинаковое число фигурок типов 1 и 2. Для заполнения будет нужно 25 фигурок (10*10/4), что пополам не делится. Заполнить квадрат указанным способом невозможно.

Человек идет через туннель для поездов. Когда он прошел четверть пути, то услышал, что сзади приближается поезд. Неизвестна ни скорость поезда ни расстояние до него.
НО:
Если человек повернется и побежит назад, то он будет у начала туннеля одновременно с поездом.
Если человек побежит вперед, то будет у конца туннеля также одновременно с поездом. Человек ускоряется мгновенно и бежит с постоянной и одинаковой скоростью в обе стороны туннеля, поезд также едет с постоянной скоростью.
На сколько больше скорость поезда по сравнению со скоростью человека?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Если человек побежит к началу туннеля, пробежит четверть пути и встретится с поездом у входа, то это значит что когда он пробежит четверть пути к выходу из туннеля, поезд достигнет входа. В этот момент человек будет на середине тоннеля (1/4+1/4=1/2), а поезд у входа в туннель. Так как выхода они достигают одновременно, значит что поезд едет в два раза быстрей.

Человек идет через туннель для поездов. Когда он прошел четверть пути, то услышал, что сзади приближается поезд. Неизвестна ни скорость поезда ни расстояние до него.
НО:
Если человек повернется и побежит назад, то он будет у начала туннеля одновременно с поездом.
Если человек побежит вперед, то будет у конца туннеля также одновременно с поездом. Человек ускоряется мгновенно и бежит с постоянной и одинаковой скоростью в обе стороны туннеля, поезд также едет с постоянной скоростью.
На сколько больше скорость поезда по сравнению со скоростью человека?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Если человек побежит к началу туннеля, пробежит четверть пути и встретится с поездом у входа, то это значит что когда он пробежит четверть пути к выходу из туннеля, поезд достигнет входа. В этот момент человек будет на середине тоннеля (1/4+1/4=1/2), а поезд у входа в туннель. Так как выхода они достигают одновременно, значит что поезд едет в два раза быстрей.

Четырём людям надо в темноте перейти через мост. У людей есть один фонарик на четверых. Переходить мост можно только с фонариком, потому что темно и мост без перил. Одновременно на мосту могут находиться не более двух человек, потому что мост старый и не выдержит больше. У каждого человека своя скорость прохождения через мост: 
- первый проходит мост за 1 минуту
- второй — за 2 минуты
- третий — за 5
- четвёртый — за 10 минут.
Когда два человека переходят мост вместе, они идут со скоростью наиболее медленного из них. Какое минимальное время понадобится этой четвёрке, чтобы перейти мост, и в какой последовательности им надо его переходить?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Обозначим людей 1,2,5,10 по времени, затрачиваемому на переход через мост. 
Вот последовательность переходов, гарантирующая минимальное время (время на каждый переход указано в скобках):
0. Все на исходной позиции: 1, 2, 5, 10 ⇔ — (0 мин.)
1. 1 и 2 идут на другой берег: 5, 10 ⇔ 1, 2 (2 мин.)
2. 1 возвращается: 1, 5, 10 ⇔ 2 (1 мин.)
3. 5 и 10 идут на другой берег: 1 ⇔ 2, 5, 10 (10 мин.)
4. 2 возвращается: 1, 2 ⇔ 5, 10 (2 мин.)
5. 1 и 2 идут на другой берег: — ⇔ 1, 2, 5, 10 (2 мин.)

Итого: 2 + 1 + 10 + 2 + 2 = 17 минут.

Четырём людям надо в темноте перейти через мост. У людей есть один фонарик на четверых. Переходить мост можно только с фонариком, потому что темно и мост без перил. Одновременно на мосту могут находиться не более двух человек, потому что мост старый и не выдержит больше. У каждого человека своя скорость прохождения через мост: 
- первый проходит мост за 1 минуту
- второй — за 2 минуты
- третий — за 5
- четвёртый — за 10 минут.
Когда два человека переходят мост вместе, они идут со скоростью наиболее медленного из них. Какое минимальное время понадобится этой четвёрке, чтобы перейти мост, и в какой последовательности им надо его переходить?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Обозначим людей 1,2,5,10 по времени, затрачиваемому на переход через мост. 
Вот последовательность переходов, гарантирующая минимальное время (время на каждый переход указано в скобках):
0. Все на исходной позиции: 1, 2, 5, 10 ⇔ — (0 мин.)
1. 1 и 2 идут на другой берег: 5, 10 ⇔ 1, 2 (2 мин.)
2. 1 возвращается: 1, 5, 10 ⇔ 2 (1 мин.)
3. 5 и 10 идут на другой берег: 1 ⇔ 2, 5, 10 (10 мин.)
4. 2 возвращается: 1, 2 ⇔ 5, 10 (2 мин.)
5. 1 и 2 идут на другой берег: — ⇔ 1, 2, 5, 10 (2 мин.)

Итого: 2 + 1 + 10 + 2 + 2 = 17 минут.

На столе стоят 10 одинаковых стаканов. В каждом из них по 10 одинаковых монет.
Известно, что в одном стакане все монеты поддельные (весят на коэффициент k отлично от настоящих - k известно и одинаково для каждой из поддельных монет).

Необходимо с помощью ВСЕГО ЛИШЬ ОДНОГО взвешивания определить, в каком стакане поддельные монеты.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

1) Вообще говоря, о типе весов ничего не сказано. Рассмотрим вариант электронных весов.

Занумеруем мысленно каждый стакан.
Положим на электронные весы 1 монету из первого стакана, 2 монеты из второго, и т.д., до 10 монет из 10-го стакана.
Вес одной подлинной монеты х грамм.
Вес одной поддельной монеты k*х грамм.

На весах получили сумму:

Sigma по n=1..10 от n*(k^l[n]*x)^n,
где l - десятимерный вектор, каждая координата которого принадлежит {0,1}, причем, с ограничением,
Sigma по n=1..10 от l[n] = 1.

Таким образом, получив сумму, мы всегда взаимно однозначно определим, вектор l. Номер его единичной координаты - номер стакана с поддельными монетами.

2) Вероятно, задача имеет решение также с чашечными весами.

На столе стоят 10 одинаковых стаканов. В каждом из них по 10 одинаковых монет.
Известно, что в одном стакане все монеты поддельные (весят на коэффициент k отлично от настоящих - k известно и одинаково для каждой из поддельных монет).

Необходимо с помощью ВСЕГО ЛИШЬ ОДНОГО взвешивания определить, в каком стакане поддельные монеты.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

1) Вообще говоря, о типе весов ничего не сказано. Рассмотрим вариант электронных весов.

Занумеруем мысленно каждый стакан.
Положим на электронные весы 1 монету из первого стакана, 2 монеты из второго, и т.д., до 10 монет из 10-го стакана.
Вес одной подлинной монеты х грамм.
Вес одной поддельной монеты k*х грамм.

На весах получили сумму:

Sigma по n=1..10 от n*(k^l[n]*x)^n,
где l - десятимерный вектор, каждая координата которого принадлежит {0,1}, причем, с ограничением,
Sigma по n=1..10 от l[n] = 1.

Таким образом, получив сумму, мы всегда взаимно однозначно определим, вектор l. Номер его единичной координаты - номер стакана с поддельными монетами.

2) Вероятно, задача имеет решение также с чашечными весами.

Имеется массив натуральных чисел. Каждое из чисел присутствует в массиве ровно два раза и только одно из чисел не имеет пары. Необходимо предложить алгоритм, чтобы за минимальное число проходов по массиву определял число не имеющее пары.

Необходимо также предложить алгоритм, если уникальных числа два.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Первая задача решается за один проход по массиву.
Необходимо подсчитать XOR-сумму всех чисел массива.
Таким образом пары чисел "уничтожат" друг друга (A xor A = 0).

Для решения второй задачи необходимо разбить диапазон возможных значений чисел на несколько одинаковых по размеру поддиапазонов, например строго пополам. За один проход по массиву нужно вычислять XOR-суммы в поддиапазонах по-отдельности. Далее необходимо делить на поддиапазоны, объединение тех диапазонов, где XOR-сумма получилась не ноль. Как только при подсчёте XOR-сумм найдутся 2 диапазона с ненулевой XOR-суммой, это и будут искомые значение.

Например, для однобайтовых чисел и двух поддиапазонов: после первого прохода будут посчитанны XOR-суммы чисел диапазонов 0-127 и 128-255. Таким образом, если числа были в разных диапазонах, то обе XOR-суммы окажутся ненулевыми.

Для увеличения скорости поиска нужно использовать большее число поддиапазонов. Число проходов равно O(logA(B)), где A - число поддиапазонов (ячеек памяти для хранения XOR-сумм), а B - разрядность чисел в массиве.

Имеется массив натуральных чисел. Каждое из чисел присутствует в массиве ровно два раза и только одно из чисел не имеет пары. Необходимо предложить алгоритм, чтобы за минимальное число проходов по массиву определял число не имеющее пары.

Необходимо также предложить алгоритм, если уникальных числа два.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Первая задача решается за один проход по массиву.
Необходимо подсчитать XOR-сумму всех чисел массива.
Таким образом пары чисел "уничтожат" друг друга (A xor A = 0).

Для решения второй задачи необходимо разбить диапазон возможных значений чисел на несколько одинаковых по размеру поддиапазонов, например строго пополам. За один проход по массиву нужно вычислять XOR-суммы в поддиапазонах по-отдельности. Далее необходимо делить на поддиапазоны, объединение тех диапазонов, где XOR-сумма получилась не ноль. Как только при подсчёте XOR-сумм найдутся 2 диапазона с ненулевой XOR-суммой, это и будут искомые значение.

Например, для однобайтовых чисел и двух поддиапазонов: после первого прохода будут посчитанны XOR-суммы чисел диапазонов 0-127 и 128-255. Таким образом, если числа были в разных диапазонах, то обе XOR-суммы окажутся ненулевыми.

Для увеличения скорости поиска нужно использовать большее число поддиапазонов. Число проходов равно O(logA(B)), где A - число поддиапазонов (ячеек памяти для хранения XOR-сумм), а B - разрядность чисел в массиве.

Как трем жадным пиратам поделить золото, чтобы ни один из них не считал, что у него меньше, чем у любого другого, даже если любые двое из них в сговоре?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Обозначим пиратов: П1, П2, П3.

1) П1 делит все золото на 3 равных, по его мнению, кучки: А, В, С.
2) П2 выбирает наибольшую кучку, пусть это будет А.
3.1) Если П2 думает, что 2 наибольших кучки не совпадают, то П2 отделяет от А кучку, делая ее такого же размера как и вторая по величине. Т.о. А поделена на А1 (кучка такого же размера как и вторая по величине) и А2 (остаток).
3.2) Если П2 думает, что 2 наибольших кучки совпадают, то пираты выбирают в следующем порядке: П3, П2, П1.
4) П3 выбирает кучку между А1 и двумя другими (В, С).
5) П2 выбирает кучку с ограничением, что: если П3 не выбрал А1, то он должен ее выбрать.
6) П1 выбирает последнюю кучку (не А2).

Кучка А1 должна быть выбрана либо П3, либо П2. Назовем пирата, выбравшего А1, ПА, другого - ПВ.

7) ПВ делит А2 на 3 равные кучки.
8) ПА выбирает кучку, являющуюся частью А2.
9) П1 выбирает кучку, являющуюся частью А2.
10) ПВ выбирает последнюю оставшуюся кучку.

Пояснение почему все пираты думают, что другой не получил больше золота.
Без потери общности, мы можем сопоставить пиратов с кучкаи следующим образом:

пираты: ПА  ПВ   П1
 кучки: А1  В    С
       А21  А23  А22

- ПА получил А1 и наибольшую кучку от А2. Для него: A1 >= B, A1 >= C. Т.о. ни один из пиратов не получил золота больше, чем он.
- ПВ получил В и кучку от А2. Для него: B >= A1, B >=C. Также, он поделил А2 на 3 такие кучки, что между собой они равны.
- П1 получил С и кучку от А2. Для него: C >= A1, C = B.
П1 считает, что ПВ не получит больше, чем он, потому что П1 выбрал свою кучку от А2 раньше ПВ.
П1 считает, что ПА не получит больше, чем он, потому что для П1: С = А, А = А1 + А2; поэтому С больше, чем А1 и кучка от А2, которую получил ПА. (Даже если ПА взял целую А2, у П1 не будет меньше золота, чем у него)

Как трем жадным пиратам поделить золото, чтобы ни один из них не считал, что у него меньше, чем у любого другого, даже если любые двое из них в сговоре?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Обозначим пиратов: П1, П2, П3.

1) П1 делит все золото на 3 равных, по его мнению, кучки: А, В, С.
2) П2 выбирает наибольшую кучку, пусть это будет А.
3.1) Если П2 думает, что 2 наибольших кучки не совпадают, то П2 отделяет от А кучку, делая ее такого же размера как и вторая по величине. Т.о. А поделена на А1 (кучка такого же размера как и вторая по величине) и А2 (остаток).
3.2) Если П2 думает, что 2 наибольших кучки совпадают, то пираты выбирают в следующем порядке: П3, П2, П1.
4) П3 выбирает кучку между А1 и двумя другими (В, С).
5) П2 выбирает кучку с ограничением, что: если П3 не выбрал А1, то он должен ее выбрать.
6) П1 выбирает последнюю кучку (не А2).

Кучка А1 должна быть выбрана либо П3, либо П2. Назовем пирата, выбравшего А1, ПА, другого - ПВ.

7) ПВ делит А2 на 3 равные кучки.
8) ПА выбирает кучку, являющуюся частью А2.
9) П1 выбирает кучку, являющуюся частью А2.
10) ПВ выбирает последнюю оставшуюся кучку.

Пояснение почему все пираты думают, что другой не получил больше золота.
Без потери общности, мы можем сопоставить пиратов с кучкаи следующим образом:

пираты: ПА  ПВ   П1
 кучки: А1  В    С
       А21  А23  А22

- ПА получил А1 и наибольшую кучку от А2. Для него: A1 >= B, A1 >= C. Т.о. ни один из пиратов не получил золота больше, чем он.
- ПВ получил В и кучку от А2. Для него: B >= A1, B >=C. Также, он поделил А2 на 3 такие кучки, что между собой они равны.
- П1 получил С и кучку от А2. Для него: C >= A1, C = B.
П1 считает, что ПВ не получит больше, чем он, потому что П1 выбрал свою кучку от А2 раньше ПВ.
П1 считает, что ПА не получит больше, чем он, потому что для П1: С = А, А = А1 + А2; поэтому С больше, чем А1 и кучка от А2, которую получил ПА. (Даже если ПА взял целую А2, у П1 не будет меньше золота, чем у него)

Дано 8 монеток и весы с двумя чашами. Известно что среди монеток есть одна фальшивая и весит она меньше настоящей. Нужно за минимальное число взвешиваний определить фальшивую монетку.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Делается все за 2 взвешивания. Сначала кладем на весы по 3 монетки. Если вес одинаковый то фальшивая среди оставшихся двух. Взвешиваем по одной и находим. Если какая то из чаш весит меньше, то фальшивая среди трех монеток на чаше. Взвешиваем по одной. Если вес одинаковый, то фальшивая та, которая не взвешивалась. Если разные, то фальшивая с меньшим весом.

Дано 8 монеток и весы с двумя чашами. Известно что среди монеток есть одна фальшивая и весит она меньше настоящей. Нужно за минимальное число взвешиваний определить фальшивую монетку.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Делается все за 2 взвешивания. Сначала кладем на весы по 3 монетки. Если вес одинаковый то фальшивая среди оставшихся двух. Взвешиваем по одной и находим. Если какая то из чаш весит меньше, то фальшивая среди трех монеток на чаше. Взвешиваем по одной. Если вес одинаковый, то фальшивая та, которая не взвешивалась. Если разные, то фальшивая с меньшим весом.

Машинисту, находящемуся с внешней стороны замкнутой (произвольно большой ) последовательности сцепленных вагонов нужно определить, сколько вагонов в составе. В вагонах произвольным образом включен/выключен свет, и его можно включать и выключать. Машинист может передвигаться в любую сторону, но видит он только текущий вагон. Никаких других опознавательных знаков нет и делать нельзя.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Машинист включает свет в первом попавшемся вагоне, а дальше начинает двигаться по часовой стрелке, обходя все вагоны и считая их. Так он движется, пока не встретит вагон с включенным светом. Тогда он выключает в этом вагоне свет и начинает двигаться обратно к первому вагону. Определить первый вагон ему помогает счетчик пройденных вагонов. Достигнув первого вагона, если в нем по прежнему горит свет - то значит круг не замкнулся и следует повторить этот алгоритм. Таким образом можно найти общее число вагонов в сцепке.

Машинисту, находящемуся с внешней стороны замкнутой (произвольно большой ) последовательности сцепленных вагонов нужно определить, сколько вагонов в составе. В вагонах произвольным образом включен/выключен свет, и его можно включать и выключать. Машинист может передвигаться в любую сторону, но видит он только текущий вагон. Никаких других опознавательных знаков нет и делать нельзя.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Машинист включает свет в первом попавшемся вагоне, а дальше начинает двигаться по часовой стрелке, обходя все вагоны и считая их. Так он движется, пока не встретит вагон с включенным светом. Тогда он выключает в этом вагоне свет и начинает двигаться обратно к первому вагону. Определить первый вагон ему помогает счетчик пройденных вагонов. Достигнув первого вагона, если в нем по прежнему горит свет - то значит круг не замкнулся и следует повторить этот алгоритм. Таким образом можно найти общее число вагонов в сцепке.

Встретились два математика, которые давно не виделись.
— Сколько у тебя детей?
— Трое.
— А сколько им лет?
— Если перемножить их возраст — получится 36
— Не могу дать ответ, мало информации.
— Если сложить их возраста - номер твоего дома.
— Мне этих данных недостаточно.
Второй математик немного подумал и сказал:
— Старший сын — рыжий.
После чего был назван ответ?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

36 можно разложить на три натуральных множителя следующим образом:

1    1    36
1    2    18
1    3    12
1    4    9
1    6    6
2    2    9
2    3    6
3    3    4

Сумма в этих случаях составляет:
38, 21, 16, 14, 13, 13, 11, 10

Ясно, что во всех случаях, кроме 13, информации достаточно.

Если старший рыжий, значит, вообще есть старший (то есть максимальный возраст встречается только один раз).
Значит, 2*2*9.

Встретились два математика, которые давно не виделись.
— Сколько у тебя детей?
— Трое.
— А сколько им лет?
— Если перемножить их возраст — получится 36
— Не могу дать ответ, мало информации.
— Если сложить их возраста - номер твоего дома.
— Мне этих данных недостаточно.
Второй математик немного подумал и сказал:
— Старший сын — рыжий.
После чего был назван ответ?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

36 можно разложить на три натуральных множителя следующим образом:

1    1    36
1    2    18
1    3    12
1    4    9
1    6    6
2    2    9
2    3    6
3    3    4

Сумма в этих случаях составляет:
38, 21, 16, 14, 13, 13, 11, 10

Ясно, что во всех случаях, кроме 13, информации достаточно.

Если старший рыжий, значит, вообще есть старший (то есть максимальный возраст встречается только один раз).
Значит, 2*2*9.

Даны две переменные - a и b. Например, они равны a=2; b=3. Необходимо поменять местами эти числа (то есть a=3, b=2). Но не используя третью переменную.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

1. 
a = a + b; 
b = a - b; 
a = a - b; 


2. 
a = a ^ b; 
b = b ^ a; 
a = a ^ b; 

Даны две переменные - a и b. Например, они равны a=2; b=3. Необходимо поменять местами эти числа (то есть a=3, b=2). Но не используя третью переменную.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

1. 
a = a + b; 
b = a - b; 
a = a - b; 


2. 
a = a ^ b; 
b = b ^ a; 
a = a ^ b; 

Нужно найти площадь произвольного многоугольника без самопересечения сторон, который задан в виде массива вершин от 1 до N. Вершина N соединена с вершиной 1.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Способ №1 - Через некоторую точку пространства проводится луч.
- Накопитель площади обнуляетя
- Каждое ребро многоуольника проецируется на луч, и вычисляется полученной прямоугольной трапеции (если луч не пересекает ребро), либо площади пары прямоугольных треугольников (если луч пересекает ребро).При этом учитывается знак проекции ребра.
- Полученная площадь складывается с накопителем площади.
- После обхода всех ребер в накопителе будет площадь.

Способ №2. Более простым будет, например, такой способ:
- берём горизонтальную прямую, которая не пересекает ни одну сторону многоугольника (например, y=Ymin, где Ymin - наименьшая ордината вершин многоугольника)
- обходим все рёбра и площадь каждой получившейся прямоугольной трапеции вычисляем по формуле S[i] = (a[i] + b[i]) * h[i] / 2, где
a[i] = y[i] - Ymin;
b[i] = y[i+1] - Ymin;
h[i] = x[i+1] - x[i];
(внимательно следим за первым/последним ребром)
- суммируем найденные площади
- если порядок обхода вершин был против часовой стрелки, то в итоге получим отрицательную сумму - ничего страшного, просто найдём её абсолютную величину

Нужно найти площадь произвольного многоугольника без самопересечения сторон, который задан в виде массива вершин от 1 до N. Вершина N соединена с вершиной 1.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Способ №1 - Через некоторую точку пространства проводится луч.
- Накопитель площади обнуляетя
- Каждое ребро многоуольника проецируется на луч, и вычисляется полученной прямоугольной трапеции (если луч не пересекает ребро), либо площади пары прямоугольных треугольников (если луч пересекает ребро).При этом учитывается знак проекции ребра.
- Полученная площадь складывается с накопителем площади.
- После обхода всех ребер в накопителе будет площадь.

Способ №2. Более простым будет, например, такой способ:
- берём горизонтальную прямую, которая не пересекает ни одну сторону многоугольника (например, y=Ymin, где Ymin - наименьшая ордината вершин многоугольника)
- обходим все рёбра и площадь каждой получившейся прямоугольной трапеции вычисляем по формуле S[i] = (a[i] + b[i]) * h[i] / 2, где
a[i] = y[i] - Ymin;
b[i] = y[i+1] - Ymin;
h[i] = x[i+1] - x[i];
(внимательно следим за первым/последним ребром)
- суммируем найденные площади
- если порядок обхода вершин был против часовой стрелки, то в итоге получим отрицательную сумму - ничего страшного, просто найдём её абсолютную величину

Имеется девять шаров, восемь из которых одинакового веса, а один - тяжелее остальных и весы, с помощью которых можно определить какой шар(группа шаров) тяжелее. За два взвешивания определить тяжелый шар.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Разделить шары на три равные кучи. Взвесить любые две. Если они равны, то тяжелый шар в оставшейся куче, тогда мы взвешиваем два любых из оставшейся кучи, и определяем какой шар тяжелее (если равны, то тяжелый шар - тот который не взвешивали). Если кучи не равны, то берем шары из тяжелой кучи и вычисляем тяжелый шар вышеописанным методом.

Имеется девять шаров, восемь из которых одинакового веса, а один - тяжелее остальных и весы, с помощью которых можно определить какой шар(группа шаров) тяжелее. За два взвешивания определить тяжелый шар.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Разделить шары на три равные кучи. Взвесить любые две. Если они равны, то тяжелый шар в оставшейся куче, тогда мы взвешиваем два любых из оставшейся кучи, и определяем какой шар тяжелее (если равны, то тяжелый шар - тот который не взвешивали). Если кучи не равны, то берем шары из тяжелой кучи и вычисляем тяжелый шар вышеописанным методом.

Имеется указатель на голову односвязного списка. Требуется найти N-й с конца элемент.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Решение: отсчитать N элементов с начала списка, взять ещё один указатель на голову списка и двигать их одновременно, пока первый не достигнет конца. Тогда второй указатель будет стоять на N-ом с конца элементе.

Альтернативное решение: Двигаться с начала списка, запоминая N-й и предыдущий N-й элементы. Когда указатель достигнет конца, взять предыдущий N-й и пройти недостающее число элементов (кол-во пройденных после последнего N-го).
Некоторое преимущество этого метода в том, что совершается лишь один проход по списку (с небольшим оверхедом в конце), а не два (за вычетом небольшого оверхеда), но за счёт усложнения кода.

Имеется указатель на голову односвязного списка. Требуется найти N-й с конца элемент.

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Решение: отсчитать N элементов с начала списка, взять ещё один указатель на голову списка и двигать их одновременно, пока первый не достигнет конца. Тогда второй указатель будет стоять на N-ом с конца элементе.

Альтернативное решение: Двигаться с начала списка, запоминая N-й и предыдущий N-й элементы. Когда указатель достигнет конца, взять предыдущий N-й и пройти недостающее число элементов (кол-во пройденных после последнего N-го).
Некоторое преимущество этого метода в том, что совершается лишь один проход по списку (с небольшим оверхедом в конце), а не два (за вычетом небольшого оверхеда), но за счёт усложнения кода.

Имеется круглый стол R = 100см. Два игрока по очереди кладут на него монеты (по одной за ход) r = 1см. Монеты можно класть только рядом с уже лежащими и они не должны накладываться одна на одну (в том числе частично), их нельзя класть ребром, они не должны падать со стола. 

Первый или второй игрок выиграет при правильной игре?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Первый кладет монету в центр стола, а дальше на каждом ходу кладет монету центрально симметрично монете второго, положенной на предыдущем ходу. Таким образом второй проиграет.

Имеется круглый стол R = 100см. Два игрока по очереди кладут на него монеты (по одной за ход) r = 1см. Монеты можно класть только рядом с уже лежащими и они не должны накладываться одна на одну (в том числе частично), их нельзя класть ребром, они не должны падать со стола. 

Первый или второй игрок выиграет при правильной игре?

Уважаемые учащиеся ниже Вы сможете увидеть ответ, перед тем, как ответить, пожалуйста, постарайтесь написать для себя ответ на черновике, и только потом сравните наш ответ с Вашим: 

Верно ли наше решение?

Ответ:

Первый кладет монету в центр стола, а дальше на каждом ходу кладет монету центрально симметрично монете второго, положенной на предыдущем ходу. Таким образом второй проиграет.