ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / задачка яндекс
21 сообщений из 21, страница 1 из 1
задачка яндекс
    #38175379
rus_bug
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rus_bug
Участник
Даны 2012 гирек разной массы. Они разбиты на две группы (по 1006 в каждой),
внутри которых упорядочены по массе. Предложите способ за 11 взвешиваний
найти 1006-ую гирьку по массе среди всех.
...
Рейтинг: 0 / 0
06.03.2013, 04:56
| Ответить | Цитировать | Написать  
задачка яндекс
    #38175482
Abstraction
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Abstraction
Участник
rus_bug,

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


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


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


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

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

Задача

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

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

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

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

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

так есть ли решение (для двух из n-1) за меньше, чем (n+1)/2 ?
...
Рейтинг: 0 / 0
07.03.2013, 04:10
| Ответить | Цитировать | Написать  
задачка яндекс
    #38176990
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Я не понимаю как ты получаешь НЕ-квадратичную сложность?
Либо у тебя на этапе ввода булевой матрицы уже расчитаны
суммы по строкам и столбцам либо есть какая-то хитрость в
условии которую ты не упомянул.
...
Рейтинг: 0 / 0
07.03.2013, 11:00
| Ответить | Цитировать | Написать  
задачка яндекс
    #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:13
| Ответить | Цитировать | Написать  
задачка яндекс
    #38177144
Фотография Яростный Меч
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Яростный Меч
Участник
rus_bugВ принципе эта легкая

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

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

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

Ответ

 
да, рассматриваем матрицу, первую строку если 1-й кого-то не знает, то он нас больше не интересует, проверяем первого кого он знает у проверяемого, начинаем искать с номера предыдущего i + 1, опять находим первого, кого он знает, если он никого не знает, проверяем номера <= i если никого не знает, нашли, если кого-то знает из предыдущих, то известного нет
Поиск известного занимает N операций и N опереций требуется чтобы проверить известного
...
Рейтинг: 0 / 0
08.03.2013, 14:39
| Ответить | Цитировать | Написать  
21 сообщений из 21, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / задачка яндекс
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&fpage=59&tid=1341899]:
 0ms
get settings:
 8ms
get forum list:
 15ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 73ms
get topic data:
 12ms
get forum data:
 3ms
get page messages:
 55ms
get tp. blocked users:
 2ms
others: 234ms
total:  410ms
созд. / загр.: 410ms
x
x
Закрыть


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