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 8358. Среднее значение — 1

28/05/2019 by Иван Киреев

Задача. Среднее значение — 1

Проект «Средний вес школьника школы» решили выполнить Мамед с Самедом. Что они будут делать с этим числом, они не раскрывают. Они попросили взвеситься всех учеников школы и занесли результаты в таблицу. Помогите им подсчитать средний вес учеников. Но они просят, чтобы учеников с самым большим и с самым маленьким весом не учитывать. Единственное их упущение, они не подсчитали общее количество учеников, но это, конечно, не помешает вам подсчитать то, что они просят.

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

В нескольких строках заданы веса учеников в килограммах, разделенных пробелами (одним или несколькими) или символом конца строки. Читать веса учеников до конца ввода.

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

Средний вес учеников школы без учета учеников с самым большим и самым маленьким весом. Ответ выводить с точностью до килограмм.

Тесты

№	Ввод	Вывод
1	40 23 27 59 68 23 84 27 53 46	46
2	21 22 23 24 25 26 27 28 20 30 29	25
3	10 20 10 20 10 20 10 20 11	11
4	60 45 70 90 55	62
5	80 80 80 70 83 90 90 90	81
6	50 90 70 70 70 70 70 70 70 70 74	70
7	70 70 70 70 70 70 70 70 70 70 70 70 70 60 50 90	69

Решение

Считываем все числа, считаем их количество и сумму. Затем из количества вычитаем количество минимальных и максимальных значений, а из суммы их соответственные произведения на эти числа.

Код через потоковую обработку

#include <iostream>
using namespace std;

int main() {
    int count = 0, min, max, cmin = 1, cmax = 1, weight;
    unsigned long long sum = 0;
    cin >> min >> max;
    if (min > max) swap(min, max);
    while (cin >> weight) {
        if (weight < min) {
            sum += min*cmin;
            min = weight;
            count += cmin;
            cmin = 1;
        } else if (weight == min) cmin++;
        else if (weight > max) {
            sum += max*cmax;
            max = weight;
            count += cmax;
            cmax = 1;
        } else if (weight == max) cmax++;
        else {
            sum += weight;
            count++;
        }
    }
    cout << sum / count + 1 * (sum % count > count / 2);
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int count = 0, min, max, cmin = 1, cmax = 1, weight;

unsigned long long sum = 0;

cin >> min >> max;

if (min > max) swap(min, max);

while (cin >> weight) {

if (weight < min) {

sum += min*cmin;

min = weight;

count += cmin;

cmin = 1;

} else if (weight == min) cmin++;

else if (weight > max) {

sum += max*cmax;

max = weight;

count += cmax;

cmax = 1;

} else if (weight == max) cmax++;

else {

sum += weight;

count++;

}

cout << sum / count + 1 * (sum % count > count / 2);

return 0;

}

Код через vector

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int count, elem;
    unsigned long long sum = 0;
    vector<int> vec;
    while (cin >> elem) vec.push_back((sum += elem, elem));
    sort (vec.begin(), vec.end());
    int i = 0;
    while (vec[i] == vec[0]) sum-=vec[i++];
    count = vec.size()-i;
    int j = vec.size()-1;
    while (vec[j] == vec[vec.size()-1]) sum-=vec[j--];
    j = vec.size()-1 - j;
    count -= j;
    cout << sum / count + 1 * (sum % count >= count / 2.);
    return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main() {

int count, elem;

unsigned long long sum = 0;

vector<int> vec;

while (cin >> elem) vec.push_back((sum += elem, elem));

sort (vec.begin(), vec.end());

int i = 0;

while (vec[i] == vec[0]) sum-=vec[i++];

count = vec.size()-i;

int j = vec.size()-1;

while (vec[j] == vec[vec.size()-1]) sum-=vec[j--];

j = vec.size()-1 - j;

count -= j;

cout << sum / count + 1 * (sum % count >= count / 2.);

return 0;

}

Код через map

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

int main() {
    int count = 0, elem;
    unsigned long long sum = 0;
    map<int, int> MAP;
    while (cin >> elem) {
        if (MAP.find(elem) == MAP.end()) MAP[elem] = 1;
        else MAP[elem]++;
        sum += elem;
        count++;
    }
    sum -= MAP.begin()->first * MAP.begin()->second + (--MAP.end())->first * (--MAP.end())->second;
    count -= MAP.begin()->second + (--MAP.end())->second;
    cout << sum / count + 1 * (sum % count > count / 2);
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

int count = 0, elem;

unsigned long long sum = 0;

map<int, int> MAP;

while (cin >> elem) {

if (MAP.find(elem) == MAP.end()) MAP[elem] = 1;

else MAP[elem]++;

sum += elem;

count++;

}

sum -= MAP.begin()->first * MAP.begin()->second + (--MAP.end())->first * (--MAP.end())->second;

count -= MAP.begin()->second + (--MAP.end())->second;

cout << sum / count + 1 * (sum % count > count / 2);

return 0;

}

Related Images:

e-olymp 1099. Говорящий Галчонок

27/03/2019 by Николай Козиний

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

Задача

«Ура-a-a! Заработало!» – радостно воскликнул Матроскин, услышав первую произнесенную Галчонком фразу.

Э.Успенский «Трое из Простоквашино»

Как Вам всем известно, Галчонок из мультфильма «Трое из Простоквашино» при стуке в дверь всегда спрашивал: «Кто там?». Статистика, как и вся математика, наука точная и она утверждает, что Галчонок мог запоминать как отдельные слова, так и целые предложения, только в том случае, если слово было произнесено не менее $n$ раз, а предложение – не менее чем $m$ раз $\left(n\leqslant m\right)$.

Ваша задача по заданному тексту определить количество слов и предложений, которые точно запомнил Галчонок.

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

В первой строке находится два натуральных числа $n$ и $m$ $\left(n , m \leqslant 100 \right)$. Во второй строке находится сам текст. Текст написан грамматически верно.

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

Два числа через пробел: сначала количество запомненных слов $s$, а потом количество запомненных предложений $p$.

Тесты

N,M	ТЕКСТ	ВЫХОДНЫЕ ДАННЫЕ
2,4	Blessed are the peacemakers, for they will be called children of God.	0 0
2,3	Kto tam? It is Pechkin. Kto tam? My name is Fedor. Kto tam? Pechkin!	4 1
1,1	Hey you! out there on the road Always doing what you’re told Can you help me Hey you! out there beyond the wall Breaking bottles in the hall Can you help me Hey you! don’t tell me there’s no hope at all Together we stand, divided we fall	33 3
2,2	Yes! No. Yes Yes! No Yes no no. No yes No No.	2 1
1,1	Workers of the world, unite!	5 1

Решение

#include <iostream>
#include <map>
using namespace std;
int main() {
    map <string,int> s;
    map <string,int> w;
    int n, m, a = 0,b = 0;
    cin >> n >> m;
    string word, sent;
    while(cin >> word){
        if(word.back() == ',')word.pop_back();
        sent = sent + word;
        if(word.back() == '.' or word.back() == '?' or word.back() == '!'){
            word.pop_back();
            sent.pop_back();
            if((++s[sent]) == m)a++;
            sent = "";
        }
        if((++w[word]) == n)b++;
    }
    cout << b << ' ' << a;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

map <string,int> s;

map <string,int> w;

int n, m, a = 0,b = 0;

cin >> n >> m;

string word, sent;

while(cin >> word){

if(word.back() == ',')word.pop_back();

sent = sent + word;

if(word.back() == '.' or word.back() == '?' or word.back() == '!'){

word.pop_back();

sent.pop_back();

if((++s[sent]) == m)a++;

sent = "";

}

if((++w[word]) == n)b++;

}

cout << b << ' ' << a;

}

Для решения данной задачи найдем все слова и все предложения в тексте. Слова будем считать одинаковыми, если они совпадают без знаков препинания в нижнем регистре они совпадают. Одинаковыми предложениями, соответственно, будем считать предложения, что совпадают без пробелов и знаков препинания. Увеличивая значения ассоциативных массивов, соответствующих предложению или слову на 1, увеличим на 1 значение b, если слова совпали больше чем $n$ раз и значение a, если предложения совпали больше чем $m$ раз.

Код задачи на ideone

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

Related Images:

e-olymp 8515. Homo or Hetero?

12/12/2018 by Владислав Бебик

Task

Consider a list of numbers with two operations:
$\cdot$ insert number— adds the specified number to the end of the list.
$\cdot$ delete number— removes the first occurrence of the specified number from the list. If the list does not contain the number specified, no changes are performed.

For example: the result of the insertion of a number $4$ to the list $[1,2,1]$ is the list $[1,2,1,4]$. If we delete the number $1$ from this list, we get the list $[2,1,4]$, but if we delete the number $3$ from the list $[1,2,1,4]$,the list stays unchanged.

The list is homogeneous if it contains at least two equal numbers and the list is heterogeneous if it contains at least two different numbers. For example: the list $[2,2]$ is homogeneous, the list $[2,1,4]$ is heterogeneous, the list $[1,2,1,4]$ is both, and the empty list is neither homogeneous, nor heterogeneous.

Write a program that handles a number of the operations insert and delete on the empty list and determines list’s homogeneity and heterogeneity after each operation.

Input

The first line of the input file contains an integer number $N$ $(1 \leq N \leq 10^{5})$ — the number of operations to handle. Following $N$ lines contain one operation description each. The operation description consists of a word “insert” or “delete”, followed by an integer number $K$ $(-10^{9} \leq K \leq 10^{9})$ — the operation argument.

Output

For each operation output a line, containing a single word, describing the state of the list after the operation:

$\cdot$ “both” — if the list is both homogeneous and heterogeneous.
$\cdot$ “homo” — if the list is homogeneous, but not heterogeneous.
$\cdot$ “hetero” — if the list is heterogeneous, but not homogeneous.
$\cdot$ “neither” — if the list is neither homogeneous nor heterogeneous.

Tests

#	Input	Output
1	11 $insert$ 1 $insert$ 2 $insert$ 1 $insert$ 4 $delete$ 1 $delete$ 3 $delete$ 2 $delete$ 1 $insert$ 4 $delete$ 4 $delete$ 4	$neither$ $hetero$ $both$ $both$ $hetero$ $hetero$ $hetero$ $neither$ $homo$ $neither$ $neither$
2	15 $insert$ -50 $insert$ -2 $insert$ 1 $insert$ 4 $delete$ 1 $delete$ 3 $delete$ -2 $delete$ -50 $insert$ 4 $delete$ 4 $delete$ 4 $insert$ 100 $insert$ -150 $delete$ -150 $delete$ 100	$neither$ $hetero$ $hetero$ $hetero$ $hetero$ $hetero$ $hetero$ $neither$ $homo$ $neither$ $neither$ $neither$ $hetero$ $neither$ $neither$

Code 1

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

struct Key {
    int a;
    int b;
};
Key x[200000];

int main() {
    int n,k,i,i1,j1=0,j2=0,p,p1=0,p2=0,q,l,m,r;
    char s[10];
    cin >> n;
    char y[n]; int z[n]; int u[n];
    for (i=0; i<n; i++) {
        cin >> s >> k;
        y[i]=s[0]; z[i]=k;
        if (s[0]=='i') {
            u[j1]=k; j1++;
        }
    }
    sort(u,u+j1);
    for (i=0; i<j1; i++) {
        if (u[i]!=u[i+1]) {
            x[j2].a=u[i]; j2++;
        }
    }
    for (i=0; i<n; i++) {
        p=0; l=0; r=j2-1;
        while (l<=r && p==0) {
            m=(l+r)/2;
            if (z[i]==x[m].a) {
                i1=m; p=1;
            } else if (z[i]<x[m].a) r=m-1;
            else l=m+1;
        }
        if (p==1) {
            q=x[i1].b;
            if (y[i]=='i') {
                q++;
                if (q==1) p1++;
                if (q==2) p2++;
                x[i1].b=q;
            } else if (q>0) {
                q--;
                if (q==0) p1--;
                if (q==1) p2--;
                x[i1].b=q;
            }
        }
        if (p1>=2 && p2>=1) cout << "both" << endl;
        else if (p1<2 && p2>=1) cout << "homo" << endl;
        else if (p1>=2 && p2<1) cout << "hetero" << endl;
        else cout << "neither" << endl;
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

struct Key {

int a;

int b;

};

Key x[200000];

int main() {

int n,k,i,i1,j1=0,j2=0,p,p1=0,p2=0,q,l,m,r;

char s[10];

cin >> n;

char y[n]; int z[n]; int u[n];

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

cin >> s >> k;

y[i]=s[0]; z[i]=k;

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

u[j1]=k; j1++;

}

sort(u,u+j1);

for (i=0; i<j1; i++) {

if (u[i]!=u[i+1]) {

x[j2].a=u[i]; j2++;

}

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

p=0; l=0; r=j2-1;

while (l<=r && p==0) {

m=(l+r)/2;

if (z[i]==x[m].a) {

i1=m; p=1;

} else if (z[i]<x[m].a) r=m-1;

else l=m+1;

}

if (p==1) {

q=x[i1].b;

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

q++;

if (q==1) p1++;

if (q==2) p2++;

x[i1].b=q;

} else if (q>0) {

q--;

if (q==0) p1--;

if (q==1) p2--;

x[i1].b=q;

}

if (p1>=2 && p2>=1) cout << "both" << endl;

else if (p1<2 && p2>=1) cout << "homo" << endl;

else if (p1>=2 && p2<1) cout << "hetero" << endl;

else cout << "neither" << endl;

}

return 0;

}

Code 2 (map)

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

int main() {
    int n,k,p1=0,p2=0,q;
    char s[10];
    map <int,int> x;
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> s >> k;
        q=x[k];
        if (s[0]=='i') {
            q++;
            if (q==1) p1++;
            if (q==2) p2++;
            x[k]=q;
        } else if (q>0) {
            q--;
            if (q==0) p1--;
            if (q==1) p2--;
            x[k]=q;
        }
        if (p1>=2 && p2>=1) cout << "both" << endl;
        else if (p1<2 && p2>=1) cout << "homo" << endl;
        else if (p1>=2 && p2<1) cout << "hetero" << endl;
        else cout << "neither" << endl;
    }
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

int n,k,p1=0,p2=0,q;

char s[10];

map <int,int> x;

cin >> n;

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

cin >> s >> k;

q=x[k];

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

q++;

if (q==1) p1++;

if (q==2) p2++;

x[k]=q;

} else if (q>0) {

q--;

if (q==0) p1--;

if (q==1) p2--;

x[k]=q;

}

if (p1>=2 && p2>=1) cout << "both" << endl;

else if (p1<2 && p2>=1) cout << "homo" << endl;

else if (p1>=2 && p2<1) cout << "hetero" << endl;

else cout << "neither" << endl;

}

return 0;

}

Solution

Let’s memorize two numbers on each step: how many of different numbers and different pairs of identical numbers in a one-dimensional array. If there are more than one different numbers in the array and more than zero different pairs of the same numbers, then print "both". If the sum of different numbers in the array is less than two and different pairs of identical numbers are more than zero, then we enter "homo". If there are more than one different numbers in the array and less than one different pairs of the same numbers, then enter "hetero". In other cases, we enter "neither". In the last case, when an array is $0$ numbers or $1$ number.

Links

Related Images:

Сумма делителей — 2

12/07/2018 by Алиса Ворохта

Задача

Профессор из тридевятого царства решил, что посчитать сумму делителей числа $n$ до $10^{10}$ сможет любой троечник, поэтому усложнил для Кости задачу, дав числа с большим количеством цифр. Но наш герой не хотел сдаваться, уж больно он хотел стать отличником.
Костя очень просит Вас помочь ему в этом деле, ведь он помнит, как успешно Вы справились с предыдущей задачей.

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

Одно целое число $n \left(1 \leqslant n < 10^{15}\right).$

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

Выведите сумму делителей числа $n.$

Тесты

Входные данные	Выходные данные
$100000000000031$	$100000000000032$
$10000019$	$10000020$
$400001520001444$	$700002730002667$
$9$	$13$
$304250263527210$	$1281001468723200$
$94083986096100$	$457766517350961$
$1234567898765$	$1517681442816$
$100000000000000$	$249992370597277$
$562949953421312$	$1125899906842623$
$81795$	$161280$
$9999999999999$	$14903272088640$
$997$	$998$
$1325$	$1674$
$2468013$	$3290688$
$951641320$	$2447078400$
$71675429738641$	$71695352830464$
$1100000000033$	$1200000000048$
$6300088$	$11859480$
$98$	$171$
$9102837465$	$15799834440$

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

#include <iostream>
#include <map>
using namespace std;
int main ()
{
    long long n, sumOfDivisors = 1;
    cin >> n;
    map<long long, long long> primeDivInPow;
    for(long long i = 2; i * i <= n; i++){
        while(n % i == 0){
            if(primeDivInPow.find(i) == primeDivInPow.end()){
                primeDivInPow[i] = 1;
            }
            primeDivInPow[i] *= i;
            n /= i;
        }
    }
    if(n != 1){
        primeDivInPow[n] = n;
    }
    for(map<long long, long long>::iterator p = primeDivInPow.begin(); p != primeDivInPow.end(); p++){
        sumOfDivisors *= (p -> second - 1) / (p -> first - 1) + p -> second;
    }
    cout << sumOfDivisors;
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main ()

{

long long n, sumOfDivisors = 1;

cin >> n;

map<long long, long long> primeDivInPow;

for(long long i = 2; i * i <= n; i++){

while(n % i == 0){

if(primeDivInPow.find(i) == primeDivInPow.end()){

primeDivInPow[i] = 1;

}

primeDivInPow[i] *= i;

n /= i;

}

if(n != 1){

primeDivInPow[n] = n;

}

for(map<long long, long long>::iterator p = primeDivInPow.begin(); p != primeDivInPow.end(); p++){

sumOfDivisors *= (p -> second - 1) / (p -> first - 1) + p -> second;

}

cout << sumOfDivisors;

return 0;

}

Решение задачи

Пусть $n$ имеет каноническое разложение $n = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots p_k^{\alpha_k},$ где $p_1 < p_2 < \ldots <p_k$ — простые делители числа $n$, $\alpha_1, \alpha_2,\ldots, \alpha_k \in \mathbb {N}$. Тогда сумма натуральных делителей числа $n$ равна $\sigma\left(n\right) = \left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\times$$\times\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right).$
Доказательство.
Рассмотрим произведение:
$\left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right)$
Если раскрыть скобки, то получим сумму членов ряда:
$p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\ldots\cdot p_k^{\beta_k},$ где $0\leqslant\beta_m\leqslant\alpha_m \left(m = 1, 2, \ldots, k\right)$
Но такие члены являются делителями $n$, причем каждый делитель входит в сумму только один раз. Поэтому рассмотренное нами произведение равно сумме всех делителей $n,$ т.е. равно $\sigma\left(n\right).$ Итак, $\sigma\left(n\right)$ можно вычислить по нашей формуле. С другой стороны, каждая сумма $1 + p_m + p_m^2+\ldots+p_m^{\alpha_m}$ является суммой геометрической прогрессии с первым членом $1$ и знаменателем $p_m$. Поэтому иначе данную формулу можно переписать так:
$$\sigma\left(n\right) = \frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdot\frac{p_2^{\alpha_2+1}-1}{p_2-1}\cdot\ldots\cdot\frac{p_k^{\alpha_k+1}-1}{p_k-1}.$$
Для того, чтобы не вычислять $p_k^{\alpha_k+1}$, перепишем данную формулу в следующем виде:
$$\sigma\left(n\right) = \left(\frac{p_1^{\alpha_1}-1}{p_1-1}+p_1^{\alpha_1}\right)\cdot\left(\frac{p_2^{\alpha_2}-1}{p_2-1}+p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(\frac{p_k^{\alpha_k}-1}{p_k-1}+p_k^{\alpha_k}\right).$$

Ссылки

Код решения

Related Images:

Сумма делителей

11/07/2018 by Алиса Ворохта

Задача

Жил-был в тридевятом государстве мальчик по имени Костя. Он был старательным учеником и получал исключительно высокие баллы по всем предметам. И вот наш герой очень захотел стать отличником, но ему не хватало нескольких баллов по алгебре. Для того чтобы их набрать, профессор дал Косте следующую задачу:
Найти сумму делителей данного числа $n.$
Костя обратился к Вам как к опытному программисту, который знает алгебру, с просьбой о помощи решить данную задачу.

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

Одно целое число $n \left(1 \leqslant n < 10^{10}\right).$

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

Выведите сумму делителей числа $n.$

Тесты

Входные данные	Выходные данные
$12$	$28$
$239$	$240$
$1234$	$1854$
$6$	$12$
$1000000007$	$1000000008$
$44100$	$160797$
$223092870$	$836075520$
$2147483648$	$4294967295$
$678906$	$1471002$
$1111111$	$1116000$
$9876543210$	$27278469036$
$99460729$	$99470703$
$5988$	$14000$
$1$	$1$
$1348781387$	$1617960960$
$135792$	$406224$
$5402250$	$17041284$
$375844500$	$1259767236$
$1000000000$	$2497558338$
$2357947691$	$2593742460$

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

#include <iostream>
#include <map>
using namespace std;
int main ()
{
    long long n, sumOfDivisors = 1;
    cin >> n;
    map<long long, long long> primeDivInPow;
    for(long long i = 2; i * i <= n; i++){
        while(n % i == 0){
            if(primeDivInPow.find(i) == primeDivInPow.end()){
                primeDivInPow[i] = 1;
            }
            primeDivInPow[i] *= i;
            n /= i;
        }
    }
    if(n != 1){
        primeDivInPow[n] = n;
    }
    for(map<long long, long long>::iterator p = primeDivInPow.begin(); p != primeDivInPow.end(); p++){
        sumOfDivisors *= (p -> second * p -> first - 1) / (p ->first - 1);
    }
    cout << sumOfDivisors;
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main ()

{

long long n, sumOfDivisors = 1;

cin >> n;

map<long long, long long> primeDivInPow;

for(long long i = 2; i * i <= n; i++){

while(n % i == 0){

if(primeDivInPow.find(i) == primeDivInPow.end()){

primeDivInPow[i] = 1;

}

primeDivInPow[i] *= i;

n /= i;

}

if(n != 1){

primeDivInPow[n] = n;

}

for(map<long long, long long>::iterator p = primeDivInPow.begin(); p != primeDivInPow.end(); p++){

sumOfDivisors *= (p -> second * p -> first - 1) / (p ->first - 1);

}

cout << sumOfDivisors;

return 0;

}

Решение задачи

Ссылки

Код решения

Related Images:

e-olymp 1477. Наибольшее среднее

25/06/2018 by Андрей Лисовой

Задача

На доске выписаны $n$ целых чисел. Все они пронумерованы от $1$ до $n.$ Разрешается выбрать два произвольных числа, вытереть оба с доски и написать новое число, равное их среднему арифметическому. Новое число получает номер $n + 1.$ После этого снова выбираются два числа и вместо них записывается их среднее арифметическое, которому дается номер $n + 2$ и т.д. Так продолжается до тех пор, пока на доске не останется только одно число. Чем больше будет это число, тем более успешной считается последовательность действий.

Определите порядок действий, который приводит к максимально возможному числу в конце.

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

В первой строке записано целое число $n$ $(1 \leqslant n \leqslant 10^5).$ Во второй строке задаются $n$ целых чисел, которые были первоначально записаны на доске. Все числа лежат в диапазоне от $-10000$ до $10000.$

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

Выведите $n — 1$ строку, в каждой из которых должны быть записаны по два целых числа, определяющие номера тех чисел, которые выбираются на соответствующем шаге.

Тесты

Входные данные	Выходные данные
$3$ $7\;2\;4$	$2\;3$ $1\;4$
$4$ $6\;2\;7\;1$	$2\;4$ $1\;5$ $3\;6$
$4$ $12\;4\;7\;2$	$2\;4$ $3\;5$ $1\;6$
$5$ $234\;2\;5\;54\;5$	$2\;3$ $5\;6$ $4\;7$ $1\;8$

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

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

int main() {
    multimap <double,int> multimap;
    int n;
    cin >> n;
    int element;
    for(int i = 1; i <= n; i++) {
        cin >> element;
        multimap.insert(pair<double,int>(element, i));
    }
    while(multimap.size() != 1) {
        pair<double,int> x = *multimap.begin();
        multimap.erase(multimap.begin());
        pair<double,int> y = *multimap.begin();
        multimap.erase(multimap.begin());
        cout << min(x.second, y.second) << " " << max(x.second, y.second) << endl;
        multimap.insert(pair<double,int>((x.first + y.first) / 2, ++n));
    }
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

multimap <double,int> multimap;

int n;

cin >> n;

int element;

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

cin >> element;

multimap.insert(pair<double,int>(element, i));

}

while(multimap.size() != 1) {

pair<double,int> x = *multimap.begin();

multimap.erase(multimap.begin());

pair<double,int> y = *multimap.begin();

multimap.erase(multimap.begin());

cout << min(x.second, y.second) << " " << max(x.second, y.second) << endl;

multimap.insert(pair<double,int>((x.first + y.first) / 2, ++n));

}

return 0;

}

Решение задачи

Для решения задачи создаем multimap, затем циклом вводим туда пары, где первое значение — это число с потока, а второе — его номер. После этого мы сохраняем первые два значения из multimap, выводим их номера и находим среднее число. Добавляем в multimap пару, где первое значение — это найденное средние двух чисел, а второе — номер. В конце концов мы получим, что в multimap будет всего одна пара и цикл остановит свою работу. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com

Related Images:

e-olymp 2892. Сумма значений

24/06/2018 by Костя Григорян

Задача

Найдите сумму значений функции
$$f \left(x \right ) = x + \frac{1}{x}$$
в нескольких целых точках.

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

В первой строке задано количество точек $n$ $\left (1 \leqslant n \leqslant 50 \right ).$ В следующей строке заданы $n$ целых чисел $x_1, x_2, …, x_n$ — точки, значения функции в которых нужно просуммировать $\left (0 \leqslant \left |x_i \right | \leqslant 10^9 \right ).$

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

Выведите одно число — сумму значений функции $f \left(x \right )$ в заданных точках. Ответ считается правильным, если абсолютная или относительная погрешность не превышает $10^{-9}.$

Тесты

Входные данные	Выходные данные
$3$	$7.833333333333333$
$1 \ 2 \ 3$
$2$	$0$
$1 \ -1$
$5$	$4.265140415140415$
$10 \ -13 \ 21 \ -18 \ 4$
$1$	$10.1$
$10$

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

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

int main() {
    vector <long double> x;
    int n;
    long double ans=0;
    cin >> n;
    x.resize(n);
    for(int i=0; i<n; i++) 
    {
        cin >> x[i];
    }
    for(int i=0; i<n; i++)
    {
        ans+=x[i]+1.0/x[i];
    }
    cout.precision(15);
    cout << fixed << ans;
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <long double> x;

int n;

long double ans=0;

cin >> n;

x.resize(n);

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

{

cin >> x[i];

}

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

{

ans+=x[i]+1.0/x[i];

}

cout.precision(15);

cout << fixed << ans;

return 0;

}

Решение задачи

Мы просто суммируем значения функции в каждой точке. Тут использовали тип long double для точек и значений функции для меньшей погрешности.

Ссылки

Условие задачи на e-olymp
Код решения

Related Images:

e-olymp 1225. Черный Ящик

18/05/2018 by Кирилл Волков

Задача

Черный Ящик представляет собой примитивную базу даных. Он может хранить массив целых чисел, а также имеет специальную переменную $i$. В начальный момент Черный Ящик пустой, переменная $i$ равна $0$. Черный Ящик обрабатывает последовательность команд (транзакций). Существует два типа транзакций:
ADD(x): добавить элемент x в Черный Ящик;
GET: увеличить $i$ на $1$ и вывести $i$-ый минимальный элемент среди всех чисел, находящихся в Черном Ящике.
Помните, что $i$-ый минимальный элемент находится на $i$-ом месте после того как все элементы Черного Ящика будут отсортированы в неубывающем порядке.
Рассмотрим работу черного ящика на примере:

№	Транзакция	$i$	Содержимое Черного Ящика после транзакции	Ответ
1	ADD(3)	0	3
2	GET	1	3	3
3	ADD(1)	1	1, 3
4	GET	2	1, 3	3
5	ADD(-4)	2	-4, 1, 3
6	ADD(2)	2	-4, 1, 2, 3
7	ADD(8)	2	-4, 1, 2, 3, 8
8	ADD(-1000)	2	-1000, -4, 1, 2, 3, 8
9	GET	3	-1000, -4, 1, 2, 3, 8	1
10	GET	4	-1000, -4, 1, 2, 3, 8	2
11	ADD(2)	4	-1000, -4, 1, 2, 2, 3, 8

Необходимо разработать эффективный алгоритм выполнения заданной последовательности транзакций. Максимальное количество транзакций ADD и GET равно $30000$ (каждого типа).
Опишем последовательность транзакций двумя целочисленными массивами:

$A_1, \ A_2, \ldots , \ A_m:$ последовательность элементов, которая будет добавляться в Черный Ящик. Элементами являются целые числа, по модулю не большие $2 000 000 000$, $m \leq 30000$. Для выше описанного примера $A = \left (3, 1, -4, 2, 8, -1000, 2 \right).$
$u_1, \ u_2, \ldots , \ u_n:$ последовательность указывает на количество элементов в Черном Ящике в момент выполнения первой, второй, … $n$-ой транзакции GET. Для выше описанного примера $u = \left (1, 2, 6, 6 \right ).$

Работа Черного Ящика предполагает, что числа в последовательности $u_1, \ u_2, \ldots , \ u_n$ отсортированы в неубывающем порядке, $n \leq m$, а для каждого $p \left (1 \leq p \leq n \right )$ имеет место неравенство $p \leq u(p) \leq m$. Это следует из того, что для $p$-го элемента последовательности $u$ мы выполняем GET транзакцию, которая выводит $p$-ый минимальный элемент из набора чисел $A_1, \ A_2, \ldots , \ A_{u_p}$.

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

Состоит из следующего набора чисел: $m, \ n, \ A_1, \ A_2, \ldots , \ A_m, \ u_1, \ u_2, \ldots , \ u_n.$ Все числа разделены пробелами и (или) символом перевода на новую строку.

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

Вывести ответы Черного Ящика на последовательность выполненных транзакций. Каждое число должно выводиться в отдельной строке.

Тесты

Входные данные	Выходные данные
7 4 3 1 -4 2 8 -1000 2 1 2 6 6	3 3 1 2
8 3 5 8 3 7 3 5 7 0 2 3 3	5 5 8
10 4 6 3 7 3 8 4 7 4 6 15 4 6 8 9	3 3 4 4
5 5 1 2 3 4 5 1 2 3 4 5	1 2 3 4 5
11 5 4 6 8 9 5 3 6 8 10 12 13 6 7 8 9 10	3 4 5 6 6

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

#include <iostream>
#include <vector>
#include <set>
#include <climits>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int m, n;
    cin >> m >> n;
    vector<int> nums(m);
    for(int i = 0; i < m; i++){
        cin >> nums[i];
    }
    multiset<int> blackBox;
    blackBox.insert(INT_MAX);
    auto it = blackBox.begin();
    for(int i = 0; i < n; i++){
        int req;
        cin >> req;
        for(int j = blackBox.size() - 1; j < req; j++){
            blackBox.insert(nums[j]);
            if(nums[j] < *it) it--;
        }
        cout << *it << endl;
        it++;
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <set>

#include <climits>

using namespace std;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(0);

int m, n;

cin >> m >> n;

vector<int> nums(m);

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

cin >> nums[i];

}

multiset<int> blackBox;

blackBox.insert(INT_MAX);

auto it = blackBox.begin();

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

int req;

cin >> req;

for(int j = blackBox.size() - 1; j < req; j++){

blackBox.insert(nums[j]);

if(nums[j] < *it) it--;

}

cout << *it << endl;

it++;

}

return 0;

}

Решение задачи

Пусть nums — множество всех элементов последовательности $A_n$. blackBox — мультимножество, представляющее собой описанный в задаче Черный Ящик на $i$-ом запросе. Изначально blackBox содержит «бесконечность» для избежания выхода за пределы. it — итератор, указывающий на $i$-ый минимальный элемент blackBox. Изначально данный итератор указывает на первый элемент множества. На $i$-ом запросе в blackBox копируются элементы массива nums от $u_{i-1}-1$-го до $u_{i}-1$-го (примем, что $u_0$ = 0). Тогда при добавлении в blackBox элемента, меньшего, чем тот, на который в данный момент указывает итератор it — $min_i$, $i$-ым минимальным элементом, становится элемент, предшествующий $min_i$. После выполнения ответа на $i$-ый запрос итератор должен указывать на $i+1$-ый минимальный элемент, то есть на элемент, следующий за $min_i$.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp
Код решения на Ideone

Related Images:

e-olymp 161. Роботы

01/03/2018 by Костя Григорян

Задача

На некотором заводе решили модернизировать производство и закупили для этого роботов. Так как для обработки детали требовалось выполнение двух операций, роботы также были двух типов: первую операцию выполняли роботы типа $A$, а вторую – роботы типа $B$. Чтобы сэкономить на покупке роботов, было решено купить не новых роботов последней модели, а уже бывших в употреблении. В результате, время, которое разные роботы тратили на выполнение одной и той же операции, существенно различалось, что привело к трудностям в планировании работ.

Составьте программу, которая по заданному набору роботов обоих типов определяет, за какое минимальное время они смогут обработать определенное количество деталей.

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

В первой строке натуральное число $N$, $1 ≤ N ≤ 100000$ – количество деталей, которое необходимо обработать.

Во второй строке натуральное число $N_a$, $1 ≤ N_a ≤ 1000$ – количество роботов, выполняющих первую операцию.

В третьей строке через пробел $N_a$ натуральных чисел $A_{i}$, $1 ≤ A_{i} ≤ 100$ – время, которое тратит $i$-ый робот типа $A$ на выполнение операции.

В четвертой строке натуральное число $N_b$, $1 ≤ N_b ≤ 1000$ – количество роботов, выполняющих вторую операцию.

В пятой строке через пробел $N_b$ натуральных чисел $B_{i}$, $1 ≤ B_{i} ≤ 100$ – время, которое тратит $i$-ый робот типа $B$ на выполнение операции.

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

В первой строке одно целое число – минимальное время, за которое все $N$ деталей будут обработаны сначала роботом типа $A$, а потом роботом типа $B$. Временем передачи детали от робота типа $A$ роботу типа $B$ пренебречь.

Тесты

Входные данные	Выходные данные
[latex]6[/latex]	[latex]9[/latex]
[latex]3[/latex]
[latex]1\, 3\, 2[/latex]
[latex]2[/latex]
[latex]2\, 3[/latex]
[latex]2[/latex]	[latex]5[/latex]
[latex]2[/latex]
[latex]3\, 2[/latex]
[latex]2[/latex]
[latex]2\, 3[/latex]
[latex]5[/latex]	[latex]41[/latex]
[latex]4[/latex]
[latex]84\, 50\, 50\ 8[/latex]
[latex]2[/latex]
[latex]1\, 21[/latex]
[latex]100[/latex]	[latex]100[/latex]
[latex]2[/latex]
[latex]1\, 50[/latex]
[latex]4[/latex]
[latex]1\, 2\, 3\, 4[/latex]

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

#include <iostream>
#include <set>
#include <climits>
using namespace std;

int inf = INT_MAX;

int main() {
    cin.sync_with_stdio(false);
    int n;
    cin >> n;
    int na;
    cin >> na;
    multiset<pair<int, int> > s;
    int a[na];
    int resa[n];
    for(int i=0; i<na; i++)
    {
        cin >> a[i];
        s.insert({a[i], a[i]});
    }
    for(int i=0; i<n; i++)
    {
        auto it=s.begin();
        int val=it->first;
        int t=it->second;
        s.erase(it);
        s.insert({val+t, t});
        resa[i]=val;
    }
    int nb;
    cin >> nb;
    int b[nb];
    for(int i=0; i<nb; i++)
    {
        cin >> b[i];
    }
    multiset<pair<int, int> > q;
    long long l=resa[n-1], r=10000100;
    while(l<r)
    {
        int w=0;
        int m=(l+r)/2;
        for(int i=0; i<nb; i++)
        {
            q.insert({b[i], b[i]});
        }
        q.insert({inf, inf});
        for(int i=n-1; i>=0; i--)
        {
            int y=m-resa[i];
            auto x=q.begin();
            if(y<(x->first))
            {
                w++;
                break;
            }
            else{
                auto it=q.lower_bound({y, -1});
                int z=it->first;
                if(z>y)
                    it--;
                int val=it->first;
                int t=it->second;
                q.erase(it);
                q.insert({val+t, t});
            }
        }
        if(w==0)
            r=m;
        else
            l=m+1;
        q.clear();  
    }
    cout << l;
    return 0;
}

#include <iostream>

#include <set>

#include <climits>

using namespace std;

int inf = INT_MAX;

int main() {

cin.sync_with_stdio(false);

int n;

cin >> n;

int na;

cin >> na;

multiset<pair<int, int> > s;

int a[na];

int resa[n];

for(int i=0; i<na; i++)

{

cin >> a[i];

s.insert({a[i], a[i]});

}

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

{

auto it=s.begin();

int val=it->first;

int t=it->second;

s.erase(it);

s.insert({val+t, t});

resa[i]=val;

}

int nb;

cin >> nb;

int b[nb];

for(int i=0; i<nb; i++)

{

cin >> b[i];

}

multiset<pair<int, int> > q;

long long l=resa[n-1], r=10000100;

while(l<r)

{

int w=0;

int m=(l+r)/2;

for(int i=0; i<nb; i++)

{

q.insert({b[i], b[i]});

}

q.insert({inf, inf});

for(int i=n-1; i>=0; i--)

{

int y=m-resa[i];

auto x=q.begin();

if(y<(x->first))

{

w++;

break;

}

else{

auto it=q.lower_bound({y, -1});

int z=it->first;

if(z>y)

it--;

int val=it->first;

int t=it->second;

q.erase(it);

q.insert({val+t, t});

}

if(w==0)

r=m;

else

l=m+1;

q.clear();

}

cout << l;

return 0;

}

Решение задачи

Решение состоит из двух этапов.
Найдем минимальное время, которое понадобится роботам первого типа, чтобы завершить обработку всех деталей. Для каждой детали, мы берем робота с минимальным временем завершения обработки этой детали и обновляем его время на время обработки им одной детали.
Найдем теперь общее минимальное время работы роботов, требуемое для завершения обработки всех деталей. Пусть нам уже известно, за какое время обрабатывают роботы первого типа каждую из данных деталей. Очевидно, что если возможно выполнить работу за $t$, то возможно выполнить работу и за $t+1$, а также, если невозможно выполнить работу за $t$, то невозможно выполнить работу за $t-1$. Следовательно, для решения данной задачи можно применить бинарный поиск по ответу. Применим бинарный поиск по ответу, рассматривая детали по мере их поступления с конца: роботы могут выполнить работу за $T$, если для каждой детали существует такой робот второго типа, который выполнит работу за $T_{2}$, такое, что $ T_{1}+T_{2}$ $\leqslant T$, где $T_{1}$ – время, за которое эту деталь выполнит робот первого типа.
Теперь оценим сложность работы алгоритма. Бинарный поиск работает за $O(\log n)$. Для каждого этапа бинарного поиска мы обрабатываем $n$ деталей. Далее для каждой из $n$ деталей работает логарифмическая вставка в мультисет. Получаем, что асимптотическая вычислительная сложность алгоритма $O(n\, \log^2n)$.

Ссылки

Условие задачи на e-olymp
Код решения
Видеозапись разбора задачи Евгением Задорожным на зимней школе по алгоритмам и программированию в Одесском национальном университете иемни И.И.Мечникова:

Related Images:

e-olymp 1868. Функция

25/12/2017 by Иван Василевский

Условие задачи
Вычислите функцию:

[latex]f(n)=\begin{cases} 1, \text{ если } n \leq 2 \\ f(\lfloor \frac{6\cdot n}{7} \rfloor)+f(\lfloor \frac{2\cdot n}{3} \rfloor), \text{ если } n \mod \; 2 = 1 \\ f(n-1)+f(n-3), \text{ если } n \mod \; 2 = 0 \end{cases}[/latex]

Входные данные
Одно натуральное число [latex] n \; [/latex] [latex](1 \leq n \leq 10^{12}) [/latex].

Выходные данные
Значение [latex] f(n) [/latex], взятое по модулю [latex] 2^{32} [/latex].
Continue reading →

Related Images:

e-olymp 1072. Химические реакции

04/03/2016 by Сплошнов Кирилл

Условие

Задача взята с сайта e-olymp, полное условие можно прочитать здесь.

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

В первой строке находится формула — левая часть уравнения, во второй- одно число [latex]N (1 \leq N \leq 10)[/latex] — количество рассматриваемых правых частей, в каждой из последующих [latex]N[/latex] строк — одна формула — предполагаемая правая часть уравнения.

Длина формулы не превосходит [latex]100[/latex] символов, каждый отдельный химический элемент встречается всего не более [latex]10000[/latex] раз в каждой формуле.

(Примечание: понятие формулы в данном алфавите можно прочитать по ссылке выше.)

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

Для каждой из [latex]N[/latex] заданных строк вывести одну строку вида

формула левой части==формула правой части

если общее количество вхождений каждого отдельного химического элемента в левую часть равно общему числу вхождений этого химического элемента в правую часть. В противном случае выведите:

формула левой части!=формула правой части

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

Решение (вспомогательные функции)

Так как задача достаточно объемная, напишем ряд вспомогательных функций:

Определяет, является ли символ цифрой.

bool isDigit(char c);

1

bool isDigit(char c);
Определяет, является ли символ буквой в верхнем регистре.

bool isUpperCaseLetter(char c);

1

bool isUpperCaseLetter(char c);
Определяет, является ли символ буквой в нижнем регистре.

bool isLowerCaseLetter(char c);

1

bool isLowerCaseLetter(char c);
Будем хранить содержимое формулы используя структуру map (карта), ключами будут выступать названия элементов (строки), значениями — количества их вхождений. Если элемента в карте нет, добавляем пару <элемент, кол-во>, иначе — прибавляем к старом числу вхождений новое. За это отвечает следующая функция.

void update(map<string, int> &map, string key, int value);

1

void update(map<string, int> &map, string key, int value);
Для простоты разобьем формулу на подформулы (по знаку [latex]+[/latex], если он встречается), и будем работать с каждой формулой по отдельности. Функция разбивает строку на подстроки по знаку [latex]+[/latex] и заполняет ими вектор [latex]storage[/latex] (так как мы не знаем кол-во подформул заранее, вектор предпочтительнее массива).

void split(string formula, vector<string> &storage);

1

void split(string formula, vector<string> &storage);
По условию, перед каждой подформулой может идти множитель, относящейся ко всей подформуле. Функция возвращает множитель ( [latex]1[/latex], если множитель не записан явно).

int getMultiplier(string formula);

1

int getMultiplier(string formula);
Основная функция. Добавляет в карту [latex]content[/latex] содержимое подформулы.

void getContent(string formula, int multiplier, map<string, int> &content);

1

void getContent(string formula, int multiplier, map<string, int> &content);
Обрабатывает формулу. Просто вызывает функции №[latex]6[/latex] и №[latex]7[/latex] по очереди для каждой из подформул (элементов из [latex]subformulas[/latex]).

void process(vector<string> subformulas, map<string, int> &content);

1

void process(vector<string> subformulas, map<string, int> &content);

Решение (основной алгоритм)

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

void getContent(string formula, int multiplier, map<string, int> &content);

1	void getContent(string formula, int multiplier, map<string, int> &content);

Тут:

[latex]formula[/latex] — подформула обрабатываемой формулы (без общего множителя);
[latex]multiplier[/latex] — множитель, определяется предыдущей функцией, перед вызовом данной;
[latex]content[/latex] — карта, куда записываются элементы всех подформул текущей формулы (доступ осуществляется по адресу).

Алгоритм разделяется на 2 случая, в зависимости от наличия скобок. Предположим, скобок в подформуле (далее — просто формуле) нет. Заведем переменные [latex]name[/latex] (название элемента. тип string) и [latex]coefficient[/latex] (задний коэффициент, тип string). Тогда, проходя по порядку по символам формулы, будем выполнять следующие действия в зависимости от текущего символа([latex]c[/latex]):

[latex]c[/latex] — цифра: добавляем его в конец строки [latex]coefficient[/latex];
[latex]c[/latex] — буква в нижнем регистре: добавляем его в конец строки [latex]name[/latex];
[latex]c[/latex] — буква в верхнем регистре: если строка [latex]name[/latex] — пустая (первый элемент в формуле), то добавляем его в конец строки [latex]name[/latex]. Иначе, сперва обнуляем [latex]name[/latex], потом добавляем. Тогда, если строка [latex]coefficient[/latex] — пустая, присваиваем [latex]coefficient=[/latex]»[latex]1[/latex]». Получаем количество вхождений элемента как [latex]multiplier*stoi(coefficient)[/latex], где stoi() — стандартная функция, преобразующая число к строке. Затем добавляем в карту элемент и полученное кол-во вхождений.

update(content, name, multiplier * stoi(coefficient));

140

update(content, name, multiplier * stoi(coefficient));

(Примечание: пункт [latex]3[/latex] для последнего элемента (кроме обновления значения [latex]name[/latex]) придется повторить отдельно.)

update(content, name, multiplier * stoi(coefficient));

153	update(content, name, multiplier * stoi(coefficient));

Если же в формуле имеются скобки, то:

Находим первую открывающую скобку.
Находим соответствующую ей закрывающую скобку.
Для выражения в скобках вычисляем задний коэффициент (см. код), заносим в переменную [latex]newMultiplier[/latex] значение множителя для выражения внутри скобок.
Рекурсивно вызываем функцию getContent() для:
1. Выражения перед открывающей скобкой, если формула не начинается с нее.
  
  getContent(formula.substr(0, begin - 1), multiplier, content);
  
  106
  
  getContent(formula.substr(0, begin - 1), multiplier, content);
  
  ([latex]begin[/latex] — номер первого символа внутри скобок.)
2. Выражения внутри скобок.
  
  getContent(formula.substr(begin, end - begin), newMultiplier, content);
  
  108
  
  getContent(formula.substr(begin, end - begin), newMultiplier, content);
  
  ([latex]end[/latex] — номер закрывающей скобки.)
3. Выражения после закрывающей скобки или заднего коэффициента, если присутствует (если только скобка/коэффициент не является концом формулы).
  
  getContent(formula.substr(afterEnd), multiplier, content);
  
  111
  
  getContent(formula.substr(afterEnd), multiplier, content);
  
  ([latex]afterEnd[/latex] — следующий после скобки/коэффициента символ.)

Этот алгоритм фактически является решением задачи. Теперь в методе [latex]main[/latex] надо всего лишь обработать главную формулу, а затем для каждого случая в цикле — сравниваемую с ней формулу, сравнив после содержимое их карт (сравнение осуществляется просто используя оператор сравнения ==). Обработка подразумевает последовательный вызов функций split() и process().

Тесты

№	Ввод	Вывод
1	C2H5OH+3O2+3(SiO2) 6 2CO2+3H2O+3SiO2 2C+6H+13O+3Si 99C2H5OH+3SiO2 3SiO4+C2H5OH C2H5OH+3O2+3(SiO2)+Ge 3(Si(O)2)+2CO+3H2O+O2	C2H5OH+3O2+3(SiO2)==2CO2+3H2O+3SiO2 C2H5OH+3O2+3(SiO2)==2C+6H+13O+3Si C2H5OH+3O2+3(SiO2)!=99C2H5OH+3SiO2 C2H5OH+3O2+3(SiO2)==3SiO4+C2H5OH C2H5OH+3O2+3(SiO2)!=C2H5OH+3O2+3(SiO2)+Ge C2H5OH+3O2+3(SiO2)==3(Si(O)2)+2CO+3H2O+O2
2	2H2O 5 HHOHHO 2H+H2+(O(O)) 2((H2)O) HOHHOHe H4O	2H2O==HHOHHO 2H2O==2H+H2+(O(O)) 2H2O==2((H2)O) 2H2O!=HOHHOHe 2H2O!=H4O
3	8Zn+Ar4+Ne 3 Ne(Ar2(Zn)4)2 2Ne(Ar2(Zn)4) Ne+2Zn2(((((Ar)))))2Zn2	8Zn+Ar4+Ne==Ne(Ar2(Zn)4)2 8Zn+Ar4+Ne!=2Ne(Ar2(Zn)4) 8Zn+Ar4+Ne==Ne+2Zn2(((((Ar)))))2Zn2

Код

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
using namespace std;

bool isDigit(char c) { return  c >= '0' && c <= '9'; }

bool isUpperCaseLetter(char c) { return  c >= 'A' && c <= 'Z'; }

bool isLowerCaseLetter(char c) { return  c >= 'a' && c <= 'z'; }

void update(map<string, int> &map, string key, int value)
{
    if (map.count(key)) //вернет 0 (false) если элемент не найден, иначе - 1 (true)
    {
        map.at(key) = map.at(key) + value; //обновляем значение элемента в карте
    }
    else
    {
        map.insert(make_pair(key, value)); //добавляем элемент в карту
    }
}

void split(string formula, vector<string> &storage)
{
    int begin = 0, length = 0;
    for (int i = 0; i < formula.length(); i++)
    {
        if (formula.at(i) == '+')
        {
            storage.push_back(formula.substr(begin, length));
            length = 1;
            begin = ++i;
        }
        else
        {
            length++;
        }
    }
    storage.push_back(formula.substr(begin, length));
}

int getMultiplier(string formula)
{
    int res = 0;
    for (int i = 0; i < formula.length(); i++)
    {
        if (isDigit(formula.at(i))) 
        {
            res *= 10;
            res += (formula.at(i) - '0'); //получаем из символа соответствующую цифру
        }
        else break;
    }
    return res == 0 ? 1 : res; //0 - если перед формулой нет множителя, тогда он должен быть 1
}

void getContent(string formula, int multiplier, map<string, int> &content)
{ 
    if (formula.find('(') != string::npos) //если есть скобки
    {
        int begin = formula.find('(') + 1; //первый символ внутри скобок
        int end;
        int bracketCounter = 1;
        for (int i = begin; true; i++)
        {
            if (formula.at(i) == '(')
            {
                bracketCounter ++;
            }
            else if (formula.at(i) == ')')
            {
                bracketCounter--;
                if (bracketCounter == 0)
                {
                    end = i; //находим соответствующую закрывающую скобку
                    break;
                }
            }
        }
        int newMultiplier = multiplier;
        int afterEnd = end + 1;
        int backCoefficient = 0; //вычисляем коэффициент за скобочным выражением
        for (int i = 1; true; i++)
        {
            if (end + i != formula.length() && isDigit(formula.at(end + i))) //пока есть числа за закрывающей скобкой, обновляем значение заднего коэффициента
            {
                backCoefficient *= 10;
                backCoefficient += (formula.at(end + i) - '0');
                afterEnd++;
            }
            else
            {
                if (backCoefficient == 0) //если чисел после закрывающей скобки нет, коэффициент равен 1
                {
                    backCoefficient++;
                }
                newMultiplier *= backCoefficient; //вычисляем новое значение множителя для выражения внутри скобок
                break;
            }
        }
        if (begin != 1)
        {
            getContent(formula.substr(0, begin - 1), multiplier, content); 
        }
        getContent(formula.substr(begin, end - begin), newMultiplier, content); 
        if (afterEnd < formula.length())
        {
            getContent(formula.substr(afterEnd), multiplier, content);
        }
    }
    else //если скобок нет
    {
        string name = "";
        string coefficient = "";
        for (char c : formula)
        {
            if (isDigit(c)) 
            {
                coefficient += c;
            }
            else if (isLowerCaseLetter(c)) 
            {
                name += c;
            }
            else if (isUpperCaseLetter(c))
            {
                if (name.empty()) 
                {
                    name += c;
                }
                else
                {
                    if (coefficient.empty()) 
                    {
                        coefficient = "1";
                    }
                    update(content, name, multiplier * stoi(coefficient));
                    name.clear();
                    name += c;
                    coefficient = "";
                }
            }
        }
        if (!name.empty())
        {
            if (coefficient.empty()) 
            {
                coefficient = "1";
            }
            update(content, name, multiplier * stoi(coefficient));
        }
    }
}

void process(vector<string> subformulas, map<string, int> &content)
{
    for (string subformula : subformulas) //для каждой подформулы:
    {
        int multiplier = getMultiplier(subformula); //вычисляем множитель перед ней
        if (multiplier != 1) //если множитель записан явно
        {
            getContent(subformula.substr(floor(log10(multiplier)+1)), multiplier, content); //передаем в функцию подформулу, начиная с первого символа, не относящегося к переднему множителю
        }
        else
        {
            getContent(subformula, multiplier, content); //иначе передаем подформулу целиком
        }
    }
}

int main() 
{
    string mainFormula;
    vector<string> mainSubformulas;
    map<string, int> mainContent;
    cin >> mainFormula;
    split(mainFormula, mainSubformulas);
    process(mainSubformulas, mainContent);
    int n;
    cin >> n;
    string formulaToCompare;
    vector<string> subformulasToCompare;
    map<string, int> contentToCompare;
    for (int i = 0; i < n; i++)
    {
        subformulasToCompare.clear(); //
        contentToCompare.clear();
        cin >> formulaToCompare;
        split(formulaToCompare, subformulasToCompare);
        process(subformulasToCompare, contentToCompare);
        cout << mainFormula << (mainContent == contentToCompare ? "==" : "!=") << formulaToCompare << endl;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

#include <iostream>

#include <cmath>

#include <string>

#include <vector>

#include <map>

using namespace std;

bool isDigit(char c) { return c >= '0' && c <= '9'; }

bool isUpperCaseLetter(char c) { return c >= 'A' && c <= 'Z'; }

bool isLowerCaseLetter(char c) { return c >= 'a' && c <= 'z'; }

void update(map<string, int> &map, string key, int value)

{

if (map.count(key)) //вернет 0 (false) если элемент не найден, иначе - 1 (true)

{

map.at(key) = map.at(key) + value; //обновляем значение элемента в карте

}

else

{

map.insert(make_pair(key, value)); //добавляем элемент в карту

}

void split(string formula, vector<string> &storage)

{

int begin = 0, length = 0;

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

{

if (formula.at(i) == '+')

{

storage.push_back(formula.substr(begin, length));

length = 1;

begin = ++i;

}

else

{

length++;

}

storage.push_back(formula.substr(begin, length));

}

int getMultiplier(string formula)

{

int res = 0;

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

{

if (isDigit(formula.at(i)))

{

res *= 10;

res += (formula.at(i) - '0'); //получаем из символа соответствующую цифру

}

else break;

}

return res == 0 ? 1 : res; //0 - если перед формулой нет множителя, тогда он должен быть 1

}

void getContent(string formula, int multiplier, map<string, int> &content)

{

if (formula.find('(') != string::npos) //если есть скобки

{

int begin = formula.find('(') + 1; //первый символ внутри скобок

int end;

int bracketCounter = 1;

for (int i = begin; true; i++)

{

if (formula.at(i) == '(')

{

bracketCounter ++;

}

else if (formula.at(i) == ')')

{

bracketCounter--;

if (bracketCounter == 0)

{

end = i; //находим соответствующую закрывающую скобку

break;

}

int newMultiplier = multiplier;

int afterEnd = end + 1;

int backCoefficient = 0; //вычисляем коэффициент за скобочным выражением

for (int i = 1; true; i++)

{

if (end + i != formula.length() && isDigit(formula.at(end + i))) //пока есть числа за закрывающей скобкой, обновляем значение заднего коэффициента

{

backCoefficient *= 10;

backCoefficient += (formula.at(end + i) - '0');

afterEnd++;

}

else

{

if (backCoefficient == 0) //если чисел после закрывающей скобки нет, коэффициент равен 1

{

backCoefficient++;

}

newMultiplier *= backCoefficient; //вычисляем новое значение множителя для выражения внутри скобок

break;

}

if (begin != 1)

{

getContent(formula.substr(0, begin - 1), multiplier, content);

}

getContent(formula.substr(begin, end - begin), newMultiplier, content);

if (afterEnd < formula.length())

{

getContent(formula.substr(afterEnd), multiplier, content);

}

else //если скобок нет

{

string name = "";

string coefficient = "";

for (char c : formula)

{

if (isDigit(c))

{

coefficient += c;

}

else if (isLowerCaseLetter(c))

{

name += c;

}

else if (isUpperCaseLetter(c))

{

if (name.empty())

{

name += c;

}

else

{

if (coefficient.empty())

{

coefficient = "1";

}

update(content, name, multiplier * stoi(coefficient));

name.clear();

name += c;

coefficient = "";

}

if (!name.empty())

{

if (coefficient.empty())

{

coefficient = "1";

}

update(content, name, multiplier * stoi(coefficient));

}

void process(vector<string> subformulas, map<string, int> &content)

{

for (string subformula : subformulas) //для каждой подформулы:

{

int multiplier = getMultiplier(subformula); //вычисляем множитель перед ней

if (multiplier != 1) //если множитель записан явно

{

getContent(subformula.substr(floor(log10(multiplier)+1)), multiplier, content); //передаем в функцию подформулу, начиная с первого символа, не относящегося к переднему множителю

}

else

{

getContent(subformula, multiplier, content); //иначе передаем подформулу целиком

}

int main()

{

string mainFormula;

vector<string> mainSubformulas;

map<string, int> mainContent;

cin >> mainFormula;

split(mainFormula, mainSubformulas);

process(mainSubformulas, mainContent);

int n;

cin >> n;

string formulaToCompare;

vector<string> subformulasToCompare;

map<string, int> contentToCompare;

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

{

subformulasToCompare.clear(); //

contentToCompare.clear();

cin >> formulaToCompare;

split(formulaToCompare, subformulasToCompare);

process(subformulasToCompare, contentToCompare);

cout << mainFormula << (mainContent == contentToCompare ? "==" : "!=") << formulaToCompare << endl;

}

return 0;

}

Ссылки

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

Код на ideaone.

Related Images:

acm.timus.ru №2002. Тестовое задание

04/12/2015 by Марченко Філіп Олександрович

Автор задачи: Кирилл Бороздин
Источник задачи: Уральская региональная командная олимпиада по программированию 2013

Ограничения:

Время:	0.5 секунды
Память	64 Мб

Условие

Это было обычное хмурое октябрьское утро. Небо было затянуто тяжёлыми серыми тучами, накрапывал дождь. Капли падали на стёкла автомобилей, били в окна домов. Илья сидел за компьютером и угрюмо взирал на унылый пейзаж за окном. Внезапно его взгляд привлекла надпись, появившаяся в правом нижнем углу экрана: «You have 1 unread email message(s)». Заранее приготовившись удалить бесполезный спам, Илья открыл письмо. Однако оно оказалось куда интереснее…

Вас приветствует отдел по работе с персоналом компании «Рутнок БКС»!

Мы рассмотрели вашу заявку на вакансию разработчика программного обеспечения и были заинтересованы вашей кандидатурой. Для оценки ваших профессиональных навыков мы предлагаем вам выполнить несложное тестовое задание: необходимо реализовать систему регистрации для форума. Она должна поддерживать три операции:

«register username password» — зарегистрировать нового пользователя с именем «username» и установить для него пароль «password». Если такой пользователь уже есть в базе данных, необходимо выдать ошибку «fail: user already exists». Иначе нужно вывести сообщение «success: new user added».
«login username password» — войти в систему от имени пользователя «username» с паролем «password». Если такого пользователя не существует в базе данных, необходимо выдать «fail: no such user». Иначе, если был введен неправильный пароль, нужно выдать «fail: incorrect password». Иначе, если пользователь уже находится в системе в данный момент, необходимо вывести «fail: already logged in». Иначе нужно вывести сообщение «success: user logged in».
«logout username» — выйти из системы пользователем «username». Если такого пользователя не существует, необходимо вывести «fail: no such user». Иначе, если пользователь не находится в системе в данный момент, следует выдать «fail: already logged out». Иначе необходимо выдать сообщение «success: user logged out».

Пользуйтесь этим письмом как формальным описанием алгоритма и строго соблюдайте порядок обработки ошибок. Желаем вам удачи!

И вот Илья, откинув все дела, уже решает тестовое задание. Попробуйте и вы выполнить его!

Исходные данные

В первой строке дано целое число [latex]n[/latex] — количество операций [latex]1\leq{n}\leq100[/latex]. В каждой из следующих [latex]n[/latex] строк содержится один запрос в соответствии с форматом, описанным выше. В качестве «username» и «password» могут выступать любые непустые строки длиной до 30 символов включительно. Строки могут состоять только из символов с кодами от 33 до 126.

Результат

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

Пример

Исходные данные

Результат

logout vasya

success: new user added

fail: incorrect password

success: user logged in

fail: no such user

success: user logged out

fail: already logged out

Решение

Для решения данной задачи нам необходимо воспользоваться структурой данных, которая хранит в себе пары вида «ключ — значение», а также структурой, которая будет хранить в себе некоторое множество. Воспользуемся структурами HashMap (Java) / map (C++) (key -> value) и HashSet (множество).

Рассмотрим операции, которые должна уметь обрабатывать наша система:

«register username password». При регистрации нового пользователя будем помещать его в нашу «базу» зарегистрированных пользователей при условии, что он не зарегистрирован. Поиском по ключу в HashMap / map проверим существование уже зарегистрированного никнейма. Если найдётся такой пользователь, то система выдаст сообщение об ошибке.
«login user password». Если база пользователей содержит в себе логин пользователя, пароли совпадают и пользователь не в он-лайне, то система разрешит user’у вход на форум. В противном случае, с соответствующими сообщениями об ошибках, не разрешит вход. Отслеживать пользователей, которые уже online, будем с помощью HashSet. Если пользователя нет в базе пользователей, которые сейчас на сайте, то открывая доступ, система поместит его в базу-online. Тогда новый запрос login с этого ника будет отклонён.
«logout name». Если пользователя нет в базе пользователей, то его logout невозможен. Иначе, если его нет в базе-online, то тоже система выдаст сообщение об ошибке. Если user есть в базе пользователей и находится в онлайне, то выход возможен. Во время logouta удаляем пользователя из базы-online.

Реализация

В данном отчёте задачи будут представлены на языках Java и C++. Опишем, для начала, какие классы и методы необходимо использовать для решения этой задачи на языке Java:

HashMap:

Будем использовать интерфейс Map, имплементация (реализация) — HashMap. Из интерфейса Map воспользуемся следующими методами:

containsKey(Key K) — возвращает true, если ключ найден. В противном случае — false;
put(Key K, Value V) — записывает пару ключ-значение в структуру;
get(Key K) — по ключу возвращает значение.

HashSet:

Используем интерфейс Set, реализация — HashSet. Будем использовать следующие методы:

contains(Object o) — возвращает true, если элемент принадлежит множеству. Иначе — false;
add(Object o) — добавляет элемент во множество;
remove(Object o) — удаляет элемент из множества.

Теперь для С++:

В С++ воспользуемся немного другим подходом. Воспользуемся только map. Создадим структуру, которая будет содержать 2 поля: пароль и статус. Воспользуемся следующими методами:

find (K key) — возвращает итератор элемента.
end() — возвращает итератор за последним элементом.

set или без него?

Для данной задачи использование set’a не принципиально. Но если предположить, что, помимо запросов регистрации, входа и выхода, был бы ещё и запрос вывести пользователей, которые онлайн, преимущество использования set’a очевидно.

Код на Java:

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

 class Ideone {
    public static void main (String[] args) {
        
        //create an DB for online and reged users
        Map DB = new HashMap<String, String> (); 
        HashSet <String> DBin = new HashSet <String> ();
        
        Scanner in = new Scanner (System.in);
        PrintWriter out = new PrintWriter(System.out);
        
        //a number of queries
        int n = in.nextInt();
        
        
        for (int i = 0; i < n; i++){
            String s, log, pass;
            
            //command
            s = in.next();
            
            if (s.equals("register")){
                log = in.next();    //login
                pass = in.next();   //password
                if (DB.containsKey(log)){   //login in DB?
                    out.println("fail: user already exists");
                    out.flush();
                }
                else {
                    DB.put(log, pass);
                    out.println("success: new user added");
                    out.flush();
                }
            }
            
            if (s.equals("login")){
                log = in.next();
                pass = in.next();
                if (DB.containsKey(log)){ //if user is reg
                    if (pass.equals(DB.get(log))) { //if the password is well
                        if (!DBin.contains(log)) {  //online?
                            DBin.add(log);
                            out.println("success: user logged in");
                            out.flush();
                        }
                        //Errors
                        else {
                            out.println("fail: already logged in");
                            out.flush();
                        }
                    }
                    else {
                        out.println("fail: incorrect password");
                        out.flush();
                    }
                }
                else {
                    out.println("fail: no such user");
                    out.flush();
                }
            }
            if (s.equals("logout")){
                log = in.next();
                if (!DB.containsKey(log)) { //unreg user can't logout... unfortunately.
                    out.println("fail: no such user");
                    out.flush();
                }
                else {
                    if (!DBin.contains(log)){   //so offline user does
                        out.println("fail: already logged out");
                        out.flush();
                    }
                    else {
                        DBin.remove(log);
                        out.println("success: user logged out");
                        out.flush();
                    }
                }
            }
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) {

//create an DB for online and reged users

Map DB = new HashMap<String, String> ();

HashSet <String> DBin = new HashSet <String> ();

Scanner in = new Scanner (System.in);

PrintWriter out = new PrintWriter(System.out);

//a number of queries

int n = in.nextInt();

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

String s, log, pass;

//command

s = in.next();

if (s.equals("register")){

log = in.next(); //login

pass = in.next(); //password

if (DB.containsKey(log)){ //login in DB?

out.println("fail: user already exists");

out.flush();

}

else {

DB.put(log, pass);

out.println("success: new user added");

out.flush();

}

if (s.equals("login")){

log = in.next();

pass = in.next();

if (DB.containsKey(log)){ //if user is reg

if (pass.equals(DB.get(log))) { //if the password is well

if (!DBin.contains(log)) { //online?

DBin.add(log);

out.println("success: user logged in");

out.flush();

}

//Errors

else {

out.println("fail: already logged in");

out.flush();

}

else {

out.println("fail: incorrect password");

out.flush();

}

else {

out.println("fail: no such user");

out.flush();

}

if (s.equals("logout")){

log = in.next();

if (!DB.containsKey(log)) { //unreg user can't logout... unfortunately.

out.println("fail: no such user");

out.flush();

}

else {

if (!DBin.contains(log)){ //so offline user does

out.println("fail: already logged out");

out.flush();

}

else {

DBin.remove(log);

out.println("success: user logged out");

out.flush();

}

Код на С++:

#include <iostream>
#include <stdio.h>
#include <string>
#include <iomanip>
#include <stack>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>

using namespace std;

struct status { //status - password and online
    string password;
    bool online = false;
};

map <string, status> database; //user database


int main () {
    int n; cin >> n; //number of queries
    typedef std::map<std::string, status> db; // use this typedef for an iterator
    while (n--){
        string com, login; //command and login
        status query; //for status input
        cin >> com;
        if (com == "register"){
            cin >> login >> query.password;
            db::iterator it = database.find(login); //returning an iterator
            if (it != database.end()) { //each el from database is in [begin, end). it = database.end() means that there is no such element in db
                cout << "fail: user already exists\n";
            }
            else {
                database[login].password = query.password; // register
                cout << "success: new user added\n";
            }
        }
        //user can log in if he isn't online but he is registered
        if (com == "login") {
            cin >> login >> query.password;
            db::iterator it = database.find(login);
            if (it != database.end()){
                if (query.password == database[login].password){
                    if(!database[login].online){
                        database[login].online = true;
                        cout << "success: user logged in\n";
                    }
                    else cout << "fail: already logged in\n";
                }
                else cout << "fail: incorrect password\n";
            }
            else cout << "fail: no such user\n";
        }
        //logout
        if (com == "logout") {
            cin >> login;
            if (database.find(login) == database.end()) cout << "fail: no such user\n";
            else {
                if (!database[login].online) cout << "fail: already logged out\n";
                else {

                    database[login].online = false;
                    cout << "success: user logged out\n";
                }
            }
        }
    }
    return 0;
}