КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Формат входных данных
В единственной строке записана скобочная последовательность.
Формат выходных данных
Если данная последовательность правильная, то программа должна вывести строку yes, иначе строку no.
Пример
| Входные данные | Выходные данные |
| ([{}]) | Yes |
| ([)] | No |
| ()() | Yes |
| ())( | No |
4) В постфиксной записи (или обратной польской записи) операция записывается после двух операндов. Например, сумма двух чисел A и B записывается как AB +. Запись BC + D *обозначает привычое нам (B + C) * D, а запись ABC + D * + означает A + (B + C) * D. Достоинство постфиксной записи в том, что она не требует скобок и дополнительных соглашений о приоритете операторов для своего чтения.
Формат входных данных
В единственной строке записано выражение в постфиксной записи, содержащее однозначные числа и операции +, -, *.
Формат выходных данных
Необходимо вывести значение записанного выражения.
Пример
| Входные данные | Выходные данные |
| 8 9 + 1 7 - * | -102 |
5) На складе хранятся контейнеры с товарами N различных видов. Все контейнеры составлены в N стопок. В каждой стопке могут находиться контейнеры с товарами любых видов (стопка может быть изначально пустой).
Автопогрузчик может взять верхний контейнер из любой стопки и поставить его сверху в любую стопку. Необходимо расставить все контейнеры с товаром первого вида в первую стопку, второго вида – во вторую стопку и т.д.
Программа должна вывести последовательность действий автопогрузчика или сообщение о том, что задача решения не имеет.
Формат входных данных
В первой строке входных данных записано одно натуральное число N, не превосходящее 500. В следующих N строках описаны стопки контейнеров: сначала записано число ki– количество контейнеров в стопке, а затем ki чисел – виды товара в контейнерах в данной стопке, снизу вверх. В каждой стопке вначале не более 500 контейнеров (в процессе переноса контейнеров это ограничение может быть нарушено).
Формат выходных данных
Программа должна вывести описание действий автопогрузчика: для каждого действия напечатать два числа – из какой стопки брать контейнер и в какую стопку класть. (Обратите внимание, что минимизировать количество операций автопогрузчика не требуется.) Если задача не имеет решения, необходимо вывести одно число 0. Если контейнеры изначально правильно размещены по стопкам, то выводить ничего не нужно.
Пример
| Входные данные | Выходные данные |
| 3 4 1 2 3 2 0 0 | 1 2 1 3 1 2 |
Объяснение примера. Изначально в первой стопке лежат четыре контейнера – снизу контейнер с товаром первого вида, над ним – с товаром второго вида, над ним третьего, и сверху еще один контейнер с товаром второго вида. Вторая и третья стопки – пусты.
#include <iostream>
using namespace std;
struct Elem
{
int val;
Elem *pr;
};
struct Stack
{
Elem *up;
Stack ()
{
up = NULL;
}
void push (int a)
{
Elem *tmp;
tmp = new Elem();
tmp->val = a;
tmp->pr = up;
up = tmp;
}
int pop ()
{
if (up != NULL)
{
int v = up->val;
Elem *tmp = up;
up = up->pr;
delete tmp;
return v;
}
else
{
cerr « "empty stack" « endl;
return 0;
}
}
int back ()
{
return up->val;
}
bool empty ()
{
return up == NULL;
}
void free ()
{
while (!empty ()) pop ();
}
~Stack ()
{
free ();
}
};
int N, k;
Stack cont[501];
int main ()
{
int tmp, i, j = 0, save = 1, qsave = 0;
cin » N;
save = 1;
if (N == 2)
{
bool ok = true, first = true;
cin » k;
if (k)
{
cin » tmp;
i = 1;
while (tmp == 1 && i < k)
{
cin » tmp;
++i;
}
j = tmp == 2;
while (i < k)
{
cin » tmp;
if (tmp == 1) ok = false;
++j;
++i;
}
}
cin » k;
if (k)
{
cin » tmp;
i = 1;
while (tmp == 2 && i < k)
{
cin » tmp;
++i;
}
if (j && tmp == 1) ok = false;
else if (tmp == 1) first = false;
j += tmp == 1;
while (i < k)
{
cin » tmp;
if (tmp == 2) ok = false;
++j;
++i;
}
}
if (ok)
{
if (first)
for (i = 0; i < j; ++i)
cout « "1 2" « endl;
else
for (i = 0; i < j; ++i)
cout « "2 1" « endl;
}
else cout « 0;
return 0;
}
for (i = 1; i <= N; ++i)
{
cin » k;
if (k)
{
cin » tmp;
j = 1;
while (tmp == i && j < k)
{
cin » tmp;
++j;
}
if (tmp != i) cont[i].push (tmp);
while (j < k)
{
cin » tmp;
cont[i].push (tmp);
++j;
}
}
}
for (i = 1; i < N; ++i)
{
while (!cont[i].empty ())
{
while (!cont[i].empty () && cont[cont[i].back ()].empty ())
{
cout « i « " " « cont[i].pop() « endl;
}
while (!cont[i].empty () && !cont[cont[i].back ()].empty ())
{
cout « i « " " « N « endl;
cont[N].push (cont[i].pop ());
}
}
while (!cont[i].empty ())
{
cout « i « " " « N « endl;
cont[N].push (cont[i].pop ());
}
}
while (!cont[N].empty ())
{
tmp = cont[N].pop ();
if (tmp == N)
{
cout « N « " " « save « endl;
++qsave;
}
else if (tmp == save)
{
save = 1 + save % 2;
for (i = 0; i < qsave; ++i)
{
cout « tmp « " " « save « endl;
}
cout « N « " " « tmp « endl;
}
else
{
cout « N « " " « tmp « endl;
}
}
for (i = 0; i < qsave; ++i)
{
cout « save « " " « N « endl;
}
return 0;
}
Графы
Дата добавления: 2015-09-15; просмотров: 424; Мы поможем в написании вашей работы!; Нарушение авторских прав |