e-olymp 399. Последствия гриппа в Простоквашино

19/05/2020 by Никита Репнин

Задача

”Дорогой дядя Фёдор!

После того, как мама испугалась, что ты можешь заболеть какой-то нечеловеческой болезнью и забрала тебя в город, Шарик видимо все-таки чем-то заболел, ибо его поступки я уже иначе объяснить не могу, как последствиями постоянного общения с Хрюшей.

Суди сам: он сначала распилил шахматную доску на квадратики, потом на каждый квадратик наклеил изображение круглой скобки и, выдав определенное количество квадратиков, заставляет меня считать, сколько разных правильных скобочных последовательностей я смогу построить из имеющегося у меня числа квадратиков. При этом он еще и требует, чтобы я использовал все квадратики!

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

Дядя Фёдор, если тебе не трудно, напиши мне программу для подсчета этого количества, ибо из-за того, что Шарик задает мне свою непонятную задачу до 20 раз на день, у меня даже не остается времени ухаживать за моей любимой коровой.

Всегда твой верный друг – кот Матроскин.”

Помогите дяде Фёдору написать программу для Матроскина, иначе тот может остаться без молока.

Входные данные

В первой строке задано число $n$ – количество заданий Шарика за день. В следующих $n$ строках задано по одному числу $k$ – количество выданных в очередной раз Матроскину квадратиков с изображением скобок. Квадратики Матроскин может переворачивать, получая при этом как открывающую, так и закрывающую скобку.

Выходные данные

Вывести в $n$ строках по одному числу – ответ на соответствующее задание Шарика.

Тесты

№	Входные данные	Выходные данные
1	3 2 3 4	1 0 2
2	5 3 11 7 43 27	0 0 0 0 0
3	6 2 28 42 14 64 0	1 2674440 24466267020 429 55534064877048198 1

Код

#include <iostream>
using namespace std;
 
int main() {
    int n, k;
    long long brackets [33];
    brackets [0] = 1;
    for(int i = 1; i <= 32; ++ i){
        brackets [i]=0;
        for(int j = 0; j < i; ++ j){
            brackets [i] += brackets [j] * brackets [i - 1 - j];
        }
    }
    cin >> n;
        for (int i = 0; i < n; i ++) {
        cin >> k;
        cout << (k % 2 == 0 ? brackets [k / 2] : 0) << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, k;

long long brackets [33];

brackets [0] = 1;

for(int i = 1; i <= 32; ++ i){

brackets [i]=0;

for(int j = 0; j < i; ++ j){

brackets [i] += brackets [j] * brackets [i - 1 - j];

}

cin >> n;

for (int i = 0; i < n; i ++) {

cin >> k;

cout << (k % 2 == 0 ? brackets [k / 2] : 0) << endl;

}

return 0;

}

Решение

Правильную скобочную последовательность можно построить лишь из четного количества скобок, т.е. для нечетного числа ответ заведомо $0$. А для $2m$ скобок ($m$ открывающих и $m$ закрывающих) ответ равен числу Каталана $C_m$. Для вычисления которого используется рекуррентное соотношение: $$C_m=\sum_{i=0}^{m-1} C_i \cdot C_{m-1-i}$$

Задача на e-olymp
Код программы на ideone
Засчитанное решение

Related Images:

e-olymp 8666. Коровий котильон

18/01/2020 by Нина Хоробрых

Задача

В коровьем котильоне — причудливом танце весны — участвуют коровы (обозначаются $ «\gt»$) и быки (обозначаются $ «\lt»$), они кланяются друг другу во время танца. Схематически обозначим пару кланяющихся животных следующим образом: $ «\gt \lt»$. Иногда вторая пара скота может находиться между кланяющейся парой: $ «\gt \gt \lt \lt»$.

Иногда и большее количество коров и быков встречается на танцевальной площадке: $ «\gt \gt \lt \lt \gt \lt»$ (имеется вторая пара кланяющихся коров справа). Сложные аранжировки могут быть совершенно легальными танцевальными образованиями:

Фермер Джон замечает, что бездомная корова иногда пробирается в группу и разбалансирует ее: $ «\gt \gt \lt \lt \lt \lt»$. Это строго запрещено; Фермер Джон хочет наказать нарушителей.

Фермер Джон скопировал данные о том, как $500$ коров участвуют в танцевальной линии, и задался вопросом, правильно ли уравновешена танцевальная линия (то есть весь скот может быть спарен как минимум одним способом чтобы правильно кланяться друг другу). Он скопировал только направление, в котором кланялась каждая корова, без каких-либо лишних пробелов, чтобы можно было определить, какая корова какому быку кланяется. Строки похожи на пример из предыдущего абзаца: «>><&lt». Фермер Джон хочет чтобы Вы написали программу, определяющую правильность танцевальной линии.

Фермер Джон имеет $n$ записей танца $P_{i}$ состоящих из символов $ «\gt»$ и $ «\lt»$;’ различной длины $K_{i} (1 \leqslant K_{i} \leqslant 200)$. Выведите «legal» для тех строк, которые содержат правильные пары кланяющихся коров и «illegal» иначе.

Входные данные

Первая строка содержит одно число $n$ $(1 \leqslant n \leqslant 1000)$. Каждая из следующих $n$ строк содержит число и строку из $K$ символов $ «\gt»$ и $ «\lt»$: $K_{i}$и $P_{i}$.

Выходные данные

Выведите в каждой строке «legal» или «illegal» в зависимости от того, содержит ли соответствующая входная строка допустимую конфигурацию.

Тесты

№	Входные данные	Выходные данные
1	2 6 >><<>< 4 ><<>	legal illegal
2	3 8 <>><><>< 6 ><>><< 9 >><>><<><	illegal legal illegal
3	5 4 ><>< 10 >>><<>><<< 8 >><<<>>< 3 >>< 12 ><>><>>><<<<	legal legal illegal illegal legal

Код

#include <iostream>
using namespace std;

int main() {
  int n, q, count;
  char ungulate;
  bool b;
  cin >> n;
 
  for ( int i = 0; i < n; i++ ) {
    int count = 0;
    b = true;
    cin >> q;
   
    for ( int j = 0; j < q; j++ ) {
      cin >> ungulate;
      if ( ungulate == '>' ) {
        count++;
      }
      else {
        count--;
      }
      if ( count < 0 ) {
        b = false;
      }
    }
    
    if ( count != 0 ) {
        b = false;
    }
    
    if ( b ) {
        cout << "legal" << endl; 
      } 
    else {
        cout << "illegal" << endl;
      }
  }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, q, count;

char ungulate;

bool b;

cin >> n;

for ( int i = 0; i < n; i++ ) {

int count = 0;

b = true;

cin >> q;

for ( int j = 0; j < q; j++ ) {

cin >> ungulate;

if ( ungulate == '>' ) {

count++;

}

else {

count--;

}

if ( count < 0 ) {

b = false;

}

if ( count != 0 ) {

b = false;

}

if ( b ) {

cout << "legal" << endl;

}

else {

cout << "illegal" << endl;

}

return 0;

}

Решение

Пара начинается с коровы и каждой из них должен соответствовать один бык, стоящий после неё. Для того, чтобы проверить правильность танцевальной линии, будем фиксировать количество встречающихся коров, а при встрече быка это число уменьшать. Отрицательное значение показывает на наличие быка без пары. В таком случае баланса уже не будет и проверять дальше смысла нет. В случае конечного результата $0$, в линии соблюден баланс — у каждого есть своя пара.

Ссылки

Код на ideone
Задача на e-olymp
Засчитанное решение на e-olymp

Related Images:

AL6

26/05/2016 by Андрей Яроцкий

Задача AL6

Условие

Дана конечная последовательность, состоящая из левых и правых скобок различных заданных типов. Как определить, можно ли добавить в нее цифры и знаки арифметических действий так, чтобы получилось правильное арифметическое выражение.

Тесты

№	Входные данные	Выходные данные
1	(	NO
2	))	NO
3	[}	NO
4	{}	YES
5	(){}[]	YES
6	({[]}{})	YES
7	[({}())[]	NO

Код программы

#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
using namespace std;
 
struct stack{
        char *bkt = new char;
        int cur;
        stack(){cur = 0;}
        void push(char x){
            bkt[cur++] = x;
        }
        void pop(){
            cur--;
        }
        char back(){
            return bkt[cur-1];
        }
        int size(){
            return cur;
        }
};
 
int main() {
    string brace;
    cin >> brace;
    stack x;
    if(brace[0] == '(' || brace[0] == '{' || brace[0] == '[') x.push(brace[0]); //Правильное выражение начинается только с открывающей скобки
    else{
        if(brace == "") cout << "YES";//Выражение без скобок также првильное
        else cout << "NO";
        return 0;
    }
    for(int i = 1; i < brace.length(); i++){
        if(brace[i] == '(' || brace[i] == '{' || brace[i] == '['){ //Любую открывающую скобку добавляем в стек
            x.push(brace[i]);
        }
        else if(abs(brace[i] - x.back()) < 3 && x.size() != 0){//Модуль разницы скобок одного типа меньше трех
            x.pop();
        }
        else{
            cout << "NO";
            return 0;
        }
    }
    if(x.size() == 0) cout << "YES";//Правильное арифметическое выражение получим при пустом стэке
    else cout << "NO";
    return 0;
}

#include <iostream>

#include <string>

#include <cstring>

#include <cmath>

using namespace std;

struct stack{

char *bkt = new char;

int cur;

stack(){cur = 0;}

void push(char x){

bkt[cur++] = x;

}

void pop(){

cur--;

}

char back(){

return bkt[cur-1];

}

int size(){

return cur;

}

};

int main() {

string brace;

cin >> brace;

stack x;

if(brace[0] == '(' || brace[0] == '{' || brace[0] == '[') x.push(brace[0]); //Правильное выражение начинается только с открывающей скобки

else{

if(brace == "") cout << "YES";//Выражение без скобок также првильное

else cout << "NO";

return 0;

}

for(int i = 1; i < brace.length(); i++){

if(brace[i] == '(' || brace[i] == '{' || brace[i] == '['){ //Любую открывающую скобку добавляем в стек

x.push(brace[i]);

}

else if(abs(brace[i] - x.back()) < 3 && x.size() != 0){//Модуль разницы скобок одного типа меньше трех

x.pop();

}

else{

cout << "NO";

return 0;

}

if(x.size() == 0) cout << "YES";//Правильное арифметическое выражение получим при пустом стэке

else cout << "NO";

return 0;

}

Решение

Арифметическое выражение является правильным если каждой открывающей скобке соответствует единственная закрывающая. Что бы убедится в правильности выражения необходимо создать структуру [latex]stack[/latex], в которую поочередно записываются открывающиеся скобки. Если встречается закрывающая скобка того же типа, что и последняя открывающая, то они обе удаляются, так как не влияют на правильность выражения. Если же закрывающая скобка не соответствует типу последней открывающей, то такое арифметическое выражение не является правильным. Если после обработки всей последовательности в стеке не осталось элементов, то такое выражение является правильным. В случае отсутствия скобок выражение также правильное.

Ссылки

Код программы на ideone.com

Условие задачи

Related Images:

ML12

23/09/2015 by Катя Писова

Условие задачи:

Даны [latex]x,y,z[/latex]. Вычислить [latex] a = x \arctan{y} — e^{1-z}[/latex] и [latex] b = \frac{\sqrt{\left|3-x^2 \right|}- \sqrt[3]{\left|y-x \right|}}{1-\frac{x^2}{2}+\frac{y^2}{4}-\frac{z^2}{8}}.[/latex]

Алгоритм решения:

1)В условии задачи не указано какие должны быть числа [latex]x,y,z[/latex] , поэтому правильнее всего использовать диапазон long double, чтобы включить как можно больше значений.

2)Подключим библиотеку <cmath> , с помощью которой подключим математические функции и, придерживаясь правил порядка вычислений, расставим скобки.

Код программы:

#include <iostream>
#include <cmath>
using namespace std;
 
int main() 
{
    long double x, y, z;
    cin>>x>>y>>z;
    long double a, b;
    a = x*atan(y) - pow(M_E,(1-z)); // M_e - число Эйлера 
    b =(sqrt(abs(3-x*x))-pow(abs(y-x),1.0/3))/(1-x*x/2 + y*y/4 - z*z/8);
    cout<<a<<endl;
    cout<<b<<endl;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

long double x, y, z;

cin>>x>>y>>z;

long double a, b;

a = x*atan(y) - pow(M_E,(1-z)); // M_e - число Эйлера

b =(sqrt(abs(3-x*x))-pow(abs(y-x),1.0/3))/(1-x*x/2 + y*y/4 - z*z/8);

cout<<a<<endl;

cout<<b<<endl;

return 0;

}

Тесты:

Ввод:	#	Вывод:	#
x	1	a	0.971813
y	2	b	1.10457
z	3

Ввод:	#	Вывод:	#
x	-9	a	-16.1645
y	13	b	2.19263
z	0

Ввод:	#	Вывод:	#
x	7	a	10.361
y	11	b	-0.107389
z	21

Здесь находится код в ideone.com

Related Images:

e-olymp 2479. Баланс скобок

13/06/2015 by Царев Николай Александрович

Условие

(Ссылка на задачу в e-olymp)

Имеется строка, содержащая скобки () и []. Скобочное выражение считается правильным, если:

оно является пустым
если A и B правильны, то AB правильно
если A правильно, то (A) и [A] правильны

Напишите программу, которая по входной строке, содержащей скобочное выражение, определит корректно ли оно. Длина строки не больше 128 символов.

Входные данные

Первая строка содержит количество тестов n. Каждая из следующих n строк содержит выражение, состоящее из скобок () и [].

Выходные данные

Для каждого теста вывести в отдельной строке «Yes«, если выражение является правильным и «No» иначе.

Тесты

3
([])
(([()])))
([()[]()])()

Yes
No
Yes

(тесты взяты с e-olymp.com)

Результаты задачи № 2479

#include <iostream>
#include <stack>
#include <string>

using namespace std;

int main()
{
    int n;
    cin >> n;
    char l;
    cin.get(l); //считывание конца строки после числа
    for(int z=0;z<n;z++){
        bool q=1; //переменная "фиксирующая" ошибку
        char hab;
        string str;
        getline(cin,str); //используем, чтобы читать до конца строки
        int j=str.size(); //размер строки ( кол-во обрабатываемых символов)
        stack<char> res; //стэк скобок
        for(int i=0;i<j;i++){
            if((str[i]=='(')||(str[i]=='[')) //если открывающая скобка - то кладем в стэк
                res.push(str[i]);
            else{ //если закрывающая скобка
                    if(!res.empty()){ //если стэк не пуст
                        hab=res.top(); //вытаскиваем последний элемент
                        if(str[i]==')'){ //сверяем на типы скобок
                            if(hab=='('){
                                res.pop(); //удаляем пару
                               }
                            else{
                                q=0;
                                cout << "No" << endl;
                                break;

                            }
                        }
                        else{
                            if(hab=='['){ //второй тип скобок (те же действия)
                                res.pop();
                               }
                            else{
                                q=0;
                                cout << "No" << endl;
                                break;
                            }
                        }
                    }
                    else{ //если стэк пуст  - то ошибочка вышла!
                        cout << "No" << endl;
                        q=0;
                        break;
                    }
            }
        }
        if(q){
        if(res.empty()) //собственно ответ
            cout << "Yes" << endl;
        else
            cout << "No" << endl;
        }

    }
    return 0;
}

#include <iostream>

#include <stack>

#include <string>

using namespace std;

int main()

{

int n;

cin >> n;

char l;

cin.get(l); //считывание конца строки после числа

for(int z=0;z<n;z++){

bool q=1; //переменная "фиксирующая" ошибку

char hab;

string str;

getline(cin,str); //используем, чтобы читать до конца строки

int j=str.size(); //размер строки ( кол-во обрабатываемых символов)

stack<char> res; //стэк скобок

for(int i=0;i<j;i++){

if((str[i]=='(')||(str[i]=='[')) //если открывающая скобка - то кладем в стэк

res.push(str[i]);

else{ //если закрывающая скобка

if(!res.empty()){ //если стэк не пуст

hab=res.top(); //вытаскиваем последний элемент

if(str[i]==')'){ //сверяем на типы скобок

if(hab=='('){

res.pop(); //удаляем пару

}

else{

q=0;

cout << "No" << endl;

break;

}

else{

if(hab=='['){ //второй тип скобок (те же действия)

res.pop();

}

else{

q=0;

cout << "No" << endl;

break;

}

else{ //если стэк пуст - то ошибочка вышла!

cout << "No" << endl;

q=0;

break;

}

if(q){

if(res.empty()) //собственно ответ

cout << "Yes" << endl;

else

cout << "No" << endl;

}

return 0;

}

Алгоритм

Решение задачи состоит в последовательной обработке каждого символа. Мы читаем символ. Если это открывающая скобка — то кладем в стэк. Если закрывающая — смотрим последний элемент в стэке. Если скобка «находит пару» — то удаляем их обоих. В противном случае — это ошибка. Если же после обработки всех символов в стэке останется скобки — то значит в строке было больше открывающих скобок, и такая строка — не правильная.

Маленький костыль для этой задачи — это лишнее считывание символа в самом начале. Делается это для того, чтобы дальше, мы спокойно могли использовать функцию getline, которая читает строку до символа конца строки. Эти дополнительным вводом, мы как бы забираем на себя символ конца строки стоящий после числа, определяющее кол-во строк.

Ссылка на ideone.com

Related Images:

А1043

21/05/2015 by Фесенко Катерина Володимирівна

Задача

Построить все правильные скобочные выражения длины 10, то есть, которые содержат по 5 левых и по 5 правых скобок.

Код на языке С++:

#include <iostream>
#include <string>
using namespace std;
 
void f(int x, string s){
	if(s.size() == 10){cout << s << endl; return;}
	if(x>0){f(x-1,s+")");}
	if(10-s.size() > x){f(x+1,s+"(");}
}
 
int main() {
	f(0,"");
	return 0;
}

#include <iostream>

#include <string>

using namespace std;

void f(int x, string s){

if(s.size() == 10){cout << s << endl; return;}

if(x>0){f(x-1,s+")");}

if(10-s.size() > x){f(x+1,s+"(");}

}

int main() {

f(0,"");

return 0;

}

Посмотреть программу можно здесь

Код на языке Java:

import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone {
	public static void f (int x, String s) {
		if(s.length() == 10) {
			System.out.println(s) ;
			return;
		}
		if(x>0) f(x-1,s+")");
		if(10-s.length() > x) f(x+1,s+"(");
	}
	public static void main (String[] args) {
		f(0, "");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void f (int x, String s) {

if(s.length() == 10) {

System.out.println(s) ;

return;

}

if(x>0) f(x-1,s+")");

if(10-s.length() > x) f(x+1,s+"(");

}

public static void main (String[] args) {

f(0, "");

}

Ссылка на программу: http://ideone.com/9MjHSA

Решение:

В переменной [latex]x[/latex] мы будем хранить количество открытых ([latex]»(«[/latex]) скобок. Далее проверяем условие, что если [latex]x>0[/latex], то можем поставить закрывающую ([latex]»)»[/latex]) скобку. Идем дальше, смотрим сколько свободных мест осталось и если мест осталось столько же, сколько открывающих, то все остальные закрывающие.

Related Images:

Ю12.29

20/12/2014 by Стеблинський Ігор Віталійович

Задача: Скобки. Текст ( например, арифметическое выражение) содержит многократно вложенные круглые скобки. Исправить его, оставив скобки первого уровня круглыми, второго — заменить на квадратные, третьего и последующих — на фигурные. Убедиться в корректности использования скобок.

Тесты:

Введенная строка	Выведенная строка
ln(sin((a+b)c-d))	ln{sin[(a+b)c-d]}
ln(sin((a+b)c-d))+ln(sin((a+b)c-d))	ln{sin[(a+b)c-d]}+ln{sin[(a+b)c-d]}
cos((a-b)c)	cos[(a-b)c]

Код string

#include <string>
#include <iostream>

using namespace std;

int main()
{
	string s;
	cin >> s;
	int l = 0;
	int maxl = 0;
	for( int i = 0 ; i < s.length() ; i++ )
	{
		if( s[i] == '(' )
		{
			s[i] = '{';
			l++;
			if( l > maxl )
			{
				maxl = l;
			}
		}
		if( s[i] == ')' )
		{
			s[i] = '}';
			l--;
		}
	}
	for( int i=0 ; i < s.length() ; i++ )
	{
		
		if( s[i] == '{' )
		{
			l++;
			if( l == maxl ) s[i] = '(';
			if( l == maxl-1 ) s[i] = '[';
		}
		if( s[i] == '}' )
		{
			if( l == maxl ) s[i] = ')';
			if( l == maxl-1 ) s[i] = ']';
			l--;
		}
	}
	cout << s << endl;
}

#include <string>

#include <iostream>

using namespace std;

int main()

{

string s;

cin >> s;

int l = 0;

int maxl = 0;

for( int i = 0 ; i < s.length() ; i++ )

{

if( s[i] == '(' )

{

s[i] = '{';

l++;

if( l > maxl )

{

maxl = l;

}

if( s[i] == ')' )

{

s[i] = '}';

l--;

}

for( int i=0 ; i < s.length() ; i++ )

{

if( s[i] == '{' )

{

l++;

if( l == maxl ) s[i] = '(';

if( l == maxl-1 ) s[i] = '[';

}

if( s[i] == '}' )

{

if( l == maxl ) s[i] = ')';

if( l == maxl-1 ) s[i] = ']';

l--;

}

cout << s << endl;

}

Код c-string

#include <cstring>
#include <iostream>

using namespace std;

int main()
{
	char s[100];
	cin >> s;
	int l = 0;
	int maxl = 0;
	for( int i=0 ; i < strlen(s); i++ )
	{
		if( s[i] == '(' )
		{
			s[i] = '{';
			l++;
			if( l > maxl )
			{
				maxl = l;
			}
		}
		if( s[i] == ')' )
		{
			s[i] = '}';
			l--;
		}
	}
	for( int i=0 ; i < strlen(s); i++ )
	{
		
		if( s[i] == '{' )
		{
			l++;
			if( l == maxl ) s[i] = '(';
			if( l == maxl-1 ) s[i] = '[';
		}
		if( s[i] == '}' )
		{
			if( l == maxl ) s[i] = ')';
			if( l == maxl-1 ) s[i] = ']';
			l--;
		}
	}
	cout << s << endl;
}

#include <cstring>

#include <iostream>

using namespace std;

int main()

{

char s[100];

cin >> s;

int l = 0;

int maxl = 0;

for( int i=0 ; i < strlen(s); i++ )

{

if( s[i] == '(' )

{

s[i] = '{';

l++;

if( l > maxl )

{

maxl = l;

}

if( s[i] == ')' )

{

s[i] = '}';

l--;

}

for( int i=0 ; i < strlen(s); i++ )

{

if( s[i] == '{' )

{

l++;

if( l == maxl ) s[i] = '(';

if( l == maxl-1 ) s[i] = '[';

}

if( s[i] == '}' )

{

if( l == maxl ) s[i] = ')';

if( l == maxl-1 ) s[i] = ']';

l--;

}

cout << s << endl;

}

Ссылки на коды:

string

c-string

Ход решения:

Вводим строку. Задаем две переменные: l — уровень вложенности скобок и maxl — максимальный уровень вложенности скобок. Делаем цикл в котором заменяем все ‘(‘ , ‘)’ скобки на ‘{‘ , ‘}’. Делаем второй цикл в котором меняем скобки, которые являются последними по уровню вложенности на ‘(‘, ‘)’ и скобки, стоящие на уровень ниже меняем на ‘[‘, ‘]’, все остальные скобки оставляем без изменений.