Условие
Задача взята с сайта e-olymp, полное условие можно прочитать здесь.
Входные данные
В первой строке находится целое число [latex]k[/latex] — число программ во входном файле. Затем идут [latex]k[/latex] программ, удовлетворяющих приведенной грамматике. Пробелы и переводы строк могут встречаться везде в программе, но не в ключевых словах [latex]BEGIN[/latex], [latex]END[/latex], [latex]LOOP[/latex] и [latex]OP[/latex], нет их и в целых числах.
Вложенность операторов [latex]LOOP[/latex] не превышает [latex]10[/latex], размер входного файла не более [latex]2[/latex] Кбайт, коэффициенты многочлена в ответе не превышают [latex]50000[/latex].
(Примечание: то, что представляет из себя программа, можно прочитать по ссылке выше.)
Выходные данные
Для каждой программы сначала идет строка с номером программы. В следующей строке записывается время работы программы в терминах [latex]n[/latex] — многочлен степени не более [latex]10[/latex]. Многочлен должен быть записан обычным способом, то есть подобные слагаемые должны быть приведены, слагаемое большей степени должно предшествовать слагаемому меньшей степени, слагаемые с коэффициентом [latex]0[/latex] не записываются, множители [latex]1[/latex] не записываются. Общий вид второй строки [latex]Runtime = a*n^{10}+b*n^9+\ldots+i*n^2+j*n+k[/latex]. Если время выполнения нулевое, нужно вывести [latex]Runtime = 0[/latex]. За строкой с многочленом должна следовать пустая строка, кроме последнего тестового случая.
Решение
Создадим массив коэффициентов [latex]coefficients[/latex] на 11 элементов (нулевой элемент — свободный член, 10-й — десятая (максимальная) степень). В цикле для каждой программы будем:
- Обнулять массив [latex]coefficients[/latex].
- Заполнять его новыми данными с помощью функции void getCoefficients(int* coefficients);
- Строить на основании полученных коэффициентов требуемую строку-многочлен, за это отвечает функция string toString(int* coefficients);
- Выводить требуемую информацию.
Рассмотрим процесс заполнения массива. Создадим вектор для строк [latex]params[/latex], где будем хранить кол-ва повторений для всех открытых циклах, от внешнего к внутреннему, и переменную-счетчик [latex]keywords[/latex]. Функция будет завершать свою работу при значении [latex]keywords[/latex] равном [latex]0[/latex]. Изначально присвоим [latex]keywords = 1[/latex] (оператор [latex]BEGIN[/latex]). Далее, в цикле будем, в зависимости от прочитанного оператора:
- [latex]END[/latex]: уменьшаем значение [latex]keywords[/latex] на [latex]1[/latex], удаляем последний элемент из [latex]params[/latex] (чтобы не было проблем с последним оператором [latex]END[/latex] (пустой вектор), положим в него перед циклом строку «[latex]1[/latex]»). Если [latex]keywords[/latex] равно нулю — завершаем работу.
- [latex]LOOP[/latex]: увеличиваем значение [latex]keywords[/latex] на [latex]1[/latex], считываем следующую строку и добавляем ее в конец [latex]params[/latex].
- [latex]OP[/latex]: Считываем следующую строку, преобразовываем ее к числу (кол-ву операций) стандартной функцией stoi(). Далее, проходя по строкам из [latex]params[/latex], если строка равна [latex]n[/latex], увеличиваем степень (номер ячейки массива, куда прибавим результат) на [latex]1[/latex], иначе — преобразовываем к числу и домножаем на кол-во операций. Прибавляем полученный результат к числу в соответствующей ячейке массива.
Функция toString() реализована достаточно просто (см. код). Пробегаем по элементам массива с конца, и если элемент [latex]n[/latex] не равен нулю, прибавляем к строке-многочлену соответствующий набор символов (отдельно учитывая случаи при [latex]n = 1[/latex], [latex]n=-1[/latex], первой и нулевой степени и т.д.). Если в итоге строка пустая, возвращаем «[latex]0[/latex]».
Тесты
| № | Ввод | Вывод |
| 1 | 2 BEGIN LOOP n OP 4 LOOP 3 LOOP n OP 1 END OP 2 END OP 1 END OP 17 END BEGIN OP 1997 LOOP n LOOP n OP 1 END END END |
Program #1 Runtime = 3*n^2+11*n+17 Program #2 |
| 2 | 3 BEGIN END BEGIN LOOP n LOOP n LOOP n OP 1 LOOP n LOOP n LOOP n OP 1 LOOP n LOOP n LOOP n OP 1 END END END OP 3 END END END OP 3 END END END OP 3 END BEGIN OP 42 LOOP n LOOP 5 LOOP n OP 7 END OP 2 END OP 1 END OP 1 END |
Program #1 Runtime = 0 Program #2 Program #3 |
Код
|
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 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 |
#include <iostream> #include <string> #include <vector> #define MAX_POWER 10 using namespace std; void getCoefficients(int* coefficients) { int keywords = 1; vector<string> params; string begin; cin >> begin; params.push_back(((string) "1")); //чтобы вектор не был пустой на последнем END (который соответствует BEGIN) while (true) { string keyword; cin >> keyword; if (keyword == (string)"END") { keywords--; params.pop_back(); if (keywords == 0) { break; } } else if (keyword == (string)"LOOP") { keywords++; string param; cin >> param; params.push_back(param); } else if (keyword == (string)"OP") { string num; cin >> num; int coefficient = stoi(num); int multiplier = 1, pow = 0; for (string param : params) { if (param == (string)"n") { pow++; } else { multiplier *= stoi(param); } } coefficients[pow] += coefficient * multiplier; } } } string toString(int* coefficients) { string result; for (int i = MAX_POWER; i > 0; i--) { if (coefficients[i] != 0) { if (coefficients[i] == 1) { result += "n"; } else if (coefficients[i] == -1) { result += "-n"; } else { result += to_string(coefficients[i]); //стандартная функция, преобразовывает число в строку result += "*n"; } if (i != 1) //если степень не первая, добавляем "^[степень]" { result += "^"; result += to_string(i); } } if (coefficients[i-1] > 0 && result.length() != 0) //проверка, чтобы + не стоял в начале строки и между членами не было "+-" { result += "+"; } } if (result.length() == 0 || coefficients[0] != 0) //прибавляем последний коэффициент, если он не равен нулю или строка пустая { result += to_string(coefficients[0]); } return result; } int main() { int n; cin >> n; int coefficients[MAX_POWER + 1]; for (int i = 1; i <= n; i++) { cout << "Program #" << i << endl; fill(coefficients, coefficients + MAX_POWER + 1, 0); //обнуляем массив коэффициентов getCoefficients(coefficients); cout << "Runtime = " << toString(coefficients) << endl; if (i != n) { cout << endl; } } return 0; } |
Ссылки
Засчитанное решение на e-olymp.
Рабочий код на ideaone.
Хорошо, молодец!