Не кинокритик. Не палеонтолог. (plakhov) wrote,
Не кинокритик. Не палеонтолог.
plakhov

Да, и задачки, конечно

1а) (широко известная) Есть очень большой файл, в котором лежит очень много (точнее, 2N+1) целых 64-битных чисел. Известно, что в нем N пар одинаковых чисел, и еще одно "непарное". Требуется найти это самое "непарное" число за O(N) времени и O(1) памяти. Естественно, числа в паре не обязательно идут подряд - иначе было бы слишком просто.

1б) То же самое, но чисел 2N+2, и непарными являются два из них. Требуется найти оба.

2) (из другой оперы) Есть шахматная доска 8х8, любая клетка которой может быть покрашены в черный или в белый цвет. Разрешается взять любой квадрат 3х3 или 4х4, и перекрасить каждую клетку внутри этого квадрата в противоположный цвет. Верно ли, что из любой начальной раскраски таким образом можно получить одноцветную доску?
Tags: math
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 37 comments