Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35
#1

Нужно сделать алгоритм, решающий задачу за время н - C++

01.09.2012, 13:45. Просмотров 502. Ответов 4
Метки нет (Все метки)

Всем привет!
Есть задача:
Исходные данные
В первой строке записано целое число N — количество бильярдных шаров (1 ≤ N ≤ 100000). В следующих N строках даны номера этих шаров в том порядке, в котором ревизор забирал их из лузы.
Результат
Выведите слово «Cheater», если закатывающий не мог закатить все N шаров в правильном порядке. Иначе выведите «Not a proof».

Реализовывал несколько алгоритмов. Первый работал за время O(n), но не всегда решал правильно. Второй алгоритм решает правильно, но за время O(n^2).
Привожу второй алгоритм.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include "stdafx.h"
#include <stdio.h>
bool SearchInViewed(int begin, int end, int *view, int j)
{
    if (begin - end > 10)
        end = begin - 10;
    for (int i = begin - 1; i > end; i--)
    {
        if (view[i] == 0)
            return false;
    }
    return true;
}
 
int main()
{
    int n, _prev;
    bool result = true;
    int viewed[100001] = {0};
    scanf("%d",&n);
    int number;
    scanf("%d", &number);
    _prev = number;
    for (int i = 0; i < n-1; i++)
    {
        scanf("%d", &number);
        if (result)
        {
            if ((_prev - number) > 1)
            {
                if (!SearchInViewed(_prev, number, viewed))
                {
                    result = false;
                }
            }
            viewed[_prev]++;
            _prev = number;
        }
    }
    (result) ? (printf("Not a proof\n")) : (printf("Cheater\n"));
    return 0;
}
Я конечно сократил время его выполнения, сделав условие в ф-ции
C++
1
2
    if (begin - end > 10)
        end = begin - 10;
Но такое условие неправильно. Т.к. тогда могут возникнуть ситуации, когда алгоритм неправильно решает.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.09.2012, 13:45
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Нужно сделать алгоритм, решающий задачу за время н (C++):

"Написать класс , решающий следующую задачу - C++
Здравствуйте подскажите нужно &quot;Написать класс , решающий следующую задачу : нахождение минимального и максимального элементов...

Нужно сделать данную задачу с матрицей в С++.Для знающих С++ - C++
Здравствуйте.Прошу помочь решить данную задачу.Я ещё учусь и потому многого не знаю.Пытаюсь решить такую задачу:Заполнить матрицу...

Нужно сделать по заданию задачу, выдает ошибку при компилировании - C++
Создать класс для работы сo строками. Разработать элементы класса: a. Поля: • * указатель на char - хранит адрес динамически выделенной...

Нужно сделать функцию расшифровки (алгоритм Цезаря) - C++
Всем привет ! Есть моя функция шифрования char find_and_encr_char(char what_find,int key){ char engl_abet=...

Нужно разобрать задачу - C++
#include &quot;stdafx.h&quot; #include &quot;chess.h&quot; using namespace std; horse targetHorse;// переменная, хранящая координаты цели - той точки,...

Нужно превести задачу с Delphi на С++ - C++
const n=10; type Segments=record a,b:Integer; end; var ArrayOfSegments:array of Segments; i,j,count,Point,MaxPos:Byte; ...

4
OhMyGodSoLong
~ Эврика! ~
1245 / 994 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
01.09.2012, 13:56 #2
Определите "правильность порядка", пожалуйста.
0
Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35
01.09.2012, 14:03  [ТС] #3
Приведу примеры.
42531 - в таком порядке доставались шары из лузы.
Порядок - это от 1 до н по порядку шары закатаны в лузу.
В примере выше такого быть не может. т.к. после 4 идет 2 - это означает, что 3 не закатана.
0
OhMyGodSoLong
~ Эврика! ~
1245 / 994 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
01.09.2012, 14:10 #4
Эм, то есть для данного N шары должны быть в лузе в виде (сверху вниз): N, N – 1, ..., 2, 1? Если да, то это просто: заведите переменную-счётчик, установите её значение в N, каждый считанный номер сравниваете с переменной, если равны, то уменьшаем счётчик на единицу и идём дальше; если нет, то шары идут в неправильной последовательности.

Или шары в смысле реально шары, а не что-то абстрактное: номера только от 1 до 15? Тогда по идее надо проверить последовательность на невозрастание. Храните в переменной номер последнего просмотренного шара, этот номер должен только убывать, но не возрастать. Если считанный номер шара больше, чем сохранённый в переменной, то сообщаем о жульничестве; если меньше или равен, то присваиваем только что считанный номер этой переменной и идём дальше. В самом начале дайте переменной значение, гарантированно большее номера шара (16, или там 1000), чтобы первая проверка сработала нормально. Если дошли до конца без эксцессов, то с последовательностью всё окей.
0
valeriikozlov
Эксперт С++
4681 / 2507 / 322
Регистрация: 18.08.2009
Сообщений: 4,550
01.09.2012, 18:36 #5
Roukff,
1. В следующий раз выкладывайте полное условие задачи. Телепатов здесь нет, что бы угадывать как мог ревизор забирал шары из лузы. Или давайте ссылку на эту задачу: http://acm.timus.ru/problem.aspx?space=1&num=1494
2. Вот реализация за O(n):
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
 
int main()
{
    #ifndef ONLINE_JUDGE
   freopen("input.txt", "rt", stdin);
   freopen("output.txt", "wt", stdout);
    #endif  
    int n, n_st=0; 
    int st[100000][2];
    scanf("%d",&n);
    int number;
    scanf("%d", &number);
    st[0][0]=st[0][1]=number;
    for (int i = 0; i < n-1; i++)
    {
        scanf("%d", &number);
        if(number==st[n_st][0]-1)
        {
            st[n_st][0]=number;
            if(n_st>0 && st[n_st][0]==st[n_st-1][1]+1)
            {
                st[n_st-1][1]=st[n_st][1];
                n_st--;        
            }   
        }
        else
        if(number==st[n_st][1]+1)
            st[n_st][1]=number;
        else
        {
            n_st++;
            st[n_st][0]=st[n_st][1]=number;         
        }   
    }
 
    (n_st==0 && st[0][0]==1 && st[0][1]==n) ? (printf("Not a proof\n")) : (printf("Cheater\n"));
    return 0;
}
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.09.2012, 18:36
Привет! Вот еще темы с ответами:

Нужно скорректировать задачу со структурами - C++
Я определила структуру «студент», поля структуры: ФИО, массив элементов структуры «дисциплина» (не менее 4-х элементов, результаты сдачи...

Нужно сдать задачу в одно действие - C++
Задача: Лиса Алиса и кот Базилио (Время: 1 сек. Память: 16 Мб Сложность: 22%) Лиса Алиса и кот Базилио вырастили денежное дерево....

пожалуйста нужно решить задачу на массивы по С!!! - C++
Дана целочисленная прямоугольная матрица. определить: 1) количество столбцов, содержащих хотябы один нудевой элемент 2)номер строки в...

Нужно исправить задачу вычисления суммы - C++
Вычислить сумму. s=1/(2+3)+2/(3+4)+..+10/(11+12) через цикл for Вот что получилось.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru