Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / Программирование [игнор отключен] [закрыт для гостей] / задачка яндекс / 21 сообщений из 21, страница 1 из 1
06.03.2013, 04:56
    #38175379
rus_bug
rus_bug
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
Даны 2012 гирек разной массы. Они разбиты на две группы (по 1006 в каждой),
внутри которых упорядочены по массе. Предложите способ за 11 взвешиваний
найти 1006-ую гирьку по массе среди всех.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.03.2013, 09:11
    #38175482
Abstraction
Abstraction
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
rus_bug,

Вам даже количество взвешиваний назвали, которое является колоссальной подсказкой.
Шаг 1: взвешиваем среднюю (503) против средней. Те гирьки, которые легче лёгкой и строго тяжелее тяжёлой, не могут быть 1006 по массе. Их выкидываем, имеем массивы размером 503.
Шаг 2:...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.03.2013, 09:15
    #38175485
AndreTM
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
Abstraction Yes (в том смысле, что +1, что задачки с брэйна и диофанта, что... пошёл я посплю...)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.03.2013, 14:21
    #38176053
rus_bug
rus_bug
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
Abstractionrus_bug,
Те гирьки, которые легче лёгкой и строго тяжелее тяжёлой, не могут быть 1006 по массе.


Разверните пожалуйста, ничего не понял, про середину сам додумался, а дальше...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.03.2013, 14:25
    #38176057
ravt
ravt
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
а дальше середину от середины, и так далее пока не найдете нужную вам.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.03.2013, 14:26
    #38176059
rus_bug
rus_bug
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
rus_bugAbstractionrus_bug,
Те гирьки, которые легче лёгкой и строго тяжелее тяжёлой, не могут быть 1006 по массе.


Разверните пожалуйста, ничего не понял, про середину сам додумался, а дальше... - с этим тоже понятно
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.03.2013, 15:12
    #38176144
Abstraction
Abstraction
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
rus_bugAbstractionrus_bug,
Те гирьки, которые легче лёгкой и строго тяжелее тяжёлой, не могут быть 1006 по массе.


Разверните пожалуйста, ничего не понял, про середину сам додумался, а дальше...а) Если гирька 1006-я по массе, то есть ровно 1006 легче её (включая её саму). Но легче лёгкой могут быть только 503 из её группы и 502 из другой. Засада. Ну, и все легче её можно выкинуть тем же образом; аналогично с теми, кто строго тяжелее тяжёлой.
б) И в кандидатах у нас остаются две группы по 503 гири, причём гири в каждой группе упорядочены по массе и все разной массы. Теперь берём 252-ые гири и сравниваем; всё, что строго легче лёгкой и строго тяжелее тяжёлой, опять уходит в брак (ибо строго легче лёгкой могут быть лишь 502 гири из набора и 503 гири из выкинутых на предыдущем шаге). Остаётся две группы по 252 гири...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.03.2013, 20:38
    #38176646
AndreTM
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
Abstraction,

В 2049-м году придётся уже давать 12 взвешиваний...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.03.2013, 21:17
    #38176683
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
Вот поинтереснее чем гирьки

Задача

Имеется 15 шаров. Среди них 2 радиоактивных.
Имеется счётчик Гейгера. Его можно поднести к
группе шаров и узнать, есть ли в ней радиоактивные
(но неизвестно - сколько их). За сколько замеров
можно найти оба радиоактивных шара в группе из
15 шаров?

Только не гуглите. Поищите ответ сами. Я тож
оптимального пока не нашёл.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.03.2013, 22:31
    #38176717
AndreTM
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
mayton,

Просто делим по три группы.
15 / 3 = три группы по пять, 2 замера (третья - исключением), худший случай - фонят две группы по пять.
2 * (5 / 3) = 2 * (два + два + один), 4 замера двоек (третьи - исключением), худший случай - фонят две группы по два.
Остается 2 замера...
Сумма = 8
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.03.2013, 23:01
    #38176737
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
8 замеров - это много.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.03.2013, 23:09
    #38176741
AndreTM
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
mayton8 замеров - это много.Твой вариант?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.03.2013, 23:21
    #38176752
Яростный Меч
Яростный Меч
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
AndreTMтри группы по пять, 2 замера (третья - исключением)если из первых двух только одна фонит, то про третью ничего не известно
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.03.2013, 00:00
    #38176769
AndreTM
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
Ну, тогда поделим на 1+2+4+8...
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.03.2013, 03:25
    #38176825
rus_bug
rus_bug
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
В принципе эта легкая

В множестве из n человек каждый может знать или не знать другого (если A
знает B, отсюда не следует, что B знает A). Все знакомства заданы булевой
матрицей n × n. В этом множестве может найтись или не найтись знаменитость
— человек, который никого не знает, но которого знают все. Предложите алго-
ритм, который бы находил в множестве знаменитость или говорил, что ее в этом
множестве нет. Сложность по времени — O(n), сложность по памяти — O(1).

я нашел решение за 2n
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.03.2013, 03:34
    #38176826
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
Если представить это множество как орграф - то знаменитость
это вершина у которой мощность входящих рёбер - максимальна
и равна n - 1.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.03.2013, 04:10
    #38176828
AndreTM
AndreTM
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
mayton,

так есть ли решение (для двух из n-1) за меньше, чем (n+1)/2 ?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.03.2013, 11:00
    #38176990
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
Я не понимаю как ты получаешь НЕ-квадратичную сложность?
Либо у тебя на этапе ввода булевой матрицы уже расчитаны
суммы по строкам и столбцам либо есть какая-то хитрость в
условии которую ты не упомянул.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.03.2013, 12:13
    #38177082
Abstraction
Abstraction
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
maytonИмеется 15 шаров. Среди них 2 радиоактивных.
Имеется счётчик Гейгера. Его можно поднести к
группе шаров и узнать, есть ли в ней радиоактивные
(но неизвестно - сколько их). За сколько замеров
можно найти оба радиоактивных шара в группе из
15 шаров? 1) Пусть есть группа из n шаров с одним радиоактивным. Шарик вычисляется за измерений, быстрее нельзя.
Для двух радиоактивных шаров теоретический минимум , в нашем случае 7 измерений. Однако при n=6 теоретический предел недостижим (из-за того, что любое измерение может оставить более 8 возможных вариантов).
Теперь к методике.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
Первое измерение: 5 шаров (1).
  Если результат негативный, из оставшихся 10 меряем 3 шара (2).
    Если результат негативный, из оставшихся 7 меряем 2 шара (3).
      Если результат негативный, дальше меряем по одному шару, радиоактивные шары найдены.

5(поз)-10(неизв), осталось 6 измерений:
Меряем 1 шар из 5 и 4 шара из 10 (2).
  Если результат негативный, меряем один шар из четырёх и два шара из шести (3).
    Если результат негативный, меряем один шар из трёх и один шар из четырёх (4).
      Если результат негативный, меряем один шар из двух (5).
        Если результат позитивный, находим второй шар из оставшихся четырёх (7).
        Если результат негативный, первый шар - оставшийся из двух, второй - один из трёх (7).
      Если результат позитивный, меряем оставшиеся два шара из трёх (5).
        Если результат позитивный, находим по шару в каждой паре (7).
        Если результат негативный, один шар найден, второй - один из четырёх (7).
    Если результат позитивный, меряем те же два шара отдельно (4).
      Если результат позитивный, находим один шар в этой паре (5), а другой - среди четырёх (7).
      Если результат негативный, один шар найден; второй - один из семи (7).
  Если результат позитивный, меряем один шар отдельно (3).
    Если результат негативный, у нас по одному шару в двух четвёрках (7).
    Если результат позитивный, то второй шар - один из 14 (7).

3(поз)-7(неизв), осталось 5 измерений:
Меряем 1 шар из 3 и 2 шара из 7 (3).
  Если результат негативный, меряем один шар из двух (4).
    При любом измерении, один шар найден, второй - один из 5 или 6 (7).
  Если результат позитивный, меряем пять шаров (4).
    Если результат позитивный, один шар найден, второй - 1 из 5 (7).
    Если результат негативный, проверяем 1 шар ещё раз отдельно (5)
      Если результат позитивный, второй шар - один из 4 (7).
      Если результат негативный, у нас по одному шару в двух парах (7).

2(поз)-5(неизв), осталось 4 измерения: эта ситуация разбиралась в случае 3-7.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.03.2013, 12:54
    #38177144
Яростный Меч
Яростный Меч
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
rus_bugВ принципе эта легкая

В множестве из n человек каждый может знать или не знать другого (если A
знает B, отсюда не следует, что B знает A). Все знакомства заданы булевой
матрицей n × n. В этом множестве может найтись или не найтись знаменитость
— человек, который никого не знает, но которого знают все. Предложите алго-
ритм, который бы находил в множестве знаменитость или говорил, что ее в этом
множестве нет. Сложность по времени — O(n), сложность по памяти — O(1).

я нашел решение за 2n 9534483
только там заведомо известно, что "знаменитость" есть
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
08.03.2013, 14:39
    #38178094
rus_bug
rus_bug
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
задачка яндекс
mayton,

Нет, никаких доп условий

Ответ

 
да, рассматриваем матрицу, первую строку если 1-й кого-то не знает, то он нас больше не интересует, проверяем первого кого он знает у проверяемого, начинаем искать с номера предыдущего i + 1, опять находим первого, кого он знает, если он никого не знает, проверяем номера <= i если никого не знает, нашли, если кого-то знает из предыдущих, то известного нет
Поиск известного занимает N операций и N опереций требуется чтобы проверить известного
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / задачка яндекс / 21 сообщений из 21, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение  
Полит. конфиден.  
созд. / загр.: 453ms
Закрыть
start [/forum/topic.php?fid=16&tablet=1&tid=1341899]:
 0ms
get settings:
 9ms
get forum list:
 9ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 155ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 54ms
get tp. blocked users:
 2ms
others: 209ms
total:  453ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]