Category Archives: 9. Последовательные контейнеры

Рассматриваются следующие последовательные контейнеры:

vector
Особый случай vector <bool>
array
forward_list
list

Задачи на использование контейнеров начинаются с класса vector. Данный класс позволяет реализовать массив с динамически изменяющимся размером. Познакомившись с материалом учебника, для тренировки постарайтесь решить задачу Банкомат.

Если в качестве домашнего задания на эту тему Вам достались задачи из задачника А.Абрамова А271-А316, то условие задачи следует модифицировать так, чтобы количество вводимых данных было произвольным. Т.е. данные должны читаться до исчерпания потока ввода. Например, вместо 15 элементов в задаче А271 следует читать все данные стандартного потока ввода.

Опубликованные решения

A288

19/04/2016 by Павел Загинайло

Задача A288

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

Даны целые числа [latex]a_{1}[/latex], …, [latex]a_{n}[/latex], каждое из которых отлично от нуля. Если в последовательности отрицательные и положительные члены чередуются (+, –, +, –, или –, +, –, +, … ), то ответом должна служить сама исходная последовательность. Иначе получить все отрицательные члены последовательности, сохранив порядок их следования.

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

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


int main() {
	vector <int> a, b;
	bool alternate = true; //переменная, которая изменяет свое значение, в зависимости от того, чередуются знаки (true) или нет (false)
	int a1; //первый элемент
	
	cin >> a1;
	int tester = a1; //в переменной хранится значение, с которым будут сравниваться последующие
	if (a1 > 0){
		b.push_back(a1);
	}
	else if (a1 < 0){
		a.push_back(a1);
		b.push_back(a1);
	}
	
	int n;
	while (cin >> n){
		if (n > 0){
			b.push_back(n);
		}
		if (n < 0){
			a.push_back(n);
			b.push_back(n);
		}
		if (tester*n > 0) alternate = false;  //если встретили два значения подряд одного знака
		tester = n;
	}
	if (alternate == true){
		for (int i = 0; i < b.size(); i++){
			cout << b[i] << " ";
		}
	}
	if (alternate == false){
		for (int i = 0; i < a.size(); i++){
			cout << a[i] << " ";
		}
	}
	return 0;
}

#include <vector>

#include <iostream>

using namespace std;

int main() {

vector <int> a, b;

bool alternate = true; //переменная, которая изменяет свое значение, в зависимости от того, чередуются знаки (true) или нет (false)

int a1; //первый элемент

cin >> a1;

int tester = a1; //в переменной хранится значение, с которым будут сравниваться последующие

if (a1 > 0){

b.push_back(a1);

}

else if (a1 < 0){

a.push_back(a1);

b.push_back(a1);

}

int n;

while (cin >> n){

if (n > 0){

b.push_back(n);

}

if (n < 0){

a.push_back(n);

b.push_back(n);

}

if (tester*n > 0) alternate = false; //если встретили два значения подряд одного знака

tester = n;

}

if (alternate == true){

for (int i = 0; i < b.size(); i++){

cout << b[i] << " ";

}

if (alternate == false){

for (int i = 0; i < a.size(); i++){

cout << a[i] << " ";

}

return 0;

}

Тесты

Входные данные	Выходные данные
5 5 3 1 2 7 8 100000
-9 -5 -1 -3 -7 -4198 -852	-9 -5 -1 -3 -7 -4198 -852
5 -3 1 81 3 -7 1 -5 6	-3 -7 -5
-1 2 -8 995 -3 777 -42	-1 2 -8 995 -3 777 -42

Решение

Для решение данной задачи я воспользовался следующим алгоритмом. Заводим два целочисленных вектора, булеву переменную, которую мы будем проверять при печати и целочисленную переменную, которая будет являться первым элементом последовательности, а также начальным значением переменной [latex]tester[/latex], с которой будет сравниваться следующий элемент, а после этого его значение мы снова положим в [latex]tester[/latex]. В ходе цикла мы положительные числа кладем в один вектор, а отрицательные в оба. И в зависимости от того чередовались ли знаки или нет (значение переменной [latex]alternate[/latex]), мы печатаем нужный вектор.

Related Images:

AL16

31/03/2016 by Таран Таня

Algolist. Data structures. Task 16.

There is a Ministry, that includes [latex]N[/latex] officials ([latex]N[/latex] is a natural number). Each official possibly has subordinates and chiefs. What is more, there are some rules:

Subordinates of my subordinate are my subordinates.
Chiefs of my chief — my chiefs.
My chief is not my subordinate.
Each official has no more than one direct chief.

In order to get a license for the export of copper, necessary to obtain a signature of the 1st official — сhief of all the сhiefs. But the situation complicated by the fact, that each official, generally speaking, can require «visas» — signatures some of his immediate subordinates and a bribe — a certain amount of dollars. Non-empty list of possible visas and corresponding to this list bribe are known for each official. The empty list means that the official doesn’t require a visa in this case. The official will put his signature, only if he receives all signatures from one of the visas list and the appropriate bribe.

You need to define and output the permissible and minimal for sum of bribes order and its cost.

Input

The input data is the following sequence of lines:

Quantity of officials [latex]N[/latex] ([latex]N < 100[/latex] ).
List of subordinates for current visa, which consists of their indeces, suitable to the order in which they came to input (could be empty, it suggests that the official doesn’t require a visa in this case).
«bribe» — signalyze, that input of current visa end. In next line you will recieve the cost of bribe — real number [latex]B[/latex] ([latex]0 < B < 10^6[/latex]) .
«next_official» — determine that information about previous official ended and next line will contain empty or not empty list of next official’s visas (there is no such command before 1st official. If there is no command «next_official « after the number, that determine a bribe, you will recieve next visa of the current official).

More info about input data you can find in test examples.

Output

You need to output in the separate lines the minimum sum of bribes for getting a license and the order. This is a string with the consecutive indices of the officials, who participated in the payment of the minimum bribe, (in order of raising in the hierarchical system, from left to right (arranging in entering the appropriate official)) separated with delimetr /.

Tests

№	Input	Output
1	2 2 bribe 50 next_official	50 2/1
2	5 2 bribe 100 3 bribe 200 4 bribe 150 next_official 5 bribe 10 next_official next_official next_official	110 5/2/1
3	7 2 bribe 150 3 bribe 50 next_official 4 bribe 40 5 bribe 20 next_official 6 bribe 150 7 bribe 200 next_official next_official next_official next_official	170 5/2/1
4	5 2 bribe 50 next_official 3 bribe 40 4 bribe 10 next_official next_official 5 bribe 10 next_official	70 5/4/2/1
5	8 2 bribe 100 next_official 3 bribe 200 4 bribe 150 3 4 bribe 50 next_official 7 bribe 25 next_official 5 bribe 10 6 bribe 80 next_official next_official next_official 8 bribe 35 next_official	220 8/7/5/3/4/2/1

Illustration for the test №3Illustration for the test №4

Illustration for the test №5

Algorithm

In order to implement solution of this problem, we construct two data structures Visa and Official. First of these stores fields vector <unsigned int> listOfSubordinatesForBribe — indices of subordinates, whose signatures are needed in this bribe and directly bribe. Every official, in their turn, has Id (serial number) and a list of all his visas — vector <Visa> listOfRequiredVisas. Also, we need two functions:

bool isBypassed(Official currentOfficial, string order) — determines whether the official is bypassed. It is realized on the condition that every official has no more than one direct chief. Therefore to find out if we take into account this official, we need to check whether there is in the list of bypassed at least one of his subordinates. Implementing a check directly on the current official Id is not possible, because we will go recursively from the leaves to the root.
void findCheapestWay(Official *listOfOfficials, Official currentOfficial, string &order, unsigned int &minimumBribe) — the main function dedicated to the search of the answer. Consider its job in detail:
Because there is no point in considering the officials, who don’t require any visa, we will process only those,who have non-empty list of visas and haven’t been visited yet. Otherwise, we will just go up to a higher level in the tree. For each official store vector <unsigned int> possibleSumsOfBribes and vector <string> possibleOrdersOfBypassing — possible variants of bribes and the order by which it was achieved. Also, we need two variables passed by reference in function — number minimumBribe and string order. They will help us to maintain a minimum bribe and its order at each hierarchy level, when we will call the recursive search for each subordinate in the visa.

Let us turn to the main executable part of the program. Organize the correct reading of the incoming data stream and save each official with its corresponding Id.
Start the search function of the first and the most important official — root. Getting in the first visa and starting a recursive search for all the subordinates we descend directly to the leaves of the tree. Leaning into a dead end, we start to climb from the bottom up, and for each official we find minimum possible bribe and order directly at his level. Thus we will be able consistently for each branch find it mimimum and pick it up by going to the root of the tree. Doing this for every possible visas, we fill the vector of potential bribes values, in which by searching the minimum element we can select required value. This will be the lowest possible price for a license.
Further details of the implementation can be seen in the comments to the code.

Code

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

const char DELIMITER = '/';                                                                                     // Delimiter character for the correct accumulation of order

struct Visa {
    vector <unsigned int> listOfSubordinatesForBribe;                                                         // Storage of subordinates' indices whose signature is required
    double bribe;                                                                                               // Required bribe
};
 
struct Official {
    unsigned int id;                                                                                                // Official id (sequence number in the input stream, starting at one)
    vector <Visa> listOfRequiredVisas;                                                                            // Storage of possible variants of visas
};
 
bool isBypassed(Official currentOfficial, string order) {                                                       // Return true, if this official is already bypassed
    bool isBypassed = false;
    for (auto currentVisa : currentOfficial.listOfRequiredVisas) {
        for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) {
            if (order.find(to_string(currentSubordinate) + DELIMITER) != string::npos) {                            // We are looking we are looking for the presence of at least one subordinate including a separator
                isBypassed = true;                                                                              // In the string of previously accumulated order of bypass 
                break;
            }
        }
    }
    return isBypassed;
}
 
void findCheapestWay(Official *listOfOfficials, Official currentOfficial, string &order, unsigned int &minimumBribe) {
    vector <unsigned int> possibleSumsOfBribes;                                                                   // Stores all the possible sums of bribes for the current official
    vector <string> possibleOrdersOfBypassing;                                                                    // Stores all the possible orders for the current of
    if (!currentOfficial.listOfRequiredVisas.empty() && !isBypassed(currentOfficial, order)) {
        int currentSumOfBribes = 0;                                                                             // Current sum of bribes for current official
        for (auto currentVisa : currentOfficial.listOfRequiredVisas) {
            for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) {
                findCheapestWay(listOfOfficials, listOfOfficials[currentSubordinate], order, minimumBribe);     // Recursively call the function for finding the minimum required bribe
                currentSumOfBribes = minimumBribe;                                                              // Store the detected minimum as a current
            }                                                                                                   // For each official we get down to the lower level
            string currentOrder;                                                                                    // Remember all the officials, that we bypassed to the current bribe 
            currentSumOfBribes = currentVisa.bribe;                                                             // Remember the bribe required by the current official as the current sum of bribes
            for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) {
                currentOrder += to_string(currentSubordinate) + DELIMITER;
            }                                                                                                   // Remember the current oder for each visa (isn't necessary an order to get the minimum sum of bribes) with delimiter
            possibleOrdersOfBypassing.push_back(order + currentOrder);                                          // Adding one of the possible orders, including previously accumulated value
            possibleSumsOfBribes.push_back(minimumBribe + currentSumOfBribes);                                  // Adding one of the possible sums, including value that we get from lower level
        }                                                                                                       // Executes processing for each visa in visas list
        vector<unsigned int>::iterator iteratorToCurrentMinBribe = min_element(possibleSumsOfBribes.begin(), possibleSumsOfBribes.end());
        unsigned int indexOfCurrentMinBribe = distance(possibleSumsOfBribes.begin(), iteratorToCurrentMinBribe);// Find the index of the lowest possible variant in the resulting vector
        minimumBribe = possibleSumsOfBribes[indexOfCurrentMinBribe];                                                // This variant will be the smallest by sum of bribes, remember it
        order = possibleOrdersOfBypassing[indexOfCurrentMinBribe];                                              // And remember corresponding to minimum bribe order
    }                                                                                                           // Executes processing only if the list of visas isn't empty and the official isn't bypassed
}
 
int main() {
    string order;                                                                                               // The order of bypass, that we're looking for
    string typeOfCommand;                                                                                       // Technical variable for processing the input stream
    unsigned int quantityOfOfficials;                                                                           // User-defined number of officials
    unsigned int minimumBribe = 0;                                                                              // Minimum sum of bribes to get a license
    cin >> quantityOfOfficials;
    Official *listOfOfficials = new Official[quantityOfOfficials + 1];                                          // Keeps all the officials in the array with the corresponding index
    unsigned int indexOfOfficial = 1;
    while (cin >> typeOfCommand) { 
        Official currentOfficial;
        while (typeOfCommand != "next_official") { 
            Visa currentVisa;
            vector <unsigned int> requiredSubordinates;
            while (typeOfCommand != "bribe") { 
                requiredSubordinates.push_back(atoi(typeOfCommand.c_str()));                                        // Before recording convert the input string to the number
                cin >> typeOfCommand;
            }                                                                                                   // Read the current visa (indices of subbordinates for bribe)
            currentVisa.listOfSubordinatesForBribe = requiredSubordinates;
            cin >> typeOfCommand;                                                                             // Read directly bribe
            currentVisa.bribe = atoi(typeOfCommand.c_str());                                                        // Before recording convert the input string to the number
            currentOfficial.listOfRequiredVisas.push_back(currentVisa);                                         // Add current visa to the current official visas list
            cin >> typeOfCommand;
        }                                                                                                       // Read the current official
        currentOfficial.id = indexOfOfficial;
        listOfOfficials[indexOfOfficial] = currentOfficial;                                                     // Put all the read data into an array
        indexOfOfficial++;                                                                                      // Go to read the next official, if present
    }                                                                                                           // Read to the end of the input stream
    findCheapestWay(listOfOfficials, listOfOfficials[1], order, minimumBribe);                                  // Call the function from main official(first) and accumulate the required values
    order.push_back('1');                                                                                       // Add the first official explicitly, cause he hasn't chief, so doesn't participate in the bypassing
    cout << minimumBribe << endl << order << endl;
    return 0;
}

#include <ctime>

#include <string>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

const char DELIMITER = '/'; // Delimiter character for the correct accumulation of order

struct Visa {

vector <unsigned int> listOfSubordinatesForBribe; // Storage of subordinates' indices whose signature is required

double bribe; // Required bribe

};

struct Official {

unsigned int id; // Official id (sequence number in the input stream, starting at one)

vector <Visa> listOfRequiredVisas; // Storage of possible variants of visas

};

bool isBypassed(Official currentOfficial, string order) { // Return true, if this official is already bypassed

bool isBypassed = false;

for (auto currentVisa : currentOfficial.listOfRequiredVisas) {

for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) {

if (order.find(to_string(currentSubordinate) + DELIMITER) != string::npos) { // We are looking we are looking for the presence of at least one subordinate including a separator

isBypassed = true; // In the string of previously accumulated order of bypass

break;

}

return isBypassed;

}

void findCheapestWay(Official *listOfOfficials, Official currentOfficial, string &order, unsigned int &minimumBribe) {

vector <unsigned int> possibleSumsOfBribes; // Stores all the possible sums of bribes for the current official

vector <string> possibleOrdersOfBypassing; // Stores all the possible orders for the current of

if (!currentOfficial.listOfRequiredVisas.empty() && !isBypassed(currentOfficial, order)) {

int currentSumOfBribes = 0; // Current sum of bribes for current official

for (auto currentVisa : currentOfficial.listOfRequiredVisas) {

for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) {

findCheapestWay(listOfOfficials, listOfOfficials[currentSubordinate], order, minimumBribe); // Recursively call the function for finding the minimum required bribe

currentSumOfBribes = minimumBribe; // Store the detected minimum as a current

} // For each official we get down to the lower level

string currentOrder; // Remember all the officials, that we bypassed to the current bribe

currentSumOfBribes = currentVisa.bribe; // Remember the bribe required by the current official as the current sum of bribes

for (auto currentSubordinate : currentVisa.listOfSubordinatesForBribe) {

currentOrder += to_string(currentSubordinate) + DELIMITER;

} // Remember the current oder for each visa (isn't necessary an order to get the minimum sum of bribes) with delimiter

possibleOrdersOfBypassing.push_back(order + currentOrder); // Adding one of the possible orders, including previously accumulated value

possibleSumsOfBribes.push_back(minimumBribe + currentSumOfBribes); // Adding one of the possible sums, including value that we get from lower level

} // Executes processing for each visa in visas list

vector<unsigned int>::iterator iteratorToCurrentMinBribe = min_element(possibleSumsOfBribes.begin(), possibleSumsOfBribes.end());

unsigned int indexOfCurrentMinBribe = distance(possibleSumsOfBribes.begin(), iteratorToCurrentMinBribe);// Find the index of the lowest possible variant in the resulting vector

minimumBribe = possibleSumsOfBribes[indexOfCurrentMinBribe]; // This variant will be the smallest by sum of bribes, remember it

order = possibleOrdersOfBypassing[indexOfCurrentMinBribe]; // And remember corresponding to minimum bribe order

} // Executes processing only if the list of visas isn't empty and the official isn't bypassed

}

int main() {

string order; // The order of bypass, that we're looking for

string typeOfCommand; // Technical variable for processing the input stream

unsigned int quantityOfOfficials; // User-defined number of officials

unsigned int minimumBribe = 0; // Minimum sum of bribes to get a license

cin >> quantityOfOfficials;

Official *listOfOfficials = new Official[quantityOfOfficials + 1]; // Keeps all the officials in the array with the corresponding index

unsigned int indexOfOfficial = 1;

while (cin >> typeOfCommand) {

Official currentOfficial;

while (typeOfCommand != "next_official") {

Visa currentVisa;

vector <unsigned int> requiredSubordinates;

while (typeOfCommand != "bribe") {

requiredSubordinates.push_back(atoi(typeOfCommand.c_str())); // Before recording convert the input string to the number

cin >> typeOfCommand;

} // Read the current visa (indices of subbordinates for bribe)

currentVisa.listOfSubordinatesForBribe = requiredSubordinates;

cin >> typeOfCommand; // Read directly bribe

currentVisa.bribe = atoi(typeOfCommand.c_str()); // Before recording convert the input string to the number

currentOfficial.listOfRequiredVisas.push_back(currentVisa); // Add current visa to the current official visas list

cin >> typeOfCommand;

} // Read the current official

currentOfficial.id = indexOfOfficial;

listOfOfficials[indexOfOfficial] = currentOfficial; // Put all the read data into an array

indexOfOfficial++; // Go to read the next official, if present

} // Read to the end of the input stream

findCheapestWay(listOfOfficials, listOfOfficials[1], order, minimumBribe); // Call the function from main official(first) and accumulate the required values

order.push_back('1'); // Add the first official explicitly, cause he hasn't chief, so doesn't participate in the bypassing

cout << minimumBribe << endl << order << endl;

return 0;

}

Code of the program (here you can analyze the working time of program)

Related Images:

A297

31/03/2016 by Молоканов Юрий

Условие

Даны целые числа [latex]a_1, \ldots , a_{100}[/latex]. Получить новую последовательность из 100 целых чисел, заменяя [latex]a_i[/latex] нулями, если [latex]|a_i|[/latex] не равно [latex]\text{max} (a_1, \ldots , a_{100})[/latex], и заменяя [latex]a_i[/latex] единицей в противном случае ([latex]i = 1, \ldots , 100[/latex]).

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

Тестирование

№	Входные данные	Выходные данные
1	0	1
2	1 0 -1	1 0 1
3	-1 0 -1	0 1 0
4	-1 -1 -1	0 0 0
5	4 4 4 4	1 1 1 1
6	10 5 -1 -10 -20 0 1 2 3	1 0 0 1 0 0 0 0 0

Код

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

int main() {
    vector<int> x;
    int t;
    cin >> t; // Читаем и помещаем в вектор первое число, считая его максимумом
    int max = t;
    x.push_back(t);
    while(cin >> t) { // Заполняем вектор оставшимися числами
        x.push_back(t);
        if(t > max)  // Если очередной элемент больше текущего максимума, обновляем максимум
            max = t;
    }
    for(int i = 0; i < x.size(); i++)    // Обрабатываем вектор в соответствии с условием
        x.at(i) = abs(x.at(i)) != max ? 0 : 1;
    for(int i = 0; i < x.size(); i++)    // Печатаем вектор
        cout << x.at(i) << ' ';
    return 0;
}

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

int main() {

vector<int> x;

int t;

cin >> t; // Читаем и помещаем в вектор первое число, считая его максимумом

int max = t;

x.push_back(t);

while(cin >> t) { // Заполняем вектор оставшимися числами

x.push_back(t);

if(t > max) // Если очередной элемент больше текущего максимума, обновляем максимум

max = t;

}

for(int i = 0; i < x.size(); i++) // Обрабатываем вектор в соответствии с условием

x.at(i) = abs(x.at(i)) != max ? 0 : 1;

for(int i = 0; i < x.size(); i++) // Печатаем вектор

cout << x.at(i) << ' ';

return 0;

}

Решение

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

Так как последовательность состоит из целых чисел и ее длина неизвестна, воспользуемся классом vector типа int:

vector<int> x;

1	vector<int> x;

Затем отдельно считаем первый элемент последовательности и возьмем его в качестве максимума, после чего поместим в вектор:

int t;
cin >> t;
int max = t;
x.push_back(t);

int t;

cin >> t;

int max = t;

x.push_back(t);

Заполним вектор оставшимися числами, попутно обновляя переменную max , если встретим число, большее хранимого максимума:

while(cin >> t) {
    x.push_back(t);
    if(t > max)
        max = t;
}

while(cin >> t) {

x.push_back(t);

if(t > max)

max = t;

}

Теперь обработаем последовательность согласно условию задачи, то есть заменим каждое число либо нулем, если его абсолютное значение не равно максимуму, либо единицей в противном случае:

for(int i = 0; i < x.size(); i++)
    x.at(i) = abs(x.at(i)) != max ? 0 : 1;

1 2	for(int i = 0; i < x.size(); i++) x.at(i) = abs(x.at(i)) != max ? 0 : 1;

Наконец, выведем ответ на задачу — полученную последовательность из нулей и единиц:

for(int i = 0; i < x.size(); i++)
    cout << x.at(i) << ' ';

1 2	for(int i = 0; i < x.size(); i++) cout << x.at(i) << ' ';

Ссылки

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

Условие задачи в сборнике задач по программированию (С. А. Абрамов).

Related Images:

A287

31/03/2016 by Настя Филипчук

Задача A287

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

Даны целые числа [latex] a_{1}\dots a_{n} [/latex]. Все члены последовательности с четными номерами, предшествующие первому по порядку члену со значением [latex] max(a_{1}\dots a_{n}) [/latex], домножить на [latex] max(a_{1}\dots a_{n}) [/latex].

Тестирование

№	Входные данные	Выходные данные
1.	1 2 3 4 3 2 1	1 8 3 4 3 2 1
2.	1 2 3 4 4 2 5 5 3 3 2 1	1 10 3 20 4 10 5 5 3 3 2 1
3.	11 4 6 7 9	11 4 6 7 9
4.	9 8 10 1 2 4 5 4 6 13	9 104 10 13 2 52 5 52 6 13
5.	-10 -4 -6 -7 -3 0 -1 -20	-10 0 -6 0 -3 0 -1 -20

Реализация

#include "iostream"
#include <vector>
using namespace std;
 
int main()
{
	vector <int> a;
	int n;
	int max_i = 0; //номер максимального элемента
	while (cin >> n) 
		a.push_back(n); 
	for (int i=0; i < a.size(); i++)
	{
		if (a[i] > a[max_i])
			 max_i=i;
	}
	for (int i=0; i<max_i; i++)
	{
		if (i % 2 != 0)
			a[i] *= a[max_i];			
	}
	for (int i = 0; i < a.size(); i++)
		cout << a[i] << " ";
	return 0;
}

#include "iostream"

#include <vector>

using namespace std;

int main()

{

vector <int> a;

int n;

int max_i = 0; //номер максимального элемента

while (cin >> n)

a.push_back(n);

for (int i=0; i < a.size(); i++)

{

if (a[i] > a[max_i])

max_i=i;

}

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

{

if (i % 2 != 0)

a[i] *= a[max_i];

}

for (int i = 0; i < a.size(); i++)

cout << a[i] << " ";

return 0;

}

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

Считываем все целые числа до конца входного потока и записываем их в вектор [latex] a [/latex]. Затем:

Сравниваем между собой каждый элемент вектора, и если находится большее значение, то запоминается номер данного элемента.
Далее проходим все члены последовательности, предшествующие первому по порядку члену с максимальным значением.
Умножаем все элементы с четными номерами на [latex] max(a_{1}\dots a_{n}) [/latex].

Ссылки

Код на ideaone.

Related Images:

A294

30/03/2016 by Кондратюк Настя

С.А.Абрамов. Задачи по программированию.

Задача

Даны действительные числа [latex]r_{1},\ldots,r_{n}[/latex], среди которых заведомо есть как отрицательные, так и не отрицательные. Получить [latex]x_{1}y_{1}+\ldots+x_{s}y_{s}[/latex], где [latex]x_{1},\ldots,x_{p}[/latex] — отрицательные члены последовательности [latex]r_{1},\ldots,r_{n}[/latex], взятые в порядке следования, [latex]y_{1},\ldots,y_{q}[/latex] — неотрицательные члены, взятые в обратном порядке, [latex]s=min\left ( p,q \right )[/latex] .

Тесты

Входные данные	Выходные данные
-1 1	-1
-1	0
-1 -1	0
1 2 -5 10 -2	-54
4 6 3 4 -8 2 7 5	-40

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

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

int main() {
	double r, sum=0;
	int s;
	vector <double> x;
	vector <double> y;
	while(cin >> r){
		if(r<0){
			x.push_back(r);
		}
		else y.push_back(r);
	}
	s = min(x.size(), y.size());
	for(int i=0; i < s; i++){
		sum += x[i] * y.back();/* умножение отрицательных чисел в порядке 
                следования на неотрицательные в обратном порядке */
		y.pop_back();
	}
	cout << sum;
	return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main() {

double r, sum=0;

int s;

vector <double> x;

vector <double> y;

while(cin >> r){

if(r<0){

x.push_back(r);

}

else y.push_back(r);

}

s = min(x.size(), y.size());

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

sum += x[i] * y.back();/* умножение отрицательных чисел в порядке

следования на неотрицательные в обратном порядке */

y.pop_back();

}

cout << sum;

return 0;

}

ideone.com

Решение

Считывая числа из входного потока, выполняем проверку и записываем положительные в вектор [latex]y[/latex], отрицательные — в вектор [latex]x[/latex]. Затем вычисляем [latex]s[/latex]. Вычисляем [latex]x_{1}y_{1}+\ldots+x_{s}y_{s}[/latex].

Related Images:

A293

29/03/2016 by Алина Гончарова

Задача

Даны целые числа [latex]a_1,\ldots,a_n[/latex].

Если в данной последовательности ни одно четное число не расположено после нечетного,

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

Тесты

Входные данные	Выходные данные
-1 -4 5 7	7 5
1 2 3 4 5 -6	5 4 3 2 1
2 1 1 1 1	—

Алгоритм

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

Код

#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    vector <int> a, b;
    int element;
    while (cin >> element) {
        a.push_back(element);
    }
    bool getNegative = true;
    for (int i = 0; i < a.size() - 1; i++) {
        if (abs(a[i]) % 2 == 1 && a[i + 1] % 2 == 0) {
            getNegative = false;
            break;
        }
    }
    if (getNegative) {
        for (int i = a.size() - 1; i >= 0; i--) {
            if (a[i] < 0) {
                b.push_back(a[i]);
            }
        }
    } else {
        for (int i = a.size() - 1; i >= 0; i--) {
            if (a[i] > 0) {
                b.push_back(a[i]);
            }
        }
    }
    for (int i = 0; i < b.size(); i++) {
        cout << b[i] << " ";
    }
    return 0;
}

#include <cmath>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

vector <int> a, b;

int element;

while (cin >> element) {

a.push_back(element);

}

bool getNegative = true;

for (int i = 0; i < a.size() - 1; i++) {

if (abs(a[i]) % 2 == 1 && a[i + 1] % 2 == 0) {

getNegative = false;

break;

}

if (getNegative) {

for (int i = a.size() - 1; i >= 0; i--) {

if (a[i] < 0) {

b.push_back(a[i]);

}

} else {

for (int i = a.size() - 1; i >= 0; i--) {

if (a[i] > 0) {

b.push_back(a[i]);

}

for (int i = 0; i < b.size(); i++) {

cout << b[i] << " ";

}

return 0;

}

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

Related Images:

A304

27/03/2016 by Катя Писова

Задача

Даны действительные числа [latex]a_{1},a_{2},\cdots[/latex] (читать до конца входного потока). Переставить члены последовательности так, чтобы сначала расположились все ее неотрицательные члены, а потом — все отрицательные. Порядок как среди неотрицательных членов, так и среди отрицательных должен быть сохранен прежним.

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

#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    vector <long double> v1, v2, v3;
    long double n;
    while (cin >> n){
        v1.push_back(n);
    }
    for (int i = 0; i < v1.size(); i++){
        if (v1[i] < 0) v3.push_back(v1[i]);
        else v2.push_back(v1[i]);
    }
    v2.insert(v2.end(), v3.begin(), v3.end());
    for (int i = 0; i < v2.size(); i++){
        cout << v2[i] << " ";
    }
    cout << endl;
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

vector <long double> v1, v2, v3;

long double n;

while (cin >> n){

v1.push_back(n);

}

for (int i = 0; i < v1.size(); i++){

if (v1[i] < 0) v3.push_back(v1[i]);

else v2.push_back(v1[i]);

}

v2.insert(v2.end(), v3.begin(), v3.end());

for (int i = 0; i < v2.size(); i++){

cout << v2[i] << " ";

}

cout << endl;

return 0;

}

Тесты

Test №	Input	Output
1	-23 45 17 -78 0 34	45 17 0 34 -23 -78
2	-56 -56.34 0.2 56 9	0.2 56 9 -56 -56.34
3	-1 3 2 1 0 -3 -2	3 2 1 0 -1 -3 -2
4	-0.333 -1 0 1 0 -2 0 2	0 1 0 0 2 -0.333 -1 -2
5	9 -9 0 -96 -11 27 -13	9 0 27 -9 -96 -11 -13

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

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

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

Related Images:

A299

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

Условие

Дана последовательность действительных чисел [latex]a_1, a_2, \dots, a_n[/latex]. Требуется домножить все члены последовательности на квадрат её наименьшего члена, если [latex]a_1 \geq 0[/latex], в противном случае — на квадрат наибольшего.

Решение

Для решения воспользуемся стандартным классом vector. Для этого заведем переменную данного типа, заполним её числами со входного потока. Далее, в зависимости от первого (нулевого) элемента вектора, воспользуемся стандартной функцией min_element() или max_element() (библиотека algorithm). Далее умножим каждый элемент на (соответственно) минимум/максимум и выведем последовательность.

Тесты

№	Входные данные	Выходные данные
1	-2 2 43 5 -10 12 0 -1	-3698 3698 79507 9245 -18490 22188 0 -1849
2	0 100 99 0 -1 1	0 100 99 0 -1 1
3	42 1 1 1 0 -1 24 -24 -42	74088 1764 1764 1764 0 -1764 42336 -42336 -74088

Код

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

int main() 
{
	vector<int> x;
	int a;
	while (cin >> a)
		x.push_back(a);
	if (x.at(0) >= 0)
	{
		int min = *min_element(x.begin(), x.end());
		for (int &i : x)
			i *= min * min;
	}
	else
	{
		int max = *max_element(x.begin(), x.end());
		for (int &i : x)
			i *= max * max;
	}
	for (int i : x)
		cout << i << " ";
	return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

vector<int> x;

int a;

while (cin >> a)

x.push_back(a);

if (x.at(0) >= 0)

{

int min = *min_element(x.begin(), x.end());

for (int &i : x)

i *= min * min;

}

else

{

int max = *max_element(x.begin(), x.end());

for (int &i : x)

i *= max * max;

}

for (int i : x)

cout << i << " ";

return 0;

}

Замечание

Перед изменением значения членов последовательности и их выводом нам необходимо найти минимум или максимум, для чего необходимо знать значения всех её членов. В связи с этим, решить задачу в формате «считал — вывел» (потоковой обработкой) невозможно.

Ссылки

Код на ideaone (vector).

Related Images:

А282б

16/03/2016 by Антон Локтев

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

Даны действительные числа [latex]a_{1}[/latex], [latex]a_{2}[/latex], [latex]\ldots[/latex], [latex]a_{2n}[/latex]. Получить [latex]a_{1}[/latex], [latex]a_{2n}[/latex], [latex]a_{2}[/latex], [latex]a_{2n-1}[/latex], [latex]a_{3}[/latex], [latex]\ldots[/latex], [latex]a_{n}[/latex], [latex]a_{n+1}[/latex].

Данную задачу можно найти здесь.

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

Последовательность действительных чисел [latex]a_{1}[/latex], [latex]a_{2}[/latex], [latex]\ldots[/latex], [latex]a_{2n}[/latex].

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

Последовательность действительных чисел [latex]a_{1}[/latex], [latex]a_{2n}[/latex], [latex]a_{2}[/latex], [latex]a_{2n-1}[/latex], [latex]a_{3}[/latex], [latex]\ldots[/latex], [latex]a_{n}[/latex], [latex]a_{n+1}[/latex] .

Тесты

№	Входные данные	Выходные данные
1	1 2 3 4 5 6	1 6 2 5 3 4
2	0 0 0 0 0 1	0 1 0 0 0 0
3	3 12 42 -6 15 0 0 0 501 20 20 20	3 20 12 20 42 20 -6 501 15 0 0 0
4	42 0 17 -2.6 -54 41888 0.25 13 1.3333 -284.73	42 -284.73 0 1.3333 17 13 -2.6 0.25 -54 41888
5	0 1 -1 0 1 -1 97 113 -7.777 0 48 -69	0 -69 1 48 -1 0 0 -7.777 1 113 -1 97

Код

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector <double> sequence, result_sequence;
    double term_of_sequence;
    while (cin >> term_of_sequence){
        sequence.push_back(term_of_sequence);
    }
    for (int i = 0; i < sequence.size() / 2; i++){
        result_sequence.push_back(sequence[i]);
        result_sequence.push_back(sequence[sequence.size() - 1 - i]);
    }
    for (int i = 0; i < result_sequence.size(); i++){
        cout << result_sequence[i] << " ";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <double> sequence, result_sequence;

double term_of_sequence;

while (cin >> term_of_sequence){

sequence.push_back(term_of_sequence);

}

for (int i = 0; i < sequence.size() / 2; i++){

result_sequence.push_back(sequence[i]);

result_sequence.push_back(sequence[sequence.size() - 1 - i]);

}

for (int i = 0; i < result_sequence.size(); i++){

cout << result_sequence[i] << " ";

}

return 0;

}

Код на ideone можно найти здесь.

Ход решения

Считываем все числа из входного потока и записываем их в вектор исходной последовательности sequence. Результатом работы нашей программы должна быть новая последовательность действительных чисел result_sequence, которая задаётся по следующему правилу: первый член новой последовательности совпадает с первым членом исходной, второй член новой последовательности является последним членом исходной, третий – второй член исходной и так далее до исчерпания чисел. Иными словами, новая последовательность из [latex]2n[/latex] чисел на нечётных номерах имеет члены исходной последовательности (от первого и до [latex]n[/latex]-го включительно), чётным же номерам новой последовательности соответствуют члены исходной с номерами от [latex]n+1[/latex] до [latex]2n[/latex] включительно, записанные в обратном порядке.

Related Images:

A278

16/03/2016 by Кудымовская Вика

Задача A278

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

Даны натуральные числа [latex]n_{1},\dots,n_{m}[/latex], действительные числа [latex]x_{1},\dots,x_{m}[/latex]. Вычислить [latex]\frac{n_{1}\cdot x_{1}+\dots+n_{m}\cdot x_{m}}{n_{1}+\dots+n_{m}}[/latex].

Тестирование

№	Входные данные	Выходные данные
1.	1 2 4 -1	-0.4
2.	1 2 3 4 5 0.6	1.88889
3.	5 -2 1 0.2 3 -3 2 0	-1.70909
4.	10 3.3 4 0.4 6 0.01 8 1 1 8	1.7469
5.	3 -0.5 2 -0.4 1 -0.3 5 32 11 5 20 -1	4.58095

Реализация (класс vector)

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
	vector<int> n;
	vector<double> x;
	int a, sum2 = 0;
	double b, res = 0, sum1 = 0; 
	while (cin >> a >> b) 
	{ 
		n.push_back(a); 
		x.push_back(b); 
	} 
	for (int i=0; i < x.size(); i++) 
	{ 
		sum1 += n[i] * x[i];
		sum2 += n[i];
		res = sum1 / sum2;
	} 
	cout << res << endl; 
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector<int> n;

vector<double> x;

int a, sum2 = 0;

double b, res = 0, sum1 = 0;

while (cin >> a >> b)

{

n.push_back(a);

x.push_back(b);

}

for (int i=0; i < x.size(); i++)

{

sum1 += n[i] * x[i];

sum2 += n[i];

res = sum1 / sum2;

}

cout << res << endl;

return 0;

}

Алгоритм решения (класс vector)

Считываем все натуральные числа до конца входного потока и записываем их в вектор [latex]n[/latex]. Аналогично, считываем все действительные числа до конца входного потока и записываем их в вектор [latex]x[/latex].

Вычисляем значение выражения [latex]n_1\cdot x_1+\dots+n_m\cdot x_m[/latex], накапливая сумму sum1.
Вычисляем значение выражения [latex]n_1+\dots+n_m[/latex], накапливая сумму sum2.
Находим результат res от деления sum1 на sum2.

Реализация (потоковая обработка)

#include <iostream>
#include <cmath> 
using namespace std;
 
int main()
{
	int member1, sum2 = 0;
	double member2, res = 0, sum1 = 0;
	while (cin >> member1 >> member2)
	{
		if (member1=='e') break;
		sum1 += member1 * member2;
		sum2 += member1;
	}
	res = sum1 / sum2;
	cout<< res << endl;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

int member1, sum2 = 0;

double member2, res = 0, sum1 = 0;

while (cin >> member1 >> member2)

{

if (member1=='e') break;

sum1 += member1 * member2;

sum2 += member1;

}

res = sum1 / sum2;

cout<< res << endl;

return 0;

}

Алгоритм решения (потоковая обработка)

Считываем все натуральные числа до конца входного потока и записываем их в переменную member1. Аналогично, считываем все действительные числа до конца входного потока и записываем их в переменную member2.
Пока вводятся данные:

Вычисляем значение выражения [latex]n_1\cdot x_1+\dots+n_m\cdot x_m[/latex], накапливая сумму sum1.
Вычисляем значение выражения [latex]n_1+\dots+n_m[/latex], накапливая сумму sum2.
Находим результат res от деления sum1 на sum2.

Для запроса на выполнение следует перейти по ссылке (класс vector).

Для запроса на выполнение следует перейти по ссылке (потоковая обработка).

Related Images:

А286

13/03/2016 by Таня Корнилова

Задача

Даны целые числа [latex]a_1,\cdots, a_{n}[/latex]. Получить новую последовательность, выбросив из исходной все члены со значением [latex]max(a_1,\cdots,a_{n})[/latex].

Тесты

№	Входные данные	Выходные данные
1	0 0 0 0 0 0 0 0
2	998 103678 3333 800000 542 2 48 132 9 745	998 103678 3333 542 2 48 132 9 745
3	1 2 42 -138 0 99 1 242 70 21	1 2 42 -138 0 99 1 70 21
4	-144 -789342454657 -155 -923 -7	-144 -789342454657 -155 -923
5	8 8 8 8 11 11 11 11 8 8 8 8	8 8 8 8 8 8 8 8

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

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
	long long a;
	long long n = 0; // номер максимального по значению элемента
	vector <long long> x;
	while (cin >> a) x.push_back(a);
	int counter = 0; // счётчик равных по значению элементов последовательности
	for (int i = 0; i < x.size(); i++) { // находим элемент с максимальным значением
		if (x[i] > x[n]) n = i; 
		else if (x[i] == x[n]) counter++;
	}
	if (counter != x.size()) { // если вся последовательность не состоит из равных элементов
		long long temp = x[n];
		for (int i = 0; i < x.size(); i++) { // удаляем все элементы с максимальным значением
			if (x[i] == temp) {
				x.erase(x.begin() + i);
				i--;
			}
		}
	} else x.clear(); // если последовательность из равных чисел
	for (int i = 0; i < x.size(); i++) {
		cout << x[i] << " ";
	}
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

long long a;

long long n = 0; // номер максимального по значению элемента

vector <long long> x;

while (cin >> a) x.push_back(a);

int counter = 0; // счётчик равных по значению элементов последовательности

for (int i = 0; i < x.size(); i++) { // находим элемент с максимальным значением

if (x[i] > x[n]) n = i;

else if (x[i] == x[n]) counter++;

}

if (counter != x.size()) { // если вся последовательность не состоит из равных элементов

long long temp = x[n];

for (int i = 0; i < x.size(); i++) { // удаляем все элементы с максимальным значением

if (x[i] == temp) {

x.erase(x.begin() + i);

i--;

}

} else x.clear(); // если последовательность из равных чисел

for (int i = 0; i < x.size(); i++) {

cout << x[i] << " ";

}

return 0;

}

Для запроса на выполнение нажать здесь.

Решение

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

Related Images:

A279

13/03/2016 by Катя Писова

Задача

Даны действительные числа [latex]a_{1},[/latex] … [latex], a_{n},[/latex] [latex]b_{1},[/latex] … [latex], b_{n}[/latex]. Вычислить [latex](a_{1} + b_{n})(a_{2} + b_{n-1})[/latex] … [latex](a_{n} + b_{1})[/latex].

Тесты

Test №	Input	Output
1	1 2 3 4 5 6	343
2	1 1 1 1	4
3	0.5 0.1 0.07 -4 7 13	-376.691
4	0 0 0 0 0 0 0 0	0
5	0.4 0.3 2 -1 0.7 0.6	1

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

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

int main()
{
    vector <long double> c;
    long double m, sum = 0, result = 1;
    while (cin >> m){
        c.push_back(m);
    }
    for (int i = 0; i < c.size()/2; i++){
        sum = c[i] + c[c.size() - 1 - i];
        result *= sum;
    }
    cout << result << endl;
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

vector <long double> c;

long double m, sum = 0, result = 1;

while (cin >> m){

c.push_back(m);

}

for (int i = 0; i < c.size()/2; i++){

sum = c[i] + c[c.size() - 1 - i];

result *= sum;

}

cout << result << endl;

return 0;

}

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

Считываем все действительные числа до конца входного потока и записываем их в один вектор c. Далее работаем по такому алгоритму: складываем первый элемент вектора с последним, а полученный результат умножаем на переменную result, значение которой изначально равно единице, т.к, единица — нейтральный элемент при умножении. Далее складываем второй элемент вектора с предпоследним, а полученный результат снова умножаем на переменную result и т.д. Так делаем до тех пор, пока не дойдем но середины вектора c. Затем выводим полученное значение переменной result.

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

Related Images:

A295

12/03/2016 by Женя Максимова

Задача. Даны целые числа [latex]a_{1},\ldots, a_{n}[/latex]. Наименьший член последовательности [latex]a_{1}, \ldots, a_{n}[/latex] заменить целой частью среднего арифметического всех членов, остальные члены оставить без изменения. Если в последовательности несколько членов со значением min [latex](a_{1}, \ldots, a_{n})[/latex], то заменить последний по порядку.

Тесты

Test	Input	Output
1	2 4 8 16 2 4	2 4 8 16 6 4
2	1 1 1 1	1 1 1 1
3	-5 5 -10 10 -10 5 5	-5 5 -10 10 0 5 5
4	2 6 9 -4 -5 7 13	2 6 9 -4 4 7 13
5	0 0 0 0 0 1	0 0 0 0 0 1
6	0 1 0 0 2 0 25	0 1 0 0 2 4 25

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

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

int main()
{
  vector<int>a;
  int el; //supporting variable for saving input values
  while(cin >> el)
    {
      a.push_back(el); //adding value to the vector
    }
  int min = a[0]; // minimal value
  int num = 0; // number of the minimal value
  double sum = 0; 
  for(int i=0; i<a.size(); i++)
    {
      if(a[i]<=min) //finding the number of the minimal value
        {
          min = a[i]; 
          num = i;
        }
      sum += a[i];
    }
  int average = floor(sum/a.size()); //calculing the average of vector elements
  a[num] = average; //replacing minimal value by the average
  for(int i = 0; i < a.size(); i++)
    {
      cout << a[i] << " ";
    }
  return 0;
}

#include<iostream>

#include<cmath>

#include<vector>

using namespace std;

int main()

{

vector<int>a;

int el; //supporting variable for saving input values

while(cin >> el)

{

a.push_back(el); //adding value to the vector

}

int min = a[0]; // minimal value

int num = 0; // number of the minimal value

double sum = 0;

for(int i=0; i<a.size(); i++)

{

if(a[i]<=min) //finding the number of the minimal value

{

min = a[i];

num = i;

}

sum += a[i];

}

int average = floor(sum/a.size()); //calculing the average of vector elements

a[num] = average; //replacing minimal value by the average

for(int i = 0; i < a.size(); i++)

{

cout << a[i] << " ";

}

return 0;

}

Алгоритм

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

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

Related Images:

A300

11/03/2016 by Таран Таня

There is a sequence of real numbers [latex]a_1, a_2, \ldots[/latex](read to the end of the input stream). You need to get the sequence of numbers [latex]b_1, \ldots, b_{10}[/latex], where [latex]b_i[/latex] is the sum of those members of input sequence, that belong left-open interval [latex](i — 1, i](i = 1, \ldots, 10)[/latex]. If the interval doesn’t contain any members of the sequence, the corresponding [latex]b_i[/latex] will be set equal to zero.

Input

The sequence of real numbers [latex]a_1, a_2, \ldots[/latex].

Output

Output the sequence [latex]b_1, \ldots, b_{10}[/latex], that satisfies specified conditions.

Tests

№	Input sequence	Output sequence
1	1 2 3 4 5 6 7 8 9 10	1 2 3 4 5 6 7 8 9 10
2	1 1 1 1 1 1 1	7 0 0 0 0 0 0 0 0 0
3	2.1 2.5 2.7	0 0 7.3 0 0 0 0 0 0 0
4	11 12 13 14 15	0 0 0 0 0 0 0 0 0 0
5	2 12 85 0.6	0.6 2 0 0 0 0 0 0 0 0
6	2.02 42 1.998 3 7.43 3.33 3.03 5.56 5 5.5	0 1.998 5.02 6.36 5 11.06 0 7.43 0 0

Algorithm

The proposed task we can solve in two different ways: using class vector and like a problem with stream processing of data.

Class vector:
Initialize a vector, that will store all the elements of the input sequence (push them to the vector to the end of the input stream). Further, sort it ascending for easy follow-up work. For the each element of initial sequence check whether it belongs to the current interval. If it is true, it will be added to the corresponding element of resulting sequence, or zero will be added otherwise. Output the resulting sequence.
Stream processing:
While we are reading the input stream, we can determine which element of the resulting sequence it belongs, by using rounding to smallest integral value that is not less that our and substracting one (we need to remember that we can’t go beyond the bounds of the array, therefore we use a separate check). Perform the output of the result.

Code (class Vector)

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

const unsigned int RESULTING_SEQUENCE_SIZE = 10;

int main() {
	double currentMember;
	vector <double> inputSequence;
    double resultingSequence[RESULTING_SEQUENCE_SIZE]{0};
    // Adds a new element to the vector to the end of the input stream
    while (cin >> currentMember) {
    	inputSequence.push_back(currentMember);
    } 
    sort(inputSequence.begin(), inputSequence.end()); // Sort ascending initial sequence
    for (int i = 0; i < RESULTING_SEQUENCE_SIZE; i++) {
    	// Accumulate the sum of suitable elements to the corresponding member of the result sequence
    	for (auto currentMember : inputSequence) {
    		resultingSequence[i] += (i < currentMember && currentMember <= i + 1 ? currentMember : 0);
    	}
    }
    // Output the sequence
    for (auto currentMember : resultingSequence) {
    	cout << currentMember << " ";
    } 
	return 0;
}

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

const unsigned int RESULTING_SEQUENCE_SIZE = 10;

int main() {

double currentMember;

vector <double> inputSequence;

double resultingSequence[RESULTING_SEQUENCE_SIZE]{0};

// Adds a new element to the vector to the end of the input stream

while (cin >> currentMember) {

inputSequence.push_back(currentMember);

}

sort(inputSequence.begin(), inputSequence.end()); // Sort ascending initial sequence

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

// Accumulate the sum of suitable elements to the corresponding member of the result sequence

for (auto currentMember : inputSequence) {

resultingSequence[i] += (i < currentMember && currentMember <= i + 1 ? currentMember : 0);

}

// Output the sequence

for (auto currentMember : resultingSequence) {

cout << currentMember << " ";

}

return 0;

}

Code (stream processing)

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

const unsigned int RESULTING_SEQUENCE_SIZE = 10;

int main() {
	double currentMember;
	double resultingSequence[RESULTING_SEQUENCE_SIZE]{0}; 
    // Process until the end of the input stream
    while (cin >> currentMember) {
    	// Accumulate the sum of suitable elements to the corresponding member of the resulting sequence
    	if (1 <= ceil(currentMember) && ceil(currentMember) <= RESULTING_SEQUENCE_SIZE) {
    		resultingSequence[(int)ceil(currentMember) - 1] += currentMember; 
    	} 
    } 
    // Output the sequence
    for (auto currentMember : resultingSequence) {
    	cout << currentMember << " ";
    } 
	return 0;
}

#include <cmath>

#include <iostream>

using namespace std;

const unsigned int RESULTING_SEQUENCE_SIZE = 10;

int main() {

double currentMember;

double resultingSequence[RESULTING_SEQUENCE_SIZE]{0};

// Process until the end of the input stream

while (cin >> currentMember) {

// Accumulate the sum of suitable elements to the corresponding member of the resulting sequence

if (1 <= ceil(currentMember) && ceil(currentMember) <= RESULTING_SEQUENCE_SIZE) {

resultingSequence[(int)ceil(currentMember) - 1] += currentMember;

}

// Output the sequence

for (auto currentMember : resultingSequence) {

cout << currentMember << " ";

}

return 0;

}

Related Images:

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

09/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\leq 100[/latex]. В каждой из следующих [latex]n[/latex] строк содержится один запрос в соответствии с форматом, описанным выше. В качестве «username» и «password» могут выступать любые непустые строки длиной до 30 символов включительно. Строки могут состоять только из символов с кодами от 33 до 126.

Результат

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

Пример

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

Результат

6register vasya 12345

logout vasya

success: new user addedfail: incorrect password

success: user logged in

fail: no such user

success: user logged out

fail: already logged out

Код

import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.Vector;
import java.util.TreeMap;
import java.lang.NumberFormatException;

public class Timus2002App
{

   //структура, описывающая атрибуты учетной записи
   public class AccountInfo
   {
      public String password;
      public boolean loggedIn;

      public AccountInfo(String argPassword, boolean argLoggedIn)
      {
         password = argPassword;
         loggedIn = argLoggedIn;
      }
   }

   
   //база данных учетной записи
   public class AccountDatabase
   {
      public static final int OK = 0;
      public static final int NOT_REGISTERED = 1;
      public static final int WRONG_PASSWORD = 2;
      public static final int ALREADY_LOGGED_IN = 3;
      public static final int ALREADY_LOGGED_OUT = 4;

      private TreeMap<String, AccountInfo> map;

      //конструктор
      public AccountDatabase()
      {
         map = new TreeMap<String, AccountInfo>();
      }

      //регистрация новой учетной записи
      public boolean register(String name, String password)
      {
         AccountInfo info = map.get(name);

         if (info != null)
         {
            return false;
         }

         map.put(name, new AccountInfo(password, false));

         return true;
      }

      //вход в систему
      public int login(String name, String password)
      {
         int result = NOT_REGISTERED;

         AccountInfo info = map.get(name);

         if (info != null)
         {
            if (!info.password.equals(password))
            {
               result = WRONG_PASSWORD;
            }
            else if (info.loggedIn)
            {
               result = ALREADY_LOGGED_IN;
            }
            else
            {
               map.put(name, new AccountInfo(info.password, true));
               result = OK;
            }
         }

         return result;
      }

      //выход из системы
      public int logout(String name)
      {
         int result = NOT_REGISTERED;

         AccountInfo info = map.get(name);

         if ( info != null )
         {
            if ( info.loggedIn )
            {
               map.put(name, new AccountInfo(info.password, false));
               result = OK;
            }
            else
            {
               result = ALREADY_LOGGED_OUT;
            }
         }

         return result;
      }

   }

   public static void main(String[] args)
   {
      int loginCount = 0;
      String line = null;
      
      Scanner in = new Scanner(System.in);
      //System.out.println("please enter number of logins: ");
      line = ( in.hasNextLine( ) ) ? in.nextLine() : null;
      try
      {
         loginCount = Integer.parseInt(line.trim());
      }
      catch( NumberFormatException e )
      {
      }
      
      if ( loginCount < 1 || loginCount > 100 )
      {
         System.out.println("**** ERROR: wrong number of logins ****");
         in.close();
         return;
      }
      
      Timus2002App mainObj = new Timus2002App();
      AccountDatabase accounts = mainObj.new AccountDatabase();
      
      for( int i = 0; i < loginCount; i++ )
      {
         //System.out.println("please enter command:");
         
         line = ( in.hasNextLine( ) ) ? in.nextLine() : null;
         if ( line == null || line.isEmpty() )
         {
            System.out.println("**** ERROR: empty input, abort processing ****");
            break;
         }
         
         //превращение введенной строки текста в вектор лексем
         StringTokenizer st = new StringTokenizer(line, " ");
         Vector<String> tokens = new Vector<String>();
         while (st.hasMoreTokens())
         {
            tokens.add( st.nextToken() );
         }

         //превращение вектора лексем в команду с аргументами
         String command   = ( tokens.size() > 0 ) ? tokens.get(0) : null;
         String name      = ( tokens.size() > 1 ) ? tokens.get(1) : null;
         String password  = ( tokens.size() > 2 ) ? tokens.get(2) : null;
         String message = null;
        
        //выполнение команд
         if ( command.equals("register"))
         {
            if ( name != null || password != null )
            {
               if ( accounts.register(name, password) )
               {
                  message = "success: new user added";
               }
               else
               {
                  message = "fail: user already exists";
               }
            }
            else
            {
               message = "fail: missing user name or password";
            }
         }
         else if ( command.equals("login"))
         {
            if ( name != null || password != null )
            {
               switch( accounts.login(name, password) )
               {
                  case AccountDatabase.NOT_REGISTERED:
                     message = "fail: no such user";
                  break;
                  case AccountDatabase.WRONG_PASSWORD:
                     message = "fail: incorrect password";
                  break;
                  case AccountDatabase.ALREADY_LOGGED_IN:
                     message = "fail: already logged in";
                  break;
                  default:
                     message = "success: user logged in";
                  break;
              }
           }
           else
           {
              message = "fail: missing user name or password";
           }
         }
         else if ( command.equals("logout"))
         {
            if ( name != null )
            {
               switch( accounts.logout(name) )
               {
                  case AccountDatabase.ALREADY_LOGGED_OUT:
                     message = "fail: already logged out";
                  break;
                  case AccountDatabase.NOT_REGISTERED:
                     message = "fail: no such user";
                  break;
                  default:
                     message = "success: user logged out";
                  break;
               }
            }
            else
            {
               message = "fail: missing user name";
            }
         }
         
         if ( message != null )
         {
            System.out.println(message);
         }
      }
      in.close();
   } 
}

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

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

import java.util.Scanner;

import java.util.StringTokenizer;

import java.util.Vector;

import java.util.TreeMap;

import java.lang.NumberFormatException;

public class Timus2002App

{

//структура, описывающая атрибуты учетной записи

public class AccountInfo

{

public String password;

public boolean loggedIn;

public AccountInfo(String argPassword, boolean argLoggedIn)

{

password = argPassword;

loggedIn = argLoggedIn;

}

//база данных учетной записи

public class AccountDatabase

{

public static final int OK = 0;

public static final int NOT_REGISTERED = 1;

public static final int WRONG_PASSWORD = 2;

public static final int ALREADY_LOGGED_IN = 3;

public static final int ALREADY_LOGGED_OUT = 4;

private TreeMap<String, AccountInfo> map;

//конструктор

public AccountDatabase()

{

map = new TreeMap<String, AccountInfo>();

}

//регистрация новой учетной записи

public boolean register(String name, String password)

{

AccountInfo info = map.get(name);

if (info != null)

{

return false;

}

map.put(name, new AccountInfo(password, false));

return true;

}

//вход в систему

public int login(String name, String password)

{

int result = NOT_REGISTERED;

AccountInfo info = map.get(name);

if (info != null)

{

if (!info.password.equals(password))

{

result = WRONG_PASSWORD;

}

else if (info.loggedIn)

{

result = ALREADY_LOGGED_IN;

}

else

{

map.put(name, new AccountInfo(info.password, true));

result = OK;

}

return result;

}

//выход из системы

public int logout(String name)

{

int result = NOT_REGISTERED;

AccountInfo info = map.get(name);

if ( info != null )

{

if ( info.loggedIn )

{

map.put(name, new AccountInfo(info.password, false));

result = OK;

}

else

{

result = ALREADY_LOGGED_OUT;

}

return result;

}

public static void main(String[] args)

{

int loginCount = 0;

String line = null;

Scanner in = new Scanner(System.in);

//System.out.println("please enter number of logins: ");

line = ( in.hasNextLine( ) ) ? in.nextLine() : null;

try

{

loginCount = Integer.parseInt(line.trim());

}

catch( NumberFormatException e )

{

}

if ( loginCount < 1 || loginCount > 100 )

{

System.out.println("**** ERROR: wrong number of logins ****");

in.close();

return;

}

Timus2002App mainObj = new Timus2002App();

AccountDatabase accounts = mainObj.new AccountDatabase();

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

{

//System.out.println("please enter command:");

line = ( in.hasNextLine( ) ) ? in.nextLine() : null;

if ( line == null || line.isEmpty() )

{

System.out.println("**** ERROR: empty input, abort processing ****");

break;

}

//превращение введенной строки текста в вектор лексем

StringTokenizer st = new StringTokenizer(line, " ");

Vector<String> tokens = new Vector<String>();

while (st.hasMoreTokens())

{

tokens.add( st.nextToken() );

}

//превращение вектора лексем в команду с аргументами

String command = ( tokens.size() > 0 ) ? tokens.get(0) : null;

String name = ( tokens.size() > 1 ) ? tokens.get(1) : null;

String password = ( tokens.size() > 2 ) ? tokens.get(2) : null;

String message = null;

//выполнение команд

if ( command.equals("register"))

{

if ( name != null || password != null )

{

if ( accounts.register(name, password) )

{

message = "success: new user added";

}

else

{

message = "fail: user already exists";

}

else

{

message = "fail: missing user name or password";

}

else if ( command.equals("login"))

{

if ( name != null || password != null )

{

switch( accounts.login(name, password) )

{

case AccountDatabase.NOT_REGISTERED:

message = "fail: no such user";

break;

case AccountDatabase.WRONG_PASSWORD:

message = "fail: incorrect password";

break;

case AccountDatabase.ALREADY_LOGGED_IN:

message = "fail: already logged in";

break;

default:

message = "success: user logged in";

break;

}

else

{

message = "fail: missing user name or password";

}

else if ( command.equals("logout"))

{

if ( name != null )

{

switch( accounts.logout(name) )

{

case AccountDatabase.ALREADY_LOGGED_OUT:

message = "fail: already logged out";

break;

case AccountDatabase.NOT_REGISTERED:

message = "fail: no such user";

break;

default:

message = "success: user logged out";

break;

}

else

{

message = "fail: missing user name";

}

if ( message != null )

{

System.out.println(message);

}

in.close();

}

Данная программа представляет собой типичный пример использования таблицы символов, согласно терминологии Coursera. Для доступа к учетным записям используется интерфейс Map, а для реализации самой базы данных учетных записей — объект типа TreeMap. Учетная запись пользователей реализована в виде одного элемента типа Map.entry, где имя пользователя — это ключ, а атрибуты учетной записи — пароль и флаг подключен/отключен — реализованы в виде отдельной структуры AccountInfo, которая является значением этого ключа.

Время работы	Выделено памяти
0.124	1 928 КБ

Ссылка на Ideone: https://ideone.com/3Y2W4z

Related Images:

A841

18/06/2015 by Григорян Артак

Задача. «Исправление ошибок». Пусть по некоторому каналу связи передается сообщение, имеющее вид последовательностей нулей и единиц (или, аналагично, точек и тире). Из-за помех, возможен ошибочный прием некоторых сигналов: нуль может быть воспринят как единица и наоборот. Можно передавать каждый сигнал трижды, заменяя, например, последовательность 1, 0, 1 последовательностью 1, 1, 1, 0, 0, 0, 1, 1, 1. Три последовательные цифры при расшифровке заменяются той цифрой, которая встречается среди них по крайне мере дважды. Такое утраивание сигналов существенно повышает вероятность правильного приема сообщения. Написать программу расшифровки.

1 0 1 0 0 1 1 1 0	1 0 1
0 0 0 1 1 1 0 0 0	0 1 0
0 1 0 1 0 1 0 1 0 1 0 1	0 1 0 1

#include<iostream>
#include<vector>
using namespace std;
 int main()
 {
 	int n;
 	vector<int> m; 
	int k=0;
 	while(cin>>n)
 	{
 		m.push_back(n);
 		k++;
 	}	
 	int p=k/3;
 	for(int j=0;j<p;j++)
 		{	
 			int a=0;
 			for(int i=0;i<3;i++)
 				{
 					if(m[i]==1)a++;
 				}
 			m.erase(m.begin(),m.begin()+3);
 			if(a==0||a==1) cout<<"0";
 			if(a==2||a==3) cout<<"1";
 		}
 	return 0;
 }

#include<iostream>

#include<vector>

using namespace std;

int main()

{

int n;

vector<int> m;

int k=0;

while(cin>>n)

{

m.push_back(n);

k++;

}

int p=k/3;

for(int j=0;j<p;j++)

{

int a=0;

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

{

if(m[i]==1)a++;

}

m.erase(m.begin(),m.begin()+3);

if(a==0||a==1) cout<<"0";

if(a==2||a==3) cout<<"1";

}

return 0;

}

Записываем входные данные в вектор. Делим вектор на части по три символа. Пробегаем по этим трем символам, увеличивая счетчик, если символ «1». Если единиц больше, чем нулей, то записываем «1». Если нулей больше, чем единиц, то записываем «0». Удаляем фрагмент вектора, для удобства, и пробегаем по следующим трем символам.

Код программы можно посмотреть тут

Related Images:

e-olimp 3837. Выражения

05/04/2015 by Вустянюк Ігор Дмитрович

Задача

Арифметические выражения, как правило, записываются с операторами между двумя операндами (такая запись называется инфиксной нотацией). Например, (x + y) * (z — w) — арифметическое выражение в инфиксной нотации. Однако легче написать программу, вычисляющую значение выражения, когда оно находится в постфиксной нотации (известная как обратная польская нотация). В постфиксной нотации оператор записывается за своими двумя операндами, которые и сами в могут быть выражениями. Например, x y + z w — * является постфиксной нотацией приведенного выше выражения. Заметим, что для такой записи скобки не нужны.

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

push: число кладется на верх стека.
pop: число снимается с вершины стека.

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

a := pop();

b := pop();

push(b O a);

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

Предположим, что мы используем вместо стека очередь. Очередь также имеет операции push иpop, но их смысл немного другой:

push: число вставляется в конец очереди.
pop: из начала очереди извлекается число.

Можете ли Вы переписать заданное выражение так, чтобы алгоритм, использующий очередь при его вычислении, давал тот же результат, что и алгоритм вычисления со стеком?

Пояснения к решению

Если задана правильная строка в постфиксной нотации, то алгоритм её вычисления на основе стека выглядит следующим образом:

Просматриваем строку слева направо
Если встречаем переменную, помещаем её в конец стека/очереди
Если встречаем символ оператора * , то выполняем следующие действия: снимаем со стека a, снимаем со стека b и кладём на стек b * a.

По условию задачи, мы должны обрабатывать строки, используя вместо стека очередь, поэтому описанные выше действия примут следующий вид: снимаем с очереди a, снимаем с очереди b и кладём в конец очереди b * a.

Постфиксную запись, рассчитанную на обработку посредством стека, будем называть s-постфиксной, а рассчитанную на обработку очередью — q-постфиксной.

Две записи «вычислятся одинаково» в том и только в том случае, когда соответствующие им деревья синтаксического разбора (англ.: parse tree, далее — ДСР) одинаковы. Идея приведённого ниже алгоритма состоит примерно в следующем: на основе s-постфиксной записи строим ДСР, обходя которое специальным образом, получаем q-постфиксную запись. Нужно обходить дерево по уровням справа налево (под уровнем дерева подразумевается множество всех вершин дерева, равноудалённых от корня; уровни дерева естественным образом нумеруются: корень расположен на уровне 0 и так далее). В приведённом ниже коде функция get_levels генерирует уровни ДСР на основе s-постфиксной нотации в виде вектора строк, k-ая компонента которого соответствует k-му уровню ДСР заданной строки, вершины которого (если таковые имеются) перечислены справа налево. Поскольку у ДСР может быть не больше уровней, чем символов в строке, то создаём вектор как раз с таким числом компонент и инициализируем его компоненты пустыми строками.

Корректность функции get_levels можно доказать индукцией по длине строки, отметим, что если строка содержит более одного элемента, то она имеет вид ФGО, где Ф и G — правильные строки, О — символ оператора. Запустить рекурсивно функцию с предпоследней позиции — всё равно, что применить её к строке G. ДСР этой строки является левым поддеревом для ДСР исходной строки и k-ый уровень этого дерева является (k+1)-ым уровнем ДСР исходной строки (именно поэтому вызываем функцию с параметром depth на 1 больше). По индукционному предположению, дойдя до начала строки G, функция корректно «расставит» уровни ДСР этой строки (с учётом + 1) и завершит свою работу. Аналогично будут правильно расставлены уровни ДСР строки Ф, которое является правым поддеревом исходной строки. Таким образом, все вершины ДСР исходной строки будут правильно расставлены, а поскольку рекурсия вызывается сначала для левого, а потом для правого её поддерева, то и перечислены вершины на каждом уровне будут справа налево.

Код на С++

Ссылка на программу в ideone.

#include <iostream>
#include <string>
#include <vector>

using namespace std;

/* Expr - строка-формула, которую мы обрабатываем
 index - текущий символ в строке Expr
 depth - текущий уровень дерева разбора
 Answer - вектор уровней */

void get_levels(string& Expr, int& index, int depth, vector<string>& Answer) {
	Answer[depth] += Expr[index];
	index--;
	if (isupper(Expr[index+1])) {
		get_levels(Expr, index, depth + 1, Answer);
		get_levels(Expr, index, depth + 1, Answer);
	}
}


int main() {
	int n, index;
	cin >> n;
	string Expr;
	for (int k = 0; k < n; k++) {
		cin >> Expr;						
		vector<string> Answer(Expr.size(), "");
		index = Expr.size() - 1;
		get_levels(Expr, index, 0, Answer);
		for (int k = Expr.size() - 1; k >= 0; k--)
			cout << Answer[k];
		cout << endl;
	}
	return 0;
}

#include <iostream>

#include <string>

#include <vector>

using namespace std;

/* Expr - строка-формула, которую мы обрабатываем

index - текущий символ в строке Expr

depth - текущий уровень дерева разбора

Answer - вектор уровней */

void get_levels(string& Expr, int& index, int depth, vector<string>& Answer) {

Answer[depth] += Expr[index];

index--;

if (isupper(Expr[index+1])) {

get_levels(Expr, index, depth + 1, Answer);

}

int main() {

int n, index;

cin >> n;

string Expr;

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

cin >> Expr;

vector<string> Answer(Expr.size(), "");

index = Expr.size() - 1;

get_levels(Expr, index, 0, Answer);

for (int k = Expr.size() - 1; k >= 0; k--)

cout << Answer[k];

cout << endl;

}

return 0;

}

Код на Java

Ссылка на программу в ideone.

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

class Index {
	int in;
	public Index(int a) {
		in = a;
	}
}

class Main
{
	public static void get_levels(char[] Expr, Index index, int depth, String[] Answer) {
		Answer[depth] += Expr[index.in];
		index.in--;
		if (Character.isUpperCase(Expr[index.in + 1])) {
			get_levels(Expr, index, depth + 1, Answer);
			get_levels(Expr, index, depth + 1, Answer);
		}
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		String str = in.nextLine();

		for (int k = 0; k < n; k++) {
			str = in.nextLine();
			char[] Expr = str.toCharArray();
			String[] Answer = new String[Expr.length];
			Arrays.fill(Answer, "");
			Index index = new Index(Expr.length - 1);
			get_levels(Expr, index, 0, Answer);
			for (int j = Expr.length - 1; j >= 0; j--)
				System.out.print(Answer[j]);
			System.out.println();
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Index {

int in;

public Index(int a) {

in = a;

}

class Main

{

public static void get_levels(char[] Expr, Index index, int depth, String[] Answer) {

Answer[depth] += Expr[index.in];

index.in--;

if (Character.isUpperCase(Expr[index.in + 1])) {

get_levels(Expr, index, depth + 1, Answer);

}

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

String str = in.nextLine();

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

str = in.nextLine();

char[] Expr = str.toCharArray();

String[] Answer = new String[Expr.length];

Arrays.fill(Answer, "");

Index index = new Index(Expr.length - 1);

get_levels(Expr, index, 0, Answer);

for (int j = Expr.length - 1; j >= 0; j--)

System.out.print(Answer[j]);

System.out.println();

}

Related Images:

e-olimp 122. Горные маршруты

02/04/2015 by Вустянюк Ігор Дмитрович

Задача. Горный туристический комплекс состоит из n турбаз, соединенных между собой k горными переходами (другие маршруты в горах опасны). Любой переход между двумя базами занимает 1 день. Туристическая группа находится на базе a и собирается попасть на базу b не более чем за d дней. Сколько существует разных таких маршрутов (без циклов) между a и b?
Ссылка на задачу

Пояснение к решению

Поиск путей представляет из себя модифицированный обход в глубину. Вместо массива «глобально посещённых» вершин, в которые уже нельзя возвращаться при обходе, я использую массив «локально посещённых» вершин. Это позволяет использовать одну и ту же вершину в разных, в том числе очень длинных и извращённых путях (в стандартном варианте ищется кратчайший путь, а нам нужны все: в том числе длинные и извращённые).

Кроме того, добавлен параметр depth — длина рассматриваемого в данный момент пути (или глубина текущего рекуррентного вызова, если угодно). Этот параметр изначально имеет значение 0 и при каждом вызове сравнивается с максимально допустимым значением. Перед рекуррентным вызовом мы увеличиваем значение depth, ведь длина нового пути будет на 1 больше. После вызова, т.е. возвращаясь на предыдущий уровень рекурсии, мы уменьшаем длину пути (ведь мы «отбросили» последнюю вершину, т.е. длина пути уменьшилась на 1).

Алгоритм работает примерно так: сначала посещаем начальную вершину и помечаем её как локально посещённую. Если она — искомая, увеличиваем количество найденных путей на 1 и алгоритм завершает свою работу (путей без циклов, содержащих более одной вершины, в этом случае быть не может). Если же начальная вершина не совпадает с целевой, то для всех вершин, в которые можно попасть из неё, применяем рекуррентно тот же алгоритм. Если таких вершин нет, алгоритм завершается, возвращая 0 (нет ни одного пути из начальной вершины в конечную). Если же такие вершины имеются, то увеличиваем параметр «глубина» и вызываем для них рекуррентно наш алгоритм. После выхода из рекурсии, возвращаем параметр «глубина» к последнему его значению (тем, что было перед вызовом) и, чтобы мы могли использовать данную вершину в других путях помечаем её как «локально свободную».

Стоит отметить, что в общем случае задача поиска всех простых путей (пусть даже удовлетворяющих определённым условиям, как в данной задаче) является NP-полной, т.е. решается исключительно переборными алгоритами, работающими за неполиномиальное время (более эффективных алгоритмов для решения таких задач на сегодняшний день неизвестно; кто их найдёт, получит миллион долларов; я не нашёл). Также отметим, что простая модификация приведённого алгоритма позволяет не только вычислять количество простых путей указанной длины, но и перечислять их.

Решение на С++

#include <stdio.h>
#include <vector>
#include <stdlib.h>
using namespace std;

struct Graph {
	vector< vector<int> > AdjList;
	int Size;
	
	Graph(int n) {
		vector<int> List;
		for (int k = 0; k < n; k++)
			AdjList.push_back(List);
		Size = n;
	}

	void add_vertex() {					// вершина == целое число == номер этой вершины в списке вершин
		Size++;
		vector<int> List;
		AdjList.push_back(List);
	}
	
	void add_edge(int u, int v) {		// u и v уже должны быть в списке вершин
		AdjList[u].push_back(v);
	}

	int simple_paths(int start, int end, int max_depth) {
		bool* on_path = (bool*) calloc(Size, sizeof(bool));
		int cur_depth = 0;
		int count = 0;
		simple_paths(start, end, on_path, cur_depth, max_depth, count);
		return count;
	}
	
	void simple_paths(int start, int end, bool* on_path, int& cur_depth, int max_depth, int& count) {
		if (cur_depth <= max_depth) {
			on_path[start] = true;
			if (start == end)
				count++;
			else
				for (int k = 0; k < AdjList[start].size(); k++) {
					int v = AdjList[start][k];
					if (!on_path[v]) {
						cur_depth++;
						simple_paths(v, end, on_path, cur_depth, max_depth, count);
						on_path[v] = false;
						cur_depth--;
					}
				}
		}
	}
	
};


int main() {
	int n, k, a, b, d, tmp1, tmp2;
	scanf("%d %d %d %d %d", &n, &k, &a, &b, &d);
	Graph G(n);
	for (int i = 0; i < k; i++) {
		scanf("%d %d", &tmp1, &tmp2);
		G.add_edge(tmp1 - 1, tmp2 - 1);
	}
	printf("%d\n", G.simple_paths(a-1, b-1, d));
	return 0;
}

#include <stdio.h>

#include <vector>

#include <stdlib.h>

using namespace std;

struct Graph {

vector< vector<int> > AdjList;

int Size;

Graph(int n) {

vector<int> List;

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

AdjList.push_back(List);

Size = n;

}

void add_vertex() { // вершина == целое число == номер этой вершины в списке вершин

Size++;

vector<int> List;

AdjList.push_back(List);

}

void add_edge(int u, int v) { // u и v уже должны быть в списке вершин

AdjList[u].push_back(v);

}

int simple_paths(int start, int end, int max_depth) {

bool* on_path = (bool*) calloc(Size, sizeof(bool));

int cur_depth = 0;

int count = 0;

simple_paths(start, end, on_path, cur_depth, max_depth, count);

return count;

}

void simple_paths(int start, int end, bool* on_path, int& cur_depth, int max_depth, int& count) {

if (cur_depth <= max_depth) {

on_path[start] = true;

if (start == end)

count++;

else

for (int k = 0; k < AdjList[start].size(); k++) {

int v = AdjList[start][k];

if (!on_path[v]) {

cur_depth++;

simple_paths(v, end, on_path, cur_depth, max_depth, count);

on_path[v] = false;

cur_depth--;

}

};

int main() {

int n, k, a, b, d, tmp1, tmp2;

scanf("%d %d %d %d %d", &n, &k, &a, &b, &d);

Graph G(n);

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

scanf("%d %d", &tmp1, &tmp2);

G.add_edge(tmp1 - 1, tmp2 - 1);

}

printf("%d\n", G.simple_paths(a-1, b-1, d));

return 0;

}

Решение на Java

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

class myInt {
	int v;
	public myInt(int a) {
		this.v = a;
	}
}

class Graph {
	Vector<Vector<Integer>> AdjList;

	public Graph(int n) {
		AdjList = new Vector<Vector<Integer>>(n);
		for (int k = 0; k < n; k++)
			AdjList.add(new Vector<Integer>());
	}
	
	public void add_vertex() {
		AdjList.add(new Vector<Integer>());
	}
	
	public void add_edge(int u, int v) {
		AdjList.elementAt(u).add(v);
	}
	
	public int simple_paths(int start, int end, int max_depth) {
		boolean[] on_path = new boolean[AdjList.size()];
		myInt cur_depth = new myInt(0);
		myInt count = new myInt(0);
		simple_paths(start, end, on_path, cur_depth, max_depth, count);
		return count.v;
	}
	
	public void simple_paths(int start, int end, boolean[] on_path, myInt cur_depth, int max_depth, myInt count) {
		if (cur_depth.v <= max_depth) {
			on_path[start] = true;
			if (start == end)
				count.v++;
			else
				for (int k = 0; k < AdjList.elementAt(start).size(); k++) {
					int v = AdjList.elementAt(start).elementAt(k);
					if (!on_path[v]) {
						cur_depth.v++;
						simple_paths(v, end, on_path, cur_depth, max_depth, count);
						on_path[v] = false;
						cur_depth.v--;
					}
				}
		}
	}
}

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), k = in.nextInt();
		int a = in.nextInt(), b = in.nextInt(), d = in.nextInt();
		int tmp1, tmp2;
		Graph G = new Graph(n);
		for (int i = 0; i < k; i++) {
			tmp1 = in.nextInt();
			tmp2 = in.nextInt();
			G.add_edge(tmp1 - 1, tmp2 - 1);
		}
		System.out.println(G.simple_paths(a-1, b-1, d));
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class myInt {

int v;

public myInt(int a) {

this.v = a;

}

class Graph {

Vector<Vector<Integer>> AdjList;

public Graph(int n) {

AdjList = new Vector<Vector<Integer>>(n);

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

AdjList.add(new Vector<Integer>());

}

public void add_vertex() {

AdjList.add(new Vector<Integer>());

}

public void add_edge(int u, int v) {

AdjList.elementAt(u).add(v);

}

public int simple_paths(int start, int end, int max_depth) {

boolean[] on_path = new boolean[AdjList.size()];

myInt cur_depth = new myInt(0);

myInt count = new myInt(0);

simple_paths(start, end, on_path, cur_depth, max_depth, count);

return count.v;

}

public void simple_paths(int start, int end, boolean[] on_path, myInt cur_depth, int max_depth, myInt count) {

if (cur_depth.v <= max_depth) {

on_path[start] = true;

if (start == end)

count.v++;

else

for (int k = 0; k < AdjList.elementAt(start).size(); k++) {

int v = AdjList.elementAt(start).elementAt(k);

if (!on_path[v]) {

cur_depth.v++;

simple_paths(v, end, on_path, cur_depth, max_depth, count);

on_path[v] = false;

cur_depth.v--;

}

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

int n = in.nextInt(), k = in.nextInt();

int a = in.nextInt(), b = in.nextInt(), d = in.nextInt();

int tmp1, tmp2;

Graph G = new Graph(n);

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

tmp1 = in.nextInt();

tmp2 = in.nextInt();

G.add_edge(tmp1 - 1, tmp2 - 1);

}

System.out.println(G.simple_paths(a-1, b-1, d));

}

Related Images:

Ю5.11

20/12/2014 by Божик Семен

Задача: Задача Иосифа. По кругу располагается [latex]n[/latex] человек. Ведущий считает по кругу и выводит («казнит») [latex]m[/latex]-го человека*. Круг смыкается, счет возобновляется со следующего после «казнённого»; так продолжается, пока «в живых» не остаётся только 1 человек. Найти номер этого человека, [а так-же для заданного [latex]n[/latex] найти такое [latex]m>1[/latex] , при котором в живых остаётся первый]**.

* — m не может превышать n по условию.

** — вторая часть задачи.

Тесты:

Ввод	Вывод	Комментарий
2 1	2 [2]	Работает
3 3	2 [не существует]	Работает
271 42	121 [69]	Работает
271 69	1 [69]	Работает

Объяснение переменных:

bool existing - булева переменная для фиксирования существования второй части задачи. vector <int> a — вектор, по задаче представляет собой нумерацию людей.

unsigned int n, m — переменные, где n и m соответсвуют условию задачи.

int JeosifFunc(a, n, m) — функция, которая выполняет основной алгоритм задачи.

Код: Проверить на ideone.

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

//функция ниже нам понадобится дважды.
int JeosifFunc(vector <int> a, unsigned int n, unsigned int m){
	for (unsigned int i=a.size(); i>1; i--){ //задаем цикл, который выполняется n-1 раз
		if (m>a.size()){        
				m=a.size()%m-1; //m не больше n => (люди в круге, используем операцию %)
		}                       
		a.erase (a.begin()+m-1);//=> последовательно стираем 
		for (unsigned int i=0; i<m-1; i++){
			a.push_back (a[i]); // для удобства первые элементы до m продублируем вконец вектора
		}
		a.erase (a.begin(), a.begin()+m-1);//стираем всё до m.
	}
	return a[0]; //ответ будет храниться в a[0].
}

int main() {
	bool existing = false;
	vector <int> a;
	unsigned int n, m;
	cin >> n >> m; // 
	for (unsigned int i=1; i<=n; i++){ // заполняем вектор числами от 1 до n
		a.push_back (i);
	}
	cout << JeosifFunc(a, n, m) << " ["; // первая часть задания на этом закончена.
	//подставим всевозможные m в виде k и зафиксируем k при JeosifFunc(a, n, k) = 1
	for (unsigned int k = 2; (k <= n)&&(existing == false); k++){// m>1 => k = 2
		if( JeosifFunc(a, n, k) == 1){ // если обнаруживается такое k, что выживает первый номер,
			existing = true;//выключаем цикл
			cout << k<< "]";// выводим k
		}
	}
	if (existing == false){ // если такого k не нашлось.
		cout << "не существует]";
	}
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

//функция ниже нам понадобится дважды.

int JeosifFunc(vector <int> a, unsigned int n, unsigned int m){

for (unsigned int i=a.size(); i>1; i--){ //задаем цикл, который выполняется n-1 раз

if (m>a.size()){

m=a.size()%m-1; //m не больше n => (люди в круге, используем операцию %)

}

a.erase (a.begin()+m-1);//=> последовательно стираем

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

a.push_back (a[i]); // для удобства первые элементы до m продублируем вконец вектора

}

a.erase (a.begin(), a.begin()+m-1);//стираем всё до m.

}

return a[0]; //ответ будет храниться в a[0].

}

int main() {

bool existing = false;

vector <int> a;

unsigned int n, m;

cin >> n >> m; //

for (unsigned int i=1; i<=n; i++){ // заполняем вектор числами от 1 до n

a.push_back (i);

}

cout << JeosifFunc(a, n, m) << " ["; // первая часть задания на этом закончена.

//подставим всевозможные m в виде k и зафиксируем k при JeosifFunc(a, n, k) = 1

for (unsigned int k = 2; (k <= n)&&(existing == false); k++){// m>1 => k = 2

if( JeosifFunc(a, n, k) == 1){ // если обнаруживается такое k, что выживает первый номер,

existing = true;//выключаем цикл

cout << k<< "]";// выводим k

}

if (existing == false){ // если такого k не нашлось.

cout << "не существует]";

}

return 0;

}

Алгоритм выполнения описан в комментариях в коде.

Особенности:

В коде очень легко запутаться, т.к. нумерация «слотов» вектора начинается с нуля, следовательно везде по коду мы должны это учитывать. Это здорово мешает в понимании кода.
Алгоритм выполнения первой задачи заключен в функцию. Без этого хода нельзя было бы выполнить вторую часть задания методом, представленным выше.
( if( JeosifFunc(a, n, k) == 1 )

Related Images:

М6a

02/12/2014 by Григорян Артак

а) Чётные числа из стандартного потока ввода поместить в хранилище с именем [latex]Even[/latex], а нечётные —[latex]Odd[/latex]. Во входном потоке неизвестное количество целых чисел через пробел.

Поток ввода	Результат
4 8 15 16 23 42	4 8 16 4215 23
0 1 1 2 3 5 8 13 21 34 55 89 144	0 2 8 34 1441 1 3 5 13 21 55 89

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

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

int main() 
{
	int x;
	vector<int> Odd;
	vector<int> Even;
	while(cin>>x) 
	{
    	if(x%2==0) Even.push_back(x);
    	else Odd.push_back(x);
	}
	for(int i=0;i<Even.size();i++)
	{
		cout<<Even[i]<<" ";
	}
	cout<<endl;
	for(int i=0;i<Odd.size();i++)
	{
		cout<<Odd[i]<<" ";
	}
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

int x;

vector<int> Odd;

vector<int> Even;

while(cin>>x)

{

if(x%2==0) Even.push_back(x);

else Odd.push_back(x);

}

for(int i=0;i<Even.size();i++)

{

cout<<Even[i]<<" ";

}

cout<<endl;

for(int i=0;i<Odd.size();i++)

{

cout<<Odd[i]<<" ";

}

return 0;

}

Создаем два вектора [latex] Odd [/latex] и [latex]Even[/latex]. С помощью цикла [latex]while[/latex] вводим неопределенное количество элементов. Внутри цикла с помощью [latex]push[/latex]_[latex]back[/latex] четные числа помещаем в [latex]Even[/latex] , а нечетные в [latex]Odd[/latex].

Код программы можно посмотреть тут