Форум программистов, компьютерный форум CyberForum.ru

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

Восстановить пароль Регистрация
 
Roukff
 Аватар для Roukff
1 / 1 / 0
Регистрация: 05.06.2011
Сообщений: 35
01.09.2012, 13:45     Нужно сделать алгоритм, решающий задачу за время н #1
Всем привет!
Есть задача:
Исходные данные
В первой строке записано целое число 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;
Но такое условие неправильно. Т.к. тогда могут возникнуть ситуации, когда алгоритм неправильно решает.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.09.2012, 13:45     Нужно сделать алгоритм, решающий задачу за время н
Посмотрите здесь:

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

Или шары в смысле реально шары, а не что-то абстрактное: номера только от 1 до 15? Тогда по идее надо проверить последовательность на невозрастание. Храните в переменной номер последнего просмотренного шара, этот номер должен только убывать, но не возрастать. Если считанный номер шара больше, чем сохранённый в переменной, то сообщаем о жульничестве; если меньше или равен, то присваиваем только что считанный номер этой переменной и идём дальше. В самом начале дайте переменной значение, гарантированно большее номера шара (16, или там 1000), чтобы первая проверка сработала нормально. Если дошли до конца без эксцессов, то с последовательностью всё окей.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 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;
}
Yandex
Объявления
01.09.2012, 18:36     Нужно сделать алгоритм, решающий задачу за время н
Ответ Создать тему
Опции темы

Текущее время: 17:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru