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

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

Войти
Регистрация
Восстановить пароль
 
Temirlan90
132 / 132 / 8
Регистрация: 30.09.2010
Сообщений: 333
#1

Последовательность - 2 - C++

17.05.2011, 14:45. Просмотров 728. Ответов 12
Метки нет (Все метки)

Последовательность - 2
(Время: 1 сек. Память: 16 Мб)

Вася написал на доске n целых чисел ai и ушел. Пришел Петя и, увидев Васину последовательность, решил ее немного изменить. Для этого он решил, что может стирать с доски лишь те числа, у которых имеются слева и справа элементы, превосходящие их. Формально, Петя может стереть число ak, если существуют значения ai и aj такие, что ai > ak и aj > ak и i < k < j. Когда на доске не осталось чисел, которые мог стереть Петя, он ушел.

Пришел Вася и очень удивился увиденному. Напишите программу, которая выводит последовательность, которую увидел Вася.
Входные данные

Первая строка входного файла INPUT.TXT содержит целое число n (1 ≤ n ≤ 10000) - количество чисел. Следующая строка содержит n разделенных пробелом целых чисел ai (-1000000 ≤ ai ≤ 1000000) - записанные на доске числа.
Выходные данные

В первой строке выходного файла OUTPUT.TXT выведите целое число k - количество оставшихся на доске чисел. На следующей строке выведите k чисел bi - оставшиеся на доске числа.
Пример
INPUT.TXT
12
1 2 3 2 4 1 3 4 2 3 2 1
OUTPUT.TXT
8
1 2 3 4 4 3 2 1
не понимаю почему 1 и 2 остаются...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.05.2011, 14:45
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Последовательность - 2 (C++):

Задана последовательность слов. Определить частоту вхождения каждого слова в последовательность. - C++
Доделать программу, чтобы работала как надо Задана последовательность слов. Определить частоту вхождения каждого слова в...

Вводится последовательность из N вещественных чисел. Определить, является ли последовательность знакочередующе - C++
Вводится последовательность из N вещественных чисел. Определить, является ли последовательность знакочередующейся. не пойму как сделать,...

Массив: Вставить в последовательность действительное число b так, чтобы последовательность осталась неубывающей. - C++
дана последовательность действительных чисел. вставить в нее действительное число b так, чтобы последовательность осталась неубывающей. ...

Если последовательность отсортирована по возрастанию, оставить ее без изменения. Иначе получить иную последовательность - C++
Дана последовательность действительных чисел X1,X2,X3,…,Xn (n&gt;2, заранее неизвестно). Если последовательность отсортирована по возрастанию,...

Дана последовательность, элементы которой есть целые двузначные числа. Упорядочить последовательность по убыванию произведений цифр - C++
Здравствуйте. На форуме есть код подобный, но по возрастанию сумм элементов. Как мне подправить код, чтобы было &quot;по убыванию произведений...

Вводится последовательность из N целых чисел. Сформировать последовательность, - C++
Вводится последовательность из N целых чисел. Сформировать последовательность, каждый элемент которой равен сумме цифр исходной...

12
while(i)k++
48 / 48 / 5
Регистрация: 13.08.2010
Сообщений: 160
17.05.2011, 14:52 #2
1 2 3 (2) 4 (1) 3 4 (2) 3 2 1 = 1 2 3 4 (3) 4 3 2 1 = 1 2 3 4 4 3 2 1

все правильно, чо им исчезать один из их сосодей либо меньше, либо одного соседа нет, что тоже не позволяет им быть стертыми
0
Temirlan90
132 / 132 / 8
Регистрация: 30.09.2010
Сообщений: 333
17.05.2011, 14:58  [ТС] #3
какой там код? )))
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.05.2011, 15:00 #4
Вообще где вы нашли такую задачу...
Но в общем-то она простая, вроде бы обычным перебором решить можно... Либо ДП(не уверен, что несколько проходов по последовательности размером в 10к уложатся в одну секунду)
В примере все просто вроде как
Тупо ходить циклом и стирать, пока не останется элементов, у которых по краям стоят большие числа
Если использовать векторы, то можно в принципе за 1 цикл все нужное сделать.
0
Temirlan90
132 / 132 / 8
Регистрация: 30.09.2010
Сообщений: 333
17.05.2011, 15:03  [ТС] #5
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
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    int n, arr[10001], arr1[10001] = {}, a = 0;
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> arr[i];
    }   
    for(int i = 1; i < n - 1; ++i) {            
        if(arr[i] > arr[i + 1] && arr[i] > arr[i - 1]) {
            arr1[a] = arr[i];
            a++;
        }
 
    }       
    for(int i = 0; i < n; ++i) {
        if(arr1[i] != 0)
            cout << arr1[i];
    }
    //system("pause >> void");
    return 0;
}
там вывод 3443 Я хз как дальше
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.05.2011, 15:19 #6
У меня как-то так получилось, ответ с аутпутом совпадает

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <vector>
int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    int N,b;
    std::cin >> N;
    std::vector<int> a;
    for (int i = 0; i < N; i++){
        std::cin >> b;
        a.push_back(b);
        if (a.size()>2)
            if ( a.back()>a[a.size()-2]&&a[a.size()-2]<a[a.size()-3])
                            a.erase(a.end()-2);
    }
    std::cout << a.size() << '\n';
    for (int i=0; i< a.size();i++)
        std::cout << a[i] << ' ';
    return 0;
}
1
Temirlan90
132 / 132 / 8
Регистрация: 30.09.2010
Сообщений: 333
17.05.2011, 15:26  [ТС] #7
5 тест не проходит
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.05.2011, 15:38 #8
Что-то не могу подобрать тест, который проваливает моя прога...
Какая ошибка то хоть, TLE, RE или WA
З.Ы. из чистого любопытства-вы настолько суровы, что соло решаете командную олимпиаду?)
0
Temirlan90
132 / 132 / 8
Регистрация: 30.09.2010
Сообщений: 333
17.05.2011, 15:39  [ТС] #9
З.Ы. из чистого любопытства-вы настолько суровы, что соло решаете командную олимпиаду?)
Нет нас таких идиотов двое!!))) второй уже спит))))) 2 решили, и 2 проваливаем))))))) вторая про охотника
0
diagon
Higher
1930 / 1196 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.05.2011, 16:04 #10
Единственный тест, который я нашел, и который проваливала моя прога исправил

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <vector>
int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    size_t N,b;
    std::cin >> N;
    std::vector<int> a;
    for (;;){
        std::cin >> b;
        a.push_back(b);
        b=a.size();
        if (a.size()==b) break;
        if (a.size()>2)
            if ( a.back()>a[a.size()-2]&&a[a.size()-2]<a[a.size()-3])a.erase(a.end()-2);
        b=a.size();
        if (a.size()==b) break;
    }
    std::cout << a.size() << '\n';
    for (int i=0; i< a.size();i++)
        std::cout << a[i] << ' ';
    return 0;
}
Но это все-же вряд ли, такое возможно только если цифр в инпуте больше, чем N
Хотя нет, не исправил, наоборот прогу угробил-_-

Не по теме:

Я раньше думал, что на командных олимпиадах давят задачами вроде вычисления длинного корня из дробного числа... А там тупо количеством

1
Temirlan90
17.05.2011, 17:31  [ТС]
  #11

Не по теме:

НУ короче Мы решили 6 из 8 задач, в принципе зашибись)))))

0
easybudda
Модератор
Эксперт CЭксперт С++
9680 / 5630 / 954
Регистрация: 25.07.2009
Сообщений: 10,808
17.05.2011, 17:59 #12
Образец высокого быдлокода
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <stdio.h>
#include <stdlib.h>
 
int read_array(int * arr, size_t size, FILE * f){
    return ( ! size ) ? 0 : ( fscanf(f, "%d", arr) == 1 ) ? read_array(arr + 1, size - 1, f) : -1;
}
 
int write_array(int * arr, size_t size, FILE * f){
    return ( ! size ) ? 0 : ( fprintf(f, "%d ", *arr) > 0 ) ? write_array(arr + 1, size - 1, f) : -1;
}
 
size_t smart_copy(int * dst, const int * src, size_t size){
    size_t ret = 0;
    
    if ( ! dst || ! src || ! size )
        return 0;
    
    dst[ret++] = *src++;
    while ( --size > 1 ){
        if ( *src >= dst[ret - 1] || *src >= *(src + 1) )
            dst[ret++] = *src;
        ++src;
    }
    if ( size )
        dst[ret++] = *src;
    
    return ret;
}
 
#define IN_FILE "input.txt"
#define OUT_FILE "output.txt"
 
int main(void){
    FILE * f;
    size_t inSize, outSize;
    int * buf;
    
    if ( ( f = fopen(IN_FILE, "r") ) == NULL ){
        fprintf(stderr, "Can't open file %s for input!\n", IN_FILE);
        exit(1);
    }
    if ( fscanf(f, "%u", &inSize) != 1 ){
        fprintf(stderr, "Can't read from input file!\n");
        exit(1);
    }
    if ( ( buf = malloc(sizeof(int) * inSize * 2) ) == NULL ){
        fprintf(stderr, "Memory error!\n");
        exit(1);
    }
    if ( read_array(buf, inSize, f) ){
        fprintf(stderr, "Error while reading from input file!\n");
        exit(1);
    }
    if ( ( outSize = smart_copy(buf + inSize, buf, inSize) ) == 0 ){
        fprintf(stderr, "Can't copy values!\n");
        exit(1);
    }
    if ( fclose(f) ){
        fprintf(stderr, "Can't close input file!\n");
        exit(1);
    }
    
    if ( ( f = fopen(OUT_FILE, "w") ) == NULL ){
        fprintf(stderr, "Can't open file %s for output!\n", OUT_FILE);
        exit(1);
    }
    if ( fprintf(f, "%u\n", outSize) < 0 ){
        fprintf(stderr, "Can't write to output file!\n");
        exit(1);
    }
    if ( write_array(buf + inSize, outSize, f) ){
        fprintf(stderr, "Error while writing to output file!\n");
        exit(1);
    }
    if ( fclose(f) ){
        fprintf(stderr, "Can't close output file!\n");
        exit(1);
    }
    
    free(buf);
    fprintf(stderr, "Done.\n");
    exit(0);
}
2
diagon
17.05.2011, 18:14     Последовательность - 2
  #13

Не по теме:

Пришел Вася и очень удивился увиденному
Я бы тоже очень удивился, если бы на доске было написано
Код
Memory error!

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.05.2011, 18:14
Привет! Вот еще темы с ответами:

Вводить последовательность вещественных чисел, пока следующее вводимое число не окажется меньше предыдущего. Вывести полученую последовательность. - C++
Вводить последовательность вещественных чисел, пока следующее вводимое число не окажется меньше предыдущего. Вывести полученую...

Вводится последовательность целых чисел,0 –конец последовательности. Определить, содержит ли последовательность хотя бы три отрицательных четных числа - C++
Составить алгоритм решения задачи и написать программу на языке С++. В алгоритме и программе массивов не использовать. ...

Преобразовать литерную последовательность в другую литерную последовательность всеми описанными ниже способами - C++
Здравствуйте, уже несколько дней мучаюсь над такой задачей : &quot;Имеется литерная последовательность, состоящая из не более чем 30 ...

Последовательность - C++
Нужна помощь в решении вот такой задачки : &quot; Сортирование последовательности элементов следующим образом : ищем максимальный элемент...


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

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

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