Категории задач
Программистам
|
Программистам
РЕЙТИНГ
ВКЛАД В САЙТ
Ошибка? Замечание? Предложение?
PHP программистам, иллюстраторам, дизайнерам - работа, рекламистам - реклама, преподавателям - тесты, рекрутинговым агентствам и менеджерам по персоналу - кандидаты, блогерам и журналистам - контент, выделенному серверу - сайт.
|
Программистам
Написание алгоритмов на разных языках программирования.
 |
Роботы
На бесконечной в обе стороны белой полоске размеченной в клеточку находятся два робота. Ровно одна из клеток на полоске - чёрная, и она находится между роботами.
Вам необходимо одинаково запрограммировать обоих роботов так, чтоб они встретились.
Программа состоит из нескольких строк, каждая из которых содержит ровно одну команду. Допустимые команды:
1) ML - сделать шаг на клетку влево и перейти к следующей строке программы;
2) MR - сделать шаг на клетку вправо и перейти к следующей строке программы;
3) IF FLAG - проверить, находимся ли мы на чёрной клетке. Если да, перейти к следующей строке программы, иначе, перейти к послеследующей строке программы;
4) GOTO N - перейти к N-й строке программы;
На выполнение каждой из команд, кроме GOTO у робота уходит 1 секунда. GOTO выполняется мгновенно.
зарегистрироваться и проверить ответ
Показать примечания к условию
Комментарии: 47
Примечания к условию задачи:
1) Расстояние между роботами и точное положение чёрной клетки вам не известны;
2) Роботы стартуют одновременно;
3) Встретиться, значит после выполнения очередной команды оказаться на одной клетке;
4) Роботы могут беспрепятственно проходить друг сквозь друга;
5) Текст программы конечен;
6) Можно считать, что в конец программы автоматически добавляется команда GOTO 1;
7) Естественно, программа должна быть валидной. Например, если в программе 10 строк, то нельзя использовать команду GOTO 20. Также не должно быть бесконечных "пустых" циклов. Например, такая программа не валидная:
1. MR
2. GOTO 3
3. GOTO 2
4. ...
|
Шифровка в центр
Мегамозг должен послать важное сообщение в центр, состоящее из 4 бит информации. К сожалению, линии связи ненадежны и любой бит информации (но только один) может испортиться. Зато общий размер передачи в центр составляет 7 бит. Как должен Мегамозг закодировать информацию, чтобы в центре гарантированно смогли прочитать сообщение при возможном искажении любого одного бита?
зарегистрироваться и проверить ответ
Комментарии: 100
Примечания к условию задачи:
|
Замена строк
Мегамозгу в очень длинном тексте требуется заменить все буквы «А» на буквы «Б», а все буквы «Б» - на буквы «А». Текстовый редактор позволяет заменить во всём тексте один произвольный набор символов на другой. Например, в результате замены «АА» → «БСАА» строка «АААААЛ» перейдёт в строку «БСААБСАААЛ». Как ему выполнить задачу?
зарегистрироваться и проверить ответ
Показать примечания к условию
Комментарии: 116
Примечания к условию задачи:Вы не знаете символов, используемых в тексте, но любая последовательность символов (даже на первый взгляд не несущая смысла, например, «%:ы)*№»), которую вы используете в заменах, теоретически может встретиться в и тексте.
В условии об этом прямо не сказано, но я так понимаю, что все остальные символы, кроме А и Б, должны остаться неизменными. Это так?
Да.
Что значит "очень длинный текст"?
1. Вручную все замены сделать невозможно.
2. Любая данная последовательность символов может в нем встретиться.
3. Мегамозг не может использовать для замены последовательности, длина которых сравнима с длиной текста.
Есть ли в арсенале текстового редактора символ, отсутствующий в тексте?
Нет.
Можно ли несколько раз производить изменения по всему тексту?
Да.
Можно ли пропускать некоторые последовательности? Например, при замене "АА"->"БСАА" строка "AAAAAЛ" перейдет в строку "БСАААААЛ" (то есть 2ую последовательность пропустили).
Нет.
Можно ли при замене пользоваться регулярными выражениями (либо их аналогами)?
Нет.
|
Сортировка восьми чисел
Есть восемь последовательно записанных чисел, которые вы не видите. Можно попросить друга упорядочить любые два из них, указав их индексы. Например, если вы попросили упорядочить второе и пятое числа, то ваш друг во второе число поместит минимум из этих двух чисел, а в пятое — максимум (при этом не известив вас, сделаны какие-либо изменения или нет). За какое минимальное число просьб вы сможете гарантированно упорядочить все числа? Обоснование минимальности не требуется.
зарегистрироваться и проверить ответ
Комментарии: 16
Примечания к условию задачи:
|
Поток чисел
I. Дан достаточно большой входной поток целых чисел, в котором все числа встречаются ровно 2 раза, кроме одного, которое входит только 1 раз. Нужно за конечное число проходов O(1) потока (массива) и используя дополнительной памяти не более O(1) найти его.
II. То же, что в первом случае, только ровно 2 числа встречаются 1 раз.
зарегистрироваться и проверить ответ
Комментарии: 78
Примечания к условию задачи:
|
Степень двойки
Дано целое число больше 0. Определить, является ли оно целой степенью 2, не используя циклов, рекурсий и операций с плавающей точкой.
зарегистрироваться и проверить ответ
Комментарии: 61
Примечания к условию задачи:
|
Проверка базовых знаний цикла for
Дан текст программы на языке С. Требуется найти три способа изменить в нем один символ так, чтобы программа стала печатать 20 звездочек. Изменить — это значит не добавить, не убрать и не переставить, а именно поменять.
main() {
int i, N=20;
for (i = 0 ; i < N ; i--) {
printf("*");
}
}
зарегистрироваться и проверить ответ
Показать примечания к условию
Комментарии: 81
Примечания к условию задачи:Если у вас нет компилятора или вам лень его запускать, то вы можете проверить работоспособность своего кода здесь.
Не забудьте выбрать компилятор C.
|
Обмен значениями
Как поменять местами значения двух числовых переменных без использования дополнительных переменных и/или памяти? В используемом языке нет оператора обмена значениями (вроде XCHG ассемблера).
зарегистрироваться и проверить ответ
Комментарии: 33
Примечания к условию задачи:
|
Быстрая структура
Некая структура хранит массив данных длиной N. У нее есть 3 метода работы с данными:
get(index) возвращает элемент по индексу,
set(Element, index) устанавливает значение по заданному индексу и
setAll(Element) устанавливает данное значение для всех элементов.
Надо написать эти три функции так, чтобы каждая из них работала за O(1). Выделение нового массива, заполнение массива через функции типа memset и т. п. работает за O(N). Можно использовать любые дополнительные переменные/массивы в самой структуре.
зарегистрироваться и проверить ответ
Комментарии: 45
Примечания к условию задачи:
|
|
Новые сообщения
Реклама
|