e-olymp 1679. Честная цепочка

19/12/2020 by Максим Ливитчук

Условие

В подземных норах в долине рядом со скалами Крейд-Моор долгое время жили в мире и согласии два гномьих племени. Гномы обоих племен работали в шахтах, добывая драгоценные камни. Первое племя добывало исключительно изумруды, а второе племя — рубины. Однажды в честь великого праздника Файрвинд гномы решили принести в дар своей богине Мирабель цепочку из изумрудов и рубинов. Самые искусные кузнецы обоих племен работали над созданием этой цепочки, собирая на ней один за одним драгоценные камни. Но как только работа была окончена, решили вожди племен пересчитать камни каждого вида. Ведь если каких-то камней окажется меньше, то богиня может отвернуться от племени, которое пожадничало. Чтобы избежать подобных последствий, было решено подарить некоторый непустой фрагмент цепочки (то есть цепь, состоящую из нескольких камней, расположенных друг за другом в исходной цепочке), в котором будет рубинов ровно столько же, сколько и изумрудов. Возможно это может быть сделано несколькими способами. Для того, чтобы узнать сколько таких способов существует, гномы обратились за помощью к вам.

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

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

В единственной строке задается последовательность камней в исходной цепочке: символ E обозначает изумруд, символ R — рубин. Количество символов в строке не превышает $500000$.

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

Выведите количество способов, которыми можно выбрать фрагмент с одинаковым количеством изумрудов и рубинов.

Тесты

№	ввод	вывод
1	REER	3
2	REERREER	12
3	RRRRRRRR	0
4	EREREERERERREREREEERERERERERRREREREERERERERE	273
5	REEERREE	7

Код

#include <iostream>
#include <map>
using namespace std;

int main() {
    int cnt = 0;
    char buf;
    map<int, long long> mp;
    mp[0] = 1;
    while(cin >>buf) {
        if(buf=='R')
            cnt++;
        else
            cnt--;
        mp[cnt]++;
    }
    long long answer = 0;
    for(auto e: mp) {
        answer += e.second*(e.second-1)/2;
    }
    cout <<answer;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

int cnt = 0;

char buf;

map<int, long long> mp;

mp[0] = 1;

while(cin >>buf) {

if(buf=='R')

cnt++;

else

cnt--;

mp[cnt]++;

}

long long answer = 0;

for(auto e: mp) {

answer += e.second*(e.second-1)/2;

}

cout <<answer;

}

Компактный код

#include 
#include <map>
using namespace std;
 
int main() {
    int cnt = 0;
    char buf;
    map mp;
    mp[0] = 1;
    while(cin >>buf) mp[buf=='R'?++cnt:--cnt]++;
    long long a = 0;
    for(auto e: mp) a += e.second*(e.second-1)/2;
    cout <<a;
}

#include

#include <map>

using namespace std;

int main() {

int cnt = 0;

char buf;

map mp;

mp[0] = 1;

while(cin >>buf) mp[buf=='R'?++cnt:--cnt]++;

long long a = 0;

for(auto e: mp) a += e.second*(e.second-1)/2;

cout <<a;

}

Решение

Составим массив из $n+1$ чисел, каждое из которых будет располагаться в месте возможного начала или конца фрагмента цепочки, который гномы должны вручить богине. Число в самом начале цепочки возьмём равным $0$, а все следующие числа будут представлять из себя количество R минус количество E, встречающихся в фрагменте с начала до этого числа.

Наглядный пример такого массива для пятого примера (подписан как cnt)

На таком массиве наглядно видно, что правильным фрагментом будет любой, начинающийся и кончающийся одинаковым числом, ведь это значит что между этими числами равное количество как R($+1$), так и E($-1$), которые сокращаются.

Выделенные в том же примере фрагменты с началом и концом в 0 и -2

Так как нам не важны конкретные правильные фрагменты, а только их суммарное количество, нам будет достаточно знать, сколько раз в массиве встречается то или иное число. В коде эту информацию хранит ассоциативная таблица mp. Запись mp[cnt]++; создаёт новый равный нулю элемент по ключу cnt, если раньше в структуре его не было, после чего инкрементирует значение.
Сам же массив воспроизводится на ходу из ввода, в переменной cnt. В конце программы количество фрагментов считается как сумма $\frac{n(n-1)}{2}$, где $n$ — mp[i] для всех встречавшихся в массиве чисел.

Ссылки

Related Images:

e-olymp 909. Количество слов

29/04/2019 by Яна Юрковская

Задача

Определить количество слов в заданном фрагменте текста.

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

В одной строке задан фрагмент текста на английском языке, количество символов в котором не превышает 250. Гарантируется, что в тексте отсутствуют тире, дефисы, цифры и числа.

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

Вывести количество слов в фрагменте текста.

Тесты

№	Ввод	Вывод
1	Hello world!	2
2	Hello world! Hello, country!	4
3	What do you think?..	4
4	How are you?	3
5	Alice was beginning to get very tired of sitting by her sister on the bank, and of having nothing to do: once or twice she had peeped into the book her sister was reading, but it had no pictures or conversations in it.	43

Код. Вариант 1

#include <iostream>
using namespace std;

int main() {
    string s;
    int count = 0;
    while (cin >> s) count++;
    cout << count;
}

#include <iostream>

using namespace std;

int main() {

string s;

int count = 0;

while (cin >> s) count++;

cout << count;

}

Код. Вариант 2

#include <iostream> 
using namespace std;

int main() {
    char *word = new char[251];
    int count = 0;
    while(cin >> word) count++;
    cout << count;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

char *word = new char[251];

int count = 0;

while(cin >> word) count++;

cout << count;

return 0;

}

Решение

Считаем текст до пробела как слово. При помощи цикла while считываем по слову пока в потоке есть текст. И подсчитываем количество слов, используя счётчик count.

Ссылки

Related Images:

А137е(а)

22/10/2014 by Осецимський Анатолій Вадимович

Даны натуральные [latex] n[/latex], действительные [latex] a_{1}…a_{n}[/latex].

Вывести: [latex] a_1+1!, a_2 +2!, …, a_n+n![/latex].

Input : 1	2	3	4	Output: 2.00	4.00	9.00	28.00
Input : 0.1	0.2	0.3	0.4	Output: 1.10	2.20	6.30	24.40

#include <iostream>
using namespace std;

int main() {
    int i=1;
    double a,fact=1.0;
    while(scanf("%lf",&a)!=EOF)//читаем поток
    {
        fact*=i;//увеличиваем факториал
        printf("%.2lf ",(a+fact));//выводим сумму цифры из потока и факториала
        i++;//увеличиваем i для увеличения факториала каждый раз при  проходе цикла
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int i=1;

double a,fact=1.0;

while(scanf("%lf",&a)!=EOF)//читаем поток

{

fact*=i;//увеличиваем факториал

printf("%.2lf ",(a+fact));//выводим сумму цифры из потока и факториала

i++;//увеличиваем i для увеличения факториала каждый раз при проходе цикла

}

return 0;

}

Описываем переменную факториала и переменную из потока типа [latex]double[/latex]. Запускаем цикл [latex]while[/latex], у которого в условии ставим:

scanf("%lf",&a)!=EOF

1	scanf("%lf",&a)!=EOF

(Работать, пока файл не закончится (конец потока)). Дальше в теле цикла описываем увеличение факториала и выводим сумму цифр из потока и факториала, в конце цикла увеличиваем [latex]i[/latex] для увеличения факториала.

Java

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		long i = 1,fact = 1;
		while(in.hasNext()){
			double r = in.nextDouble();
			fact *= i;i++;
			System.out.print(r+fact + " ");
		}
	}
}