Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
nakazkan
0 / 0 / 0
Регистрация: 30.01.2019
Сообщений: 1
1

Задача на sqrt-декомпозицию

30.01.2019, 22:17. Просмотров 426. Ответов 0

Помогите пжста найти косяк в программе .Задача с КФ на ДО,но надо решить с помощью sqrt decomposi'ции.
Вот задача :
На мат-мехе, в аудитории 00 стоит бесконечное количество парт, расставленных в ряд и пронумерованных натуральными числами. Сегодня в этой аудитории проходит экзамен по Линейному Анализу Жутких Уравнений. Время от времени приходят студенты. Каждый студент знает, за какую парту он хочет сесть, но на экзамене нельзя двум студентам сидеть вместе, поэтому, если парта занята, он занимает первую свободную парту с большим номером (подальше от преподавателя).

Кроме того, некоторые студенты не сдают экзамен и уходят. После этого за парту, которую занимал ушедший студент, может сесть вновь прибывший.

Преподаватель знает, когда будут приходить студенты, и когда они будут уходить учить заново. Вам требуется по этой информации узнать, за какой партой будет сидеть каждый из студентов (чтобы заранее положить туда конспект).

Формат входного файла

Первая строка входного файла содержит натуральное число n — количество событий, происходящих в течение экзамена (n <= 100 000).

Следующие n строк содержат информацию об этих событиях. Число a > 0 обозначает, что пришёл студент, желающий занять парту номер a (а <= 100 000). Число a < 0 обозначает, что студент освободил парту с номером —а. (Гарантируется, что он за ней действительно сидел).

ввод:6 5 5 5 -6 5 5

вывод: 5 6 7 6 8

КОД:
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#pragma warning (disable:4996)
 
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
#pragma warning (disable:4996)
 
 
int main()
{
 
    freopen("exam.in", "r", stdin);
    freopen("exam.out", "w", stdout);
 
    int n, m,a,in,c,flag=0;
    int raz = 317;
    vector<int>sq(raz);
 
    
    cin >> n ;
    vector<int>g(100000);
    for (int j = 0; j < n; j++) {
        cin >> a;
        
        if (a > 0) {
a--;
in = a / raz;
 
            for (int p = in; p < raz; p++) 
            {
                if (sq[p] < 317){
                    for (int i = p * raz; i < (p + 1)*raz; i++) {
                        if (g[i] == 0&&i>=a) {
                            g[i] = 1;
                            sq[p]++;
                            flag = 1;
                            c = i;
                            break;
                        }
                    }
                }
                if (flag == 1) {
                    flag = 0;
                    break;
 
                }
                
            }
            cout << c+1 << endl;
        }
        else {
            a++;
            a = a * (-1);
            g[a] = 0;
            in = a / raz;
            sq[in]--;
        }
    }
    return 0;
}
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.01.2019, 22:17
Ответы с готовыми решениями:

Цикл: Для числа N вычислить значение следующего выражения: sqrt((1) + sqrt((2) + ... + sqrt(2 * N)))
Как это решить? sqrt((1)+sqrt((2)+..+sqrt(2n)))

Вычислить значение выражения sqrt (2 + sqrt (2 + sqrt (2 ... sqrt2))), (n-слагаемых)
Вычислить значение выражения sqrt (2 + sqrt (2 + sqrt (2 ... sqrt2))), (n-слагаемых),с помощью...

Рекурсия: вычислить значение выражения sqrt(1+sqrt(2+...sqrt(n)))
Вычислить с помощью рекурсии и без нее - y(n) = sqrt(1+sqrt(2+...sqrt(n).. Как выполнить задание с...

Дано натуральное число n. Вычислить sqrt(2+ sqrt(5 + sqrt(7...))
Дано натуральное число n.Вычислить sqrt(2+ sqrt(5 + sqrt(7...)). Под корнями располагается n первых...

Вычислить значение выражения: Sqrt(x+sqrt(x+.sqrt(x) на с++
Для данного натурального N и вещественного x(x&gt;0) вычислить значение выражения:...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.01.2019, 22:17

Рекурсия: вычисление sqrt(1 + sqrt(2 + ... + sqrt(n)))
Не подскажите как расписать рекурсивно формулу? Спасибо!

[C++ Error] Sqrt x.cpp(16): E2268 Call to undefined function 'sqrt'. Что это за ошибка???
Когда я испльзую функцию sqrt() компилятор выводит: Sqrt x.cpp(16): E2268 Call to undefined...

Вычислить y=sqrt(1+sqrt(4+sqrt(9+.+sqrt(36+sqrt(49)
Помогите пожалуйста с решением данной задачи. \sqrt{1+\sqrt{4+\sqrt{9+...+\sqrt{36+\sqrt{49}}}}}...


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

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

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