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

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

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

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

17.05.2011, 14:45. Просмотров 716. Ответов 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 остаются...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.05.2011, 14:45     Последовательность - 2
Посмотрите здесь:

Реализовать последовательность «галопирующая последовательность» К1816ВЕ51 - Микроконтроллеры
Добрый день в программе keil uvision 4 Организовать подсистему внешних прерываний в системе на базе К1816ВЕ51. Количество источников...

Дана последовательность А1...А50. Получить новую последовательность, исключив отрицательные элементы - Pascal
Дана последовательность А1...А50. Получить новую последовательность, исключив отрицательные элементы

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

Задана последовательность N вещественных чисел. Отсортировать последовательность по убыванию методом выбор - Pascal ABC
И снова прошу помощи написать код. Задана последовательность N вещественных чисел. Отсортировать последовательность по убыванию...

2. Дана целочисленная последовательность. Определить количество вхождений каждого числа в последовательность - Pascal
Написал программу var a,c:array of integer; count,i,p,u: integer; begin for i:=1 to 10 do begin read(p); a:=p; end;

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

Считать последовательность цифр и преобразовать ее в последовательность соответствующих латинских букв - Turbo Pascal
Все что сам смог написать в Паскале Program lit; Var A,N:char; Begin A:=chr(70); N:=A; writeln(ord(N)); Writeln(A); End.

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
while(i)k++
48 / 48 / 5
Регистрация: 13.08.2010
Сообщений: 160
17.05.2011, 14:52     Последовательность - 2 #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

все правильно, чо им исчезать один из их сосодей либо меньше, либо одного соседа нет, что тоже не позволяет им быть стертыми
Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
17.05.2011, 14:58  [ТС]     Последовательность - 2 #3
какой там код? )))
diagon
Higher
1927 / 1193 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.05.2011, 15:00     Последовательность - 2 #4
Вообще где вы нашли такую задачу...
Но в общем-то она простая, вроде бы обычным перебором решить можно... Либо ДП(не уверен, что несколько проходов по последовательности размером в 10к уложатся в одну секунду)
В примере все просто вроде как
Тупо ходить циклом и стирать, пока не останется элементов, у которых по краям стоят большие числа
Если использовать векторы, то можно в принципе за 1 цикл все нужное сделать.
Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
17.05.2011, 15:03  [ТС]     Последовательность - 2 #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 Я хз как дальше
diagon
Higher
1927 / 1193 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.05.2011, 15:19     Последовательность - 2 #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;
}
Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
17.05.2011, 15:26  [ТС]     Последовательность - 2 #7
5 тест не проходит
diagon
Higher
1927 / 1193 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.05.2011, 15:38     Последовательность - 2 #8
Что-то не могу подобрать тест, который проваливает моя прога...
Какая ошибка то хоть, TLE, RE или WA
З.Ы. из чистого любопытства-вы настолько суровы, что соло решаете командную олимпиаду?)
Temirlan90
131 / 131 / 8
Регистрация: 30.09.2010
Сообщений: 333
17.05.2011, 15:39  [ТС]     Последовательность - 2 #9
З.Ы. из чистого любопытства-вы настолько суровы, что соло решаете командную олимпиаду?)
Нет нас таких идиотов двое!!))) второй уже спит))))) 2 решили, и 2 проваливаем))))))) вторая про охотника
diagon
Higher
1927 / 1193 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.05.2011, 16:04     Последовательность - 2 #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
Хотя нет, не исправил, наоборот прогу угробил-_-

Не по теме:

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

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

Не по теме:

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

easybudda
Эксперт С++
9456 / 5469 / 927
Регистрация: 25.07.2009
Сообщений: 10,495
17.05.2011, 17:59     Последовательность - 2 #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);
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.05.2011, 18:14     Последовательность - 2
Еще ссылки по теме:

Считать последовательность цифр и преобразовать ее в последовательность соответствующих латинских букв - Pascal ABC
нужно чтобы 1-A 2-B 3-C 4-D и так до 26 латинских букв.

Если последовательность упорядочена по неубыванию, то оставить ее без изменения, иначе получить последовательность an, an-1, ... , a1 - C (СИ)
Здравствуйте! Помогите пожалуйста переделать программу под язык Си с Паскаля! Дана последовательность действительных чисел a1, a2, ......

дана последовательность вещественных чисел а1,а2,.а15 Определить являеться ли последовательность упорядоченной по возрастанию - Pascal
дана последовательность вещественных чисел а1,а2,...а15 Определить являеться ли последовательность упорядоченной по возрастанию. В случае...

Проверить возрастает/убывает последовательность чисел и вывести начала/конец и саму последовательность - Pascal ABC
Условие в коментариях кода. Суть я понимаю, набросок кода сделал, но вот как сделать, чтобы определялось все нормально, а не так криво ,...

Задана последовательность из N чисел. Найти самую длинную последовательность, обладающую данным свойством - Turbo Pascal
Прошу помощи мастеров решить ОДНУ задачкУ: 1) Задана последовательность из N чисел. Найти самую длинную последовательность, обладающую...


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

Или воспользуйтесь поиском по форуму:
diagon
17.05.2011, 18:14     Последовательность - 2
  #13

Не по теме:

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

Yandex
Объявления
17.05.2011, 18:14     Последовательность - 2
Ответ Создать тему
Опции темы

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