 Якобы для программистов. |
Рейтинг
 |
 |
Добро пожаловать, гость ( Вход | Регистрация )
Правила раздела
Публикующим:
1. Задачу можно опубликовать двумя способами:
- создав для нее отдельную тему с информативным названием;
- добавив задачу в готовый сборник (например «Бескрылки», «Мини-задачи», «Вопросы ЧГК») или создав свой (например, «Загадки от /для Светы»).
2. Если вы публикуете задачу, решение которой не знаете, напишите об этом. По умолчанию считается, что вам известен правильный ответ и вы готовы проверять других игроков.
Решающим:
1. В темах запрещается писать ответы и подсказки, если возможность открытого обсуждения не оговорена отдельно (в случае открытого обсуждения для текста следует использовать цвет фона или белый, оставляя другим игрокам возможность самостоятельного решения).
2. Правильность решения можно проверить, написав личное сообщение автору.
  |
| nik_vic |
 3.10.2012, 22:54
Сообщение
#1
|
|
Активный участник  Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125  |
Дан список А1....Аn целых неотрицательных чисел. Требуется найти первый его элемент такой, что A(k+m) не равен ни A(k)+A(m), ни A(k)+A(m)+1. За линейное время - по числу членов.
====== Здесь, конечно, не хватает кванторов. Исправляюсь. Для каких-то k, m. -------------------- Где это видано?
|
   |
 
|
| VitalyKolobkov |
4.10.2012, 2:13
Сообщение
#2
|
|
Участник Группа: Пользователи Braingames Сообщений: 244 Регистрация: 18.2.2011 Пользователь №: 23 171 |
QUOTE(nik_vic @ 3.10.2012, 23:54)  Дан список А1....Аn целых неотрицательных чисел. Требуется найти первый его элемент такой, что A(k+m) не равен ни A(k)+A(m), ни A(k)+A(m)+1. За линейное время - по числу членов. А вы уверены, что она решается за линейное время? |
|
|
|
| nik_vic |
4.10.2012, 10:05
Сообщение
#3
|
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
QUOTE(VitalyKolobkov @ 4.10.2012, 3:13) А вы уверены, что она решается за линейное время? Да. -------------------- Где это видано?
|
|
|
|
| Alexandroppolus |
9.10.2012, 21:29
Сообщение
#4
|
 Активный участник Группа: Модераторы BrainGames Сообщений: 973 Регистрация: 25.10.2009 Пользователь №: 17 196 |
Список реализован как массив? (т.е. значение A(i) можно узнать за время О(1) ?)
|
|
|
|
| nik_vic |
9.10.2012, 22:58
Сообщение
#5
|
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
QUOTE(Яростный Меч @ 9.10.2012, 22:29) Список реализован как массив? (т.е. значение A(i) можно узнать за время О(1) ?) Да, никаких финтов. -------------------- Где это видано?
|
|
|
|
| VitalyKolobkov |
10.10.2012, 1:28
Сообщение
#6
|
|
Участник Группа: Пользователи Braingames Сообщений: 244 Регистрация: 18.2.2011 Пользователь №: 23 171 |
Я только сейчас заметил, что надо определить, что A(k+m) НЕ равен ни A(k)+A(m), ни A(k)+A(m)+1.
|
|
|
|
| nik_vic |
10.10.2012, 12:10
Сообщение
#7
|
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
QUOTE(VitalyKolobkov @ 10.10.2012, 2:28) Я только сейчас заметил, что надо определить, что A(k+m) НЕ равен ни A(k)+A(m), ни A(k)+A(m)+1. Моя вина. B погоне за краткостью упустил необходимость кванторов для k,m. Т.е. требуется найти минимальное s такое, что для некоторых k,m, s=k+m ... - далее по тексту. -------------------- Где это видано?
|
|
|
|
| Alexandroppolus |
10.10.2012, 12:45
Сообщение
#8
|
|
Активный участник Группа: Модераторы BrainGames Сообщений: 973 Регистрация: 25.10.2009 Пользователь №: 17 196 |
напоминает задачу "Камни в урнах", вывернутую наизнанку
 |
|
|
|
| nik_vic |
10.10.2012, 12:55
Сообщение
#9
|
|
Активный участник Группа: Пользователи Braingames Сообщений: 753 Регистрация: 22.1.2008 Пользователь №: 6 125 |
QUOTE(Яростный Меч @ 10.10.2012, 13:45) напоминает задачу "Камни в урнах", вывернутую наизнанку Поэтому все решения - только в личку. -------------------- Где это видано?
|
|
|
|
|
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0 -
|
Упрощённая версия | Сейчас: 16.7.2025, 23:48 |
Invision Power Board
v2.1.4 © 2025 IPS, Inc.