1 / 1 / 1
Регистрация: 05.06.2011
Сообщений: 35
|
|||||||||||
1 | |||||||||||
Нужно сделать алгоритм, решающий задачу за время н01.09.2012, 13:45. Показов 1204. Ответов 4
Метки нет (Все метки)
Всем привет!
Есть задача: Исходные данные В первой строке записано целое число N — количество бильярдных шаров (1 ≤ N ≤ 100000). В следующих N строках даны номера этих шаров в том порядке, в котором ревизор забирал их из лузы. Результат Выведите слово «Cheater», если закатывающий не мог закатить все N шаров в правильном порядке. Иначе выведите «Not a proof». Реализовывал несколько алгоритмов. Первый работал за время O(n), но не всегда решал правильно. Второй алгоритм решает правильно, но за время O(n^2). Привожу второй алгоритм.
0
|
01.09.2012, 13:45 | |
Ответы с готовыми решениями:
4
"Написать класс , решающий следующую задачу Очень нужно сделать задачу на Visual C++ Нужно сделать задачу, а то я уже не знаю как симплекс-метод или любой другой решающий транспортную задачу |
~ Эврика! ~
1256 / 1005 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
|
|
01.09.2012, 13:56 | 2 |
Определите "правильность порядка", пожалуйста.
0
|
1 / 1 / 1
Регистрация: 05.06.2011
Сообщений: 35
|
|
01.09.2012, 14:03 [ТС] | 3 |
Приведу примеры.
42531 - в таком порядке доставались шары из лузы. Порядок - это от 1 до н по порядку шары закатаны в лузу. В примере выше такого быть не может. т.к. после 4 идет 2 - это означает, что 3 не закатана.
0
|
~ Эврика! ~
1256 / 1005 / 74
Регистрация: 24.07.2012
Сообщений: 2,002
|
|
01.09.2012, 14:10 | 4 |
Эм, то есть для данного N шары должны быть в лузе в виде (сверху вниз): N, N – 1, ..., 2, 1? Если да, то это просто: заведите переменную-счётчик, установите её значение в N, каждый считанный номер сравниваете с переменной, если равны, то уменьшаем счётчик на единицу и идём дальше; если нет, то шары идут в неправильной последовательности.
Или шары в смысле реально шары, а не что-то абстрактное: номера только от 1 до 15? Тогда по идее надо проверить последовательность на невозрастание. Храните в переменной номер последнего просмотренного шара, этот номер должен только убывать, но не возрастать. Если считанный номер шара больше, чем сохранённый в переменной, то сообщаем о жульничестве; если меньше или равен, то присваиваем только что считанный номер этой переменной и идём дальше. В самом начале дайте переменной значение, гарантированно большее номера шара (16, или там 1000), чтобы первая проверка сработала нормально. Если дошли до конца без эксцессов, то с последовательностью всё окей.
0
|
4727 / 2548 / 757
Регистрация: 18.08.2009
Сообщений: 4,568
|
||||||
01.09.2012, 18:36 | 5 | |||||
Roukff,
1. В следующий раз выкладывайте полное условие задачи. Телепатов здесь нет, что бы угадывать как мог ревизор забирал шары из лузы. Или давайте ссылку на эту задачу: http://acm.timus.ru/problem.aspx?space=1&num=1494 2. Вот реализация за O(n):
1
|
01.09.2012, 18:36 | |
01.09.2012, 18:36 | |
Помогаю со студенческими работами здесь
5
Есть ли алгоритм решающий следующее задание? нужно сделать задачу Нужно сделать задачу с рандомом Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |