Сделал для вас расширение: dl.dropbox.com/u/133677/PrefsFlush_1.0.0.xpi
Раз в минуту делает flush и больше ничего не умеет. Распространяется как есть, делайте с ним что хотите :-)
А если данные о пробках только в одну сторону есть? Рисуется только одна линия ;-)
А ещё бывают дороги с односторонним движением… Нет, как ни крути — направление пробки показывать надо.
Мудрец k называет цвет ans[k] = (k — sum(i!=k, color[i])) mod 100.
Утверждение «мудрец прав» означает, что ans[k] = color[k] и эквивалентно color[k] = (k — sum(i!=k, color[i])) mod 100 => k = sum(color[i]) mod 100, что и выражается фразой «k-й мудрец будет прав тогда и только тогда, когда его номер равен сумме цветов по модулю 100».
Вы, конечно, правы. На самом деле мудрец должен называть свой номер минус сумму видимых цветов, естественно по модулю 100.
Тогда доказательство начинает соответствовать решению и всё становится хорошо :-)
Решил для двух мудрецов, подумал про разделение зон ответственности. Написал варианты для трёх, решил разделить ответственность по аналогии. Получилось. Ну а дальше всё просто, и решение сразу сформировалось, и доказательство придумалось.
Решение белым цветом (надеюсь, парсер не съет теги):
Перенумеруем мудрецов и шляпы от 0 до 99. Каждый мудрец считает сумму своего номера и номеров видимых ему шляп, берёт по модулю 100 и называет это число. Для произвольного количества мудрецов решение аналогично.
Доказательство: мудрец оказывается прав тогда и только тогда, когда его номер совпадает с остатком от деления суммы номеров шляп на 100. Следовательно, для любой суммы номеров цветов шляп найдётся ровно один мудрец, который не ошибся.
Забавно, что правильный цвет всегда называет ровно один мудрец, и это верно для любого решения головоломки.
1. Я-то как раз понимаю, что имеется в виду под N/2. А вот будет ли очевидна для тех, кому эта таблица может пригодиться, какая связь между «поиск за N», «поиск за N/2» и «вставка за N» и почему все три этих времени различаются? И почему тогда не учтена аналогичная поправка к логрифмам? Потому что посчитать сложнее?
2. Тогда чем поиск отличается от выбора? Вообще, обычно в таких таблицах рассматривается операция удаления.
3. Плохо поправили, не везде. Число ошибок всё равно превышает все разумные пределы. Откуда, например, логарифмы в хешировании и неупорядоченных массивах-списках?
4. Внимательно вглядитесь в вашу же таблицу — я говорил именно про «бинарный поиск», а не про BST.
1. Смысл в записях вида N/2 хоть и есть, но весьма небольшой — всё равно это лишь ассимптотические оценки, причём с неизвестной константой перед ними.
2. Догадаться о том, что скрывается под названиями струтур данных и операций иногда можно только по временной оценке :-) Но что такое выбор я так и не понял.
3. Ошибки: вместо NlnN должно быть lnN, но одним этим исправлением, боюсь, не отделаться.
4. Бинарный поиск и хэширование структурами данных не являются.
> If you receive a call while flying the quadricopter, the autopilot stabilizes it and lands after few seconds.
Так что летать над водоёмами и прочими неприятными для посадки поверхности не стоит.
Помимо сохранения инварианта важный элемент реализации — конечность времени работы. В вашем коде это гарантируется постоянным уменьшением интервала либо установкой флага found, но в самой статье об этом моменте практически ничего не сказано. А между тем на моей памяти большинство неправильных реализаций двоичного поиска именно зависали, а не выдавали неверный ответ.
Ну вы же говорите что вам буквы нужны довольно часто — а тут compose key очень кстати. Тех же, кому они нужны редко, и charmap устроит.
Хотя не исключаю что есть и группа пользователей, которым charmap уже неудобен, а compose настроить ещё лень :)
Про 3G не знаю.
Раз в минуту делает flush и больше ничего не умеет. Распространяется как есть, делайте с ним что хотите :-)
А ещё бывают дороги с односторонним движением… Нет, как ни крути — направление пробки показывать надо.
Утверждение «мудрец прав» означает, что ans[k] = color[k] и эквивалентно color[k] = (k — sum(i!=k, color[i])) mod 100 => k = sum(color[i]) mod 100, что и выражается фразой «k-й мудрец будет прав тогда и только тогда, когда его номер равен сумме цветов по модулю 100».
Тогда доказательство начинает соответствовать решению и всё становится хорошо :-)
Перенумеруем мудрецов и шляпы от 0 до 99. Каждый мудрец считает сумму своего номера и номеров видимых ему шляп, берёт по модулю 100 и называет это число. Для произвольного количества мудрецов решение аналогично.
Доказательство: мудрец оказывается прав тогда и только тогда, когда его номер совпадает с остатком от деления суммы номеров шляп на 100. Следовательно, для любой суммы номеров цветов шляп найдётся ровно один мудрец, который не ошибся.
Забавно, что правильный цвет всегда называет ровно один мудрец, и это верно для любого решения головоломки.
2. Тогда чем поиск отличается от выбора? Вообще, обычно в таких таблицах рассматривается операция удаления.
3. Плохо поправили, не везде. Число ошибок всё равно превышает все разумные пределы. Откуда, например, логарифмы в хешировании и неупорядоченных массивах-списках?
4. Внимательно вглядитесь в вашу же таблицу — я говорил именно про «бинарный поиск», а не про BST.
1. Смысл в записях вида N/2 хоть и есть, но весьма небольшой — всё равно это лишь ассимптотические оценки, причём с неизвестной константой перед ними.
2. Догадаться о том, что скрывается под названиями струтур данных и операций иногда можно только по временной оценке :-) Но что такое выбор я так и не понял.
3. Ошибки: вместо NlnN должно быть lnN, но одним этим исправлением, боюсь, не отделаться.
4. Бинарный поиск и хэширование структурами данных не являются.
Так что летать над водоёмами и прочими неприятными для посадки поверхности не стоит.
А вообще штука интересная.
Хотя не исключаю что есть и группа пользователей, которым charmap уже неудобен, а compose настроить ещё лень :)