e-olymp 2267. Journey

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

The army of Rzeczpospolita is moving from the city Kostroma to the village Domnino. Two hetmans, Stefan and Konstantin, lead the army.

Stefan procured the roadmap of Kostroma province, and every night he routes the army from one village to the other along some road. Konstantin bought the map of secret trails between villages in advance, and every day he leads the march along the one of such trails. Each hetman asks their guide Ivan Susanin for a route before each march.

The length of each road is indicated on Stefan’s map. So Stefan knows the minimal distance from each village to the Domnino village according to his map. Similarly Konstantin knows the minimal distance from each village to Domnino village along trails on his map.

Ivan Susanin does not want to be disclosed as a secret agent, so each time he chooses a road (for Stefan) or a trail (for Konstantin) so, that the minimal distance to the Domnino village according to the map owned by the asking hetman is strictly decreasing.

Help Ivan to ﬁnd the longest possible route to the Domnino village.

Input

The ﬁrst line contains three integer numbers [latex]n, s[/latex] and [latex]t[/latex] — number of villages in Kostroma province, and numbers of start and Domnino village [latex](2 \le n \le 1000; 1 \le s; t \le n)[/latex]. Villages are numbered from [latex]1[/latex] to [latex]n[/latex]. Start and Domnino villages are distinct.

Two blocks follow, the ﬁrst one describing Stefan’s map, and the second one describing Konstantin’s map.

The first line of each block contains an integer number [latex]m[/latex] — the number of roads/trails between villages [latex](n-1 \le m \le 100000)[/latex]. Each of the following [latex]m[/latex]lines contains three integer numbers [latex]a, b[/latex], and [latex]l[/latex] — describing the road/trail between villages [latex]a[/latex] and [latex]b[/latex] of length [latex]l[/latex] [latex](1 \le a, b \le n; 1 \le l \le 10^6)[/latex].

Rzeczpospolita army can move in any direction along a road or a trail. It’s guaranteed that one can travel from any village to any other using each of the maps. The army starts its movement in the evening from the village number and moves one road each night and one trail each day.

Output

Output the total length of the longest route that Ivan Susanin can arrange for Rzeczpospolita army before reaching the Domnino village (along the roads and trails). If Ivan Susanin can route the army forever without reaching the Domnino village, output the number «[latex]-1[/latex]».

Tests

№	Input	Output
1	5 1 5 5 1 2 2 1 4 2 2 3 1 3 4 1 5 3 1 4 1 2 2 2 4 2 2 3 1 2 5 2	-1
2	3 1 3 4 1 2 10 2 3 10 1 3 20 2 3 30 4 2 1 10 1 3 10 1 1 10 2 3 10	20

Algorithm

The problem has been resolved together with Sploshnov Kirill.

So, we are dealing with a rather cumbersome task for the graphs, therefore we analyze it consistently. To get started we define the data structure

struct Route {
    int color;
    unsigned int to; 
    unsigned int length;
};

struct Route {

int color;

unsigned int to;

unsigned int length;

};

because dealing with the routes and subsequently, we will have to color our edges. For convenience, we don’t think about two maps as about different graphs, and can establish one graph, where edges of each map are painted in a different color.
For example edges of first map color in RED, and the other in BLUE. Then select the first map is equivalent to passing by red edges, or blue otherwise. In this way, route, that we are looking for, should be based on the successively alternating colors of the edges.
Proceed directly to the solution.
From the condition is understandable, that each hetman knows the shortest path to the final village. This data will be needed for us too, so for each map (edges of the same color) use Dijkstra’s algorithm and find the shortest path from each vertex to the target. (Function void djikstra(vector<Route>* graph, int* distancesInColoredGraph, unsigned int quantityOfAllVertices, int finishVertex, int color); ). We need absolutely standard Dijkstra’s algorithm with the only difference that the edges of the opposite color aren’t available. You can learn more about Dijkstra’s algorithm in the sources of information listed at the end of the article.
Continue analyzing the condition, we understand, that we can’t pass over the edges so, that the shortest distance to the final vertex increased. This will help us to simplify the graph, and significantly reduce the number of possible variants of passage, namely, any bidirectional edge will be either removed completely or strictly directed. Then, passing on to the edges of the same color in each map, if it doesn’t satisfy the specified condition coloring it as DELETED. (Function void simplify(vector<Route>* graph, int* distance, unsigned int quantityOfAllVertices, int color); ).
Now we can get started with the search for the longest route. There are two options: either there is the longest path, or we can walk along the edges infinitely, if it does not contradict the statement of the problem, that is, in the combined of two maps graph there is a cycle. So we organize checks on acyclic. Now we have the right to pass along the edges only alternating colors at each step. In order to find a cycle, we use vertex coloring, and will explore the graph until we try to treat already colored vertex or not conclude that it is acyclic. (Function bool cyclicDFS(vector<Route>* graph, int* passedInRedGraph, int* passedInBlueGraph, int currentVertex, int color); ). This algorithm can be obtained after detailed acquaintance with the usual cycle searching algorithm (reference to the source is located at the end of the article). If we find any loop in this graph, then our job is over and we should just output «[latex]-1[/latex]».
Otherwise, make sure that the graph is acyclic, we are looking for the longest route. As our graph has been simplified and has no cycles, and all edges are directed, then the task of finding this way becomes computationally simple. For this declaring an array of longest distance dynamically, along the way memorizing the already calculated values, sequentially find the maximum length of the route until we arrive at the finish village. (Function int maxDistDFS(vector<Route>* graph, int* maxDistancesInRedGraph, int* maxDistancesInBlueGraph, int currentVertex, int color) ). This will be the answer to the task.

Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.

Code

#include <vector>
#include <iostream>
#include <algorithm>
#define DELETED -1
#define WHITE 0
#define GREY 1
#define BLACK 2
#define RED 3
#define BLUE 4
#define MAX_INT 2147483647
using namespace std;
 
//  The structure, describing the roads/trails 
struct Route {
    int color;
    unsigned int to; 
    unsigned int length;
    //  Constructor by destination, length and color of edge
    Route(unsigned int to, unsigned int length, int color) {
        this->to = to;
        this->color = color;
        this->length = length;
    }
};
 
/*  
    Function implements ordinary Dijkstra's algorithm (for all edges of the same color)
    As a result, an array of distances filled with the minimum distance to each vertex
*/
void djikstra(vector<Route>* graph, int* distancesInColoredGraph, unsigned int quantityOfAllVertices, int finishVertex, int color) {
    int vertexWithMinDist = -1;
    bool* passed = new bool[quantityOfAllVertices];
    fill(passed, passed + quantityOfAllVertices, false);
    fill(distancesInColoredGraph, distancesInColoredGraph + quantityOfAllVertices, MAX_INT);
    distancesInColoredGraph[finishVertex] = 0;
    for (unsigned int indexOfCurrentVertex = 0; vertexWithMinDist == -1 || indexOfCurrentVertex < quantityOfAllVertices && distancesInColoredGraph[vertexWithMinDist] != MAX_INT; indexOfCurrentVertex++) {
        vertexWithMinDist = -1;
        for (unsigned int indexOfVertex = 0; indexOfVertex < quantityOfAllVertices; indexOfVertex++) {
            if (!passed[indexOfVertex] && (vertexWithMinDist == -1 || distancesInColoredGraph[indexOfVertex] < distancesInColoredGraph[vertexWithMinDist])) {
                vertexWithMinDist = indexOfVertex;
            }
        }
        passed[vertexWithMinDist] = true;
        for (unsigned int adjacentVertex = 0; adjacentVertex < graph[vertexWithMinDist].size(); adjacentVertex++) {
            if (graph[vertexWithMinDist][adjacentVertex].color == color 
                && graph[vertexWithMinDist][adjacentVertex].length + distancesInColoredGraph[vertexWithMinDist] < distancesInColoredGraph[graph[vertexWithMinDist][adjacentVertex].to]) {
                distancesInColoredGraph[graph[vertexWithMinDist][adjacentVertex].to] = graph[vertexWithMinDist][adjacentVertex].length + distancesInColoredGraph[vertexWithMinDist];
            }
        }
    }
}
 
//  Function indicates the edges we don't need as deleted (because we can't pass them)
void simplify(vector<Route>* graph, int* distance, unsigned int quantityOfAllVertices, int color) {
    //  Note as DELETED routes in which the minimum distance to finish vertex increases, cause we can't walk them on the strength of problem's condition
    for (unsigned int indexOfCurrentVertex = 0; indexOfCurrentVertex < quantityOfAllVertices; indexOfCurrentVertex++) {
        for (unsigned int adjacentVertex = 0; adjacentVertex < graph[indexOfCurrentVertex].size(); adjacentVertex++) {
            if (graph[indexOfCurrentVertex][adjacentVertex].color == color 
                && distance[indexOfCurrentVertex] <= distance[graph[indexOfCurrentVertex][adjacentVertex].to]) {
                graph[indexOfCurrentVertex][adjacentVertex].color = DELETED;
            }
        }
    }
}
 
//  Function determines whether you can go in cycle by the edges of alternating colors 
bool cyclicDFS(vector<Route>* graph, int* passedInRedGraph, int* passedInBlueGraph, int currentVertex, int color) {
    bool answer = false;
    //  Note processing vertex
    if (color == RED) {
        passedInRedGraph[currentVertex] = GREY;
    } else {
        passedInBlueGraph[currentVertex] = GREY;
    }
    /*
        Implement ordinary checking on cycle, by coloring graph
        Treat until we don't determine it is acyclic or try to color vertex that is already colored
        We should take into account the fact, that each time we alternate the color of the edges
    */
    for (unsigned int adjacentVertex = 0; adjacentVertex < graph[currentVertex].size() && !answer; adjacentVertex++) {
        if (graph[currentVertex][adjacentVertex].color == color) {
            if (color == BLUE && passedInRedGraph[graph[currentVertex][adjacentVertex].to] == GREY 
                || color == RED && passedInBlueGraph[graph[currentVertex][adjacentVertex].to] == GREY) {
                answer = true;
            }
            if (color == RED && passedInBlueGraph[graph[currentVertex][adjacentVertex].to] == WHITE) {
                if (cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, graph[currentVertex][adjacentVertex].to, BLUE)) {
                    answer = true;
                }
            } else if (passedInRedGraph[graph[currentVertex][adjacentVertex].to] == WHITE) {
                if (cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, graph[currentVertex][adjacentVertex].to, RED)) {
                    answer = true;
                }
            }
        }
    }
    //  Note processed vertex
    if (color == RED) {
        passedInRedGraph[currentVertex] = BLACK;
    } else {
        passedInBlueGraph[currentVertex] = BLACK;
    }
    return answer;
}
 
//  Function determines whether there is a suitable cycle in the graph
bool isCyclic(vector<Route>* graph, unsigned int quantityOfAllVertices, int currentVertex) {
    int* passedInRedGraph = new int[quantityOfAllVertices];
    int* passedInBlueGraph = new int[quantityOfAllVertices];
    fill(passedInRedGraph, passedInRedGraph + quantityOfAllVertices, WHITE);
    fill(passedInBlueGraph, passedInBlueGraph + quantityOfAllVertices, WHITE);
    return cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, currentVertex, RED);
}
 
//  Function determines the longest path in the graph by the edges of alternating colors, by finding and memorizing the maximum path to each of the vertices
int maxDistDFS(vector<Route>* graph, int* maxDistancesInRedGraph, int* maxDistancesInBlueGraph, int currentVertex, int color) {
    //  Return the length of the path from the current vertex, if it's found already
    if (color == RED && maxDistancesInRedGraph[currentVertex] != -1) {
        return maxDistancesInRedGraph[currentVertex];
    }
    if (color == BLUE && maxDistancesInBlueGraph[currentVertex] != -1) {
        return maxDistancesInBlueGraph[currentVertex];
    }
    int maxDistance = -1;   //  Initially, we consider the longest path by any negative number
    for (unsigned int adjacentVertex = 0; adjacentVertex < graph[currentVertex].size(); adjacentVertex++) {
        /*
            Recursively find the longest path to the finish vertex
            We should take into account the fact, that each time we alternate the color of the edges
        */
        if (graph[currentVertex][adjacentVertex].color == color) {
            int currentMaxDistance = maxDistDFS(graph, maxDistancesInRedGraph, maxDistancesInBlueGraph, graph[currentVertex][adjacentVertex].to, 
                color == RED ? BLUE : RED) + graph[currentVertex][adjacentVertex].length;
            maxDistance = max(maxDistance, currentMaxDistance);
        }
    }
    //  Remember the results received in the process of bypassing for later use
    if (color == RED) {
        maxDistancesInRedGraph[currentVertex] = maxDistance;
    } else {
        maxDistancesInBlueGraph[currentVertex] = maxDistance;
    }
    return maxDistance;
}
 
//  Function returns the longest path in the graph from the start vertex to the finish
int getMaxDist(vector<Route>* graph, unsigned int quantityOfAllVertices, int startVertex, int finishVertex) {
    int* maxDistancesInRedGraph = new int[quantityOfAllVertices];
    int* maxDistancesInBlueGraph = new int[quantityOfAllVertices];
    fill(maxDistancesInRedGraph, maxDistancesInRedGraph + quantityOfAllVertices, -1);
    fill(maxDistancesInBlueGraph, maxDistancesInBlueGraph + quantityOfAllVertices, -1);
    maxDistancesInRedGraph[finishVertex] = 0;
    maxDistancesInBlueGraph[finishVertex] = 0;
    return maxDistDFS(graph, maxDistancesInRedGraph, maxDistancesInBlueGraph, startVertex, RED);
}
 
int main() {
    ios::sync_with_stdio(false);
    unsigned int quantityOfAllVertices, quantityOfVertices, startVertex, finishVertex, from, to, length;
    cin >> quantityOfAllVertices >> startVertex >> finishVertex;
    startVertex--; finishVertex--;  //  Shift numbering
    vector<Route>* graph = new vector<Route>[quantityOfAllVertices];    // Stores graph as array of routes for each vertex
    cin >> quantityOfVertices;
    while (quantityOfVertices--) {
        cin >> from >> to >> length;
        from--; to--;   //  Shift numbering
        if (from != to) {   //  Don't read cycles
            // Initially, all roads are bidirectional, add symmetrically
            graph[from].push_back(Route(to, length, RED));
            graph[to].push_back(Route(from, length, RED));
        }
    }
    cin >> quantityOfVertices;
    while (quantityOfVertices--) {
        cin >> from >> to >> length;
        from--; to--; 
        if (from != to) {
            graph[from].push_back(Route(to, length, BLUE));
            graph[to].push_back(Route(from, length, BLUE));
        }
    }
    int* distancesInRedGraph = new int[quantityOfAllVertices];  //  Shortest distances from each vertex to the final by red edges
    int* distancesInBlueGraph = new int[quantityOfAllVertices]; //  Shortest distances from each vertex to the final by blue edges
    djikstra(graph, distancesInRedGraph, quantityOfAllVertices, finishVertex, RED);     //  Find and remember the shortest path by the red edges
    djikstra(graph, distancesInBlueGraph, quantityOfAllVertices, finishVertex, BLUE);   //  Find and remember the shortest path by the blue edges
    simplify(graph, distancesInRedGraph, quantityOfAllVertices, RED);   //  Note red edges which we can't pass, so that later they don't take into account
    simplify(graph, distancesInBlueGraph, quantityOfAllVertices, BLUE); //  Note blue edges which we can't pass, so that later they don't take into account
    cout << (isCyclic(graph, quantityOfAllVertices, startVertex) ? -1 : getMaxDist(graph, quantityOfAllVertices, startVertex, finishVertex)) << endl;
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

#include <vector>

#include <iostream>

#include <algorithm>

#define DELETED -1

#define WHITE 0

#define GREY 1

#define BLACK 2

#define RED 3

#define BLUE 4

#define MAX_INT 2147483647

using namespace std;

// The structure, describing the roads/trails

struct Route {

int color;

unsigned int to;

unsigned int length;

// Constructor by destination, length and color of edge

Route(unsigned int to, unsigned int length, int color) {

this->to = to;

this->color = color;

this->length = length;

}

};

Function implements ordinary Dijkstra's algorithm (for all edges of the same color)

As a result, an array of distances filled with the minimum distance to each vertex

void djikstra(vector<Route>* graph, int* distancesInColoredGraph, unsigned int quantityOfAllVertices, int finishVertex, int color) {

int vertexWithMinDist = -1;

bool* passed = new bool[quantityOfAllVertices];

fill(passed, passed + quantityOfAllVertices, false);

fill(distancesInColoredGraph, distancesInColoredGraph + quantityOfAllVertices, MAX_INT);

distancesInColoredGraph[finishVertex] = 0;

for (unsigned int indexOfCurrentVertex = 0; vertexWithMinDist == -1 || indexOfCurrentVertex < quantityOfAllVertices && distancesInColoredGraph[vertexWithMinDist] != MAX_INT; indexOfCurrentVertex++) {

vertexWithMinDist = -1;

for (unsigned int indexOfVertex = 0; indexOfVertex < quantityOfAllVertices; indexOfVertex++) {

if (!passed[indexOfVertex] && (vertexWithMinDist == -1 || distancesInColoredGraph[indexOfVertex] < distancesInColoredGraph[vertexWithMinDist])) {

vertexWithMinDist = indexOfVertex;

}

passed[vertexWithMinDist] = true;

for (unsigned int adjacentVertex = 0; adjacentVertex < graph[vertexWithMinDist].size(); adjacentVertex++) {

if (graph[vertexWithMinDist][adjacentVertex].color == color

&& graph[vertexWithMinDist][adjacentVertex].length + distancesInColoredGraph[vertexWithMinDist] < distancesInColoredGraph[graph[vertexWithMinDist][adjacentVertex].to]) {

distancesInColoredGraph[graph[vertexWithMinDist][adjacentVertex].to] = graph[vertexWithMinDist][adjacentVertex].length + distancesInColoredGraph[vertexWithMinDist];

}

// Function indicates the edges we don't need as deleted (because we can't pass them)

void simplify(vector<Route>* graph, int* distance, unsigned int quantityOfAllVertices, int color) {

// Note as DELETED routes in which the minimum distance to finish vertex increases, cause we can't walk them on the strength of problem's condition

for (unsigned int indexOfCurrentVertex = 0; indexOfCurrentVertex < quantityOfAllVertices; indexOfCurrentVertex++) {

for (unsigned int adjacentVertex = 0; adjacentVertex < graph[indexOfCurrentVertex].size(); adjacentVertex++) {

if (graph[indexOfCurrentVertex][adjacentVertex].color == color

&& distance[indexOfCurrentVertex] <= distance[graph[indexOfCurrentVertex][adjacentVertex].to]) {

graph[indexOfCurrentVertex][adjacentVertex].color = DELETED;

}

// Function determines whether you can go in cycle by the edges of alternating colors

bool cyclicDFS(vector<Route>* graph, int* passedInRedGraph, int* passedInBlueGraph, int currentVertex, int color) {

bool answer = false;

// Note processing vertex

if (color == RED) {

passedInRedGraph[currentVertex] = GREY;

} else {

passedInBlueGraph[currentVertex] = GREY;

}

Implement ordinary checking on cycle, by coloring graph

Treat until we don't determine it is acyclic or try to color vertex that is already colored

We should take into account the fact, that each time we alternate the color of the edges

for (unsigned int adjacentVertex = 0; adjacentVertex < graph[currentVertex].size() && !answer; adjacentVertex++) {

if (graph[currentVertex][adjacentVertex].color == color) {

if (color == BLUE && passedInRedGraph[graph[currentVertex][adjacentVertex].to] == GREY

|| color == RED && passedInBlueGraph[graph[currentVertex][adjacentVertex].to] == GREY) {

answer = true;

}

if (color == RED && passedInBlueGraph[graph[currentVertex][adjacentVertex].to] == WHITE) {

if (cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, graph[currentVertex][adjacentVertex].to, BLUE)) {

answer = true;

}

} else if (passedInRedGraph[graph[currentVertex][adjacentVertex].to] == WHITE) {

if (cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, graph[currentVertex][adjacentVertex].to, RED)) {

answer = true;

}

// Note processed vertex

if (color == RED) {

passedInRedGraph[currentVertex] = BLACK;

} else {

passedInBlueGraph[currentVertex] = BLACK;

}

return answer;

}

// Function determines whether there is a suitable cycle in the graph

bool isCyclic(vector<Route>* graph, unsigned int quantityOfAllVertices, int currentVertex) {

int* passedInRedGraph = new int[quantityOfAllVertices];

int* passedInBlueGraph = new int[quantityOfAllVertices];

fill(passedInRedGraph, passedInRedGraph + quantityOfAllVertices, WHITE);

fill(passedInBlueGraph, passedInBlueGraph + quantityOfAllVertices, WHITE);

return cyclicDFS(graph, passedInRedGraph, passedInBlueGraph, currentVertex, RED);

}

// Function determines the longest path in the graph by the edges of alternating colors, by finding and memorizing the maximum path to each of the vertices

int maxDistDFS(vector<Route>* graph, int* maxDistancesInRedGraph, int* maxDistancesInBlueGraph, int currentVertex, int color) {

// Return the length of the path from the current vertex, if it's found already

if (color == RED && maxDistancesInRedGraph[currentVertex] != -1) {

return maxDistancesInRedGraph[currentVertex];

}

if (color == BLUE && maxDistancesInBlueGraph[currentVertex] != -1) {

return maxDistancesInBlueGraph[currentVertex];

}

int maxDistance = -1; // Initially, we consider the longest path by any negative number

for (unsigned int adjacentVertex = 0; adjacentVertex < graph[currentVertex].size(); adjacentVertex++) {

Recursively find the longest path to the finish vertex

We should take into account the fact, that each time we alternate the color of the edges

if (graph[currentVertex][adjacentVertex].color == color) {

int currentMaxDistance = maxDistDFS(graph, maxDistancesInRedGraph, maxDistancesInBlueGraph, graph[currentVertex][adjacentVertex].to,

color == RED ? BLUE : RED) + graph[currentVertex][adjacentVertex].length;

maxDistance = max(maxDistance, currentMaxDistance);

}

// Remember the results received in the process of bypassing for later use

if (color == RED) {

maxDistancesInRedGraph[currentVertex] = maxDistance;

} else {

maxDistancesInBlueGraph[currentVertex] = maxDistance;

}

return maxDistance;

}

// Function returns the longest path in the graph from the start vertex to the finish

int getMaxDist(vector<Route>* graph, unsigned int quantityOfAllVertices, int startVertex, int finishVertex) {

int* maxDistancesInRedGraph = new int[quantityOfAllVertices];

int* maxDistancesInBlueGraph = new int[quantityOfAllVertices];

fill(maxDistancesInRedGraph, maxDistancesInRedGraph + quantityOfAllVertices, -1);

fill(maxDistancesInBlueGraph, maxDistancesInBlueGraph + quantityOfAllVertices, -1);

maxDistancesInRedGraph[finishVertex] = 0;

maxDistancesInBlueGraph[finishVertex] = 0;

return maxDistDFS(graph, maxDistancesInRedGraph, maxDistancesInBlueGraph, startVertex, RED);

}

int main() {

ios::sync_with_stdio(false);

unsigned int quantityOfAllVertices, quantityOfVertices, startVertex, finishVertex, from, to, length;

cin >> quantityOfAllVertices >> startVertex >> finishVertex;

startVertex--; finishVertex--; // Shift numbering

vector<Route>* graph = new vector<Route>[quantityOfAllVertices]; // Stores graph as array of routes for each vertex

cin >> quantityOfVertices;

while (quantityOfVertices--) {

cin >> from >> to >> length;

from--; to--; // Shift numbering

if (from != to) { // Don't read cycles

// Initially, all roads are bidirectional, add symmetrically

graph[from].push_back(Route(to, length, RED));

graph[to].push_back(Route(from, length, RED));

}

cin >> quantityOfVertices;

while (quantityOfVertices--) {

cin >> from >> to >> length;

from--; to--;

if (from != to) {

graph[from].push_back(Route(to, length, BLUE));

graph[to].push_back(Route(from, length, BLUE));

}

int* distancesInRedGraph = new int[quantityOfAllVertices]; // Shortest distances from each vertex to the final by red edges

int* distancesInBlueGraph = new int[quantityOfAllVertices]; // Shortest distances from each vertex to the final by blue edges

djikstra(graph, distancesInRedGraph, quantityOfAllVertices, finishVertex, RED); // Find and remember the shortest path by the red edges

djikstra(graph, distancesInBlueGraph, quantityOfAllVertices, finishVertex, BLUE); // Find and remember the shortest path by the blue edges

simplify(graph, distancesInRedGraph, quantityOfAllVertices, RED); // Note red edges which we can't pass, so that later they don't take into account

simplify(graph, distancesInBlueGraph, quantityOfAllVertices, BLUE); // Note blue edges which we can't pass, so that later they don't take into account

cout << (isCyclic(graph, quantityOfAllVertices, startVertex) ? -1 : getMaxDist(graph, quantityOfAllVertices, startVertex, finishVertex)) << endl;

return 0;

}

Related Images:

e-olymp 2307. The sum

24/05/2016 by Таран Таня

The array of [latex]n[/latex] elements is given. Find the sum of numbers on a segment.

Input

The first line contains two integers [latex]n[/latex] and [latex]k[/latex] [latex](1 \le n \le 10^5, 0 \le k \le 10^5)[/latex] — the number of elements in array and the number of queries. The next [latex]k[/latex] lines contain the queries of two forms:

[latex]A[/latex] [latex]l[/latex] [latex]r[/latex] [latex]x[/latex] — assign the value of [latex]x[/latex] to each element form position [latex]l[/latex] to [latex]r[/latex] [latex](1 \le l \le r \le n, 0 \le x \le 10^9)[/latex]
[latex]Q[/latex] [latex]l[/latex] [latex]r[/latex] — find the sum of array elements on positions from [latex]l[/latex] to [latex]r[/latex] [latex](1 \le l \le r \le n)[/latex]

Initially the array is filled with zeroes.

Output

For each query of the form «[latex]Q[/latex] [latex]l[/latex] [latex]r[/latex]» print the sum of numbers on a segment.

Tests

№	Input	Output
1	5 9 A 2 3 2 A 3 5 1 A 4 5 2 Q 1 3 Q 2 2 Q 3 4 Q 4 5 Q 5 5 Q 1 5	3 2 3 4 2 7
2	10 6 A 1 10 1 Q 1 10 A 1 5 2 Q 1 10 A 4 7 3 Q 1 10	10 15 21
3	100000 2 A 1 100000 1000000000 Q 1 100000	100000000000000

Algorithm

After reading the statement of the problem it is understandable that we should implement segment tree with support for multiple modification request — assignment. To make modifications to the whole segment and quickly answer for the amounts queries, we organize data structure in which each node store «colored» — if it is painted in any color or not and a sum on corresponding to this node segment.

struct Node {
    int color;
    long long sumOnSegment;
};

struct Node {

int color;

long long sumOnSegment;

};

Under the node coloring we will understand that all segment with all its subsegments should be colored in the appropriate color (assigned a specific number). Also define the mark that the node isn’t colored (in the code defined as WHITE), for example, any negative number, because queries contain only positive. This implementation allows us to do «delayed» update of the tree. Specifically, for each request of modification, instead of changing the values at all vertices where it is required, change only some of them, leaving «colored» markers for the other segments, which means that the whole segment with its subsegments should be painted in this color.
But if we do it so, after each modification request segment tree will stop being up to date. For resolving this problem, organise a function, that will «push» information from parents to children: void push(Node *tree, int currentNode, int left, int right) . This function is called during requests processing to update the appropriate values:

assign parent’s color to the children
recalculate the amount of the segment for children (as the length of the segment multiplied by the current color (number))
set parent node as uncolored

Thus, to solve this task, we need two usual for segment tree functions:

void update(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder, int color)
long long sum(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder)

With the difference that, when we are going down by the tree, pushes information only as far as necessary (it should be noted, that in this way the asymptotic doesn’t impair and remains standard [latex]O(\log n)[/latex]).

Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.

Footnote: such realization, where the problem constraints too large queries, and in the current version when we update a range and only mark its child that it needs to be updated and update it when needed, usually calls lazy propagation. This approach allows us to solve a variety of new at first glance seemed complex tasks. More information listed at the end of the article.

Code

#include <cmath>
#include <iostream>
#define WHITE -1
using namespace std;

//  Function, that return lowest power of 2, bigger than a given number
int lowestBiggerPowOf2Than(int number) {                    
    int answer;
    answer = 1 << (int)(log2((double)number - 1) + 1);
    return answer;
}

//  The structure describing the components from which consists a tree
struct Node {
    int color;
    long long sumOnSegment;
    //  The default constructor
    Node() {
        color = WHITE;
        sumOnSegment = 0;
    }
    //  Construct the node by its color and sum on corresponding segment
    Node(int color, long long sumOnSegment) {
        this->color = color;
        this->sumOnSegment = sumOnSegment;
    }
    //  Define, if this node is painted in some color (some number is assigned)
    bool isColored() {
        return color != WHITE;
    }
};

//  Function, that pushes information from parent to the children
void push(Node *tree, int currentNode, int left, int right) {
    if (tree[currentNode].isColored()) {
        int middle = (left + right) / 2;
        int leftChild = 2 * currentNode;
        //  Pass color from parent to children
        tree[leftChild].color = tree[currentNode].color;
        tree[leftChild + 1].color = tree[currentNode].color;
        //  Execute recalculation of the amount in the corresponding segments at children
        tree[leftChild].sumOnSegment = (long long)(middle - left + 1) * tree[leftChild].color;
        tree[leftChild + 1].sumOnSegment = (long long)(right - middle) * tree[leftChild + 1].color;
        //  Note parent's node as uncolored
        tree[currentNode].color = WHITE;
    }
}

//  Function, that updates the value of all nodes on a segment for the specified 
void update(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder, int color) {
    if (leftBorder == left && rightBorder == right) {
        tree[currentNode] = Node(color, (long long)(right - left + 1) * color);
    } else {
        //  Executes the delayed update (pushes information)
        push(tree, currentNode, left, right);
        int leftChild = 2 * currentNode;
        int middle = (left + right) / 2;
        if (rightBorder <= middle) {
            update(tree, leftChild, left, middle, leftBorder, rightBorder, color);
        } else if (leftBorder >= middle + 1) {
            update(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder, color);
        } else {
            update(tree, leftChild, left, middle, leftBorder, middle, color);
            update(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder, color);
        }
        //  Update the amount in corresponding to parent segment
        tree[currentNode].sumOnSegment = tree[leftChild].sumOnSegment + tree[leftChild + 1].sumOnSegment;
    } 
}

//  Function, that calculates the sum at a specified segment
long long sum(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) {
    if (left == leftBorder && right == rightBorder) {
        return tree[currentNode].sumOnSegment;
    } else {
        //  Executes the delayed update (pushes information)
        push(tree, currentNode, left, right);
        int leftChild = 2 * currentNode;
        int middle = (left + right) / 2;
        if (rightBorder <= middle) {
            return sum(tree, leftChild, left, middle, leftBorder, rightBorder);
        } else if (leftBorder >= middle + 1) {
            return sum(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder);
        } else {
            return sum(tree, leftChild, left, middle, leftBorder, middle) 
                + sum(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    unsigned int quantityOfNumbers;
    cin >> quantityOfNumbers;
    unsigned int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers);
    Node *tree = new Node[sizeOfTree];
    unsigned int quantityOfRequests;
    cin >> quantityOfRequests;
    for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) {
        char request;
        cin >> request;
        unsigned int leftBorder, rightBorder;
        if (request == 'A') {
            int value;
            cin >> leftBorder >> rightBorder >> value;
            update(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1, value);
        } else if (request == 'Q') {
            cin >> leftBorder >> rightBorder;
            cout << sum(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1) << endl;
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

#include <cmath>

#include <iostream>

#define WHITE -1

using namespace std;

// Function, that return lowest power of 2, bigger than a given number

int lowestBiggerPowOf2Than(int number) {

int answer;

answer = 1 << (int)(log2((double)number - 1) + 1);

return answer;

}

// The structure describing the components from which consists a tree

struct Node {

int color;

long long sumOnSegment;

// The default constructor

Node() {

color = WHITE;

sumOnSegment = 0;

}

// Construct the node by its color and sum on corresponding segment

Node(int color, long long sumOnSegment) {

this->color = color;

this->sumOnSegment = sumOnSegment;

}

// Define, if this node is painted in some color (some number is assigned)

bool isColored() {

return color != WHITE;

}

};

// Function, that pushes information from parent to the children

void push(Node *tree, int currentNode, int left, int right) {

if (tree[currentNode].isColored()) {

int middle = (left + right) / 2;

int leftChild = 2 * currentNode;

// Pass color from parent to children

tree[leftChild].color = tree[currentNode].color;

tree[leftChild + 1].color = tree[currentNode].color;

// Execute recalculation of the amount in the corresponding segments at children

tree[leftChild].sumOnSegment = (long long)(middle - left + 1) * tree[leftChild].color;

tree[leftChild + 1].sumOnSegment = (long long)(right - middle) * tree[leftChild + 1].color;

// Note parent's node as uncolored

tree[currentNode].color = WHITE;

}

// Function, that updates the value of all nodes on a segment for the specified

void update(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder, int color) {

if (leftBorder == left && rightBorder == right) {

tree[currentNode] = Node(color, (long long)(right - left + 1) * color);

} else {

// Executes the delayed update (pushes information)

push(tree, currentNode, left, right);

int leftChild = 2 * currentNode;

int middle = (left + right) / 2;

if (rightBorder <= middle) {

update(tree, leftChild, left, middle, leftBorder, rightBorder, color);

} else if (leftBorder >= middle + 1) {

update(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder, color);

} else {

update(tree, leftChild, left, middle, leftBorder, middle, color);

update(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder, color);

}

// Update the amount in corresponding to parent segment

tree[currentNode].sumOnSegment = tree[leftChild].sumOnSegment + tree[leftChild + 1].sumOnSegment;

}

// Function, that calculates the sum at a specified segment

long long sum(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) {

if (left == leftBorder && right == rightBorder) {

return tree[currentNode].sumOnSegment;

} else {

// Executes the delayed update (pushes information)

push(tree, currentNode, left, right);

int leftChild = 2 * currentNode;

int middle = (left + right) / 2;

if (rightBorder <= middle) {

return sum(tree, leftChild, left, middle, leftBorder, rightBorder);

} else if (leftBorder >= middle + 1) {

return sum(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder);

} else {

return sum(tree, leftChild, left, middle, leftBorder, middle)

+ sum(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder);

}

int main() {

ios::sync_with_stdio(false);

unsigned int quantityOfNumbers;

cin >> quantityOfNumbers;

unsigned int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers);

Node *tree = new Node[sizeOfTree];

unsigned int quantityOfRequests;

cin >> quantityOfRequests;

for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) {

char request;

cin >> request;

unsigned int leftBorder, rightBorder;

if (request == 'A') {

int value;

cin >> leftBorder >> rightBorder >> value;

update(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1, value);

} else if (request == 'Q') {

cin >> leftBorder >> rightBorder;

cout << sum(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1) << endl;

}

return 0;

}

Related Images:

e-olymp 2906. Can you answer these queries — 1

23/05/2016 by Таран Таня

You are given an integer sequence.

[latex]a_1, a_2, \ldots, a_n (|a_i| \le 15007, 1 \le n \le 50000)[/latex].

A query is defined as follows:

[latex]Query(x, y) = MAX (a_i + a_{i+1} + \ldots + a_j, x \le i \le j \le y)[/latex]

Given [latex]m[/latex] queries, your program must output the results of these queries.

Input

The first line contains the integer [latex]n[/latex]. In the second line [latex]n[/latex] integers of the sequence are given. The third line contains the integer [latex]m[/latex]. Then [latex]m[/latex] lines follow, where line [latex]i[/latex] contains two numbers [latex]x_i[/latex] and [latex]y_i[/latex].

Output

Print the results of the [latex]m[/latex] queries, one query per line.

Tests

№	Input	Output
1	3 -1 2 3 1 1 2	2
2	5 1 2 3 4 5 1 1 5	15
3	5 -1 -2 -3 -4 -5 1 1 5	-1
4	8 1 2 -3 -2 10 1 -15 7 4 1 1 3 4 3 6 1 8	1 -2 11 11
5	9 1 -2 3 -4 5 -6 7 -8 9 3 1 9 2 8 2 4	9 7 3

Algorithm

After analyzing the condition of the problem, we can understand that we need on a given segments of array to find subsegment with a maximum amount. We can solve this task by using segment tree, but before this we should modify it a bit. Create a structure of which our tree consists:

struct Node {
    int answer;         
    int sumOnPrefix;
    int sumOnSuffix;
    int sumOnSegment;
}

struct Node {

int answer;

int sumOnPrefix;

int sumOnSuffix;

int sumOnSegment;

}

That is, in each vertex of tree we store [latex]4[/latex] values:

the answer to the task for the current subsegment
the maximum amount among all prefixes
the maximum amount among all suffixes
the sum on the segment

First we need to get the values in the leaves. It’s simple enough all [latex]4[/latex] fields take the value of the number, that corresponds to this leaf. Now, having values in the leaves, we need to learn how to get the values in parent. For this we use the function Node mergeNodes(Node leftChild, Node rightChild), which assign to parent’s fields such values:

Answer in the parent equal to the answer in the right or the left child (means that the best subsegment of the current node is entirely in the left or right child), or the maximum amount of the maximum suffix in the left child and the maximum prefix in the right child (which means that it is partially is in the left child and partially is in the right child).
The maximum amount of the parent on prefix is equal to the maximum prefix of left child or sum on segment of left child and maximum prefix of right child.
The maximum amount of the parent on suffix is equal to the maximum suffix of right child or sum on segment of right child and maximum suffix of right child.
Amount on segment of the parent is equal to the sum on segment of left child and sum on segment of right child.

Now, with all the auxiliary functions for working with a built data structure, we need only to construct a tree and learn to get an answer on it.
We need two more functions:

void build(int *base, Node *tree, int currentNode, int left, int right) — recursive construction of a tree from the leaves to the root by initial sequence numbers.
Node answer(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) — as in the usual tree segments we get an answer going down by the tree, but instead of any associative function (eg sum or maximum) we execute the merger of nodes described earlier. Resulting node will store an answer corresponding to a given in the query segment.

Rest details of the implementation can be found in the code of the program or in the sources of information listed at the end of the article.

Code

#include <cmath>
#include <iostream>
#define INF -15008
using namespace std;

//  Function, that teturn lowest power of 2, bigger than a given number
int lowestBiggerPowOf2Than(int number) {                    
    int answer;
    answer = 1 << (int)(log2((double)number - 1) + 1);
    return answer;
}

//  The structure describing the components from which consists a tree
struct Node {
    int answer;         
    int sumOnPrefix;
    int sumOnSuffix;
    int sumOnSegment;
    //  Empty node takes the value less by 1 than what we can get, because we are looking for maximum subsegment
    Node() {
        answer = INF;
        sumOnPrefix = INF;
        sumOnSuffix = INF;
        sumOnSegment = INF;
    }
    // Constructs a node by a value of the initial sequence of numbers
    Node(int value) {
        answer = value;
        sumOnPrefix = value;
        sumOnSuffix = value;
        sumOnSegment = value;
    }
};

//  Function, that merges two nodes (childs) and returns new node (parent)
Node mergeNodes(Node leftChild, Node rightChild) {
    Node crossedNode;
    crossedNode.sumOnSegment = leftChild.sumOnSegment + rightChild.sumOnSegment;
    crossedNode.sumOnPrefix = max(leftChild.sumOnPrefix, leftChild.sumOnSegment + rightChild.sumOnPrefix);
    crossedNode.sumOnSuffix = max(rightChild.sumOnSuffix, leftChild.sumOnSuffix + rightChild.sumOnSegment);
    crossedNode.answer = max(leftChild.sumOnSuffix + rightChild.sumOnPrefix, max(leftChild.answer, rightChild.answer));
    return crossedNode;
}

//  Function, that building a tree recursive
void build(int *base, Node *tree, int currentNode, int left, int right) {
    if (left == right) {
        tree[currentNode] = Node(base[left]);
    } else {
        int leftChild = 2 * currentNode;
        int middle = (left + right) / 2;
        build(base, tree, leftChild, left, middle);
        build(base, tree, leftChild + 1, middle + 1, right);
        // Use the previously described function to get the value of parent by his children
        tree[currentNode] = mergeNodes(tree[leftChild], tree[leftChild + 1]);
    }
}

//  Function, that return node, storing the answer to the problem (subsegment with a maximum amount)
Node answer(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) {
    if (left == leftBorder && right == rightBorder) {
        return tree[currentNode];
    }
    int leftChild = 2 * currentNode;
    int middle = (left + right) / 2;
    if (rightBorder <= middle) {
        return answer(tree, leftChild, left, middle, leftBorder, rightBorder);
    }
    if (leftBorder > middle) {
        return answer(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder);
    }
    return mergeNodes(answer(tree, leftChild, left, middle, leftBorder, middle),
        answer(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder));
}

int main() {
    std::ios::sync_with_stdio(false);
    unsigned int quantityOfNumbers;
    cin >> quantityOfNumbers;
    int *base = new int[quantityOfNumbers];     //  A given sequence of numbers 
    for (unsigned int indexOfNumber = 0; indexOfNumber < quantityOfNumbers; indexOfNumber++) {
        cin >> base[indexOfNumber];
    }
    int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers);
    Node *tree = new Node[sizeOfTree];
    build(base, tree, 1, 0, quantityOfNumbers - 1);
    unsigned int quantityOfRequests;
    cin >> quantityOfRequests;
    for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) {
        unsigned int leftBorder, rightBorder;
        cin >> leftBorder >> rightBorder;
        cout << answer(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1).answer << endl;
    }
    return 0;
}

#include <cmath>

#include <iostream>

#define INF -15008

using namespace std;

// Function, that teturn lowest power of 2, bigger than a given number

int lowestBiggerPowOf2Than(int number) {

int answer;

answer = 1 << (int)(log2((double)number - 1) + 1);

return answer;

}

// The structure describing the components from which consists a tree

struct Node {

int answer;

int sumOnPrefix;

int sumOnSuffix;

int sumOnSegment;

// Empty node takes the value less by 1 than what we can get, because we are looking for maximum subsegment

Node() {

answer = INF;

sumOnPrefix = INF;

sumOnSuffix = INF;

sumOnSegment = INF;

}

// Constructs a node by a value of the initial sequence of numbers

Node(int value) {

answer = value;

sumOnPrefix = value;

sumOnSuffix = value;

sumOnSegment = value;

}

};

// Function, that merges two nodes (childs) and returns new node (parent)

Node mergeNodes(Node leftChild, Node rightChild) {

Node crossedNode;

crossedNode.sumOnSegment = leftChild.sumOnSegment + rightChild.sumOnSegment;

crossedNode.sumOnPrefix = max(leftChild.sumOnPrefix, leftChild.sumOnSegment + rightChild.sumOnPrefix);

crossedNode.sumOnSuffix = max(rightChild.sumOnSuffix, leftChild.sumOnSuffix + rightChild.sumOnSegment);

crossedNode.answer = max(leftChild.sumOnSuffix + rightChild.sumOnPrefix, max(leftChild.answer, rightChild.answer));

return crossedNode;

}

// Function, that building a tree recursive

void build(int *base, Node *tree, int currentNode, int left, int right) {

if (left == right) {

tree[currentNode] = Node(base[left]);

} else {

int leftChild = 2 * currentNode;

int middle = (left + right) / 2;

build(base, tree, leftChild, left, middle);

build(base, tree, leftChild + 1, middle + 1, right);

// Use the previously described function to get the value of parent by his children

tree[currentNode] = mergeNodes(tree[leftChild], tree[leftChild + 1]);

}

// Function, that return node, storing the answer to the problem (subsegment with a maximum amount)

Node answer(Node *tree, int currentNode, int left, int right, int leftBorder, int rightBorder) {

if (left == leftBorder && right == rightBorder) {

return tree[currentNode];

}

int leftChild = 2 * currentNode;

int middle = (left + right) / 2;

if (rightBorder <= middle) {

return answer(tree, leftChild, left, middle, leftBorder, rightBorder);

}

if (leftBorder > middle) {

return answer(tree, leftChild + 1, middle + 1, right, leftBorder, rightBorder);

}

return mergeNodes(answer(tree, leftChild, left, middle, leftBorder, middle),

answer(tree, leftChild + 1, middle + 1, right, middle + 1, rightBorder));

}

int main() {

std::ios::sync_with_stdio(false);

unsigned int quantityOfNumbers;

cin >> quantityOfNumbers;

int *base = new int[quantityOfNumbers]; // A given sequence of numbers

for (unsigned int indexOfNumber = 0; indexOfNumber < quantityOfNumbers; indexOfNumber++) {

cin >> base[indexOfNumber];

}

int sizeOfTree = 2 * lowestBiggerPowOf2Than(quantityOfNumbers);

Node *tree = new Node[sizeOfTree];

build(base, tree, 1, 0, quantityOfNumbers - 1);

unsigned int quantityOfRequests;

cin >> quantityOfRequests;

for (unsigned int indexOfRequest = 0; indexOfRequest < quantityOfRequests; indexOfRequest++) {

unsigned int leftBorder, rightBorder;

cin >> leftBorder >> rightBorder;

cout << answer(tree, 1, 0, quantityOfNumbers - 1, leftBorder - 1, rightBorder - 1).answer << endl;

}

return 0;

}

Related Images:

e-olymp 4002. Down with cheating!

10/04/2016 by Таран Таня

During the test, Professor Floyd noticed that some students exchanged notes. At first, he wanted to put a bad mark everyone, but that day the professor was in a good mood, therefore he decided to split all the students into two groups and put a bad mark to only those,who writting off.
The professor recorded all the pairs of students, who exchanged notes. You need to determine whether they can be divided into two groups, where student of one group exchange notes only with student of other group.

Input

There are two numbers in first line [latex]m[/latex] and [latex]n[/latex] — quantity of students and quantity of pairs, who exchanged notes. [latex](1 \le n \le 100[/latex], [latex]0 \le m \le n(n-1)/2)[/latex]. Further in [latex]m[/latex] lines there are description of student pairs: two different numbers, corresponding to the student serial number, who exchanged notes (numbering from [latex]1[/latex]). Each pair of students is listed only once.

Output

Print the answer to the Professor’s Floyd task. If it is possible to divide the students into two groups output «YES», or «NO» otherwise.

Test

№	Input	Output
1	3 2 1 2 2 3	YES
2	3 3 1 2 1 3 2 3	NO
3	12 9 1 3 2 3 4 5 5 6 6 8 6 9 7 9 8 10 11 12	*YES*
4	12 10 1 3 2 3 4 5 5 6 6 8 6 9 7 9 8 9 8 10 11 12	NO

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

Algorithm

After reading the statement of the problem becomes clear that our goal is to determine whether it is possible to divide the graph into two sets in each of them there aren’t adjacent vertices — check whether the graph is bipartite.
For the implementation, we need a basic function
bool isBipartite(vector<int> *listOfVertices, int *colorOfVertices, int sourceVertex, int quantityOfVertex), that takes a graph (in this program as an array of vectors of adjacent vertices, but can be done similar implementation on the adjacency matrix), array of vertices’ colors, vertex, which we start checking, and the number of vertices.
To solve the problem we perform graph coloring. Naturally, we organize data reading process. And our next sequence of steps is:

Initially, we define all the vertices as WHITE — not processed.
Call the fucntion for the first vertex (in our numbering — zero).
Assign source vertex with one of the colors (for convenience in program we denote it as RED) — equivalent to the action that we put the vertex in the first of two sets.
Color all adjacent vertex with inverse color (in program it’s BLUE — has opposite to RED number value) — equivalent to the action that we put vertices in the second set.
Color all adjacent to the adjacent vertices with RED color — we put them in the first set.
Repeat this until we have completed bypassing (for convenience we use queue) — coloring of all connected vertices. But we can find adjacent vertices with same color that sygnalize that our graph cannot be colored with two color — so it isn’t bipartite.

It should be noted that the function implemented in such way works for only one connected component. Therefore, to check the disconnected graphs we must check all vertices which color is white.

Code

#define RED -1																							// First set of vertices
#define BLUE 1																							// Second set of vertices
#define WHITE 0																							// Not processed vertices
#include <queue>
#include <vector>
#include <iostream>
using namespace std;

bool isBipartite(vector<int> *listOfVertices, int *colorOfVertices, int sourceVertex, int quantityOfVertex) {
	bool isBipartite = true;
	colorOfVertices[sourceVertex] = RED;																    //	Color vertex which we started
	queue <int> orderOfBypassing;																		//	Stores order of bypassing with queue
	orderOfBypassing.push(sourceVertex);																    //  Remember the initial vertex
	while (!orderOfBypassing.empty()) {																	//	Process until we bypass all connected vertices
		int currentVertex = orderOfBypassing.front();													//	Remember vertex that came first in queue
		orderOfBypassing.pop();																			//	Remove it
		for (auto adjacentVertex : listOfVertices[currentVertex]) {										//	Process all adjacent with current and not processed earlier vertices
			if (colorOfVertices[adjacentVertex] == WHITE) {
				colorOfVertices[adjacentVertex] = -colorOfVertices[currentVertex];						//	Color adjacent vertex with inverse color
				orderOfBypassing.push(adjacentVertex);													//	Add this vertex to the order of bypass
			}
			else if (colorOfVertices[adjacentVertex] == colorOfVertices[currentVertex]) {				//	If two adjacent vertices in one set are the same color
				isBipartite = false;																	    //	Graph isn't bipartite
				break;																					//	We can stop processing
			}
		}
	}
	return isBipartite;
}

int main() {
	bool answer = true;
	int quantityOfVertex, quantityOfConnections;
	cin >> quantityOfVertex >> quantityOfConnections;
	vector<int> *listOfVertices = new vector<int>[quantityOfVertex];									    //	Stores for the each vertex adjacent vertices
	while (quantityOfConnections--) {																	//	Read all given connections
		int firstVertex, secondVertex;
		cin >> firstVertex >> secondVertex;
		firstVertex--;																					//	We store it numbering from zero, so decrement index of vertices
		secondVertex--;
		listOfVertices[firstVertex].push_back(secondVertex);											    //	Add vertex to the vector of adjacent vertex
		listOfVertices[secondVertex].push_back(firstVertex);											    //	Do it symmetrically
	}
	int *colorOfVertices = new int[quantityOfVertex];													//	For each vertex stores it's color
	for (int indexOfVertex = 0; indexOfVertex < quantityOfVertex; indexOfVertex++) {
		colorOfVertices[indexOfVertex] = WHITE;															//	Intially, all vertices are white (not processed)
	}
	for (int indexOfVertex = 0; indexOfVertex < quantityOfVertex && answer; indexOfVertex++) {			//	Process to the end or until we recognize, that graph isn't bipartite
		if (colorOfVertices[indexOfVertex] == WHITE) {													//	Process only WHITE vertices
			answer &= isBipartite(listOfVertices, colorOfVertices, indexOfVertex, quantityOfVertex);	    //	Logical conjunction of answers for all graph component 
		}
	}
	cout << (answer ? "YES" : "NO");
	return 0;
}

#define RED -1 // First set of vertices

#define BLUE 1 // Second set of vertices

#define WHITE 0 // Not processed vertices

#include <queue>

#include <vector>

#include <iostream>

using namespace std;

bool isBipartite(vector<int> *listOfVertices, int *colorOfVertices, int sourceVertex, int quantityOfVertex) {

bool isBipartite = true;

colorOfVertices[sourceVertex] = RED; // Color vertex which we started

queue <int> orderOfBypassing; // Stores order of bypassing with queue

orderOfBypassing.push(sourceVertex); // Remember the initial vertex

while (!orderOfBypassing.empty()) { // Process until we bypass all connected vertices

int currentVertex = orderOfBypassing.front(); // Remember vertex that came first in queue

orderOfBypassing.pop(); // Remove it

for (auto adjacentVertex : listOfVertices[currentVertex]) { // Process all adjacent with current and not processed earlier vertices

if (colorOfVertices[adjacentVertex] == WHITE) {

colorOfVertices[adjacentVertex] = -colorOfVertices[currentVertex]; // Color adjacent vertex with inverse color

orderOfBypassing.push(adjacentVertex); // Add this vertex to the order of bypass

}

else if (colorOfVertices[adjacentVertex] == colorOfVertices[currentVertex]) { // If two adjacent vertices in one set are the same color

isBipartite = false; // Graph isn't bipartite

break; // We can stop processing

}

return isBipartite;

}

int main() {

bool answer = true;

int quantityOfVertex, quantityOfConnections;

cin >> quantityOfVertex >> quantityOfConnections;

vector<int> *listOfVertices = new vector<int>[quantityOfVertex]; // Stores for the each vertex adjacent vertices

while (quantityOfConnections--) { // Read all given connections

int firstVertex, secondVertex;

cin >> firstVertex >> secondVertex;

firstVertex--; // We store it numbering from zero, so decrement index of vertices

secondVertex--;

listOfVertices[firstVertex].push_back(secondVertex); // Add vertex to the vector of adjacent vertex

listOfVertices[secondVertex].push_back(firstVertex); // Do it symmetrically

}

int *colorOfVertices = new int[quantityOfVertex]; // For each vertex stores it's color

for (int indexOfVertex = 0; indexOfVertex < quantityOfVertex; indexOfVertex++) {

colorOfVertices[indexOfVertex] = WHITE; // Intially, all vertices are white (not processed)

}

for (int indexOfVertex = 0; indexOfVertex < quantityOfVertex && answer; indexOfVertex++) { // Process to the end or until we recognize, that graph isn't bipartite

if (colorOfVertices[indexOfVertex] == WHITE) { // Process only WHITE vertices

answer &= isBipartite(listOfVertices, colorOfVertices, indexOfVertex, quantityOfVertex); // Logical conjunction of answers for all graph component

}

cout << (answer ? "YES" : "NO");

return 0;

}

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:

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:

e-olymp 332. Детская железная дорога

28/11/2015 by Таран Таня

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

Какое слово получится у Витэка?

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

Первая и единственная строка содержит исходное слово. Кубики у Витэка только из заглавных букв латинского алфавита и их количество не превышает [latex]500000[/latex].

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

Слово, которое образовал Витэк.

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

Тесты

Входные данные	Выходные данные
CBABC	ABCCB
XXXXX	XXXXX
ABEABFABBABC	ABBABCABEABF
RATOBCQATOBC	ATOBCQATOBCR
OROOXOOSTO	OOROOXOOST
LBDEAFAARDEABBAF	AARDEABBAFLBDEAF

Алгоритм

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

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

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

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

Рассмотрим на произвольно выбранном примере:

LBDEAFAARDEABBAF

Тогда следует сравнить такие подслова:

AFAARDEABBAF
AARDEABBAF
ARDEABBAF
ABBAF
AF

Найти среди них минимальное лексикографическое и передвинуть его в начало слова.

Реализуем описанный выше алгоритм на практике с некоторыми особенностями.

Прочитаем слово.
Найдем минимальный символ в данном слове.
Создадим вектор для хранения индексов вхождения минимального символа (indicesOfMinSymbol) и будем добавлять в него значение только в том случае, если текущий символ является минимальным, а предыдущий нет. (Обратившись к предоставленному примеру, можно заметить, что не имеет смысла отдельно проводить сравнение подслов AARDEABBAF и ARDEABBAF, так как первое из них явно «выгоднее». Также мы сможем упростить ситуацию и избавиться от большого количества лишних проверок, когда на вход поступает слово состоящее из всех одинаковых символов (например, XXXXX), в котором не нужно выполнять ни единого сравнения и как-либо изменять слово).
Объявим индекс начала текущего наименьшего лексикографического подслова (indexOfMinLexicSubstr) и для каждого значения из заполненного ранее вектора будем сравнивать от иднекса начала текущего наименьшего лексикографического подслова столько символов, сколько осталось до конца строки от текущего индекса вхождения минимального символа, с подстрокой, начинающейся с этого индекса и заканчивающейся в конце слова, с помощью функции compare. (Рассмотрим произвольные подслова из заданного примера: AFAARDEABBAF и AARDEABBAF. Тогда исходя из пункта 4 следует сравнить подслова AFААRDEABB и AARDEABBAF. Мы имеем полное право выполнить такое упрощение, так как отсутствие следующего символа меньше, чем наличие любого другого символа, и если будет выбрано первое подслово, то второе подслово, стоящее справа от него, автоматически также будет сдвинуто в начало.
Однако существует немаловажное исключение при построении такого алгоритма. Его удобно рассмотреть на каком-либо конкретном случае, например, OROOXOOSTO. Когда мы дойдем до сравнения подслов OOSTO (на данный момент будет являться минимальным) и О, исходя из выше описанного алгоритма, мы получим равенство подстрок и не изменим индекс начала минимальной строки, тогда ложно будет построена как наименьшая лексикографическая строка из данной OOSTOOROOX. Исправить эту проблему можно дополнительной проверкой того, что выйдет при сдвиге второй (более короткой) подстроки в начало заданного слова. То есть для данного примера, можно заметить, что подслово OROO лексикографически меньше чем OSTO (сравниваем такое же количество символов в начале строки, сколько оставалось до конца у текущей наименьшей лексикографической подстроки).
Примечание: следует отметить, что даже без выполнения второй проверки алгоритм проходил все тесты к данной задаче на сайте e-olymp, что может говорить лишь о неполноте тестов.).
И только в том случае, если функция compare в пункте 4 вернула значение больше чем [latex]0[/latex], то есть правое подслово меньше, или же меньше подслово получаемое при сдвиге правой строки в сравнении с текущим наименьшим лексикографическим, тогда изменяем значение индекса минимального лексикографического подслова на текущий индекс вхождения минимального символа.
После прохождения всего вектора, выполняем сдвиг найденного минимального лексикографического подслова в начало, благодаря встроенной функции rotate, и выполняем вывод полученного слова.

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

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

int main() {
	string word;
	cin >> word;
	char minSymbol = word[0]; 
	vector <int> indicesOfMinSymbol; // Вектор для хранения индексов вхождения "минимального" символа
	for (int i = 1; i < word.size(); i++) {
		 if (word[i] < minSymbol) {
		     minSymbol = word[i];
		 }
	} // Поиск "минимального" символа в данном слове
	for (int i = 0; i < word.size(); i++) {
		 if (word[i] == minSymbol && word[i - 1] != minSymbol) {
		     indicesOfMinSymbol.push_back(i);
		 } // Добавляем индекс, если текущий является "минимальным", а предыдущий таковым не был
	} // Заполняем вектор индексами вхождения "минимального" символа
	int indexOfMinLexicSubstr = indicesOfMinSymbol[0]; // Индекс начала текущего минимального лексикографического подслова
	for (int i = 1; i < indicesOfMinSymbol.size(); i++) {
		 if (word.compare(indexOfMinLexicSubstr, word.size() - indicesOfMinSymbol[i], word, indicesOfMinSymbol[i], string::npos) > 0
		 	 || (word.compare(indexOfMinLexicSubstr, word.size() - indicesOfMinSymbol[i], word, indicesOfMinSymbol[i], string::npos) == 0
		 	     &&  word.compare(0, indicesOfMinSymbol[i] - indexOfMinLexicSubstr, word, indexOfMinLexicSubstr + word.size() - indicesOfMinSymbol[i], string::npos) < 0)) {
			 indexOfMinLexicSubstr = indicesOfMinSymbol[i]; 
		 } // Сравниваем текущее минимальное подслово и подслово начинающееся со следующего вхождения "минимального" символа, если они равны, то следует проверить, что выйдет, благодаря задействованию символов из начала строки
    } // Поиск наименьшего лексикографического подслова
	rotate(word.begin(), word.begin() + indexOfMinLexicSubstr, word.end()); // Cдвигаем наименьшее лексикографическое подслово в начало
	cout << word;
	return 0;
}

#include <string>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

string word;

cin >> word;

char minSymbol = word[0];

vector <int> indicesOfMinSymbol; // Вектор для хранения индексов вхождения "минимального" символа

for (int i = 1; i < word.size(); i++) {

if (word[i] < minSymbol) {

minSymbol = word[i];

}

} // Поиск "минимального" символа в данном слове

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

if (word[i] == minSymbol && word[i - 1] != minSymbol) {

indicesOfMinSymbol.push_back(i);

} // Добавляем индекс, если текущий является "минимальным", а предыдущий таковым не был

} // Заполняем вектор индексами вхождения "минимального" символа

int indexOfMinLexicSubstr = indicesOfMinSymbol[0]; // Индекс начала текущего минимального лексикографического подслова

for (int i = 1; i < indicesOfMinSymbol.size(); i++) {

if (word.compare(indexOfMinLexicSubstr, word.size() - indicesOfMinSymbol[i], word, indicesOfMinSymbol[i], string::npos) > 0

|| (word.compare(indexOfMinLexicSubstr, word.size() - indicesOfMinSymbol[i], word, indicesOfMinSymbol[i], string::npos) == 0

&& word.compare(0, indicesOfMinSymbol[i] - indexOfMinLexicSubstr, word, indexOfMinLexicSubstr + word.size() - indicesOfMinSymbol[i], string::npos) < 0)) {

indexOfMinLexicSubstr = indicesOfMinSymbol[i];

} // Сравниваем текущее минимальное подслово и подслово начинающееся со следующего вхождения "минимального" символа, если они равны, то следует проверить, что выйдет, благодаря задействованию символов из начала строки

} // Поиск наименьшего лексикографического подслова

rotate(word.begin(), word.begin() + indexOfMinLexicSubstr, word.end()); // Cдвигаем наименьшее лексикографическое подслово в начало

cout << word;

return 0;

}

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

Засчитанное решение

Related Images:

e-olymp 330. Слово-чемпион

19/11/2015 by Таран Таня

Задано некоторое предложение на неизвестном языке. Назовем слово в нем чемпионом, если оно является палиндромом и количество букв в нем максимально. Буквами алфавита в неизвестном языке являются буквы латинского алфавита и арабские цифры. Гарантируется, что других символов, кроме пробелов и знаков препинания в предложении нет.

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

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

Предложение на неизвестном языке.

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

Номер слова-чемпиона.

Тесты

Предложение	Номер слова-чемпиона
Oo, it aaa is not bb.	3
Tummut, suuruu 18!	1
Qrtew asd x, pol 123 xcv.	3
Antaa, qor — aapapaa for Saippuakivikauppias kappak!	6
A b C d E f G h	1
NoPalindrome	0
123321 oro 1234554321?	3

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

Алгоритм

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

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

После проведенных операций найдем длину текущего слова и, если она превышает максимальную длину ранее найденного слова-чемпиона, проверим, является ли текущее слово палиндромом. Осуществим это с помощью рекурсивной функции, сравнивающей соответствующие символы в данной строке по индексам. Функция работает до тех пор, пока начальный и конечный индекс не сравняются или поменяются местами (изначально первый индекс (start) равен нулю, а конечный (end) меньше длины строки на единицу), или же соответствующие символы окажутся разными. Если данное слово оказалось палиндромом, храним его порядковый номер в предложении.
Как только предложение завершено, выводим индекс найденного слова-чемпиона, или индекс первого из них, если таковых было несколько.

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

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

const int registerShift = 'A' - 'a'; // Сдвиг от верхнего регистра к нижнему по таблице ASCII

// Функция, для определения, является ли текущий символ "буквой" в контексте данной задачи
bool IsAllowedSymbol(char symbol) {
	return ((symbol >= '1' && symbol <= '9') || (symbol >= 'a' && symbol <= 'z') || (symbol >= 'A' && symbol <= 'Z')) ? true : false;
}

// Функция, для определения, является ли текущее слово палиндромом
bool IsPalindrom(char *word, int begin, int end) {
	return (end <= begin) ? true : (word[begin] != word[end]) ? false : IsPalindrom(word, ++begin, --end);
}

// Функция, которая переводит все слово в нижний регистр
void ToLowerCase(char *word) {
	 for (int i = 0; i < strlen(word); i++) {
	 	  if (word[i] >= 'A' && word[i] <= 'Z')
	 	      word[i] -= registerShift;
	 }
}

int main() {
	char word[1001];
	int wordSize, maxSize = 0, indexOfPalindrom = 0;
    for (int i = 1; cin >> word; i++) {
    	 ToLowerCase(word); // Перевод слова в нижний регистр 
    	 if (!IsAllowedSymbol(word[strlen(word) - 1]))
    	     word[strlen(word) - 1] = '\0'; // Не учитывать последний символ слова, если это не "буква" (т. е. знак препинания)
    	 wordSize = strlen(word);
    	 if (wordSize > maxSize) {
	         if (IsPalindrom(word, 0, wordSize - 1)) {
	         	 maxSize = wordSize;
	             indexOfPalindrom = i;	    
	         } // Храним новый максимум и индекс текущего наибольшего палиндрома, если он был найден
	     }
    } // Чтение по словам до конца предложения
	cout << indexOfPalindrom;
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

const int registerShift = 'A' - 'a'; // Сдвиг от верхнего регистра к нижнему по таблице ASCII

// Функция, для определения, является ли текущий символ "буквой" в контексте данной задачи

bool IsAllowedSymbol(char symbol) {

return ((symbol >= '1' && symbol <= '9') || (symbol >= 'a' && symbol <= 'z') || (symbol >= 'A' && symbol <= 'Z')) ? true : false;

}

// Функция, для определения, является ли текущее слово палиндромом

bool IsPalindrom(char *word, int begin, int end) {

return (end <= begin) ? true : (word[begin] != word[end]) ? false : IsPalindrom(word, ++begin, --end);

}

// Функция, которая переводит все слово в нижний регистр

void ToLowerCase(char *word) {

for (int i = 0; i < strlen(word); i++) {

if (word[i] >= 'A' && word[i] <= 'Z')

word[i] -= registerShift;

}

int main() {

char word[1001];

int wordSize, maxSize = 0, indexOfPalindrom = 0;

for (int i = 1; cin >> word; i++) {

ToLowerCase(word); // Перевод слова в нижний регистр

if (!IsAllowedSymbol(word[strlen(word) - 1]))

word[strlen(word) - 1] = '\0'; // Не учитывать последний символ слова, если это не "буква" (т. е. знак препинания)

wordSize = strlen(word);

if (wordSize > maxSize) {

if (IsPalindrom(word, 0, wordSize - 1)) {

maxSize = wordSize;

indexOfPalindrom = i;

} // Храним новый максимум и индекс текущего наибольшего палиндрома, если он был найден

}

} // Чтение по словам до конца предложения

cout << indexOfPalindrom;

return 0;

}

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

Засчитанное решение

Related Images:

MLoop 3

02/11/2015 by Таран Таня

Используйте метод золотого сечения для того, чтобы отыскать с точностью [latex]\varepsilon[/latex] локальный максимум функции $f\left( x \right) = \ln \left(1+ x^{2} - \cos x \right) - e^{\sin \pi x}$ на отрезке $\left[a;b\right]$ .

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

[latex]a, b[/latex] — концы отрезка, на котором требуется найти максимум, и точность [latex]\varepsilon[/latex].

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

Точка локального максимума и локальный максимум в формате [latex](x_{max}, y_{max})[/latex].

Тесты

[latex]\varepsilon[/latex]	[latex]a[/latex]	[latex]b[/latex]	[latex](x_{max}, y_{max})[/latex]
[latex]0.001[/latex]	[latex]1.05[/latex]	[latex]2.2[/latex]	[latex](1.74435, 0.951781)[/latex]
[latex]0.0001[/latex]	[latex]1.05[/latex]	[latex]2.2[/latex]	[latex](1.74417, 0.951781)[/latex]
[latex]0.0001[/latex]	[latex]5.7[/latex]	[latex]8[/latex]	[latex](7.57498, 3.68407)[/latex]
[latex]0.0001[/latex]	[latex]3[/latex]	[latex]4[/latex]	[latex](3.61901, 2.31289)[/latex]

Алгоритм

Для начала проанализируем данную нам функцию. Найдем ее область определения.

[latex]D(f) = x^2 + 1 + \cos x > 0 [/latex]
[latex]D(f) = x^2 + 1 + \cos x = x^2 + [/latex] [latex]\frac{1}{2}[/latex] [latex] \cos^2[/latex] [latex]\frac{x}{2}[/latex] [latex] > 0[/latex] [latex]\forall[/latex] [latex]x[/latex] [latex]\in [/latex] [latex] \mathbb{R}[/latex]

Таким образом, функция определена на всей числовой оси и мы имеем право рассматривать функцию для любого значения аргумента (также это видно по графику).
Однако следует помнить о том, что используемый нами метод золотого сечения принадлежит к группе симметричных методов и накладывает некоторые ограничения на исследуемую функцию. Применимость данного метода гарантируется только для непрерывных, унимодальных функций.
Унимодальная функция — это функция, которая монотонна на обе стороны от точки максимума [latex]x_{max}[/latex].

[latex]x_1 \le[/latex] [latex]x_2 \le[/latex] [latex]x_{max}[/latex] [latex]\Rightarrow[/latex] [latex]f(x_1) \le[/latex] [latex]f(x_2) \le[/latex][latex]f(x_{max})[/latex]
[latex]x_1 \ge[/latex] [latex]x_2 \ge[/latex] [latex]x_{max}[/latex] [latex]\Rightarrow[/latex] [latex]f(x_1) \le[/latex] [latex]f(x_2) \le[/latex][latex]f(x_{max})[/latex]

Отсюда следует, что если функция [latex]f(x)[/latex] унимодальна на отрезке [latex][a; b][/latex], то максимум этой функции единственен, а локальные минимумы обязательно располагаются на его концах. Так как данная нам функция не является таковой, то для корректного применения метода и получения желаемого результата мы будем собственноручно задавать такие отрезки, на которых представленная функция унимодальна (их несложно выделить по графику).

Проведя анализ функции, обратимся к самому методу золотого сечения.

Для того чтобы найти определенное значение функции на заданном отрезке, отвечающее заданному критерию поиска (в нашем случае максимум), рассматриваемый отрезок требуется поделить в пропорции золотого сечения в обоих направлениях, то есть выбираются две точки [latex]x_1[/latex] и [latex]x_2[/latex] такие, что

[latex]\frac{b — a}{b — x_1}[/latex] [latex]= \frac{b — a}{x_2 — a} =[/latex] [latex]\varphi[/latex] [latex] = \frac{1 + \sqrt{5}}{2}[/latex]

То есть точка [latex]x_1[/latex] делит отрезок [latex][a; x_2][/latex] в отношении золотого сечения. Аналогично [latex]x_2[/latex] делит отрезок [latex][x_1; b][/latex] в той же пропорции. Для нахождения максимума выполняем следующую последовательность действий:

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

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

#include <iostream>
#include <math.h>
using namespace std;

const double goldenRatio = (1 + sqrt(5)) / 2; // "Золотое" число

// Рассматриваемая нами функция
double function(double x) {
	return log(1 + x * x - cos(x)) - pow(M_E, sin(M_PI * x));
}

int main() {
	double a, b; // Концы отрезка
	double accuracy; // Точность, с которой мы находим локальный максимум
	double x1, x2; // Точки, делящие текущий отрезок в отношении золотого сечения
	cin >> a >> b >> accuracy;
	while (fabs(b - a) > accuracy) {
		   x1 = b - (b - a) / goldenRatio; 
	       x2 = a + (b - a) / goldenRatio;
	       if (function(x1) <= function(x2)) // Условие для поиска максимума
	           a = x1; 
	       else 
	           b = x2;
	} // Выполняем, пока не достигнем заданной точности
	cout << "(" << (a + b) / 2 << ", " << function((a + b) / 2) << ")"; 
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

const double goldenRatio = (1 + sqrt(5)) / 2; // "Золотое" число

// Рассматриваемая нами функция

double function(double x) {

return log(1 + x * x - cos(x)) - pow(M_E, sin(M_PI * x));

}

int main() {

double a, b; // Концы отрезка

double accuracy; // Точность, с которой мы находим локальный максимум

double x1, x2; // Точки, делящие текущий отрезок в отношении золотого сечения

cin >> a >> b >> accuracy;

while (fabs(b - a) > accuracy) {

x1 = b - (b - a) / goldenRatio;

x2 = a + (b - a) / goldenRatio;

if (function(x1) <= function(x2)) // Условие для поиска максимума

a = x1;

else

b = x2;

} // Выполняем, пока не достигнем заданной точности

cout << "(" << (a + b) / 2 << ", " << function((a + b) / 2) << ")";

return 0;

}

Ссылки

Код программы
Больше информации о методе золотого сечения:
Источник 1; Источник 2; Источник 3;

Related Images:

MLoops24

01/11/2015 by Таран Таня

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex]n > 0[/latex] (количество столбцов) и [latex] m > 0[/latex] (количество строк).

0 10 1110 3110 132110 1113122110
311311222110 13211321322110 1113
122113121113222110 3113112221131
1123113322110 132113213221133112
132123223110 1113122113121113222

0 10 1110 3110 132110 1113122110

311311222110 13211321322110 1113

122113121113222110 3113112221131

1123113322110 132113213221133112

132123223110 1113122113121113222

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

Количество столбцов ([latex]n > 0[/latex]) и количество строк ([latex] m > 0[/latex]) в таблице.

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

Построенная для данной последовательности таблица с соответствующим количеством столбцов и строк.

Тесты

[latex]n[/latex]

[latex]m[/latex]

Результат работы программы

0
10

0 10

1110

3110

1321

0 10

1110

3110

13211

0 111

0 10 1110 3110 132110 1113122110
311311222110 13211321322110 1113
122113121113222110 3113112221131
1123113322110 132113213221133112
132123223110 1113122113121113222

0 10 1110 3110 132110 1113122110

311311222110 13211321322110 1113

122113121113222110 3113112221131

1123113322110 132113213221133112

132123223110 1113122113121113222

0 10 1110 3110 132110 1113122110 311311222110 1321
1321322110 1113122113121113222110 3113112221131112
3113322110 132113213221133112132123222110 11131221
131211132221232112111312111213322110 3113112221131
1123113321112131221123113111231121123222110 132113
21322113311213212312311211131122211213211331121321
12211213322110 11131221131211132221232112111312111
21311121321123113213221121113122123211211131221222
1121123222110 311311222113111231133211121312211231
13111231121113311211131221121321131211132221123113

0 10 1110 3110 132110 1113122110 311311222110 1321

1321322110 1113122113121113222110 3113112221131112

3113322110 132113213221133112132123222110 11131221

131211132221232112111312111213322110 3113112221131

1123113321112131221123113111231121123222110 132113

21322113311213212312311211131122211213211331121321

12211213322110 11131221131211132221232112111312111

21311121321123113213221121113122123211211131221222

1121123222110 311311222113111231133211121312211231

13111231121113311211131221121321131211132221123113

0 10 1110

3110 13211

0 11131221

10 3113112

22110 1321

1321322110

1113122113

1211132221

Алгоритм

Для начала определим алгоритм построения предоставленной последовательности. Перед нами так называемая Look-and-Say sequence, начинающаяся с 0. Чтобы получить последующий член последовательности, нам потребуется обратиться к предыдущему и выполнить следующее:

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

Разберем на примере:

Первый член последовательности — [latex]0[/latex] («Основание» последовательности);
Второй член последовательности — [latex]10[/latex] («Вижу» один ноль);
Третий член последовательности — [latex]1110[/latex] («Вижу» одну единицу и один ноль);
Четвертый член последовательности — [latex]3110[/latex] («Вижу» три единицы и один ноль).
…

Реализуем данное построение на практике. Создадим два вектора для хранения предыдущего и текущего члена последовательности (previousTerm и currentTerm соответственно), а также переменные для хранения номера элемента с которым ведется сравнение (изначально start [latex] = 0[/latex]) и счетчик количества совпадающих элементов (изначально quantity [latex] = 0[/latex]). Запустим цикл от первого до последнего элемента массива previousTerm и выполним ряд действий, а именно:

Пока последующие элементы совпадают с текущим сравниваемым, инкрементируем счетчик.
Как только находиться элемент не совпадающий с текущим сравниваемым, выполняем вывод количества вхождений и само число, также записываем данные значения в вектор currentTerm. Переходим к следующей цифре для сравнения и присваиваем счетчику значение [latex]1[/latex].
Отдельно выполняем предыдущий пункт для последней последовательности цифр или одной цифры, так как нет возможности сравнения с последующими.
Как только один член последовательности полностью построен, обнуляем значения индекса сравниваемой цифры и счетчика. Также очищаем вектотр previousTerm и передаем ему значения вектора currentTerm, очищаем вектор currentTerm.

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

При запуске метода сразу же увеличиваем текущий номер столбца, в который записывается символ, на [latex]1[/latex].
Далее проверяем не превышает ли номер текущего столбца возможный. Если это так, то выполняем перевод курсора на новую строку, присваиваем текущему столбцу значение [latex]1[/latex] и инкрементируем значение номера текущей строки.
Если количество строк превышает заданное, заканчиваем работу программы.
В противном же случае выполняем печать символа, если это не пробел в начале строки (если это все же пробел в начале строки, то ничего не печатаем и уменьшаем значение текущего столбца для печати). Для упрощения вывода пробел передается в метод по его коду в таблице ASCII — [latex]32[/latex]. Мы имеем полное право использовать число [latex]32[/latex] без угрозы ошибки, так как передавать мы будем только цифры [latex]0, 1, 2, 3[/latex].

Таким образом общий алгоритм работы программы можем сформулировать так:

Считываем заданное количество столбцов ([latex]n > 0[/latex]) и количество строк ([latex] m > 0[/latex]).
Для последующей работы объявляем переменные хранящие значения номера текущего столбца и строки (currentNumberColumn и currentNumberRow соответственно), два вектора для хранения предыдущего и текущего члена последовательности (previousTerm и currentTerm соответственно), а также переменные для хранения номера элемента с которым ведется сравнение (start) и счетчик количества совпадающих элементов (quantity) .
Отправляем в вектор previousTerm значение «основания» последовательности — [latex]0[/latex].
Выводим первый член последовательности и пробел после него (если потребуется).
Далее запускаем бесконечный цикл, так как окончание работы программы предусмотрено в методе ToPrint.
И выполняем последовательное построение членов последовательности (описано выше) и тут же вывод, пока количество строк не превышает заданное.

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

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

void ToPrint(int n, int m, int *currentNumberColumn, int *currentNumberRow, int symbolToPrint) {
	(*currentNumberColumn)++; // Инкрементируем значение номера столбца, так как есть символ на печать
	if (*currentNumberColumn > n) {
		cout << endl; // Переходим на новую строку
	  	(*currentNumberRow)++;
	  	*currentNumberColumn = 1; 
	} // Если следует выполнить переход на следующую строку, выполняем этот переход по всем индексам
	if (*currentNumberRow > m)
	    exit(0); // Заканчиваем работу программы, как только количество строк превышает заданное
	else if (symbolToPrint == 32 && *currentNumberColumn == 1) // В таблице ASCII 32 - пробел
	    (*currentNumberColumn)--; // Возвращаем предыдущее значение номера столбца, так как ничего не было напечатано
    else if (symbolToPrint == 32)
        cout << char(symbolToPrint); // Выводим пробел, если это не начало строки
    else
      	cout << symbolToPrint;
}

int main() {
	int n, m; // Количество столбцов и строк соответственно
	cin >> n >> m;
	int start = 0; // Индекс элемента текущей цифры с которой ведется сравнение
    int quantity = 0; // Количество идущих подряд одинаковых элементов в данном члене
    int currentNumberRow = 1; // Номер текущей строки, в которой будет записан символ
    int currentNumberColumn = 0; // Номер текущего столбца, в который будет записан символ
    vector <short> currentTerm; // Вектор, хранящий значение текущего члена последовательности
    vector <short> previousTerm; // Вектор, хранящий значение предыдущего члена последовательности
	previousTerm.push_back(0); // Записываем в вектор предыдущего члена значение первого члена последовательности
    ToPrint(n, m, &currentNumberColumn, &currentNumberRow, 0); // Выводим первый член последовательности
    ToPrint(n, m, &currentNumberColumn, &currentNumberRow, 32); // Выводим пробел после него (если он не понадобится его уберет метод ToPrint)
    while (true) {
           for (int i = 0; i < previousTerm.size(); i++) { 
    	        if (previousTerm[i] == previousTerm[start]) 
    	 	        quantity++; // Считаем количество идущих подряд одинаковых цифр
    	        else {
    		      	currentTerm.push_back(quantity); // Записываем в вектор количество текущих цифр
    	          	currentTerm.push_back(previousTerm[start]); // Записываем саму цифру
    	          	ToPrint(n, m, &currentNumberColumn, &currentNumberRow, quantity);
    	          	ToPrint(n, m, &currentNumberColumn, &currentNumberRow, previousTerm[start]); // Печатаем полученные данные
    	          	start += quantity; // Переходим к следующей цифре для сравнения
    	          	quantity = 1; // Присваиваем количеству одинаковых идущих подряд цифр 1, так как мы перешли к следующей цифре
    	        } // Если значение текущей цифры не совпадает с предыдущим, выполняем вывод и заполнение вектора следующего члена
    	        if (i == (previousTerm.size() - 1)) {
    	            currentTerm.push_back(quantity); 
    	            currentTerm.push_back(previousTerm[start]);
    	            ToPrint(n, m, &currentNumberColumn, &currentNumberRow, quantity);
    	            ToPrint(n, m, &currentNumberColumn, &currentNumberRow, previousTerm[start]);
    	        } // Отдельный вывод для последнего элемента данного члена
           } // Цикл для прохода по всем цифрам предыдущего члена последовательности
           start = 0;      
           quantity = 0; // Обнуляем все параметры для подсчета, так как дальше будем работать со следующим членом последовательности
           ToPrint(n, m, &currentNumberColumn, &currentNumberRow, 32); // Печатаем пробел после текущего члена последовательности
           previousTerm.clear(); 
           previousTerm = currentTerm; // Записываем в вектор предыдущего члена текущий построенный член последовательности
           currentTerm.clear();
    } // Бесконечный цикл, так как условие окончание работы программы задано в методе печати
}

#include <iostream>

#include <vector>

using namespace std;

void ToPrint(int n, int m, int *currentNumberColumn, int *currentNumberRow, int symbolToPrint) {

(*currentNumberColumn)++; // Инкрементируем значение номера столбца, так как есть символ на печать

if (*currentNumberColumn > n) {

cout << endl; // Переходим на новую строку

(*currentNumberRow)++;

*currentNumberColumn = 1;

} // Если следует выполнить переход на следующую строку, выполняем этот переход по всем индексам

if (*currentNumberRow > m)

exit(0); // Заканчиваем работу программы, как только количество строк превышает заданное

else if (symbolToPrint == 32 && *currentNumberColumn == 1) // В таблице ASCII 32 - пробел

(*currentNumberColumn)--; // Возвращаем предыдущее значение номера столбца, так как ничего не было напечатано

else if (symbolToPrint == 32)

cout << char(symbolToPrint); // Выводим пробел, если это не начало строки

else

cout << symbolToPrint;

}

int main() {

int n, m; // Количество столбцов и строк соответственно

cin >> n >> m;

int start = 0; // Индекс элемента текущей цифры с которой ведется сравнение

int quantity = 0; // Количество идущих подряд одинаковых элементов в данном члене

int currentNumberRow = 1; // Номер текущей строки, в которой будет записан символ

int currentNumberColumn = 0; // Номер текущего столбца, в который будет записан символ

vector <short> currentTerm; // Вектор, хранящий значение текущего члена последовательности

vector <short> previousTerm; // Вектор, хранящий значение предыдущего члена последовательности

previousTerm.push_back(0); // Записываем в вектор предыдущего члена значение первого члена последовательности

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, 0); // Выводим первый член последовательности

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, 32); // Выводим пробел после него (если он не понадобится его уберет метод ToPrint)

while (true) {

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

if (previousTerm[i] == previousTerm[start])

quantity++; // Считаем количество идущих подряд одинаковых цифр

else {

currentTerm.push_back(quantity); // Записываем в вектор количество текущих цифр

currentTerm.push_back(previousTerm[start]); // Записываем саму цифру

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, quantity);

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, previousTerm[start]); // Печатаем полученные данные

start += quantity; // Переходим к следующей цифре для сравнения

quantity = 1; // Присваиваем количеству одинаковых идущих подряд цифр 1, так как мы перешли к следующей цифре

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

if (i == (previousTerm.size() - 1)) {

currentTerm.push_back(quantity);

currentTerm.push_back(previousTerm[start]);

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, quantity);

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, previousTerm[start]);

} // Отдельный вывод для последнего элемента данного члена

} // Цикл для прохода по всем цифрам предыдущего члена последовательности

start = 0;

quantity = 0; // Обнуляем все параметры для подсчета, так как дальше будем работать со следующим членом последовательности

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, 32); // Печатаем пробел после текущего члена последовательности

previousTerm.clear();

previousTerm = currentTerm; // Записываем в вектор предыдущего члена текущий построенный член последовательности

currentTerm.clear();

} // Бесконечный цикл, так как условие окончание работы программы задано в методе печати

}

Ссылки

Код программы
Дополнительная информация о «Look-and-Say» sequence:
Источник 1; Источник 2; Источник 3; Источник 4;

Related Images:

e-olymp 16. Дракон

05/10/2015 by Таран Таня

У каждой [latex]S[/latex]-ножки [latex]1[/latex] голова. Найти количество ног [latex]N[/latex] у [latex]K[/latex]-главого дракона, если у всех вместе [latex]A[/latex] голов и [latex]B[/latex] ног.

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

4 числа: [latex]S[/latex], [latex]K[/latex], [latex]A[/latex], [latex]B[/latex]. Все числа не превышают [latex]1000[/latex].

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

Количество ног у дракона. Если входные данные противоречивы, вывести [latex]-1[/latex], в случае наличия нескольких решений – вывести любое из них.

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

Тесты

[latex]S[/latex]	[latex]K[/latex]	[latex]A[/latex]	[latex]B[/latex]	[latex]N[/latex]	Комментарий
4	7	35	36	2	7 многоножек и 4 2-ногих дракона
10	3	10	34	8	1 многоножка и 3 8-ногих дракона
44	17	37	132	0	3 многоножки и 2 0 — ногих дракона
4	19	42	42	13	4 многоножки и 2 13 — ногих дракона
1	0	1	1	0	1 многоножка и 1 0 — ногий дракон
5	8	3	6	-1	Количество голов в сумме меньше чем у одного дракона
5	17	6	2	-1	Количество ног в сумме меньше чем у одной многоножки

Алгоритм

Для начала введем несколько дополнительных параметров. Обозначим количество имеющихся драконов через [latex]D[/latex], а количество многоножек как [latex]M[/latex]. Внесем имеющиеся данные в таблицу для удобства построения решения.

Дракон				Многоножка
Один		Несколько		Одна		Несколько
Голов	Ног	Голов	Ног	Голов	Ног	Голов	Ног
[latex]K[/latex]	[latex]N[/latex]	[latex]KD[/latex]	[latex]ND[/latex]	[latex]1[/latex]	[latex]S[/latex]	[latex]M[/latex]	[latex]SM[/latex]

Воспользуемся полученной таблицей и промоделируем сложившуюся ситуацию в виде системы уравнений:
[latex] \left\{\begin{matrix}
KD + M = A & \\
ND + SM = B &
\end{matrix}\right.[/latex]

Выразим из первого уравнения количество многоножек и подставим во второе уравнение:
[latex] \left\{\begin{matrix}
A — KD = M & \\
ND + S(A — KD) = B &
\end{matrix}\right.[/latex]

Раскрыв скобки, преобразуем выражение во втором уравнении:
[latex] \left\{\begin{matrix}

A — KD = M & \\
B — SA = D(N — SK) &
\end{matrix}\right.[/latex]

Теперь мы можем выразить количество драконов:
[latex] \left\{\begin{matrix}

A — KD = M & \\
\frac{B — SA}{N — SK} = D &
\end{matrix}\right.[/latex]

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

[latex]D[/latex] — количество драконов, следовательно, это положительное целое число.
Выполняя деление мы предполагаем, что [latex]N — SK[/latex] [latex]\neq[/latex] [latex]0[/latex]. Следует проверить имеет ли данный случай смысл и решение в контексте условия задачи.
Вернемся к системе считая, что [latex]N = SK[/latex]:
[latex] \left\{\begin{matrix}A — KD = M & \\
ND + S(A — KD) = B &
\end{matrix}\right.[/latex][latex] \left\{\begin{matrix}A — KD = M & \\
SKD + SA — SKD = B &
\end{matrix}\right.[/latex][latex] \left\{\begin{matrix}A — KD = M & \\
SA = B &
\end{matrix}\right.[/latex] Приходим к выводу, что, при условии [latex]SA = B[/latex], задача гарантировано имеет решение вида [latex]N = SK[/latex].
Теперь оценим знак полученного нами выражения:
[latex]\frac{B — SA}{N — SK}[/latex] [latex]> 0[/latex] [latex] \Rightarrow[/latex] [latex](B — SA > 0[/latex] [latex]\wedge[/latex] [latex]N — SK > 0)[/latex] [latex]\vee[/latex] [latex](B — SA < 0[/latex] [latex]\wedge[/latex] [latex]N — SK < 0)[/latex].
Оценим значение [latex]B — SA [/latex]:
[latex]B — SA = ND +SM — SA = ND +S(M — A) [/latex] [latex]M[/latex] — количество голов у одной многоножки, [latex]A[/latex] — общее количество голов [latex] \Rightarrow[/latex] [latex]M — A <= 0[/latex] , делаем вывод, что
[latex]B — SA <= 0[/latex] [latex]\forall[/latex] [latex]B, S, A[/latex] [latex] \Rightarrow[/latex] [latex]N — SK <= 0[/latex] [latex] \Rightarrow[/latex] [latex]N <= SK [/latex]

Анализ условия задачи окончен. Перейдем к реализации решения, принимая во внимание все условия и ограничения полученные в процессе размышлений.
Запустим цикл от [latex]0[/latex] до [latex]SK[/latex] (выполнять цикл далее не имеет смысла, так как там не будет найдено ни одного решения), который перебирает количество ног дракона. Объединим все получившиеся ограничения:

Прежде всего выполняем проверку для избежания деления на [latex]0[/latex]. (Условие проверки : [latex]SA = B[/latex] [latex] \Rightarrow[/latex] выводим результат [latex]N = SK [/latex] и заканчиваем работу программы).
Иначе выполняем ряд последовательных проверок для текущего [latex]N[/latex] в цикле:
- [latex]\frac{B — SA}{N — SK}[/latex] — целая величина. (Условие проверки : [latex]B — SA[/latex] делится нацело на [latex]N — SK[/latex])
- Количество ног драконов не превышает общее количество ног минус количество ног одной многоножки (имеется хотя бы одна многоножка, которая имеет [latex]S[/latex] ног). (Условие проверки: [latex]B — S >= DN[/latex])
- Количество голов драконов меньше чем общее количество голов (имеется хотя бы [latex]1[/latex] многоножка с [latex]1[/latex] головой). (Условие проверки: [latex]A > DK[/latex])

Как только выполняются все вышеописанные условия из пункта 2, выполняем вывод текущего количества ног дракона и заканчиваем работу программы, в противном случае выводим [latex]-1[/latex], так как данные противоречивы.

Примечание: в ходе решения выяснилось, что автор задачи предполагает существование 0 — ногих драконов, 0 — ногих многожек и т.д. Эти условия повлияли на вид некоторых неравенств.

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

#include <iostream>
using namespace std;

int main() {
	int s, k, a, b;// заданные величины в соответствующем условию порядке
	int n = 0;// текущее количество ног дракона
	int d;// текущее количество драконов
	cin >> s >> k >> a >> b;
	if (a * s == b){
	    cout << s * k;
	    return 0;
	}// отдельный случай, при a * s = b
	while (n < s * k) {
		if ((b - s * a) % (n - s * k) == 0) { 
		    d = (b - s * a) / (n - s * k);
		    if (b - s >= d * n && a > d * k) {
		       	cout << n;
		        return 0;
		    }// проверяем удовлетворяет ли текущее количество драконов и текущее количество ног все условия
		}// выполняем все проверки только для целых d
		n++;
    }// выполняем перебор только до s*k
	cout << -1;// выводим -1, если решений не нашлось(входные данные противоречивы)
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int s, k, a, b;// заданные величины в соответствующем условию порядке

int n = 0;// текущее количество ног дракона

int d;// текущее количество драконов

cin >> s >> k >> a >> b;

if (a * s == b){

cout << s * k;

return 0;

}// отдельный случай, при a * s = b

while (n < s * k) {

if ((b - s * a) % (n - s * k) == 0) {

d = (b - s * a) / (n - s * k);

if (b - s >= d * n && a > d * k) {

cout << n;

return 0;

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

}// выполняем все проверки только для целых d

n++;

}// выполняем перебор только до s*k

cout << -1;// выводим -1, если решений не нашлось(входные данные противоречивы)

return 0;

}

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

Related Images:

Mif 17.20

02/10/2015 by Таран Таня

Задача. Принадлежит ли точка [latex](x, y)[/latex] фигуре на рисунке?

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

Координаты точки в формате [latex](x, y)[/latex] ([latex]x, y[/latex] — действительные числа).

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

Вывести «YES», если точка принадлежит фигуре, и «NO» в противоположном случае.
(Точку, которая находится на контуре, также считаем принадлежащей данной фигуре).

Тесты

[latex]x[/latex]	[latex]y[/latex]	Результат
0	0	YES
-5	-5	YES
0	2.5	YES
3.5	4.2	YES
-4	-2.7	YES
3	-4	NO
-2	-1.5	NO
1	6	NO
3.5	0.5	NO
1000	2	NO

Решение

Проанализировав фигуру, можно определить, что она не симметрична, хотя данное свойство было бы нам полезно. Однако мы имеем полное право выполнить параллельный перенос фигуры на [latex]0.5[/latex] единиц влево. Рассмотрим текущее расположение фигуры.

Работать с фигурой стало проще, благодаря симметричности относительно начала координат [latex]O[/latex]. Для того чтобы не противоречить данному условию из-за выполненного сдвига, как только считываем координаты, уменьшаем абсциссу на [latex]0.5[/latex] единиц.
(На рисунке выделены основные данные, обозначенные определенными константами, которые понадобятся нам в ходе решения).

Для определения принадлежности точки фигуре будем постепенно убирать те области, в которых точка явно не может принадлежать фигуре:

В первую очередь исключим все точки, у которых модули значений координат превышают [latex]5.5[/latex] по оси абсцисс или [latex]5[/latex] по оси ординат.
(Условие проверки : [latex]|y| > c [/latex] [latex]\vee[/latex] [latex]|x| > d [/latex] )
Осталось рассмотреть две области, в которых точка не принадлежит фигуре тогда и только тогда, когда лежит ниже чем прямая [latex]y = 2[/latex] и правее [latex]x = 1.5[/latex] или же выше чем [latex]y = -2[/latex] и левее [latex]x =- 1.5[/latex].
(Условие проверки : [latex](x < -b[/latex] [latex]\wedge[/latex] [latex]y > -a)[/latex] [latex]\vee[/latex] [latex](x > b[/latex] [latex]\wedge[/latex] [latex]y < a)[/latex])
Если хотя бы одно из предыдущих условий выполнилось, приходим к заключению, что точка не принадлежит данной фигуре. Выводим «NO».
В противном случае выводим «YES».

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

#include <iostream>
#include <math.h>
using namespace std;

const double a = 2;
const double b = 1.5;
const double c = 5;
const double d = 5.5;

int main(){
	double x, y;
	cin >> x >> y;
	x -= 0.5;
	cout << (fabs(y) > c || fabs(x) > d || (x < -b && y > -a) || (x > b && y < a) ? "NO" : "YES");
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

const double a = 2;

const double b = 1.5;

const double c = 5;

const double d = 5.5;

int main(){

double x, y;

cin >> x >> y;

x -= 0.5;

cout << (fabs(y) > c || fabs(x) > d || (x < -b && y > -a) || (x > b && y < a) ? "NO" : "YES");

return 0;

}

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

Related Images:

Ю2.15

01/10/2015 by Таран Таня

Задача. Общая точка

Два отрезка на плоскости заданы координатами своих концов. Определить имеют ли эти отрезки общие точки.

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

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

Координаты концов двух отрезков [latex]AB, CD [/latex] в формате [latex] A(x_1, y_1) B(x_2, y_2) C (x_3, y_3) D(x_4, y_4)[/latex] ([latex]x_i, y_i[/latex] — действительные числа).

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

Расположение отрезков, а именно:

«Intersect at point [latex](x, y)[/latex]»
«Don’t intersect»
«Paralell»
«On the same line, but don’t intersect»
«Overlap» (Находятся на одной прямой и хотя бы одна из точек совпадает)

Тесты

Координаты [latex] A(x_1, y_1) B(x_2, y_2) C (x_3, y_3) D(x_4, y_4)[/latex]	Расположение отрезков
1 1 5 4 1 3 5 3	Intersect at point (3.66667, 3)
-7 2 -4 2 -6 3 -3 3	Paralell
1 2 3 2 2 2 6 2	Overlap
1 2 4 2 5 2 7 2	On the same line, but don’t intersect
1 2 4 4 2 1 5 3	Paralell
1 1 4 2 7 3 10 4	On the same line, but don’t intersect
1 1 5 3 5 3 7 4	Overlap
1 1 5 4 1 4 5 2	Intersect at point (3.4, 2.8)
1 1 2 4 3 2 6 4	Don’t intersect

Координаты [latex] A(x_1, y_1) B(x_2, y_2) C (x_3, y_3) D(x_4, y_4)[/latex]	Расположение отрезков
1 1 1 5 3 2 3 4	Paralell
1 2 4 5 2 2 2 5	Intersect at point (2, 3)
2 1 2 2 2 4 2 6	On the same line, but don’t intersect
2 1 2 5 1 2 4 2	Intersect at point (2, 2)
1 2 4 2 2 3 2 5	Don’t intersect

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

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

areCollinear — функция, принимающая координаты векторов, задаваемых отрезками, и возвращающая логическое значение true, если они коллинеарны, и false в противном случае.
( Основная формула: [latex]\frac{x_1}{x_2}[/latex] [latex]=[/latex] [latex]\frac{y_1}{y_2}[/latex] )
getMin — возвращает минимум двух чисел.
getMax — возвращает максимум двух чисел.
projectionsIntersect — функция, принимающая абсциссы или ординаты двух векторов и возвращающая логическое значение true, если проекции отрезков на соответствующую ось пересекаются, и false в противном случае.
getSlope — функция, принимающая координаты отрезка и возвращающая угол наклона прямой, на которой он расположен.
( Основная формула: [latex]\frac{y_2 — y_1}{x_2 — x_1}[/latex] )
getYIntercept — функция, принимающая координаты отрезка и возвращающая свободный член уравнения прямой, на которой он расположен.
( Основная формула: [latex]\frac{x_2y_1 — x_1y_2}{x_2 — x_1}[/latex] )
getCos — функция, принимающая координаты двух векторов и возвращающая косинус угла между ними.
( Основная формула: [latex]\frac{x_1x_2 + y_1y_2}{\sqrt(x_1^2 + y_1^2) + \sqrt(x_2^2 + y_2^2)}[/latex] )

Перейдем к основной части программы. Сразу следует оговорить, что последующее решение будет базироваться на векторах и работе с уравнением прямой вида [latex] y = kx + b [/latex], поэтому для удобства отдельно заведем переменные для координат векторов соответствующих отрезкам и значений вычисленных коэффициентов и свободных членов уравнений прямых. Одной из главных проблем на пути решения стали отрезки располагающиеся на прямых вида [latex]x = a [/latex], ведь если обратится к пунктам 5, 6 можно заметить, что в таких случаях мы получим исключение из-за деления на ноль. Этим вызвано вынужденное разделение программы на два блока — где ни один из отрезков не располагается параллельно оси ординат и когда хотя бы один из них параллелен. Это удается достичь благодаря инициализации логических переменных, принимающих значение true, когда отрезок расположен на прямой [latex]x = a[/latex]. Также изначально подсчитываем значения переменных yIntercept1, yIntercept2, slope1, slope2 тогда, когда это возможно, так как они будут задействованы в дальнейшем.

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

Решим систему уравнений для двух заданных прямых и таким образом найдем точку их пересечения.
[latex] \left\{\begin{matrix}
k_1x + b_1 = y & \\
k_2x + b_2 = y &
\end{matrix}\right.[/latex]
Найдя точку с координатами [latex](xIntersection,yIntersection)[/latex], следующим шагом станет проверка : принадлежит ли найденная точка имеющимся отрезкам. Для этого воспользуемся формулой скалярного произведения и определим косинус угла между векторами с началом в точке [latex](xIntersection, yIntersection)[/latex] и концами в соответствующих концах отрезка. Выполняем ее для двух отрезков. Если в обоих случаях найденный косинус будет [latex] \le[/latex] [latex]0[/latex], то точка находится на двух отрезках одновременно и является их пересечением. Выводим сообщение «Intersect at point [latex](xIntersection, yIntersection)[/latex]«.
В случае, если такая точка не найдена в следствие определенных причин, рассмотрим следующие возможные ситуации:
а) При условии, что равны свободные члены уравнения прямых и точка не была найдена, можем проверить утверждение, что рассматриваемые прямые совпадают, а заданные отрезки находятся на ней. Здесь требуют рассмотрения два варианта: отрезки накладываются, если проекции отрезков на ось абсцисс накладываются друг на друга, или же отрезки находятся на одной прямой и не пересекаются. Выводим соответствующее сообщение : «Overlap»/»On the same line, but don’t intersect».
б) Если свободные члены не равны и не выполнилось ни одно из предыдущих утверждений, приходим к выводу, что возможно отрезки, которые задают вектора, параллельны. Выполняем проверку на коллинеарность , в случае подтверждения предположения выводим сообщение : «Parallel».
в) Пройдя через все вышеупомянутые проверки и не получив логического значения true, определяем, что данные отрезки не пересекаются и не удовлетворяют ни одному из особенных случаев. Выводим сообщение : «Don’t intersect».Таким образом рассмотрение общего случая окончено. Перейдем ко второй ситуации:

Если оба отрезка расположены на прямых вида [latex]x = a[/latex], то имеем следующие варианты:
а) Если отрезки расположены на одной прямой и их проекции на ось ординат пересекаются, выводим сообщение : «Overlap».
б) Если отрезки расположены на одной прямой и их проекции на ось ординат не пересекаются, выводим сообщение : «On the same line, but don’t intersect».
в) Если отрезки расположены не на одной прямой, выводим сообщение «Paralell».
При условии, что только одна из прямых имеет вид [latex]x = a[/latex], рассмотрим следующие ситуации:
а)Только одна из прямых имеет вид [latex]x = a[/latex] и обе имеют коэффициент угла наклона равный [latex]0[/latex]. Перед нами две прямые вида: [latex] y = b[/latex] и [latex]x = a [/latex]. Выполняем смену между соответствующими координатами, чтобы не дублировать код для двух аналогичных ситуаций и рассматриваем только одну из них. Нетрудно заметить, что единственным решением является точка [latex](x_3/x_4, y_1/y_2)[/latex] . Используя метод getCos, выполняем уже описанную выше проверку на принадлежность точки отрезку. Если да — выводим сообщение : «Intersect at point [latex](x_3, y_1)[/latex]», в противном случае : «Don’t intersect».
б) Однако, ни одна из предыдущих проверок могла не выполниться, так как существует еще одно расположение отрезков на прямых [latex] y = kx + b [/latex] и [latex]x = a [/latex]. Выполняем аналогичную операцию по смене координат во избежание дублирования кода. Единственным решением данной системы может являться точка [latex](x3/x4 + yIntercept1, x3/x4)[/latex]. Повторяем операции аналогичные последним из пункта б). Выводим сообщение: «Intersect at point [latex](x3 + yIntercept1, x3)[/latex]» или «Don’t intersect».
(В последних двух пунктах несколько раз координаты были записаны через черту, что , вероятно, требует пояснения: в этих ситуациях наблюдалось равенство и какую координату мы выберем не существенно).

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

#include <iostream>
#include <math.h>
using namespace std;

bool areCollinear(double x1, double y1, double x2, double y2) {
	return x1 / x2 == y1 / y2 ? true : false;// проверка на коллинеарность
}

double getMin(double x1, double x2) {
	return x1 < x2 ? x1 : x2;
}

double getMax(double x1, double x2) {
	return x1 > x2 ? x1 : x2;
}

// Проверка на пересечение проекций на оси, посредством нахождения взаимного расположения концов проекций
bool projectionsIntersect(double x1, double x2, double x3, double x4) {
	return ((getMin(x1, x2) <= getMin(x3, x4) && getMin(x3, x4) <= getMax(x1, x2)) || ((getMin(x3, x4) <= getMin(x1, x2) && getMin(x1, x2) <= getMax(x3,x4))));
}

// Вычисление коэффициента угла наклона уравнения прямой
double getSlope(double x1, double  y1, double x2, double y2) {
	return (y2 - y1) / (x2 - x1); 
}

// Вычисление свободного члена уравнения прямой
double getYIntercept(double x1, double  y1, double x2, double y2) {
	return (x2 * y1 - x1 * y2) / (x2 - x1);
}

// Нахождение косинуса угла между векторами
double getCos(double x1, double  y1, double x2, double y2) {
	return (x1 * x2 + y1 * y2) / (sqrt(x1 * x1 + y1 * y1) + sqrt(x2 * x2 + y2 * y2));
}

int main() {
    double slope1, slope2; // Коэффициенты углов наклона уравнений прямых, на которых расположены отрезки
	bool f1 = false, f2 = false; // Логические флаги для прямых вида x = a 
	double yIntercept1, yIntercept2; // Свободные члены уравнений прямых, на которых расположены отрезки
	double xIntersection, yIntersection; // Координаты точки пересечения, если она существует
	double x1, y1, x2, y2, x3, y3, x4, y4; // Заданные координаты концов отрезков 
	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
	double vx1 = x2 - x1;
	double vy1 = y2 - y1; // Вычислим координаты векторов,
	double vx2 = x4 - x3; // Задаваемых данными отрезками
	double vy2 = y4 - y3;
	slope1 = (vx1 != 0 ? getSlope(x1, y1, x2, y2) : 0); // Для прямых вида x = a
	slope2 = (vx2 != 0 ? getSlope(x3, y3, x4, y4) : 0); // Присваиваем значение 0 коэффициенту угла наклона
	vx1 != 0 ? yIntercept1 = getYIntercept(x1, y1, x2, y2) : f1 = true; // Для прямых вида x = a 
    vx2 != 0 ? yIntercept2 = getYIntercept(x3, y3, x4, y4) : f2 = true; // Присваиваем флагу значение true
	if (!f1 && !f2) {
		xIntersection = (yIntercept2 - yIntercept1) / (slope1 - slope2); // Находим решение системы уравнений 
		yIntersection = slope1 * xIntersection + yIntercept1;
		if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0) // Проверяем находится ли точка на обоих отрезках 
	        cout << "Intersect at a point (" << xIntersection << "," << yIntersection << ")"; 
	    else if (yIntercept1 == yIntercept2) {
    		if (projectionsIntersect(x1, x2, x3, x4))
        		cout << "Overlap";
            else 
		        cout << "On the same line, but don't intersect";
        } 
        else if (yIntercept1 != yIntercept2 && (areCollinear(vx1, vy1, vx2, vy2) || (y1 == y2 && y3 == y4))) 
            cout << "Paralell";
	    else 
	        cout << "Don't intersect";
	} // Блок нахождения расположения для всех отрезков, кроме тех, где хотя бы один из них расположен на прямой вида x = a
	else {
	    if (slope1 == 0 && slope2 == 0 && f1 && f2) {
		    if (x1 == x4 &&  projectionsIntersect(y1, y2, y3, y4))
        	    cout << "Overlap";
            else if (x1 != x4)
        	    cout << "Paralell";
            else
                cout << "On the same line, but don't intersect";
	    } // Блок для двух прямых вида x = a
        else if (f1 ^ f2 && slope1 == 0 && slope2 == 0) {
        	if (f1) {
        		swap(x1, x3);
        		swap(x2, x4);
        		swap(y1, y3);
        		swap(y2, y4);
        		swap(yIntercept1, yIntercept2);	
        	}
        	yIntersection = y1;
        	xIntersection = x3;
        	if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0) 
        		cout << "Intersect at a point ("  << xIntersection << "," << yIntersection << ")";
            else 
               	cout << "Don't intersect";
        } // Блок для прямых вида y = b и x = a
        else if (slope1 == 0 ^ slope2 == 0) {
        	if (slope1 == 0) {
        		swap(x1, x3);
        		swap(x2, x4);
        		swap(y1, y3);
        		swap(y2, y4);
        		swap(yIntercept1, yIntercept2);
        	}
        	xIntersection = x3;
        	yIntersection = x3 + yIntercept1;
        	if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0) 
        		cout << "Intersect at a point ("  << xIntersection << "," << yIntersection << ")";
        	else 
        		cout << "Don't intersect";
        } // Блок нахождения расположения, когда только одна пряма имеет вид x = a, а вторая y = kx +b
    } // Блок нахождения расположения, если хотя бы один отрезок находится на прямой вида x = a
	return 0;
}

100

101

102

103

104

105

106

107

108

109

#include <iostream>

#include <math.h>

using namespace std;

bool areCollinear(double x1, double y1, double x2, double y2) {

return x1 / x2 == y1 / y2 ? true : false;// проверка на коллинеарность

}

double getMin(double x1, double x2) {

return x1 < x2 ? x1 : x2;

}

double getMax(double x1, double x2) {

return x1 > x2 ? x1 : x2;

}

// Проверка на пересечение проекций на оси, посредством нахождения взаимного расположения концов проекций

bool projectionsIntersect(double x1, double x2, double x3, double x4) {

return ((getMin(x1, x2) <= getMin(x3, x4) && getMin(x3, x4) <= getMax(x1, x2)) || ((getMin(x3, x4) <= getMin(x1, x2) && getMin(x1, x2) <= getMax(x3,x4))));

}

// Вычисление коэффициента угла наклона уравнения прямой

double getSlope(double x1, double y1, double x2, double y2) {

return (y2 - y1) / (x2 - x1);

}

// Вычисление свободного члена уравнения прямой

double getYIntercept(double x1, double y1, double x2, double y2) {

return (x2 * y1 - x1 * y2) / (x2 - x1);

}

// Нахождение косинуса угла между векторами

double getCos(double x1, double y1, double x2, double y2) {

return (x1 * x2 + y1 * y2) / (sqrt(x1 * x1 + y1 * y1) + sqrt(x2 * x2 + y2 * y2));

}

int main() {

double slope1, slope2; // Коэффициенты углов наклона уравнений прямых, на которых расположены отрезки

bool f1 = false, f2 = false; // Логические флаги для прямых вида x = a

double yIntercept1, yIntercept2; // Свободные члены уравнений прямых, на которых расположены отрезки

double xIntersection, yIntersection; // Координаты точки пересечения, если она существует

double x1, y1, x2, y2, x3, y3, x4, y4; // Заданные координаты концов отрезков

cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;

double vx1 = x2 - x1;

double vy1 = y2 - y1; // Вычислим координаты векторов,

double vx2 = x4 - x3; // Задаваемых данными отрезками

double vy2 = y4 - y3;

slope1 = (vx1 != 0 ? getSlope(x1, y1, x2, y2) : 0); // Для прямых вида x = a

slope2 = (vx2 != 0 ? getSlope(x3, y3, x4, y4) : 0); // Присваиваем значение 0 коэффициенту угла наклона

vx1 != 0 ? yIntercept1 = getYIntercept(x1, y1, x2, y2) : f1 = true; // Для прямых вида x = a

vx2 != 0 ? yIntercept2 = getYIntercept(x3, y3, x4, y4) : f2 = true; // Присваиваем флагу значение true

if (!f1 && !f2) {

xIntersection = (yIntercept2 - yIntercept1) / (slope1 - slope2); // Находим решение системы уравнений

yIntersection = slope1 * xIntersection + yIntercept1;

if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0) // Проверяем находится ли точка на обоих отрезках

cout << "Intersect at a point (" << xIntersection << "," << yIntersection << ")";

else if (yIntercept1 == yIntercept2) {

if (projectionsIntersect(x1, x2, x3, x4))

cout << "Overlap";

else

cout << "On the same line, but don't intersect";

}

else if (yIntercept1 != yIntercept2 && (areCollinear(vx1, vy1, vx2, vy2) || (y1 == y2 && y3 == y4)))

cout << "Paralell";

else

cout << "Don't intersect";

} // Блок нахождения расположения для всех отрезков, кроме тех, где хотя бы один из них расположен на прямой вида x = a

else {

if (slope1 == 0 && slope2 == 0 && f1 && f2) {

if (x1 == x4 && projectionsIntersect(y1, y2, y3, y4))

cout << "Overlap";

else if (x1 != x4)

cout << "Paralell";

else

cout << "On the same line, but don't intersect";

} // Блок для двух прямых вида x = a

else if (f1 ^ f2 && slope1 == 0 && slope2 == 0) {

if (f1) {

swap(x1, x3);

swap(x2, x4);

swap(y1, y3);

swap(y2, y4);

swap(yIntercept1, yIntercept2);

}

yIntersection = y1;

xIntersection = x3;

if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0)

cout << "Intersect at a point (" << xIntersection << "," << yIntersection << ")";

else

cout << "Don't intersect";

} // Блок для прямых вида y = b и x = a

else if (slope1 == 0 ^ slope2 == 0) {

if (slope1 == 0) {

swap(x1, x3);

swap(x2, x4);

swap(y1, y3);

swap(y2, y4);

swap(yIntercept1, yIntercept2);

}

xIntersection = x3;

yIntersection = x3 + yIntercept1;

if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0)

cout << "Intersect at a point (" << xIntersection << "," << yIntersection << ")";

else

cout << "Don't intersect";

} // Блок нахождения расположения, когда только одна пряма имеет вид x = a, а вторая y = kx +b

} // Блок нахождения расположения, если хотя бы один отрезок находится на прямой вида x = a

return 0;

}

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

Аналогичная задача на сайте e-olymp:
839. Пересечение отрезков (Засчитанное решение)

Related Images:

e-olymp 22. «Зеркально простые» числа

22/09/2015 by Таран Таня

Назовем число «зеркально простым», если само число является простым, и простым является число, записанное теми же цифрами в обратном порядке.

Найти количество «зеркально простых» чисел на промежутке от [latex]a[/latex] до [latex]b[/latex].

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

Два числа [latex]a[/latex] и [latex]b[/latex] ( [latex]1[/latex][latex]\le[/latex] [latex]a[/latex], [latex]b[/latex] [latex]\le[/latex] [latex]10000[/latex]).

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

Вывести количество «зеркально простых» чисел на промежутке от [latex]a[/latex] до [latex]b[/latex] включительно.

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

Тесты

Границы промежутка	Количество «зеркально простых» чисел
1 10	4
100 200	12
1008 1230	19
3340 3950	31
9900 10000	4

Алгоритм

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

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

Достигнув верхней границы промежутка, выводим количество «зеркально простых» чисел.

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

#include <iostream>
using namespace std;

int main() {
    int a, b;
    int number1, number2;// переменные для хранения текущего числа из промежутка и "зеркального" соответственно
    int counter = 0;// счетчик количества "зеркально простых" чисел
    cin >> a >> b;
    if(a > b){
       a += b;
       b = a - b;
       a -= b;
    }// меняем местами границы промежутка, если они введены в неправильном порядке
    if (a == 1) 
        counter--;// декрементируем счетчик, если в промежуток попадает число 1, которое не является простым
    for (int i = a; i <= b; i++){
         number1 = i; 
         bool f1 = true;// флаг выполнения условия для number1
         bool f2 = true;// флаг выполнения условия для number2
         for (int j = 2; j*j <= number1; j++){
              f1 = number1%j;
              if (!f1) 
                  break;
         }// проверяем является ли number1 простым
         if (f1){
             number2 = 0;
             while (number1 > 0){
                    number2 = number2*10 + number1%10;
                    number1 /= 10;
             }// собираем число "зеркальное" текущему
             for (int j = 2; j*j <= number2; j++){
                  f2 = number2%j;
                  if (!f2) 
                      break; 
             }// проверяем является ли number2 простым 
             if (f2) 
                 counter++;// инкрементируем счетчик 
         }
    }
    cout << counter;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b;

int number1, number2;// переменные для хранения текущего числа из промежутка и "зеркального" соответственно

int counter = 0;// счетчик количества "зеркально простых" чисел

cin >> a >> b;

if(a > b){

a += b;

b = a - b;

a -= b;

}// меняем местами границы промежутка, если они введены в неправильном порядке

if (a == 1)

counter--;// декрементируем счетчик, если в промежуток попадает число 1, которое не является простым

for (int i = a; i <= b; i++){

number1 = i;

bool f1 = true;// флаг выполнения условия для number1

bool f2 = true;// флаг выполнения условия для number2

for (int j = 2; j*j <= number1; j++){

f1 = number1%j;

if (!f1)

break;

}// проверяем является ли number1 простым

if (f1){

number2 = 0;

while (number1 > 0){

number2 = number2*10 + number1%10;

number1 /= 10;

}// собираем число "зеркальное" текущему

for (int j = 2; j*j <= number2; j++){

f2 = number2%j;

if (!f2)

break;

}// проверяем является ли number2 простым

if (f2)

counter++;// инкрементируем счетчик

}

cout << counter;

return 0;

}

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

Засчитанное решение

Related Images:

ML19

18/09/2015 by Таран Таня

Задача. Известна длина окружности. Найти площадь круга, ограниченного этой окружностью.

Тесты

Длина окружности	Точность	Результат работы программы
0	3	Невозможно выполнить для вырожденной окружности
-1	8	Ошибка ввода данных
34	-5	Ошибка ввода данных
25	18	Вывод с заданной точностью невозможен. Максимально возможная точность 13
25	13	49.7359197162173
83	5	548.20920
113.42	3	1 023.692
12 345 678	3	Вывод с заданной точностью невозможен. Максимально возможная точность 1
12 345 678	1	12 128 861 224 697.9
1 000 000 000	0	Число содержит больше 15 значащих цифр. Точный вывод невозможен

Алгоритм

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

Для удобства преобразуем известные нам формулы:

[latex]L = 2 \pi \cdot R[/latex] [latex]S = \pi \cdot R^2 [/latex] [latex] \longrightarrow[/latex] [latex]R= \frac{L}{2\pi}[/latex] [latex]\longrightarrow[/latex] [latex]S = \frac{L^2}{4\pi}[/latex];

Воспользовавшись данной формулой находим искомую величину. Однако реализуя вывод с заданной точностью, требуется проверить сможет ли используемый нами тип данных double его обеспечить. Принимая во внимание факт, что данный тип хранит не более чем [latex]15[/latex] значащих десятичных цифр осуществляем следующую последовательность действий:

Находим значение переменной possibleAccuracy как разность между максимально возможным количеством значащих цифр (maxAccuracy = [latex]15[/latex]) и имеющемся в данном числе .
Отрицательное значение переменной possibleAccuracy сигнализирует о том, что найденная площадь круга превышает [latex] 10^{15} [/latex]. Следовательно, выводим предупреждение о том, что точный подсчет невозможен даже с нулевой точностью после запятой.
При условии, что запрашиваемая точность превышает максимальную, выводим уведомление и значение максимальной точности.
При ложности пункта 2 и 3, используя манипулятор setprecision, выводим нужное количество знаков.

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

#include <iostream>
#include <iomanip> 
#include <math.h>
using namespace std;

const int maxAccuracy = 15;

int main() {
	double circumference, circleArea;
	int givenAccuracy, possibleAccuracy;// заданная пользователем и максимально возможная в данном случае точность соответственно
	cin >> circumference >> givenAccuracy;
	if (circumference == 0)
	    cout << "Невозможно выполнить для вырожденной окружности";// выведение уведомления, если задана вырожденная окружность
	else if (circumference < 0 || givenAccuracy < 0){
		     cout << "Ошибка ввода данных";// проверка введенных данных
	} else {
		circleArea = circumference * (circumference / (4 * M_PI));
		possibleAccuracy = maxAccuracy - ceil(log10(circleArea));
		if (possibleAccuracy < 0) 
		    cout << "Число содержит больше 15 значащих цифр. Точный вывод невозможен";// предупреждение, если число превышает 10^15
		else if (possibleAccuracy < givenAccuracy)
		    	 cout << "Вывод с заданной точностью невозможен. Максимально возможная точность " << possibleAccuracy;
	    else
		  cout << fixed << setprecision(givenAccuracy) << circleArea;
	}
	return 0;
}

#include <iostream>

#include <iomanip>

#include <math.h>

using namespace std;

const int maxAccuracy = 15;

int main() {

double circumference, circleArea;

int givenAccuracy, possibleAccuracy;// заданная пользователем и максимально возможная в данном случае точность соответственно

cin >> circumference >> givenAccuracy;

if (circumference == 0)

cout << "Невозможно выполнить для вырожденной окружности";// выведение уведомления, если задана вырожденная окружность

else if (circumference < 0 || givenAccuracy < 0){

cout << "Ошибка ввода данных";// проверка введенных данных

} else {

circleArea = circumference * (circumference / (4 * M_PI));

possibleAccuracy = maxAccuracy - ceil(log10(circleArea));

if (possibleAccuracy < 0)

cout << "Число содержит больше 15 значащих цифр. Точный вывод невозможен";// предупреждение, если число превышает 10^15

else if (possibleAccuracy < givenAccuracy)

cout << "Вывод с заданной точностью невозможен. Максимально возможная точность " << possibleAccuracy;

else

cout << fixed << setprecision(givenAccuracy) << circleArea;

}

return 0;

}

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

Related Images:

e-olymp 29. Уровень палиндромности

15/09/2015 by Таран Таня

Задано натуральное [latex]M[/latex]. Если число не палиндром – записываем его в обратном порядка и слагаем с заданным. Действия повторяем до тех пор, пока не получим число-палиндром. Количество выполненных операций назовем уровнем палиндромности заданного числа.

Найти уровень палиндромности заданного числа [latex]M[/latex].

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

Единственное число [latex]M[/latex] ([latex]0[/latex] [latex] <[/latex] [latex]M[/latex] [latex] <[/latex] [latex]10000[/latex]).

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

Единственное число – уровень палиндромности.

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

Тесты

Входные данные	Выходные данные
1	0
79	6
101	0
198	5
865	2
9998	6

Алгоритм

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

Для начала инициализируем счетчик, который хранит в себе текущее значение уровня палиндромности, и логическую переменную, значение которой ложно до тех пор пока палиндром не найден. Данное условие и будет критерием для выполнения тела основного цикла.
Присвоив значения переменным в цикле, выполняем последовательный разбор введенного числа на цифры и сборку «зеркального» числа.
Проверяем равенство числа и ему обратного.
Выполнение условного оператора сигнализирует о том, что палиндром найден, следовательно выводим «уровень», изменяем значение логической переменной на противоположное и выходим из цикла.
В противном случае суммируем текущее число и «зеркальное», инкрементируем счетчик.
Повторяем пункты 2, 3, 5 до истинности пункта 3 и перехода к 4.

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

#include <iostream>
using namespace std;

int main() {
	long x, x1, x2;// переменные для хранения числа, его копии и числа записанного в обратном порядке соответственно
	int c;
	int k = 0;// счетчик "уровня палиндромности"
	cin >> x;
	bool f = false;// флаг выполнения условия палиндромности числа
	while(!f){
		 x1 = x;
		 x2 = 0;
		 while (x1 > 0){
		        c = x1%10;
		        x1 /= 10;
		        x2 = x2*10 + c;// собираем число записанное в обратном порядке
	     }
	if (x == x2){
		cout << k;// выводим счетчик, если число палиндром
		f = true; 
		break;// выход из цикла, при условии, что палиндром найден
	} else { 
			x += x2;// суммируем значение числа и обратно записанного, если оно не является палиндромом
			k++; 
	}
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

long x, x1, x2;// переменные для хранения числа, его копии и числа записанного в обратном порядке соответственно

int c;

int k = 0;// счетчик "уровня палиндромности"

cin >> x;

bool f = false;// флаг выполнения условия палиндромности числа

while(!f){

x1 = x;

x2 = 0;

while (x1 > 0){

c = x1%10;

x1 /= 10;

x2 = x2*10 + c;// собираем число записанное в обратном порядке

}

if (x == x2){

cout << k;// выводим счетчик, если число палиндром

f = true;

break;// выход из цикла, при условии, что палиндром найден

} else {

x += x2;// суммируем значение числа и обратно записанного, если оно не является палиндромом

k++;

}

return 0;

}

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

Засчитанное решение

Related Images:

e-olymp 126. Номер квартиры

15/09/2015 by Таран Таня

Задача. Многоквартирный дом имеет [latex]N[/latex] квартир, [latex]P[/latex] подъездов и [latex]Q[/latex] этажей, причем на каждом этаже каждого подъезда имеется одинаковое количество квартир. Определить в каком подъезде и на каком этаже находится квартира с заданным номером [latex]K[/latex].

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

В единственной строке файла записаны значения [latex]N[/latex], [latex]P[/latex], [latex]Q[/latex], [latex]K[/latex]. [latex]1[/latex] ≤ [latex]K[/latex] ≤ [latex]N[/latex] ≤ [latex]1000[/latex], [latex]P\cdot Q[/latex] ≤ [latex]N[/latex].

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

В единственную строку файла нужно вывести номер подъезда и этаж, на котором находится квартира с номером [latex]K[/latex].

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

Тесты

Входные данные	Выходные данные
250 5 5 1	1 1
30 2 5 27	2 4
300 3 10 111	2 2
80 5 4 77	5 4
98 7 2 39	3 2
90 3 15 90	3 15

Перед нами была поставлена задача определить в доме с заданным количеством квартир, подъездов и этажей положение конкретной квартиры, а именно указать номер подъезда и этаж. Для дальнейшего хода решения определим две целочисленные переменные — flatEntrance (количество квартир в одном подъезде) и flatFloor (количество квартир на одном этаже). Найдем номер подъезда получив целую часть от деления номера квартиры на количество квартир в одном подъезде. Далее выполняем проверку остатка от деления, если он отличен от нуля, то это указывает на то, что квартира находится уже в следующем подъезде. В таком случае инкрементируем переменную entrance.

Для нахождения номера этажа поступим аналогично. Однако следует проверить не делится ли номер квартиры на количество квартир в одном подъезде нацело, если да — она располагается на последнем этаже. Если этого не сделать, то в последующей формуле получим [latex]0[/latex]. В общем случае номер этажа находим поделив остаток от деления номера квартиры на количество квартир в подъезде на количество квартир на этаже (учитываем, что каждый новый подъезд предполагает продолжение нумерации с первого этажа). И снова выполняем проверку остатка от деления. При надобности инкрементируем переменную floor.

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

#include <iostream>
using namespace std;

int main() {
	int N, P, Q, K, flatEntrance, flatFloor, entrance, floor;
	cin >> N >> P >> Q >> K;
	flatEntrance = N/P;
    flatFloor = N/P/Q;
	entrance = K/flatEntrance; 
	if (K%flatEntrance != 0){
		entrance++;
	}
	if (K%flatEntrance == 0){
	    floor = Q;
	} else {
		    floor = (K%flatEntrance)/flatFloor; 
		    if (K%flatFloor != 0){
		  	    floor++;
		    }
    }
    cout << entrance << " " << floor << endl;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int N, P, Q, K, flatEntrance, flatFloor, entrance, floor;

cin >> N >> P >> Q >> K;

flatEntrance = N/P;

flatFloor = N/P/Q;

entrance = K/flatEntrance;

if (K%flatEntrance != 0){

entrance++;

}

if (K%flatEntrance == 0){

floor = Q;

} else {

floor = (K%flatEntrance)/flatFloor;

if (K%flatFloor != 0){

floor++;

}

cout << entrance << " " << floor << endl;

return 0;

}

Следует отметить, что упростить программу и избавиться от двух условных операторов можно подключив библиотеку math.h и воспользовавшись функцией ceil() — округлением до ближайшего большего целого числа. Тогда код программы выглядит так:

#include <iostream>
#include <math.h>
using namespace std;

int main() {
	int N, P, Q, K, flatEntrance, flatFloor, entrance, floor;
	cin >> N >> P >> Q >> K;
	flatEntrance = N/P;
    flatFloor = N/P/Q;
	entrance = ceil(double(K)/flatEntrance);
	if (K%flatEntrance == 0){
	    floor = Q;
	} else {
		    floor = ceil((K%flatEntrance)/double(flatFloor)); 
    }
    cout << entrance << " " << floor << endl;
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

int N, P, Q, K, flatEntrance, flatFloor, entrance, floor;

cin >> N >> P >> Q >> K;

flatEntrance = N/P;

flatFloor = N/P/Q;

entrance = ceil(double(K)/flatEntrance);

if (K%flatEntrance == 0){

floor = Q;

} else {

floor = ceil((K%flatEntrance)/double(flatFloor));

}

cout << entrance << " " << floor << endl;

return 0;

}

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

Input

Output

Tests

Algorithm

Code

Links

Related Images:

Input

Output

Tests

Algorithm

Code

Links

Related Images:

Input

Output

Tests

Algorithm

Code

Links

Related Images:

Input

Output

Test

Algorithm

Code

Links

Related Images:

Input

Tests

Algorithm

Code

Related Images:

Input

Output

Tests

Algorithm

Code (class Vector)

Code (stream processing)

Related Images:

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

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

Тесты

Алгоритм

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

Related Images:

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

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

Тесты

Алгоритм

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

Related Images:

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

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

Тесты

Алгоритм

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

Ссылки

Related Images:

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

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

Тесты

Алгоритм

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

Ссылки

Related Images:

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

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

Related Images:

Related Images:

Related Images:

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

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

Related Images:

Related Images:

Related Images:

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

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

Тесты

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