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:

e-olymp 479. Вышивка “крестиком”

28/11/2018 by Владимир Дроздин

Задача взята с сайта e-olymp.

Задача

Валя на уроках труда училась вышивке крестиком. Но для вышивки ей нужно было приготовить макет узора, который также имел форму “крестика”, в котором количество вышитых крестиков по диагонали было равно номеру тренировочного узора. Помогите Вале приготовить нужное количество макетов.

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

Сначала кол-во макетов, потом их номера. Все номера узоров у Вали имели одну странность — всегда были нечетными и не превышали 80.

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

Макеты, в порядке, перечисленном во входном файле, разделенные пустой строкой.

Тесты

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

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

2 3 5

X X
X
X X

X X
X X
X
X X
X X

1 9

X X
X X
X X
X X
X
X X
X X
X X
X X

Код

#include <iostream>
using namespace std;
 
int main() {
    int n, x;
    cin >> n;
    for (int l = 0; l < n; l ++){
        cin >> x;
        for (int j = 0; j < x; j ++){
            for (int i = 0; (i <= j) or (i <= x - 1 - j); i ++){
                if ((i == j) or (j == x - 1 - i)) cout << "X";
                else cout << " ";
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, x;

cin >> n;

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

cin >> x;

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

for (int i = 0; (i <= j) or (i <= x - 1 - j); i ++){

if ((i == j) or (j == x - 1 - i)) cout << "X";

else cout << " ";

}

cout << endl;

}

cout << endl;

}

return 0;

}

Решение

В данной задаче будем использовать потоковую обработку. Сначала считываем количество макетов [latex] n [/latex]. Затем в цикле for (int l = 0; l < n; l ++); считываем номера узоров. Выводить [latex] X [/latex] будем по диагоналям (справа налево и наоборот). Однако, стоит учесть, что после последнего символа [latex] X [/latex] в строке, выводить пробел не стоит. В условии задачи данный факт не фигурирует, однако, если же сделать иначе, то задача на сайте e-olymp не пройдет. Из этого вытекает, что пробелы должны располагаться исключительно до последнего крестика в строке. Для этого во внутреннем цикле ставим соответсвующее условие, чтобы при достижении последнего крестика в строке осуществлялся переход на другую строку, если это возможно. Также стоит не забыть, что между разными узорами нужно пропускать строку.

Ссылки

Засчитанное решение на e-olymp.

Код в ideone.

Related Images:

MS9. Шифрование символов

29/08/2017 by Курьянов Павел

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

Входные данные
Последовательность символов.

Выходные данные
Зашифрованная последовательность символов, напечатанная через пробел.

Тесты

входные данные	выходные данные
pack my box with five dozen liquor jugs	p 11 2 8 4b 4d 14 59 42 d 17 58 57 1e 1d 1c 48 46 f 1f 13 45 44 b 15 1f b 4e 4c 5 18 4 1a 1d 52 4a 1f 12 14

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

#include <iostream>
using namespace std;

int main() {
    unsigned char a, b; 
    scanf("%c", &b); 
    cout<<b<<" ";
    while (scanf("%c", &a)) {
        if (a == '\n')  break;
        printf("%x ", a^b);
        b=a;
}
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned char a, b;

scanf("%c", &b);

cout<<b<<" ";

while (scanf("%c", &a)) {

if (a == '\n') break;

printf("%x ", a^b);

b=a;

}

return 0;

}

Решение задачи
Объявляем 2 символьные переменные. Считываем первый символ и выводим его. Остальные символы будут считываться в цикле, пока не произойдет переход на следующую строку.По мере ввода запоминаем старый символ во 2 переменной и складываем их по модулю 2 и выводим результат в шестнадцатеричной системе.

Ссылки

Подзадача — дешефратор
Написать программу, которая сможешь преобразовать полученный код обратно в текст.

Входные данный
Код полученный из выполнения основной задачи.

Выходные данные
Изначальный текст.

Тесты

входные данные	выходные данные
p 11 2 8 4b 4d 14 59 42 d 17 58 57 1e 1d 1c 48 46 f 1f 13 45 44 b 15 1f b 4e 4c 5 18 4 1a 1d 52 4a 1f 12 14	pack my box with five dozen liquor jugs

Код задачи

#include <iostream>
using namespace std;

int main()
{
    unsigned short a;
    unsigned char b;
    cin>>b;
    cout<<b;
    while (cin >> hex >> a)
    {
        b = a^b;
        cout << b;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

unsigned short a;

unsigned char b;

cin>>b;

cout<<b;

while (cin >> hex >> a)

{

b = a^b;

cout << b;

}

return 0;

}

Решение задачи
Так как сложение по модулю 2 обратно само себе, то нам нужно считать символы в том же порядке и применить тот же алгоритм при шифровании.

Related Images:

Душевая кабина

14/04/2017 by Антон Куперман

Разбор задачи F с 1/8 ACM ICPC по украинскому региону 25 марта 2017.

Задача

Степан приобрел душевую кабину, которую решил установить в дачном домике. Дачный домик представляет собой прямоугольник [latex]N \times M[/latex], разбитый на одинарные квадратики. Степан знает, что душевая кабина занимает ровно две клетки с общей стороной. Также Степану известно, что некоторые клетки дома заняты разными вещами. Помогите Степану узнать сколькими способами он может разместить душевую кабину в дачном домике.

Ввод

В первом ряду входных данных находятся два целых числа [latex] N,M(1<=N,M<=1000)[/latex] — размеры дачного домика Степана. Каждый из следующих [latex] N[/latex] рядов содержит по [latex] M[/latex] символов — описание дачного домика Степана. Символ «#» означает, что соответствующая клетка уже чем-то занята, а символ «.» — что она свободна и может стать одной из двух, занятых душевой кабиной.

Вывод

Одно число — количество способов расположить душевую кабину в дачном домике.

Тесты

Код

#include <iostream>
using namespace std;

int main() {
    int n,m;
    long s=0;
    cin>>n>>m;
    char x[n*m];
    for(int i=0;i<n*m;i++)
    {
        cin>>x[i];
    }
    for(int i=0;i<n*m;i++)
    {
        if(x[i]=='.')
        {
            if(x[i]==x[i+1])
            {
                if((i+1)%m!=0)
                {
                    s++;
                }
            }
            if(x[i]==x[i+m])
            {
                s++;
            }
        }
    }
    cout<<s;
    
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n,m;

long s=0;

cin>>n>>m;

char x[n*m];

for(int i=0;i<n*m;i++)

{

cin>>x[i];

}

for(int i=0;i<n*m;i++)

{

if(x[i]=='.')

{

if(x[i]==x[i+1])

{

if((i+1)%m!=0)

{

s++;

}

if(x[i]==x[i+m])

{

s++;

}

cout<<s;

return 0;

}

Решение

Считываем символы в массив . Размер такого массива всегда будет [latex]n \times m[/latex]. Зная это, заводим цикл, в котором проверяем наличие точки(‘.’). Затем проверяем первое условие: если следующий символ тоже точка и если мы не перешли на новую строку, увеличиваем счетчик. Зная количество символов в каждой строке, проверяем символ «под» точкой и если они совпадают опять же увеличиваем счетчик.