e-olymp 1453. Форд-Беллман

30/04/2016 by Молоканов Юрий

Условие

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

Сначала записано количество вершин графа [latex]n[/latex] ([latex]1 \leq n \leq 100[/latex]), за которым идет количество ребер [latex]m[/latex] ([latex]1 \leq m \leq 10000[/latex]) Следующие [latex]m[/latex] троек чисел описывают ребра: начало ребра, конец ребра и его вес (вес — целое число от [latex]-100[/latex] до [latex]100[/latex]).

Выведите [latex]n[/latex] чисел — расстояния от вершины номер [latex]1[/latex] до всех вершин графа. Если пути до соответствующей вершины не существует, вместо длины пути выведите число [latex]30000[/latex].

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

№	Входные данные	Выходные данные
1	4 5 1 2 10 2 3 10 1 3 100 3 1 -10 2 3 1	0 10 11 30000

Код

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

struct edge {
	int a, b, cost;
	edge(int na, int nb, int nc) {
		int a = na;
		int b = nb;
		int cost = nc;
	}
};

const int INF = 30000;
 
int main() {
	int n, m, a, b, c;
	vector<edge> e;
	cin >> n >> m;
	for(int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		edge newEdge(a, b, c);
		e.push_back(newEdge);
	}
	vector<int> d(n, INF);
	d[0] = 0;
	for(int i = 0; i < n - 1; i++)
		for(int j = 0; j < m; j++)
			if(d[e[j].a] < INF)
				d[e[j].b] = min(d[e[j].b], d[e[j].a] + e[j].cost);
	for(int i = 0; i < n - 1; i++)
		cout << d[i] << ' ';
	return 0;
}

#include <vector>

#include <cmath>

using namespace std;

struct edge {

int a, b, cost;

edge(int na, int nb, int nc) {

int a = na;

int b = nb;

int cost = nc;

}

};

const int INF = 30000;

int main() {

int n, m, a, b, c;

vector<edge> e;

cin >> n >> m;

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

cin >> a >> b >> c;

edge newEdge(a, b, c);

e.push_back(newEdge);

}

vector<int> d(n, INF);

d[0] = 0;

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

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

if(d[e[j].a] < INF)

d[e[j].b] = min(d[e[j].b], d[e[j].a] + e[j].cost);

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

cout << d[i] << ' ';

return 0;

}

Решение

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

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

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

for(int i = 1; i < s.length() && s.length() - i > max; i++) {	
	int j = 0;
/*
Перебираем различные длины префиксов (суффиксов), пока не дойдем до длины 1 и пока можем встретить грань, длиннее хранящейся.
i - первый символ очередного суффикса
j - длина текущей грани и первый символ очередного префикса
*/

for(int i = 1; i < s.length() && s.length() - i > max; i++) {

int j = 0;

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

i - первый символ очередного суффикса

j - длина текущей грани и первый символ очередного префикса

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

C++

while(j < s.length() - i && s.at(j) == s.at(i + j)) j++;

1
2

while(j < s.length() - i && s.at(j) == s.at(i + j))
j++;

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

Отметим, что значение переменной j, получаемое в каждой итерации, представляет собой максимально возможную длину грани либо исходной строки (если проверки на совпадение пар символов закончились из-за достижения конца строки), либо подстроки, получаемой путем отбрасывания правой части исходной до того символа, на котором обнаружилось несовпадение.

Ссылки

Условие задачи на E-Olymp;

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

Подтверждение решения на E-Olymp.

Related Images:

A297

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

Условие

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

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

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

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

Код

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

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

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

int main() {

vector<int> x;

int t;

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

int max = t;

x.push_back(t);

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

x.push_back(t);

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

max = t;

}

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

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

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

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

return 0;

}

Решение

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

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

vector<int> x;

1	vector<int> x;

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

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

int t;

cin >> t;

int max = t;

x.push_back(t);

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

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

while(cin >> t) {

x.push_back(t);

if(t > max)

max = t;

}

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

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

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

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

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

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

Ссылки

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

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

Related Images:

AL13

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

Условие

Имеется [latex]n[/latex] черных и белых карточек, сложенных в стопку. Карточки раскладываются на стол в одну линию следующим образом: первая кладется на стол, вторая — под низ стопки, третья — на стол, четвертая — под низ стопки и т.д., пока все карточки не будут выложены на стол. Каким должно быть исходное расположение карточек в стопке, чтобы разложенные на столе карточки чередовались по цвету: белая, черная, белая, черная и т.д.?

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

№	Входные данные	Выходные данные
1	1	1
2	2	01
3	5	10011
4	12	101100010011
5	20	00111001101100010011

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

Код

#include <iostream>
using namespace std;

// Узел. Используется в очереди
struct node {
    bool val;   // Значение узла
    node *next; // Указатель на следующий узел
    node(int v, node *n = NULL) {
        val = v;
        next = n;
    }
};

// Очередь. Используется как представление стопки
struct Queue {
    node *head;
    Queue(node *h = NULL) {
        head = h;
    }
    void push(bool v) { // Добавить элемент в очередь
        head = new node(v, head);
    }
    bool pop() {    // Изъять элемент из очереди
        if(head != NULL && (head -> next) != NULL) {
            node *i = head;
            node *p = i;
            while(i -> next != NULL) {
                p = i;
                i = i -> next;
            }
            bool v = i -> val;
            p -> next = NULL;
            delete i;
            return v;
        } else {
            node *n = head;
            bool v = head -> val;
            head = head -> next;
            delete n;
            return v;
        }
    }
};

int main() {
    int n;  // Количество карточек в стопке
    cin >> n;
    Queue cards;
    bool t = n % 2; // Цвет текущей карточки. Инициализируется цветом последней выкладываемой карточки
    for(int i = 0; i < n - 1; i++) { // Собираем стопку, не добавляя верхнюю карточку
        cards.push(t);  // Добавляем текущую карточку
        cards.push(cards.pop());    // Перекладываем карточку из-под стопки наверх
        t = !t; // Меняем цвет текущей карточки
    }
    cards.push(1);  // Добавляем белую карточку наверх
    for(int i = 0; i < n; i++)   // Выводим полученную стопку
        cout << cards.pop();
    return 0;
}

#include <iostream>

using namespace std;

// Узел. Используется в очереди

struct node {

bool val; // Значение узла

node *next; // Указатель на следующий узел

node(int v, node *n = NULL) {

val = v;

next = n;

}

};

// Очередь. Используется как представление стопки

struct Queue {

node *head;

Queue(node *h = NULL) {

head = h;

}

void push(bool v) { // Добавить элемент в очередь

head = new node(v, head);

}

bool pop() { // Изъять элемент из очереди

if(head != NULL && (head -> next) != NULL) {

node *i = head;

node *p = i;

while(i -> next != NULL) {

p = i;

i = i -> next;

}

bool v = i -> val;

p -> next = NULL;

delete i;

return v;

} else {

node *n = head;

bool v = head -> val;

head = head -> next;

delete n;

return v;

}

};

int main() {

int n; // Количество карточек в стопке

cin >> n;

Queue cards;

bool t = n % 2; // Цвет текущей карточки. Инициализируется цветом последней выкладываемой карточки

for(int i = 0; i < n - 1; i++) { // Собираем стопку, не добавляя верхнюю карточку

cards.push(t); // Добавляем текущую карточку

cards.push(cards.pop()); // Перекладываем карточку из-под стопки наверх

t = !t; // Меняем цвет текущей карточки

}

cards.push(1); // Добавляем белую карточку наверх

for(int i = 0; i < n; i++) // Выводим полученную стопку

cout << cards.pop();

return 0;

}

Решение

Алгоритм разбора стопки можно описать следующим образом:

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

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

Пока на столе не останется одна карточка, выполняем действия:
1. добавляем карточку, выложенную на стол последней из имеющихся, на верх стопки;
2. перекладываем карточку из-под стопки наверх.
Добавляем карточку наверх.

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

Для решения задачи удобнее всего будет воспользоваться очередью, поскольку при построении стопки мы добавляем карточки только в один ее конец, а изымаем при перекладывании всегда из противоположного. Более того, в данном случае структуру можно значительно облегчить, оставив из методов только push() и pop(), причем из последнего можно за ненадобностью удалить проверку исключительной ситуации при попытке изъять карточку из пустой стопки, так как по алгоритму прямо перед изъятием всегда выполняется добавление карточки. Карточки могут быть только двух цветов, поэтому узлы очереди будут хранить значения типа bool.

Перейдем к практическому решению. Прежде всего получим количество карточек в требуемой стопке и объявим очередь:

int n;
cin >> n;
Queue cards;

int n;

cin >> n;

Queue cards;

Затем объявим переменную для цвета текущей карточки и инициализируем ее таким образом, чтобы последняя добавляемая карточка была белой. Так как при четном числе карточек в стопке последняя выкладываемая (она же — первая добавляемая) будет черной, а при нечетном — белой, то при кодировании черных и белых цветов как [latex]0[/latex] и [latex]1[/latex] соответственно инициализируется она следующим значением:

bool t = n % 2;

1	bool t = n % 2;

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

for(int i = 0; i < n - 1; i++) {
    cards.push(t);
    cards.push(cards.pop());
    t = !t;
}
cards.push(1);

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

cards.push(t);

cards.push(cards.pop());

t = !t;

}

cards.push(1);

Наконец, разбираем стопку, начиная с условного низа, и выводим ее как ответ на поставленную задачу:

for(int i = 0; i < n; i++)
    cout << cards.pop();

1 2	for(int i = 0; i < n; i++) cout << cards.pop();

Ссылки

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

Список задач по структурам данных на Algolist.manual.ru.

Related Images:

e-olymp 2820. Перемещение коня

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

Условие

Ваш друг проводит научные исследования по проблеме Конского Минимального Путешествия (КМП), которая состоит в том, чтобы найти кратчайший замкнутый тур ходов конём, который посещает каждую клетку заданного набора из [latex]n[/latex] клеток на шахматной доске ровно один раз. Он считает, что самая трудная часть задачи состоит в определении наименьшего числа ходов для перемещения коня между двумя заданными клетками и что, как только вы поможете ему решить эту подзадачу, то ему решить всю задачу будет намного легче. Вы, конечно, знаете, что дело обстоит как раз наоборот. Таким образом, вы в свою очередь решили предложить ему самому написать программу, которая решает «трудную» часть.

Ваша задача состоит в том, чтобы написать программу, которая принимает координаты двух клеток [latex]a[/latex] и [latex]b[/latex] в качестве входных данных, а затем определяет количество ходов конем кратчайшим путём из [latex]a[/latex] в [latex]b[/latex].

Входные данные будут содержать один или более тестов. Каждый тест состоит из одной строки, содержащей координаты двух клеток, разделенные одним пробелом. Координаты клетки являются двумя символами, первый из которых буква ([latex]\text{a}[/latex]–[latex]\text{h}[/latex]), задающая столбец и второй – цифра ([latex]1[/latex]–[latex]8[/latex]), задающая строку на шахматной доске.

Для каждого теста вывести одну строку следующего содержания: «To get from [latex]\text{xx}[/latex] to [latex]\text{yy}[/latex] takes [latex]n[/latex] knight moves.»

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

№	Входные данные	Выходные данные
1	1	-1
2	0.25	-0.75
3	0.1	-0.861111
4	0.01	-0.827962
5	0.0000001	-0.822467

Код

#include <iostream>
#include <string>
#include <cmath>
using namespace std;
 
// Клетка шахматной доски
struct cell {
    int a;  // Вертикальная координата (числа)
    int b;  // Горизонтальная координата (буквы)
    int d;  // Расстояние до этой клетки из начальной
}; 
 
// Узел. Используется в очереди
struct node {
    cell val;
    node *next;
    node(cell v, node *n = NULL) {
        val = v;
        next = n;
    }
};
 
// Очередь. Используется для поиска в ширину
struct Queue {
    node *head;
    Queue(node *h = NULL) {
        head = h;
    }
    void push(cell v) { // Добавить элемент в очередь
        head = new node(v, head);
    }
    cell pop() {    // Изъять элемент из очереди
        if((head -> next) != NULL) {
            node *i = head;
            node *p = i;
            while(i -> next != NULL) {
                p = i;
                i = i -> next;
            }
            cell v = i -> val;
            p -> next = NULL;
            delete i;
            return v;
        } else {
            node *n = head;
            cell v = head -> val;
            head = head -> next;
            delete n;
            return v;
        }
    }
    void clear() {  // Очистить очередь
        head = NULL;
    }
};
 
int main() {
    string r;   // Строка для запроса
    Queue q;    // Очередь
    cell current, goal, next;   // Текущая, конечная и следующая клетки
    bool visited[8][8]; // Посещенные клетки
    while(getline(cin, r)) {
        
        // Готовим текущую и конечную клетки
        current.a = (int)(r[1] - '1');
        current.b = (int)(r[0] - 'a');
        goal.a = (int)(r[4] - '1');
        goal.b = (int)(r[3] - 'a');
        current.d = 0;
        
        // Готовим массив посещенных клеток
        for(int i = 0; i < 8; i++)
            for(int j = 0; j < 8; j++)
                visited[i][j] = false;
        visited[current.a][current.b] = true;
        
        // Готовим очередь
        q.push(current);
        
        // Выполняем поиск в ширину
        while( !(current.a == goal.a && current.b == goal.b) ) {    // Пока координаты очередной клетки из очереди не совпадут с координатами конечной
            current = q.pop();  // Достаем новую клетку из очереди
            next.d = current.d + 1; // Расстояние до клеток нового слоя поиска будет на 1 больше, чем до клеток предыдущего
            // Перебираем 8 потенцальных ходов из текущей клетки комбинациями сдвигов по координатам
            for(int i = -2; i <= 2; i++) 
                if(i != 0)
                    for(int j = -(3 - abs(i)); j <= 3 - abs(i); j += 2 * (3 - abs(i))) {
                        // Присваиваем следующей клетке новые координаты
                        next.a = current.a + i;
                        next.b = current.b + j;
                        if(0 <= next.a && next.a <= 7 && 0 <= next.b && next.b <= 7 && !visited[next.a][next.b]) {  // Если следующая клетка находится в пределах доски и не была посещена
                            q.push(next);   // Добавляем ее в очередь
                            visited[next.a][next.b] = true; // Отмечаем ее посещенной
                        }
                    }
        }
        
        // Выводим ответ
        cout << "To get from " << r[0] << r[1] << " to " << r[3] << r[4] << " takes " << current.d << " knight moves." << endl;
        
        // Очищаем очередь для следующего теста
        q.clear();
    }
    return 0;
}

100

101

102

103

104

105

#include <iostream>

#include <string>

#include <cmath>

using namespace std;

// Клетка шахматной доски

struct cell {

int a; // Вертикальная координата (числа)

int b; // Горизонтальная координата (буквы)

int d; // Расстояние до этой клетки из начальной

};

// Узел. Используется в очереди

struct node {

cell val;

node *next;

node(cell v, node *n = NULL) {

val = v;

next = n;

}

};

// Очередь. Используется для поиска в ширину

struct Queue {

node *head;

Queue(node *h = NULL) {

head = h;

}

void push(cell v) { // Добавить элемент в очередь

head = new node(v, head);

}

cell pop() { // Изъять элемент из очереди

if((head -> next) != NULL) {

node *i = head;

node *p = i;

while(i -> next != NULL) {

p = i;

i = i -> next;

}

cell v = i -> val;

p -> next = NULL;

delete i;

return v;

} else {

node *n = head;

cell v = head -> val;

head = head -> next;

delete n;

return v;

}

void clear() { // Очистить очередь

head = NULL;

}

};

int main() {

string r; // Строка для запроса

Queue q; // Очередь

cell current, goal, next; // Текущая, конечная и следующая клетки

bool visited[8][8]; // Посещенные клетки

while(getline(cin, r)) {

// Готовим текущую и конечную клетки

current.a = (int)(r[1] - '1');

current.b = (int)(r[0] - 'a');

goal.a = (int)(r[4] - '1');

goal.b = (int)(r[3] - 'a');

current.d = 0;

// Готовим массив посещенных клеток

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

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

visited[i][j] = false;

visited[current.a][current.b] = true;

// Готовим очередь

q.push(current);

// Выполняем поиск в ширину

while( !(current.a == goal.a && current.b == goal.b) ) { // Пока координаты очередной клетки из очереди не совпадут с координатами конечной

current = q.pop(); // Достаем новую клетку из очереди

next.d = current.d + 1; // Расстояние до клеток нового слоя поиска будет на 1 больше, чем до клеток предыдущего

// Перебираем 8 потенцальных ходов из текущей клетки комбинациями сдвигов по координатам

for(int i = -2; i <= 2; i++)

if(i != 0)

for(int j = -(3 - abs(i)); j <= 3 - abs(i); j += 2 * (3 - abs(i))) {

// Присваиваем следующей клетке новые координаты

next.a = current.a + i;

next.b = current.b + j;

if(0 <= next.a && next.a <= 7 && 0 <= next.b && next.b <= 7 && !visited[next.a][next.b]) { // Если следующая клетка находится в пределах доски и не была посещена

q.push(next); // Добавляем ее в очередь

visited[next.a][next.b] = true; // Отмечаем ее посещенной

}

// Выводим ответ

cout << "To get from " << r[0] << r[1] << " to " << r[3] << r[4] << " takes " << current.d << " knight moves." << endl;

// Очищаем очередь для следующего теста

q.clear();

}

return 0;

}

Решение

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

Прежде всего найдем зависимость [latex]a_{n+1}[/latex] от [latex]a_n[/latex] и выведем рекуррентную формулу для очередного члена:

[latex]a_{n+1} = a_n \cdot \frac {a_{n+1}}{a_n} = a_n \cdot \frac {\frac {(-1)^{i+1}}{(i+1)^2}}{\frac {(-1)^i}{i^2}} = a_n \cdot -(\frac {i}{i+1})^2[/latex]

Для вычислений мы используем рекуррентное соотношение, поэтому до выполнения цикла, накапливающего сумму, переменным члена ряда a и суммы sum потребуется присвоить значение [latex]a_1 = \frac {(-1)^1}{1^2} = -1[/latex]:

double a = -1, sum = -1, E;

1	double a = -1, sum = -1, E;

Теперь опишем, каким образом будет работать цикл:

Цикл будет начинаться со счетчиком [latex]i = 1[/latex], который будет инкрементироваться в конце каждой итерации.
Цикл будет выполняться до тех пор, пока абсолютное значение очередного члена ряда [latex]a_i[/latex] будет не меньше, чем заданная точность [latex]\varepsilon[/latex].
В каждой итерации цикла значение суммы будет увеличиваться на [latex]a_i[/latex].

Реализуем описанный алгоритм с помощью цикла for. Чтобы сократить количество операций в теле цикла до одной, вычислять очередной член ряда будем при проверке выполнения условия продолжения. При присвоении переменной a нового значения воспользуемся кастингом (double) ; в противном случае уже второй член ряда будет обнуляться из-за умножения на дробь с целой частью [latex]0[/latex]:

for(int i = 1; abs(a *= (double)(-i*i)/(i+1)/(i+1)) >= E; i++)
    sum += a;

1 2	for(int i = 1; abs(a = (double)(-ii)/(i+1)/(i+1)) >= E; i++) sum += a;

Наконец, выведем требуемое значение — сумму ряда:

cout << sum;

1	cout << sum;

Ссылки

Условие задачи на E-Olymp;

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

Подтверждение решения на E-Olymp.

Related Images:

e-olymp 1308. Наибольшая грань подстроки

30/11/2015 by Молоканов Юрий

Условие

Гранью (border, verge, brink) [latex]br[/latex] строки [latex]S[/latex] называется любой собственный префикс этой строки, равный суффиксу [latex]S[/latex].

Строка [latex]S = abaababaabaab[/latex] имеет две грани (не пустые): [latex]ab[/latex] и [latex]abaab[/latex]. Строка [latex]S = abaabaab[/latex] также имеет две грани: [latex]ab[/latex] и [latex]abaab[/latex], но вторая грань — перекрывающаяся. Строка длины [latex]n[/latex] из повторяющегося символа, например [latex]aaaaaaaa[/latex] (или [latex]a^8[/latex]), имеет [latex]n — 1[/latex] грань. Для [latex]S = a^8[/latex] это грани: [latex]a[/latex], [latex]aa[/latex], [latex]aaa[/latex], [latex]aaaa[/latex], [latex]aaaaa[/latex], [latex]aaaaaa[/latex], [latex]aaaaaaa[/latex].

Понятие «собственный префикс» исключает грань, совпадающую с самой строкой.

Длина грани — это количество символов в ней.

Сделаем обобщение задачи. Пусть необходимо вычислить значения наибольших граней для всех подстрок [latex]S[1..i][/latex] ([latex]i = 1..n[/latex]) и сохранить их в массиве [latex]br[1..n][/latex].

Найдите наибольшее значение грани в массиве наибольших граней [latex]br[/latex] для всех подстрок [latex]S[/latex].

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

№	Входные данные	Выходные данные	Комментарий
1	abaabaab	5	abaab в исходной строке
2	abaababaabaab	6	abaaba в подстроке abaababaabaab
3	aaaaaaaa	7	aaaaaaa в исходной строке
4	YM	0	Грань отсутствует, т.к. префикс и суффикс не могут совпадать с самой строкой, а кроме Y в качестве префикса и M в качестве суффикса вариантов выбора нет
5	&#%*%#&	1	& в исходной строке
6	15015105	2	15 в подстроке 15015105
7	f0A+.f0A+.f0A.+.A0f	8	f0A+.f0A в подстроке f0A+.f0A+.f0A.+.A0f

Код

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

int main() {
    string s;
    getline(cin, s);
    int max = 0;    // Длина наибольшей грани
    for(int i = 1; i < s.length() && s.length() - i > max; i++) { 
        int j = 0;
        /*
        Перебираем различные длины префиксов (суффиксов), пока не дойдем до длины 1 и пока можем встретить грань, длиннее хранящейся.
        i - первый символ очередного суффикса
        j - длина текущей грани и первый символ очередного префикса
        */
        while(j < s.length() - i && s.at(j) == s.at(i + j))  // Накапливаем длину, пока символы префикса и суффикса совпадают
            j++;
        if(j > max)  // Если длина текущей грани больше хранящейся, обновляем максимум
            max = j;
    }
    cout << max;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

getline(cin, s);

int max = 0; // Длина наибольшей грани

for(int i = 1; i < s.length() && s.length() - i > max; i++) {

int j = 0;

i - первый символ очередного суффикса

j - длина текущей грани и первый символ очередного префикса

while(j < s.length() - i && s.at(j) == s.at(i + j)) // Накапливаем длину, пока символы префикса и суффикса совпадают

j++;

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

max = j;

}

cout << max;

return 0;

}

Решение

for(int i = 1; i < s.length() && s.length() - i > max; i++) {   
    int j = 0;
/*
Перебираем различные длины префиксов (суффиксов), пока не дойдем до длины 1 и пока можем встретить грань, длиннее хранящейся.
i - первый символ очередного суффикса
j - длина текущей грани и первый символ очередного префикса
*/

for(int i = 1; i < s.length() && s.length() - i > max; i++) {

int j = 0;

i - первый символ очередного суффикса

j - длина текущей грани и первый символ очередного префикса

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

C++

while(j < s.length() - i && s.at(j) == s.at(i + j)) j++;

1
2

while(j < s.length() - i && s.at(j) == s.at(i + j))
j++;

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

Ссылки

Условие задачи на E-Olymp;

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

Подтверждение решения на E-Olymp.

Related Images:

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

30/11/2015 by Молоканов Юрий

Условие

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

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

№	Входные данные	Выходные данные
1	Hello, world!	2
2	War is Peace. Freedom is Slavery. Ignorance is Strength.	9
3	— «4», «8», <15>; (16), {23}, [42]!?	6
4	A flock of sparrows – some of them juveniles – alighted and sang.	11
5	A mean Earth solar day is approximately 24 hours, whereas a mean Martian ‘sol’ is 24 hours, 39 minutes, and 35.244 seconds.	22
6	Lorem ipsum dolor sit amet, consectetur adipisicing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua.	19

Код

Реализация с помощью посимвольного считывания

#include <iostream>
using namespace std;

// Проверяет, принадлежит ли символ алфавиту
bool AllowedSign(char x) {
	return ((x >= '0' && x <= '9') || (x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z'))?1:0;
}

int main() {
	char x;
	int count = 0;	// Счетчик слов в предложении
	bool wordBegin = true;	// Будет ли следующий считанный символ, принадлежащий алфавиту, началом нового слова
	while(EOF != (x = getchar())) { 
		if(AllowedSign(x) && wordBegin) {	// Если текущий символ принадлежит алфавиту и ожидается новое слово
			count++;
			wordBegin = false;	// Указываем, что последующие находимые символы алфавита не будут началом слова
		} else if(x == ' ')	// Если текущий символ - пробел
			wordBegin = true;	// Указываем для следующей итерации, что текущее слово "закончилось" и ожидается новое
	}
	cout << count;
	return 0;
}

#include <iostream>

using namespace std;

// Проверяет, принадлежит ли символ алфавиту

bool AllowedSign(char x) {

return ((x >= '0' && x <= '9') || (x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z'))?1:0;

}

int main() {

char x;

int count = 0; // Счетчик слов в предложении

bool wordBegin = true; // Будет ли следующий считанный символ, принадлежащий алфавиту, началом нового слова

while(EOF != (x = getchar())) {

if(AllowedSign(x) && wordBegin) { // Если текущий символ принадлежит алфавиту и ожидается новое слово

count++;

wordBegin = false; // Указываем, что последующие находимые символы алфавита не будут началом слова

} else if(x == ' ') // Если текущий символ - пробел

wordBegin = true; // Указываем для следующей итерации, что текущее слово "закончилось" и ожидается новое

}

cout << count;

return 0;

}

Реализация с помощью строк c-string

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

// Проверяет, принадлежит ли символ алфавиту
bool AllowedSign(char x) {
	return ((x >= '0' && x <= '9') || (x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z'))?1:0;
}

int main() {
	const int size = 500;
	int count = 0;	// Счетчик слов в предложении
	char word[size];
	while(cin >> word) {
		bool isWord = false;	// По умолчанию считаем, что считанная последовательность символов словом не является
		for(int i = 0; i < strlen(word) && !isWord; i++)	// Проверяем символы массива, пока не дойдем до его конца или не убедимся, что считанная последовательность ялвяется словом
			if(AllowedSign(word[i])) {	// Если текущий символ принадлежит алфавиту
				count++;
				isWord = true;	// Указываем, что последовательность является словом
			}
	}
	cout << count;
	return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

// Проверяет, принадлежит ли символ алфавиту

bool AllowedSign(char x) {

return ((x >= '0' && x <= '9') || (x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z'))?1:0;

}

int main() {

const int size = 500;

int count = 0; // Счетчик слов в предложении

char word[size];

while(cin >> word) {

bool isWord = false; // По умолчанию считаем, что считанная последовательность символов словом не является

for(int i = 0; i < strlen(word) && !isWord; i++) // Проверяем символы массива, пока не дойдем до его конца или не убедимся, что считанная последовательность ялвяется словом

if(AllowedSign(word[i])) { // Если текущий символ принадлежит алфавиту

count++;

isWord = true; // Указываем, что последовательность является словом

}

cout << count;

return 0;

}

Решение

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

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

Теперь перейдем к практическому решению задачи.

Реализация с помощью посимвольного считывания

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

Для решения задачи этим методом воспользуемся функцией bool AllowedSign(char x), возвращающей значение true, если переданный ей символ принадлежит алфавиту неизвестного языка, и объявим логическую переменную wordBegin, определяющую, будет ли следующий считанный символ алфавита началом нового слова, и присвоим ей до начала выполнения цикла посимвольного считывания значение true. Сам цикл будет выполняться до тех пор, пока не будет прочитан весь входной поток:

bool wordBegin = true;
while(EOF != (x = getchar()))

1 2	bool wordBegin = true; while(EOF != (x = getchar()))

При этом на каждой его итерации будут возможны, в зависимости от текущего символа и значения переменной wordBegin, следующие два варианта действий. Если считанный символ принадлежит алфавиту и при этом ожидается новое слово ( wordBegin = true), инкрементируем счетчик слов count и присваиваем wordBegin значение false. С этого момента и до тех пор, пока не будет достигнут конец слова, все последующие считываемые символы алфавита не будут влиять на счетчик:

if(AllowedSign(x) && wordBegin) {
	count++;
	wordBegin = false;
}

if(AllowedSign(x) && wordBegin) {

count++;

wordBegin = false;

}

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

else if(x == ' ')
	wordBegin = true;

1 2	else if(x == ' ') wordBegin = true;

Как видно, неалфавитные символы (знаки препинания) игнорируются и на подсчет слов никак не влияют. Наконец, после того, как будет прочитан весь входной поток, выводится значение счетчика слов count, что и есть ответом на поставленный вопрос задачи:

cout << count;

1	cout << count;

Реализация с помощью строк c-string

Как и в предыдущем варианте решения, воспользуемся функцией AllowedSign, определяющей принадлежность символа алфавиту, а также объявим переменную bool isWord, отвечающую за то, является ли проверяемая последовательность символов словом неизвестного языка. Тогда суть метода будет заключаться в считывании из входного потока последовательностей символов и проверке того, являются ли они словами. В основе метода лежит цикл, считывающий из входного потока «потенциальные слова» до тех пор, пока это возможно:

while(cin >> word)

1	while(cin >> word)

После считывания последовательности символов присваиваем переменной isWord значение false, изначально считая, что эта последовательность словом не является:

bool isWord = false;

1	bool isWord = false;

Затем поочередно проверяем символы последовательности до тех пор, пока isWord сохраняет значение false, или пока не дойдем до конца этой последовательности. Если в процессе проверки окажется, что очередной проверяемый символ принадлежит алфавиту, инкрементируем счетчик слов count и указываем, что последовательность является словом, переходя таким образом к проверке следующего «потенциального слова» в предложении, если таковые имеются:

for(int i = 0; i < strlen(word) && !isWord; i++)
	if(AllowedSign(word[i])) {
		count++;
		isWord = true;
	}

for(int i = 0; i < strlen(word) && !isWord; i++)

if(AllowedSign(word[i])) {

count++;

isWord = true;

}

Наконец, как и в первом случае, выводим количество найденных слов:

cout << count;

1	cout << count;

Ссылки

Условие задачи на E-Olymp;

Коды программ на Ideone.com: посимвольное считывание, строки c-string;

Подтверждение решения на E-Olymp.

Related Images:

MLoop22

31/10/2015 by Молоканов Юрий

Условие

Вычислите с точностью [latex]\varepsilon[/latex] сумму ряда [latex]\sum_{i=1}^{\infty} \frac {(-1)^i}{i^2}[/latex].

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

№	Входные данные	Выходные данные
1	1	-1
2	0.25	-0.75
3	0.1	-0.861111
4	0.01	-0.827962
5	0.0000001	-0.822467

Код

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

int main() {
	double a = -1, sum = -1, E;	// Объявляем переменные для члена ряда, суммы и точности, присваиваем первым двум значение первого члена ряда 
	cin >> E;
	for(int i = 1; abs(a *= (double)(-i*i)/(i+1)/(i+1)) >= E; i++)	// Повторяем цикл, пока значение очередного члена ряда по модулю не меньше заданной точности
		sum += a;	// Накапливаем сумму
	cout << sum;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double a = -1, sum = -1, E; // Объявляем переменные для члена ряда, суммы и точности, присваиваем первым двум значение первого члена ряда

cin >> E;

for(int i = 1; abs(a *= (double)(-i*i)/(i+1)/(i+1)) >= E; i++) // Повторяем цикл, пока значение очередного члена ряда по модулю не меньше заданной точности

sum += a; // Накапливаем сумму

cout << sum;

return 0;

}

Решение

[latex]a_{n+1} = a_n \cdot \frac {a_{n+1}}{a_n} = a_n \cdot \frac {\frac {(-1)^{i+1}}{(i+1)^2}}{\frac {(-1)^i}{i^2}} = a_n \cdot -(\frac {i}{i+1})^2[/latex]

double a = -1, sum = -1, E;

1	double a = -1, sum = -1, E;

Теперь опишем, каким образом будет работать цикл:

Цикл будет начинаться со счетчиком [latex]i = 1[/latex], который будет инкрементироваться в конце каждой итерации.
Цикл будет выполняться до тех пор, пока абсолютное значение очередного члена ряда [latex]a_i[/latex] будет не меньше, чем заданная точность [latex]\varepsilon[/latex].
В каждой итерации цикла значение суммы будет увеличиваться на [latex]a_i[/latex].

for(int i = 1; abs(a *= (double)(-i*i)/(i+1)/(i+1)) >= E; i++)
	sum += a;

1 2	for(int i = 1; abs(a = (double)(-ii)/(i+1)/(i+1)) >= E; i++) sum += a;

Наконец, выведем требуемое значение — сумму ряда:

cout << sum;

1	cout << sum;

Ссылки

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

Список задач на циклы.

Related Images:

MLoops22

31/10/2015 by Молоканов Юрий

Условие

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

1491625364964811001211441
6919622525628932436140044
1484529576625676729784841
9009611024108911561225129

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

№	Входные данные	Выходные данные
1	1 1	1
2	7 1	1491625
3	10 2	1491625364 9648110012
4	1 3	1 4 9
5	1 6	1 4 9 1 6 2
6	5 5	14916 25364 96481 10012 11441
7	25 4	1491625364964811001211441 6919622525628932436140044 1484529576625676729784841 9009611024108911561225129

Код

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

// Возвращает длину числа
int GetLength(int a) {
	return (a==0?1:log10(a)+1);
}

// Возвращает левую часть числа до заданной цифры включительно
int LeftPart(int a, int n) {
	return a/pow(10, GetLength(a) - n);
}

// Возвращает правую часть числа после заданной цифры
int RightPart(int a, int n) {
	int p = pow(10, GetLength(a) - n);
	return a%p;
}

int main() {
	int n, m, i = 0, toPrint; // Столбцы, строки, счетчик очередного числа для возведения в квадрат, текущее значение для печати
	bool haveRest = false;	// Есть ли часть числа, "отрезанная" после переноса строки
	cin >> n >> m;
	int columnsLeft = n;	// Присваиваем переменной для оставшихся свободных столбцов значения общего количества столбцов
	while(m > 0) {
		if(columnsLeft == 0) {	// Если не осталось свободных столбцов
			m--;
			if(m > 0)
				cout << endl;
			columnsLeft = n;	// Восстанавливаем число оставшихся столбцов
			haveRest = false;	// "Отрезанной" части числа нет
		} else {	// Если есть свободные столбцы
			i = (haveRest?i:++i);
			toPrint = (haveRest?toPrint:i*i);	// Если "отрезанной" части числа нет, записываем в toPrint квадрат очередного числа
			if(GetLength(toPrint) <= columnsLeft) {	// Если хватает свободных столбцов для печати числа в toPrint
				cout << toPrint;
				columnsLeft -= GetLength(toPrint);	// Обновляем количество свободных столбцов
				haveRest = false;	// "Отрезанной" части числа нет
			} else {	// Если свободных столбцов не хватает для печати числа в toPrint целиком
				cout << LeftPart(toPrint, columnsLeft);	// Печатаем левую часть числа в toPrint, чтобы заполнить все оставшиеся свободные столбцы
				toPrint = RightPart(toPrint, columnsLeft);	// Присваиваем toPrint значение его ненапечатанной части
				m--;
				if(m > 0)
					cout << endl;
				columnsLeft = n;	// Восстанавливаем число оставшихся столбцов
				haveRest = true;	// "Отрезанная" часть числа есть
			}
		}
	}
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

// Возвращает длину числа

int GetLength(int a) {

return (a==0?1:log10(a)+1);

}

// Возвращает левую часть числа до заданной цифры включительно

int LeftPart(int a, int n) {

return a/pow(10, GetLength(a) - n);

}

// Возвращает правую часть числа после заданной цифры

int RightPart(int a, int n) {

int p = pow(10, GetLength(a) - n);

return a%p;

}

int main() {

int n, m, i = 0, toPrint; // Столбцы, строки, счетчик очередного числа для возведения в квадрат, текущее значение для печати

bool haveRest = false; // Есть ли часть числа, "отрезанная" после переноса строки

cin >> n >> m;

int columnsLeft = n; // Присваиваем переменной для оставшихся свободных столбцов значения общего количества столбцов

while(m > 0) {

if(columnsLeft == 0) { // Если не осталось свободных столбцов

m--;

if(m > 0)

cout << endl;

columnsLeft = n; // Восстанавливаем число оставшихся столбцов

haveRest = false; // "Отрезанной" части числа нет

} else { // Если есть свободные столбцы

i = (haveRest?i:++i);

toPrint = (haveRest?toPrint:i*i); // Если "отрезанной" части числа нет, записываем в toPrint квадрат очередного числа

if(GetLength(toPrint) <= columnsLeft) { // Если хватает свободных столбцов для печати числа в toPrint

cout << toPrint;

columnsLeft -= GetLength(toPrint); // Обновляем количество свободных столбцов

haveRest = false; // "Отрезанной" части числа нет

} else { // Если свободных столбцов не хватает для печати числа в toPrint целиком

cout << LeftPart(toPrint, columnsLeft); // Печатаем левую часть числа в toPrint, чтобы заполнить все оставшиеся свободные столбцы

toPrint = RightPart(toPrint, columnsLeft); // Присваиваем toPrint значение его ненапечатанной части

m--;

if(m > 0)

cout << endl;

columnsLeft = n; // Восстанавливаем число оставшихся столбцов

haveRest = true; // "Отрезанная" часть числа есть

}

return 0;

}

Решение

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

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

Опираясь на вышеперечисленное, опишем алгоритм работы цикла построения таблицы более подробно:

В первую очередь проверяется условие продолжения цикла. Цикл будет выполняться до тех пор, пока количество полностью напечатанных строк (то есть строк, длина которых равна заданному количеству столбцов) будет меньше требуемого количества строк в готовой таблице.
Определяется количество свободных столбцов в текущей строке. Если оно равно нулю, выполняется перевод на новую строку, количество полностью напечатанных строк увеличивается на [latex]1[/latex] и итерация цикла завершается.
Определяется последовательность цифр, печатаемая в текущей итерации цикла. Если с прошлой итерации в результате переноса строки осталась «отрезанная» часть числа, то в этой итерации будет выводиться она; иначе же будет выводиться квадрат очередного натурального числа.
Проверяется, сможет ли число, сформированное на предыдущем шаге, полностью уместиться в текущей строке. Если его длина меньше или равна количеству свободных столбцов, то оно выводится в поток и итерация цикла завершается; в противном случае выводится та его часть, которая может уместиться в строке, ненапечатанная часть сохраняется и будет выведена в следующей итерации (если выполнится условие продолжения цикла), количество полностью напечатанных строк увеличивается на [latex]1[/latex] и итерация цикла также завершается.

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

int i для хранения очередного натурального числа, квадрат которого нужно вычислить;
int toPrint для хранения числа, которое нужно будет выводить в очередной итерации цикла;
int columnsLeft для хранения числа свободных столбцов в текущей строке;
bool haveRest для обозначения наличия или отсутствия «отрезанной» в результате переноса строки части числа;
функция int GetLength(int a), возвращающая длину числа a;
функция int LeftPart(int a, int n), возвращающая левую часть числа a до n-той цифры включительно;
функция int RightPart(int a, int n), возвращающая правую часть числа a после n-той цифры.

До начала выполнения цикла присвоим переменной haveRest значение false («отрезанные» части чисел могут появится не раньше второй итерации), а переменной columnsLeft — считанное значение количества столбцов в таблице n.

Составим код цикла, следуя описанному выше алгоритму построения таблицы. Условием продолжения цикла будет наличие не напечатанных до конца строк m (в дальнейшем будем декрементировать m всякий раз при переносе строки):

while(m > 0)

1	while(m > 0)

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

if(columnsLeft == 0) {	// Если не осталось свободных столбцов
	m--;
	if(m > 0)
		cout << endl;
	columnsLeft = n;	// Восстанавливаем число оставшихся столбцов
	haveRest = false;	// "Отрезанной" части числа нет
}

if(columnsLeft == 0) { // Если не осталось свободных столбцов

m--;

if(m > 0)

cout << endl;

columnsLeft = n; // Восстанавливаем число оставшихся столбцов

haveRest = false; // "Отрезанной" части числа нет

}

Если же свободные столбцы есть, определяем число, которое будет печататься в этой итерации. В случае, если «отрезанная» часть отсутствует, переменной toPrint присваиваем значение квадрата очередного натурального числа, иначе оставляем ее без изменений ( toPrint получает значение ненапечатанной части числа в конце цикла, если таковая имеется):

i = (haveRest?i:++i);
toPrint = (haveRest?toPrint:i*i);	// Если "отрезанной" части числа нет, записываем в toPrint квадрат очередного числа

1 2	i = (haveRest?i:++i); toPrint = (haveRest?toPrint:i*i); // Если "отрезанной" части числа нет, записываем в toPrint квадрат очередного числа

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

if(GetLength(toPrint) <= columnsLeft) {	// Если хватает свободных столбцов для печати числа в toPrint
	cout << toPrint;
	columnsLeft -= GetLength(toPrint);	// Обновляем количество свободных столбцов
	haveRest = false;	// "Отрезанной" части числа нет
}

if(GetLength(toPrint) <= columnsLeft) { // Если хватает свободных столбцов для печати числа в toPrint

cout << toPrint;

columnsLeft -= GetLength(toPrint); // Обновляем количество свободных столбцов

haveRest = false; // "Отрезанной" части числа нет

}

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

else {	// Если свободных столбцов не хватает для печати числа в toPrint целиком
	cout << LeftPart(toPrint, columnsLeft);	// Печатаем левую часть числа в toPrint, чтобы заполнить все оставшиеся свободные столбцы
	toPrint = RightPart(toPrint, columnsLeft);	// Присваиваем toPrint значение его ненапечатанной части
	m--;
	if(m > 0)
		cout << endl;
	columnsLeft = n;	// Восстанавливаем число оставшихся столбцов
	haveRest = true;	// "Отрезанная" часть числа есть
}

else { // Если свободных столбцов не хватает для печати числа в toPrint целиком

cout << LeftPart(toPrint, columnsLeft); // Печатаем левую часть числа в toPrint, чтобы заполнить все оставшиеся свободные столбцы

toPrint = RightPart(toPrint, columnsLeft); // Присваиваем toPrint значение его ненапечатанной части

m--;

if(m > 0)

cout << endl;

columnsLeft = n; // Восстанавливаем число оставшихся столбцов

haveRest = true; // "Отрезанная" часть числа есть

}

Ссылки

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

Последовательность в OEIS;

Список задач на циклы.

Related Images:

e-olymp 388. Превращение

30/09/2015 by Молоканов Юрий

Условие

Возьмем какое-нибудь натуральное число [latex]N[/latex]. Будем изменять его следующим образом: если число четное, то разделим его на [latex]2[/latex], если нечетное, прибавим [latex]1[/latex]. После нескольких таких изменений мы всегда получаем число [latex]1[/latex]. Например, из числа [latex]11[/latex] получается число [latex]12[/latex], затем [latex]6[/latex], [latex]3[/latex], [latex]4[/latex], [latex]2[/latex] и, наконец, [latex]1[/latex]. Таким образом, для получения [latex]1[/latex] из [latex]11[/latex] нужно проделать [latex]6[/latex] изменений.

Напишите программу, которая считывает натуральное число и выводит количество изменений данного числа до получения [latex]1[/latex].

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

№	Входные данные	Выходные данные
1	1	0
2	11	6
3	65	13
4	1024	10

Код

#include <iostream>
using namespace std;

int main() {
	int n, i;	// n для числа, i для счета преобразований
	cin >> n;
	for (i = 0; n > 1; i++) n = (n%2>0?n+1:n/2);	// Преобразовываем n, пока не получим 1
	cout << i;	// Выводим значение счетчика
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, i; // n для числа, i для счета преобразований

cin >> n;

for (i = 0; n > 1; i++) n = (n%2>0?n+1:n/2); // Преобразовываем n, пока не получим 1

cout << i; // Выводим значение счетчика

return 0;

}

Решение

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

#include <iostream>
using namespace std;

int main() {
	int n, i;	// n для числа, i для счета преобразований

#include <iostream>

using namespace std;

int main() {

int n, i; // n для числа, i для счета преобразований

Теперь опишем, каким образом будет работать цикл:

Цикл начинается со значением счетчика 0, так как возможны случаи, когда операций над [latex]n[/latex] вообще не нужно будет производить (конкретно — при [latex]n=1[/latex]).
Поскольку нам гарантируют, что входное число [latex]n[/latex] — натуральное, то цикл будет работать до тех пор, пока [latex]n>1[/latex].
После каждой итерации значение счетчика будет увеличено на [latex]1[/latex].
Тело цикла состоит из единственного оператора присваивания переменной с числом [latex]n[/latex] нового значения. [latex]n[/latex] может быть преобразовано двумя способами, и для определения нужного используется проверка на его четность:
- если [latex]n[/latex] — нечетное, то значение [latex]n[/latex] увеличивается на [latex]1[/latex];
- в противном случае [latex]n[/latex] делится на [latex]2[/latex].

Реализуем описанный алгоритм, после которого отправляем на печать значение счетчика i:

for (i = 0; n > 1; i++) n = (n%2>0?n+1:n/2);
cout << i;

1 2	for (i = 0; n > 1; i++) n = (n%2>0?n+1:n/2); cout << i;

Ссылки

Условие задачи на E-Olymp;

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

Подтверждение решения на E-Olymp.

Related Images:

Mif 17.16

30/09/2015 by Молоканов Юрий

Условие

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

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

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

№	Входные данные	Выходные данные
1	0 0	Yes
2	-6 0	Yes
3	5.0 -2.0	Yes
4	-3.33 -5	No
5	0.12345 0.54321	No

Код

#include <iostream>
using namespace std;

int main() {
    double x, y;	// Координаты точки
    cin >> x >> y;
    cout << ((x*x+y*y<=36&&(x<=0||y<=0))?"Yes":"No");	// Тернарная операция для определения принадлежности точки
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double x, y; // Координаты точки

cin >> x >> y;

cout << ((x*x+y*y<=36&&(x<=0||y<=0))?"Yes":"No"); // Тернарная операция для определения принадлежности точки

return 0;

}

Решение

В основе заданной фигуры лежит круг с радиусом [latex]6[/latex] и центром в начале системы координат [latex](0, 0)[/latex], из которого исключена первая четверть. Таким образом, нам нужно удостовериться, что положение заданной точки одновременно удовлетворяет следующим условиям:

точка расположена в пределах круга, то есть сумма квадратов координат [latex]x^2+y^2[/latex] меньше или равна квадрату радиуса [latex]6^2=36[/latex];
хотя бы одна из координат точки [latex](x, y)[/latex] не превышает значения [latex]0[/latex] (другими словами, точка не лежит в первой четверти).

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

cout << ((x*x+y*y<=36&&(x<=0||y<=0))?"Yes":"No");

1	cout << ((xx+yy<=36&&(x<=0\|\|y<=0))?"Yes":"No");

Ссылки

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

Уравнение окружности;

Список задач на ветвления.

Related Images:

Ю2.29

30/09/2015 by Молоканов Юрий

Условие

Для заданного [latex]0 \le n \le 200[/latex], рассматриваемого как возраст человека, вывести фразу вида: «Мне 21 год», «Мне 32 года», «Мне 12 лет».

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

№	Входные данные	Выходные данные
1	0	Мне 0 лет
2	1	Мне 1 год
3	14	Мне 14 лет
4	24	Мне 24 года
5	111	Мне 111 лет
6	151	Мне 151 год
7	200	Мне 200 лет

Код

#include <iostream>
using namespace std;

int main() {
	int n;	// Переменная для возраста
	cin >> n;
	cout << "Мне " << n << (n%10>4||n%10<1||n%100/10==1?" лет":(n%10>1?" года":" год"));	// Тернарные операции для определения нужной формы слова "год"
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n; // Переменная для возраста

cin >> n;

cout << "Мне " << n << (n%10>4||n%10<1||n%100/10==1?" лет":(n%10>1?" года":" год")); // Тернарные операции для определения нужной формы слова "год"

return 0;

}

Решение

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

В первой сотне лет:

в первом десятке лет, до 5 лет употребляется слово «год»: 1 год, 2 года, 3 года, 4 года, а от 5 лет до 10 лет употребляется слово «лет»: 5 лет, …, 10 лет;

во втором десятке лет употребляется слово «лет»: 11 лет, 12 лет, …, 20 лет;

от третьего до 9-го десятка лет, в первых четырёх годах десятка употребляется слово «год»: 21 год, 22 года, 23 года, 24 года, а в остальных годах десятка употребляется слово «лет»: 25 лет, …, 29 лет, 30 лет.

В следующих сотнях лет повторяется порядок первой сотни лет.

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

Если число заканчивается на [latex]0[/latex] или цифру, превышающую [latex]4[/latex], или если вторая с конца цифра этого числа — [latex]1[/latex], то выводим слово «лет» и завершаем программу; иначе переходим ко второй проверке.
Если последняя цифра числа превышает [latex]1[/latex] (то есть является одной из следующих: [latex]2[/latex], [latex]3[/latex], [latex]4[/latex]), то выводим слово «года»; иначе выводим слово «год».

Наконец, реализуем вышеописанный алгоритм в виде двух вложенных одна в другую тернарных операций:

cout << "Мне " << n << (n%10>4||n%10<1||n%100/10==1?" лет":(n%10>1?" года":" год"));

1	cout << "Мне " << n << (n%10>4\|\|n%10<1\|\|n%100/10==1?" лет":(n%10>1?" года":" год"));

Ссылки

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

Правила употребления слова «год».

Related Images:

ML23

24/09/2015 by Молоканов Юрий

Условие

Найти длины биссектрис [latex]a_1[/latex], [latex]b_1[/latex], [latex]c_1[/latex] треугольника, если известны длины противоположных сторон [latex]a[/latex], [latex]b[/latex], [latex]c[/latex].

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

№	Входные данные	Выходные данные
1	6, 7, 9	7.35803, 6.49923, 4.67652
2	3.5, 4.5, 5.5	4.66027, 3.79967, 2.88195
3	100000, 100000, 100000	86602.5, 86602.5, 86602.5
4	1, 1.118034, 1.118034	1, 0.898056, 0.898056

Код

#include <iostream>
#include <cmath>
using namespace std;
 
double getL(double c, double a, double b) {    // Возвращает длину биссектрисы к стороне A при сторонах A, B, C
    double s = a + b;
    return sqrt(a * b * (s + c) * (s - c))/s;  // Формула длины биссектрисы через три стороны
}
 
int main() {
    double a, b, c;
    cin >> a >> b >> c;
    cout << "Длины биссектрис к сторонам A, B и C равны " << getL(a, b, c) << ", " << getL(b, a, c) << " и " << getL(c, a, b) << ".";
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

double getL(double c, double a, double b) { // Возвращает длину биссектрисы к стороне A при сторонах A, B, C

double s = a + b;

return sqrt(a * b * (s + c) * (s - c))/s; // Формула длины биссектрисы через три стороны

}

int main() {

double a, b, c;

cin >> a >> b >> c;

cout << "Длины биссектрис к сторонам A, B и C равны " << getL(a, b, c) << ", " << getL(b, a, c) << " и " << getL(c, a, b) << ".";

return 0;

}

Решение

Для вычисления длины биссектрисы через три стороны произвольного треугольника воспользуемся формулой [latex]l_c = \frac{\sqrt{ab(a+b+c)(a+b-c)}}{a+b}[/latex], где:

[latex]l_c[/latex] — длина биссектрисы, проведенной к стороне [latex]c[/latex];
[latex]a[/latex], [latex]b[/latex], [latex]c[/latex] — стороны треугольника.

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

double getL(double c, double a, double b) {
	return sqrt(a * b * (a + b + c) * (a + b - c))/(a + b);
}

double getL(double c, double a, double b) {

return sqrt(a * b * (a + b + c) * (a + b - c))/(a + b);

}

Можно заметить, что сумма [latex]a+b[/latex] встречается в формуле три раза. Для лучшей читаемости и компактности кода заменим a + b на s :

double getL(double c, double a, double b) {
    double s = a + b;
    return sqrt(a * b * (s + c) * (s - c))/s;
}

double getL(double c, double a, double b) {

double s = a + b;

return sqrt(a * b * (s + c) * (s - c))/s;

}

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

cout << "Длины биссектрис к сторонам A, B и C равны " << getL(a, b, c) << ", " << getL(b, a, c) << " и " << getL(c, a, b) << ".";

1	cout << "Длины биссектрис к сторонам A, B и C равны " << getL(a, b, c) << ", " << getL(b, a, c) << " и " << getL(c, a, b) << ".";

Ссылки

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

Формулы длины биссектрис в треугольнике;

Список задач на линейные вычисления.

Related Images:

e-olymp 125. Олимпиада

14/09/2015 by Молоканов Юрий

Условие

Олимпиада началась в [latex]h_1[/latex] часов [latex]m_1[/latex] минут [latex]s_1[/latex] секунд, а закончилась в эти же календарные сутки в [latex]h_2[/latex] часов [latex]m_2[/latex] минут [latex]s_2[/latex] секунд. Сколько времени (час мин сек) проходила олимпиада?

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

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

[latex]0 \le h_1 \le h_2 \le 23[/latex], [latex]0 \le m_1, m_2 \le 59[/latex], [latex]0 \le s_1, s_2 \le 59[/latex].

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

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

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

№	Входные данные	Выходные данные
1	9 30 0 12 45 30	3 15 30
2	9 30 30 12 45 0	3 14 30
3	9 45 0 12 30 30	2 45 30
4	9 45 30 12 30 0	2 44 30

Код

#include <iostream>
using namespace std;
 
int main() {
    int h1, m1, s1, h2, m2, s2;
    cin >> h1 >> m1 >> s1 >> h2 >> m2 >> s2;
    if (s2 < s1) {
         s2 += 60;
         m2 -= 1;
    }
    if (m2 < m1) {
         m2 += 60;
         h2 -= 1;
    }
    cout << h2 - h1 << " " << m2 - m1 << " " << s2 - s1;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int h1, m1, s1, h2, m2, s2;

cin >> h1 >> m1 >> s1 >> h2 >> m2 >> s2;

if (s2 < s1) {

s2 += 60;

m2 -= 1;

}

if (m2 < m1) {

m2 += 60;

h2 -= 1;

}

cout << h2 - h1 << " " << m2 - m1 << " " << s2 - s1;

return 0;

}

Решение

Очевидным решением задачи является вывод через пропуск разниц [latex]h_2 — h_1[/latex], [latex]m_2 — m_1[/latex] и [latex]s_2 — s_1[/latex]. Однако если часы, минуты или секунды конца олимпиады будут меньше соответсвующих значений ее начала, то результат разницы разницы будет отрицательным. Чтобы этого избежать, существуют два if-блока, которые увеличивают количество секунд на [latex]60[/latex] и уменьшают количество минут на [latex]1[/latex], а так же выполняют аналогичные действия с минутами и часами в том случае, если входное количество минут или секунд начала олимпиады будут превышать соответственно минуты и секунды конца. После этого выводятся разницы, указанные в начале решения, которые теперь будут отображать реальную продолжительность олимпиады и гарантированно будут неотрицательными.

Ссылки

Условие задачи на E-Olymp;

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

Подтверждение решения на E-Olymp.