Сортировка вагонов

@Pasha0005 · Регистрация: 01.02.2018

Студворк — интернет-сервис помощи студентам

Ограничение по времени работы программы: 1 секунда

К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик.

Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути 2 в сторону от тупика). Напишите программу, определяющую, можно ли это сделать.
Входные данные

Первая строка входных данных содержит число N
— количество вагонов в поезде (1⩽N⩽100). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до N
, каждое из которых встречается ровно один раз.
Выходные данные

Если сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите сообщение YES, если это сделать нельзя, выведите NO.

@Pasha0005 · 22.03.2018, 20:02 **[ТС]**

Помогите, пожалуйста

@ТабуретY · 22.03.2018, 20:24

Тут много чего не хватает, рисунка, примеров выходных данных

@Pasha0005 · 22.03.2018, 20:37 **[ТС]**

ок
ПРИМЕРЫ
ввод
3
3 2 1
вывод
YES
Надо весь поезд завезти в тупик, а затем целиком вывезти его на 2-й путь.
ввод
4
4 1 3 2
вывод
YES

Сначала надо в тупик завезти два вагона, один из которых оставит в тупике, а второй — вывезти на 2-й путь, после чего завезти в тупик еще два вагона и вывезти 3 вагона, стоящие в тупике, на 2-й путь
ввод
3
2 3 1
вывод
NO

Добавлено через 59 секунд
Рисунок не могу

Рыжий Лис · 23.03.2018, 05:24

Сообщение от Pasha0005

Рисунок не могу

Хотя бы скрин экрана с рисунком.

@TensaZangetsu · 29.05.2020, 13:45

Вот нужная картинка

@TensaZangetsu · 29.05.2020, 13:47

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
#include <iostream>
#include <stack>
#include <queue>
 
using namespace std;
 
stack<int> s;
queue<int> op;
 
int main() {
    int n;
    cin >> n;
 
    int num = 1;
    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        if (!s.empty() && val > s.top()) {
            cout << 0 << endl;
            return 0;
        }
        op.push(1);
        s.push(val);
        while (!s.empty() && s.top() == num) {
            op.push(2);
            s.pop();
            num++;
        }
    }
 
    int val = op.front();
    op.pop();
    int count = 1;
    while (!op.empty()) {
        if (op.front() == val) {
            count++;
        }
        else {
            cout << val << " " << count << endl;
            val = op.front();
            count = 1;
        }
        op.pop();
    }
    cout << val << " " << count << endl;
 
    return 0;
}

Решение похожей задачи на C++

Рыжий Лис · 29.05.2020, 13:47

Больше двух лет прошло, на что ты надеешься?

@TensaZangetsu · 29.05.2020, 13:50

Может кому пригодится

@Semen-Semenich · 29.05.2020, 17:18

Сообщение от TensaZangetsu

Может кому пригодится

мне бы пригодилось но на питоне а в с++ я и сам найду

@eaa · 29.05.2020, 17:43

обычный стек, что тут такого...
вроде недавно была такая задача, если я не ошибаюсь.

@Вия · 20.06.2020, 14:22

Помогите, пожалуйста, найти программу к этой задаче на питон.

Добавлено через 4 минуты
Ваша программа отлично работает! Спасибо! А на питоне можете помочь? Буду очень благодарна!

@zhurban · 20.06.2020, 15:07

Вия, работает как и тото код на С++

Python
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
s = []
op = []
n = int(input())
num = 1
for i in range(n):
    val = int(input())
    if len(s) > 0 and val > s[len(s) - 1]:
        print(0)
        quit(0)
    op.append(1)
    s.append(val)
    while len(s) > 0 and s[len(s) - 1] == num:
        op.append(2)
        s.pop()
        num += 1
val = op.pop(0)
count = 1
while len(op) > 0:
    if op[0] == val:
        count += 1
    else:
        print("{0} {1}".format(val, count))
        val = op[0]
        count = 1
    op.pop(0)
print("{0} {1}".format(val, count))

@Вия · 21.06.2020, 00:38

Программа выдаёт ошибку в процессе выполнения..

Добавлено через 31 минуту
zhurban, Программа выдаёт ошибку в процессе выполнения. Вы можете помочь?

@Yar3567 · 21.06.2020, 06:20

Python
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
s = []
op = []
n = int(input())
tr = list(map(int, input().split()))
num = 1
for val in tr:
    if len(s) > 0 and val > s[len(s) - 1]:
        print(0)
        quit(0)
    op.append(1)
    s.append(val)
    while len(s) > 0 and s[len(s) - 1] == num:
        op.append(2)
        s.pop()
        num += 1
val = op.pop(0)
count = 1
while len(op) > 0:
    if op[0] == val:
        count += 1
    else:
        print("{0} {1}".format(val, count))
        val = op[0]
        count = 1
    op.pop(0)
print("{0} {1}".format(val, count))

@Евгнений · 30.06.2020, 18:12

примерно тот же код, но без quit()

Python
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
s = []
op = []
n = int(input())
tr = list(map(int, input().split()))
num = 1
p=True
for val in tr:
    if len(s) > 0 and val > s[len(s) - 1]:
        print(0)
        p=False
        break
    op.append(1)
    s.append(val)
    while len(s) > 0 and s[len(s) - 1] == num:
        op.append(2)
        s.pop()
        num += 1
if p:
    val = op.pop(0)
    count = 1
    while len(op) > 0:
        if op[0] == val:
            count += 1
        else:
            print("{0} {1}".format(val, count))
            val = op[0]
            count = 1
        op.pop(0)
    print("{0} {1}".format(val, count))

@Вия · 30.06.2020, 22:56

Евгнений[/nick], благодарю Вас!

Добавлено через 1 минуту
Евгнений, благодарю Вас!

@Евгнений · 01.07.2020, 09:24

Вия, всегда пожалуйста

@MaMush · 01.05.2022, 15:42

Мне и щас помогло...

@Tim977 · 15.08.2022, 22:01

TensaZangetsu, Спасибо, хороший код

! Я немного переделал конкретно под заданную задачу

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
#include <iostream>
#include <stack>
#include <queue>
 
using namespace std;
 
stack<int> s;
queue<int> op;
 
int main() {
    int n;
    cin >> n;
    int num = 1;
    for (int i = 0; i < n; i++) {
        int val;
        cin >> val;
        if (!s.empty() && val > s.top()) {
            cout << "NO";
            return 0;
        }
        op.push(1);
        s.push(val);
        while (!s.empty() && s.top() == num) {
            op.push(2);
            s.pop();
            num++;
        }
    }
    int val = op.front();
    op.pop();
    int count = 1;
    cout << "YES";
    return 0;
}

(Я с Сириуса, Сириус принял, на информатикс не пробовал заливать, но тоже должен принять)

Новые блоги и статьи Все статьи Все блоги /
Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .
Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка. Hrethgir 08.04.2026 Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .	Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .

@Pasha0005 0 / 0 / 0 Регистрация: 01.02.2018 Сообщений: 46

	Сортировка вагонов 16.03.2018, 19:12. Показов 49041. Ответов 24 Метки нет (Все метки) Ограничение по времени работы программы: 1 секунда К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько вагонов и снова часть оказавшихся вагонов вывезти в сторону пути 2. И так далее (так, что каждый вагон может лишь один раз заехать с пути 1 в тупик, а затем один раз выехать из тупика на путь 2). Заезжать в тупик с пути 2 или выезжать из тупика на путь 1 запрещается. Нельзя с пути 1 попасть на путь 2, не заезжая в тупик. Известно, в каком порядке изначально идут вагоны поезда. Требуется с помощью указанных операций сделать так, чтобы вагоны поезда шли по порядку (сначала первый, потом второй и т.д., считая от головы поезда, едущего по пути 2 в сторону от тупика). Напишите программу, определяющую, можно ли это сделать. Входные данные Первая строка входных данных содержит число N — количество вагонов в поезде (1⩽N⩽100). Дальше идут номера вагонов в порядке от головы поезда, едущего по пути 1 в сторону тупика. Вагоны пронумерованы натуральными числами от 1 до N , каждое из которых встречается ровно один раз. Выходные данные Если сделать так, чтобы вагоны шли в порядке от 1 до N, считая от головы поезда, когда поезд поедет по пути 2 из тупика, можно, выведите сообщение YES, если это сделать нельзя, выведите NO. 0

@Pasha0005 0 / 0 / 0 Регистрация: 01.02.2018 Сообщений: 46
	22.03.2018, 20:02 [ТС]
	Помогите, пожалуйста 0

@ТабуретY 1741 / 913 / 480 Регистрация: 05.12.2013 Сообщений: 3,074
	22.03.2018, 20:24
	Тут много чего не хватает, рисунка, примеров выходных данных 0

@Pasha0005 0 / 0 / 0 Регистрация: 01.02.2018 Сообщений: 46
	22.03.2018, 20:37 [ТС]
	ок ПРИМЕРЫ ввод 3 3 2 1 вывод YES Надо весь поезд завезти в тупик, а затем целиком вывезти его на 2-й путь. ввод 4 4 1 3 2 вывод YES Сначала надо в тупик завезти два вагона, один из которых оставит в тупике, а второй — вывезти на 2-й путь, после чего завезти в тупик еще два вагона и вывезти 3 вагона, стоящие в тупике, на 2-й путь ввод 3 2 3 1 вывод NO Добавлено через 59 секунд Рисунок не могу 0

@TensaZangetsu 3 / 3 / 0 Регистрация: 29.05.2020 Сообщений: 11
	29.05.2020, 13:45
	Вот нужная картинка Миниатюры 0

Рыжий Лис Просто Лис 5973 / 3735 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	29.05.2020, 13:47
	Больше двух лет прошло, на что ты надеешься? 0

@TensaZangetsu 3 / 3 / 0 Регистрация: 29.05.2020 Сообщений: 11
	29.05.2020, 13:50
	Может кому пригодится 1

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	29.05.2020, 17:43
	обычный стек, что тут такого... вроде недавно была такая задача, если я не ошибаюсь. 0

@Вия 2 / 2 / 0 Регистрация: 28.05.2020 Сообщений: 40
	20.06.2020, 14:22
	Помогите, пожалуйста, найти программу к этой задаче на питон. Добавлено через 4 минуты Ваша программа отлично работает! Спасибо! А на питоне можете помочь? Буду очень благодарна! 0

@Вия 2 / 2 / 0 Регистрация: 28.05.2020 Сообщений: 40
	21.06.2020, 00:38
	Программа выдаёт ошибку в процессе выполнения.. Добавлено через 31 минуту zhurban, Программа выдаёт ошибку в процессе выполнения. Вы можете помочь? 0

@Вия 2 / 2 / 0 Регистрация: 28.05.2020 Сообщений: 40
	30.06.2020, 22:56
	Евгнений[/nick], благодарю Вас! Добавлено через 1 минуту Евгнений, благодарю Вас! 0

@Евгнений 11 / 15 / 1 Регистрация: 13.05.2020 Сообщений: 49
	01.07.2020, 09:24
	Вия, всегда пожалуйста 1

@MaMush 4 / 9 / 2 Регистрация: 05.10.2020 Сообщений: 51
	01.05.2022, 15:42
	Мне и щас помогло... 0