A719a

14/05/2015 by Ілларіонова Марія Валеріївна

Симметричные квадратные матрицы [latex]A[/latex] и [latex]B[/latex] порядка [latex]n[/latex] заданы последовательностями из [latex]n\left(n+1 \right)/2[/latex] чисел, аналогично правым треугольным матрицам. Получить матрицу [latex]AB[/latex].

[latex]n[/latex]	[latex]A[/latex]	[latex]B[/latex]	[latex]AB[/latex]
3	0 1 2 0 2 1	0 1 3 0 2 1	7 4 4 6 5 5 5 4 11
2	0 1 0	1 0 1	0 1 1 0
3	1 2 3 4 5 6	1 0 0 4 2 2	1 14 10 2 26 18 3 32 22
4	1 1 1 1 2 2 2 3 3 4	6 6 6 6 5 5 5 3 2 1	24 21 16 14 42 36 26 22 54 46 31 25 60 51 33 26

Тесты проверены на этом сайте.

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

#include <iostream>
using namespace std;

int A[100][100];
int B[100][100];
int C[100][100];

int main() {
    int n;
    cin >> n;
    int i=0, j=0, t=0;
    for (i=0; i<n; i++) {
        for (j=i; j<n; j++) {
            cin >> t;
            A[i][j]=A[j][i]=t;
        }
    }
    for (i=0; i<n; i++) {
        for (j=i; j<n; j++) {
            cin >> t;
            B[i][j]=B[j][i]=t;
        }
    }
    for (i=0; i<n; i++) {
        for (j=0; j<n; j++) {
            for (int k=0; k<n; k++) {
                C[i][j]+=A[i][k]*B[k][j];
            }
        }
    }
    for (i=0; i<n; i++) {
        for (j=0; j<n; j++) {
            cout << C[i][j] << "\t";
        }
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int A[100][100];

int B[100][100];

int C[100][100];

int main() {

int n;

cin >> n;

int i=0, j=0, t=0;

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

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

cin >> t;

A[i][j]=A[j][i]=t;

}

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

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

cin >> t;

B[i][j]=B[j][i]=t;

}

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

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

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

C[i][j]+=A[i][k]*B[k][j];

}

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

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

cout << C[i][j] << "\t";

}

cout << endl;

}

return 0;

}

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

Изначально мы считываем последовательность из [latex]n\left(n+1 \right)[/latex] для двух матриц (чтобы они были симметричекими, цикл по столбцам запускается с позиции текущей строки, а затем введённое значение копируется относительно главной диагонали).

Пусть [latex]C=\begin{Vmatrix}c_{ij}\end{Vmatrix} \in M_{m\times n}\left( \mathbb{R}\right) \left(i=1,2,\ldots,m; j=1,2,\ldots,n \right)[/latex].

Умножение матриц происходит по формуле [latex]c_{ij}=\sum_{r=1}^{n}{a_{ir}b_{rj}}\left(i=1,2,\ldots,m; j=1,2,\ldots,n \right)[/latex].

Related Images:

e-olimp 4856. Кратчайший путь

24/04/2015 by Ілларіонова Марія Валеріївна

Задача e-olimp.com №4856. Ссылка на засчитанное решение.

Дан неориентированный взвешенный граф. Найти кратчайший путь между двумя данными вершинами.

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

Первая строка содержит натуральные числа [latex]n[/latex] и [latex]m[/latex] [latex]\left(n\leq 2000, m\leq 50000 \right)[/latex] — количество вершин и рёбер графа. Вторая строка содержит натуральные числа [latex]s[/latex] и [latex]f[/latex] [latex]\left(1\leq s, f\leq n, s\neq f \right)[/latex] — номера вершин, длину пути между которыми требуется найти. Следующие [latex]m[/latex] строк содержат по три числа [latex]b_{i}[/latex], [latex]e_{i}[/latex] и [latex]w_{i}[/latex]- номера концов [latex]i[/latex]-ого ребра и его вес соответственно [latex]\left(1 \leq b_{i}, e_{i}\leq n, 0\leq w_{i}\leq 100000\right)[/latex].

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

Первая строка должна содержать одно число — длину минимального пути между вершинами [latex]s[/latex] и [latex]f[/latex]. Во второй строке через пробел выведите вершины на кратчайшем пути из [latex]s[/latex] в [latex]f[/latex] в порядке обхода. Если путь из [latex]s[/latex] в [latex]f[/latex] не существует, выведите -1.

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

#include <iostream> 
#include <vector>
#include <set>
#include <utility>
using namespace std;
#define INF 1000000000000
#define MAX 100000

vector <pair <int, long long> > G[MAX];
vector <int> path;
vector <int> ans;
set <pair <long long, int> > q;
long long length[MAX];
int parent[MAX];

int main() {
    ios::sync_with_stdio(false);
    int n, m, a, b;
    cin >> n >> m >> a >> b;
    a--, b--; // начнём отсчёт с 0, для удобства
    for (int i=0; i<m; i++) {
        int from, to, len;
        cin >> from >> to >> len;
        from--, to--;
        G[to].push_back(make_pair(from, len));
        G[from].push_back(make_pair (to, len));
    }
    for (int i=0; i<n; i++) length[i]=INF;
    length[a]=0;
    q.insert (make_pair (length[a], a));
    while (!q.empty()) { // будем выполнять, пока наша очередь не пуста
        int v = q.begin()->second;
        q.erase (q.begin());
        for (int i=0; i<G[v].size(); i++) {
            int to=G[v][i].first, len=G[v][i].second;
            if (length[v]+len<length[to]) { // изначально она бесконечно большая, поэтому сразу меньше, а если будет оказываться больше, то просто не будем менять
                   q.erase (make_pair (length[to], to)); // мы убираем нашу бесконечность или больший путь вместе со следующей вершиной, а вместо них
                   length[to]=length[v]+len; // ставим новую длину
                   parent[to]=v; // и записываем предка
                   q.insert (make_pair (length[to], to));
            }
        }
    }
    if (length[b]==INF) { // если последняя вершина оказалась бесконечностью, значит, мы её не достигли
        cout << "-1"; 
        return 0;
    } 
    cout << length[b] << endl;
    int c=b;
    while (c!=a) {
        ans.push_back(c+1); // так как начинали с 1, то увеличиваем
        c=parent[c];
    }
    ans.push_back(a+1);
    cout << ans[ans.size()-1];
    for(int it = ans.size()-2; it >=0; it--) cout << " " << ans[it];
    cout << endl;
    return 0;   
}

#include <iostream>

#include <vector>

#include <set>

#include <utility>

using namespace std;

#define INF 1000000000000

#define MAX 100000

vector <pair <int, long long> > G[MAX];

vector <int> path;

vector <int> ans;

set <pair <long long, int> > q;

long long length[MAX];

int parent[MAX];

int main() {

ios::sync_with_stdio(false);

int n, m, a, b;

cin >> n >> m >> a >> b;

a--, b--; // начнём отсчёт с 0, для удобства

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

int from, to, len;

cin >> from >> to >> len;

from--, to--;

G[to].push_back(make_pair(from, len));

G[from].push_back(make_pair (to, len));

}

for (int i=0; i<n; i++) length[i]=INF;

length[a]=0;

q.insert (make_pair (length[a], a));

while (!q.empty()) { // будем выполнять, пока наша очередь не пуста

int v = q.begin()->second;

q.erase (q.begin());

for (int i=0; i<G[v].size(); i++) {

int to=G[v][i].first, len=G[v][i].second;

if (length[v]+len<length[to]) { // изначально она бесконечно большая, поэтому сразу меньше, а если будет оказываться больше, то просто не будем менять

q.erase (make_pair (length[to], to)); // мы убираем нашу бесконечность или больший путь вместе со следующей вершиной, а вместо них

length[to]=length[v]+len; // ставим новую длину

parent[to]=v; // и записываем предка

q.insert (make_pair (length[to], to));

}

if (length[b]==INF) { // если последняя вершина оказалась бесконечностью, значит, мы её не достигли

cout << "-1";

return 0;

}

cout << length[b] << endl;

int c=b;

while (c!=a) {

ans.push_back(c+1); // так как начинали с 1, то увеличиваем

c=parent[c];

}

ans.push_back(a+1);

cout << ans[ans.size()-1];

for(int it = ans.size()-2; it >=0; it--) cout << " " << ans[it];

cout << endl;

return 0;

}

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

Related Images:

e-olimp 5078. Турнир

22/04/2015 by Ілларіонова Марія Валеріївна

Задача e-olimp.com №5078.

Ссылка на засчитанное решение (C++).

Ссылка на засчитанное решение (Java).

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

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

Входной файл содержит числа [latex]n \left(1\leq n\leq 100 \right)[/latex] — число вершин в графе и [latex]m \left(1\leq m\leq n\left(n-1 \right) \right)[/latex] — число ребер. Затем следует [latex]m[/latex] пар чисел — ребра графа.

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

Выведите в выходной файл YES если граф является турниром и NO в противном случае.

Код программы (С++):

#include <iostream>
using namespace std;

int A[110][110];

int main() {
	ios::sync_with_stdio(false);
	int n, m, a, b;
	cin >> n >> m;
	for (int i=0; i<m; i++) {
		cin >> a >> b;
		a--;
		b--;
		A[a][b]=1;
	}
	for (int i=0; i<n; i++) {
		for (int j=i+1; j<n; j++) {
			if (A[i][j]==1) {
				if (A[j][i]==1) {
					cout << "NO\n";
					return 0;
				}
			}
			else {
				if (A[j][i]==0) {
					cout << "NO\n";
					return 0;
				}
			}
		}
	}
	cout << "YES\n";
	return 0;
}

#include <iostream>

using namespace std;

int A[110][110];

int main() {

ios::sync_with_stdio(false);

int n, m, a, b;

cin >> n >> m;

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

cin >> a >> b;

a--;

b--;

A[a][b]=1;

}

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

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

if (A[i][j]==1) {

if (A[j][i]==1) {

cout << "NO\n";

return 0;

}

else {

if (A[j][i]==0) {

cout << "NO\n";

return 0;

}

cout << "YES\n";

return 0;

}

Java:

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

class Ideone {
	public static void main (String[] args) {
		Scanner in = new Scanner (System.in);
		int n, m, a, b;
		n = in.nextInt();
		m = in.nextInt();
		boolean [][] A = new boolean[n][n];
		for (int i=0; i<m; i++) {
			a = in.nextInt();
			b = in.nextInt();
			a--;
			b--;
			A[a][b]=true;
		}
		boolean f = false;
		for (int i=0; i<n; i++) {
			for (int j=i+1; j<n; j++) {
				if (A[i][j] && A[j][i]) {
					System.out.println("NO");
					f = true;
					break;
				}
				else if (!A[i][j] && !A[j][i]) {
					System.out.println("NO");
					f = true;
					break;
				}
			}
		}
		if (!f) System.out.println("YES");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) {

Scanner in = new Scanner (System.in);

int n, m, a, b;

n = in.nextInt();

m = in.nextInt();

boolean [][] A = new boolean[n][n];

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

a = in.nextInt();

b = in.nextInt();

a--;

b--;

A[a][b]=true;

}

boolean f = false;

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

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

if (A[i][j] && A[j][i]) {

System.out.println("NO");

f = true;

break;

}

else if (!A[i][j] && !A[j][i]) {

System.out.println("NO");

f = true;

break;

}

if (!f) System.out.println("YES");

}

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

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

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

Related Images:

e-olimp 3809. ГАС Очередь

02/04/2015 by Ілларіонова Марія Валеріївна

Задача e-olimp.com №3809. Ссылка на засчитанное решение.

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

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

Известно, что у каждого человека есть такой критерий, как раздражительность. Если этот параметр равен [latex]w[/latex], то через [latex]t[/latex] часов ожидания в очереди этот человек обрушит на голову чиновника ровно [latex]wt[/latex] единиц злобы и ругани. Так, если посетителя начнут обслуживать сразу же после его прихода, то чиновник не пострадает, а если посетитель пришел в начале третьего часа, а его обслуживание началось только в начале пятого — количество гнева будет равно [latex]2w[/latex].

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

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

В первой строке задано одно целое число [latex]t[/latex] — количество случаев, которые вам предстоит обработать. Далее следуют [latex]t[/latex] описаний самих случаев.

Описание каждого случая состоит из: числа [latex]n[/latex] в первой строке — количества посетителей, и [latex]n[/latex] описаний самих посетителей. Для каждого посетителя в отдельной строке указаны два целых числа [latex]r_{i}[/latex] и [latex]w_{i}[/latex] [latex]\left(1\leq r_{i},w_i\leq {10}^{6} \right)[/latex] — номер часа, в начале которого посетитель пришел, и его коэффициент раздражительности, соответственно.

Суммарное количество посетителей во всех случаях одного теста не превосходит [latex]10^{5}[/latex].

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

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

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

#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

pair <long long, long long> v [100010]; // массив пар (время, ярость) поменяла местами, чтобы не писать перегруженный оператор, так как сравнивается по умолчанию по первому значению
priority_queue <pair <long long, long long> > q; // очередь пар (ярость, время)

int main() {
	long long t;
	scanf("%lld", &t);
	while (t--) {
		long long n;
		scanf("%lld", &n);
		long long ans=0;
		for (int i=0; i<n; i++) {
			long long r, w;
			scanf("%lld%lld", &r, &w);
			v[i]=make_pair(r,w);
		}
		sort (v, v+n); // сортируем по времени прибытия
		long long k=0;
		long long tim=1;
		for (; tim<=1000000; ) { // цикл от 1 до максимального количества пришедших
			while (v[k].first==tim) { // если встретился такой человек, пришедший в нужный момент времени
				q.push(make_pair(v[k].second, v[k].first)); // то закидываем его в очередь по ярости (по невозрастанию)
				k++;
				if (k==n) break; // выходим из циклов, если прошли все возможные люди
			}
			if (k==n) break;
			if (q.empty()) {
				if (k<n) tim=max(tim+1, v[k].first); // если очередь уже пуста, но люди не закончились, то время ставим на максимум, чтобы не получить TLE
				else tim++;
			}
			else {
				ans+=(long long)q.top().first*(tim-q.top().second);
				tim++;
				q.pop();
			}
		}
		while (!q.empty()) {
			ans+=(long long)q.top().first*(tim-q.top().second); // если очередь не пуста, а люди уже прийти не могут, то просто запускаем по одному
			tim++;
			q.pop();
		}
		printf("%lld\n", ans);
	}
	return 0;
}

#include <cstdio>

#include <queue>

#include <vector>

#include <utility>

#include <algorithm>

using namespace std;

pair <long long, long long> v [100010]; // массив пар (время, ярость) поменяла местами, чтобы не писать перегруженный оператор, так как сравнивается по умолчанию по первому значению

priority_queue <pair <long long, long long> > q; // очередь пар (ярость, время)

int main() {

long long t;

scanf("%lld", &t);

while (t--) {

long long n;

scanf("%lld", &n);

long long ans=0;

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

long long r, w;

scanf("%lld%lld", &r, &w);

v[i]=make_pair(r,w);

}

sort (v, v+n); // сортируем по времени прибытия

long long k=0;

long long tim=1;

for (; tim<=1000000; ) { // цикл от 1 до максимального количества пришедших

while (v[k].first==tim) { // если встретился такой человек, пришедший в нужный момент времени

q.push(make_pair(v[k].second, v[k].first)); // то закидываем его в очередь по ярости (по невозрастанию)

k++;

if (k==n) break; // выходим из циклов, если прошли все возможные люди

}

if (k==n) break;

if (q.empty()) {

if (k<n) tim=max(tim+1, v[k].first); // если очередь уже пуста, но люди не закончились, то время ставим на максимум, чтобы не получить TLE

else tim++;

}

else {

ans+=(long long)q.top().first*(tim-q.top().second);

tim++;

q.pop();

}

while (!q.empty()) {

ans+=(long long)q.top().first*(tim-q.top().second); // если очередь не пуста, а люди уже прийти не могут, то просто запускаем по одному

tim++;

q.pop();

}

printf("%lld\n", ans);

}

return 0;

}

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

Для реализации наиболее подходящей структурой хранения данных является очередь с приоритетом, максимум из которой можно извлечь за [latex]O \left( \log n \right)[/latex], тогда суммарное асимптотическое время решения задачи займёт [latex]O \left( \ n log n \right)[/latex].

Related Images:

e-olimp 1667. Конденсация графа

29/03/2015 by Ілларіонова Марія Валеріївна

Задача e-olimp.com №1667. Ссылка на засчитанное решение.

Вам задан связный ориентированный граф с [latex]N[/latex] вершинами и [latex]M[/latex] ребрами [latex]\left(1\leq N\leq 20000, 1\leq M\leq 200000 \right)[/latex]. Найдите компоненты сильной связности заданного графа и топологически отсортируйте его конденсацию.

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

Граф задан во входном файле следующим образом: первая строка содержит числа [latex]N[/latex] и [latex]M[/latex]. Каждая из следующих [latex]M[/latex] строк содержит описание ребра — два целых числа из диапазона от [latex]1[/latex] до [latex]N[/latex] — номера начала и конца ребра.

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

В первой строке выведите число [latex]K[/latex] — количество компонент сильной связности в заданном графе. В следующей строке выведите [latex]N[/latex] чисел — для каждой вершины выведите номер компоненты сильной связности, которой принадлежит эта вершина. Компоненты сильной связности должны быть занумерованы таким образом, чтобы для любого ребра номер компоненты сильной связности его начала не превышал номера компоненты сильной связности его конца.

Тесты:

6 7

1 2

2 3

3 1

4 5

5 6

6 4

2 4

1 1 1 2 2 2

10 19

1 4

7 8

5 10

8 9

9 6

2 6

6 2

3 8

9 2

7 2

9 7

4 5

3 6

7 3

6 7

10 8

10 1

2 9

2 7

1 2 2 1 1 2 2 2 2 1

Иллюстрация к первому тесту:

Иллюстрация ко второму тесту:

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

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

vector <int> G[100010];
vector <int> Gt[100010]; // транспонированній граф
vector<bool> used;
vector<int> order, component;
int res[100010];
int n, m, num=1;

void dfs_1 (int u) {
 used[u]=1;
 for (int i=0; i<G[u].size(); i++) {
     if (used[G[u][i]]==0) {
         dfs_1(G[u][i]);
     }
 }
 order.push_back(u);
}

void dfs_2 (int u) {
  used[u]=1;
  component.push_back(u);
  for (int i=0; i<Gt[u].size(); i++) {
      if (used[Gt[u][i]]==0) {
          dfs_2 (Gt[u][i]);
      }
  }
}

int main() {
 ios::sync_with_stdio(false);
 cin >> n >> m;
 
 while (m--) {
     int a, b;
     cin >> a >> b;
     a--;
     b--;
     G[a].push_back(b);
     Gt[b].push_back(a);
 }
 
 used.assign (n, false);

 for (int i=0; i<n; i++) {
         if (used[i]==0) dfs_1(i);
 }
 
 used.assign (n, false);
 
 for (int i=0; i<n; i++) {
      int v=order[n-1-i];
      if (used[v]==0) {
          dfs_2 (v);
          for(auto I=component.begin(); I!=component.end(); I++)
              res[*I]=num;
          num++;
          component.clear();
      }
  }
  
  cout << num-1 << endl;
  for (int i=0; i<n-1; i++) cout << res[i] << " ";
  cout << res[n-1] << endl;
  return 0;
}

#include <iostream>

#include <vector>

using namespace std;

vector <int> G[100010];

vector <int> Gt[100010]; // транспонированній граф

vector<bool> used;

vector<int> order, component;

int res[100010];

int n, m, num=1;

void dfs_1 (int u) {

used[u]=1;

for (int i=0; i<G[u].size(); i++) {

if (used[G[u][i]]==0) {

dfs_1(G[u][i]);

}

order.push_back(u);

}

void dfs_2 (int u) {

used[u]=1;

component.push_back(u);

for (int i=0; i<Gt[u].size(); i++) {

if (used[Gt[u][i]]==0) {

dfs_2 (Gt[u][i]);

}

int main() {

ios::sync_with_stdio(false);

cin >> n >> m;

while (m--) {

int a, b;

cin >> a >> b;

a--;

b--;

G[a].push_back(b);

Gt[b].push_back(a);

}

used.assign (n, false);

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

if (used[i]==0) dfs_1(i);

}

used.assign (n, false);

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

int v=order[n-1-i];

if (used[v]==0) {

dfs_2 (v);

for(auto I=component.begin(); I!=component.end(); I++)

res[*I]=num;

num++;

component.clear();

}

cout << num-1 << endl;

for (int i=0; i<n-1; i++) cout << res[i] << " ";

cout << res[n-1] << endl;

return 0;

}

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

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

Теперь нужно сделать такой обход из этой вершины, который посетил бы только эту компоненту сильной связности и не зашёл бы ни в какую другую. Для этого служит функция dfs_2, которая применяется к траспонированному графу [latex]G^{T}[/latex] (граф, полученный из [latex]G[/latex] изменением направления каждого ребра на противоположное). В этом графе будут те же компоненты сильной связности, что и в исходном графе. Пусть [latex]G^{*}[/latex] — это граф конденсации, получаемый из данного графа сжатием каждой компоненты сильной связности в одну вершину (очевидно, что он ацикличен). Тогда [latex]\left(G^{T} \right)^{*}[/latex] будет равен транспонированному графу конденсации исходного графа [latex]G^{*}[/latex]. Это значит, что теперь из рассматриваемой нами «корневой» компоненты уже не будут выходить рёбра в другие компоненты.

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

Таким образом, чтобы обойти всю «корневую» компоненту сильной связности, содержащую некоторую вершину [latex]u[/latex], достаточно запустить обход из этой вершины в графе[latex]G^{T}[/latex]. Этот обход посетит все вершины этой компоненты сильной связности и только их. Дальше мы можем мысленно удалить эти вершины из графа, находить очередную вершину с максимальным значением времени выхода и запускать обход на транспонированном графе из неё.

Так после каждого запуска dfs_2 в векторе component окажутся все вершины, принадлежащие одной компоненте связности. Поэтому каждой из тих вершин присваиваем номер компоненты, после чего вектор component чистится и идёт новая итерация (номер компоненты при этом увеличивается на 1).

Related Images:

e-olimp 693. Минимум в стеке

19/03/2015 by Ілларіонова Марія Валеріївна

Задача e-olimp.com №693. На вход программы подается набор операций со стеком. Каждая операция состоит в добавлении или удалении элемента из стека. После выполнения каждой операции найдите наименьшее число, которое находится в стеке. Сложите все полученные числа и получите ответ. Если после некоторой операции стек оказался пуст, то ничего не прибавляйте к ответу. Если выполнить удаление невозможно, так как стек пуст, то не выполняйте его.

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

Входные данные генерируются в самой программе. На вход подаются параметры для генерации входной последовательности.

Первое число содержит количество операций [latex]n (1\leq n\leq10^{6})[/latex] со стеком. Затем следуют четыре неотрицательных целых числа [latex]a, b, c, x_{0}[/latex] не превосходящие [latex]10000[/latex].

Для получения входных данных генерируем последовательность [latex]x[/latex].

Первое число в генерируемой последовательности [latex]x_{1}[/latex]. Первое, а также каждое следующее число вычисляется из предыдущего по формуле:

[latex]x_{i}=\left(a\cdot x_{i-1}^{2} + b\cdot x_{i-1} + c\right)/100 \bmod{10^{6}}[/latex],

где ‘/‘ — операция целочисленного деления, а ‘[latex] \mod{}[/latex]’ — остаток от деления.

Если [latex]x_{i} \mod{5}<2[/latex], то необходимо удалить число из стека. В противном случае необходимо добавить в стек число [latex]x_{i}[/latex].

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

Выведите результирующую сумму.

Ссылка на задачу. Ссылка на засчитанное решение.

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

#include <iostream>
#include <stack>
#include <utility>
#include <algorithm>
using namespace std;
 
const long long mod=1000000;
stack <pair <long long, long long> > st;
 
int main() {
	long long n, a, b, c, x, ans=0;
	cin >> n >> a >> b >> c >> x;
	while (n--) {
		x=(a*x*x+b*x+c)/100%mod;
		if (x%5<2) {
			if (!st.empty()) st.pop();
		}
		else {
			long long mini= st.empty() ? x : min(x, st.top().second);
			st.push(make_pair(x, mini));
		}
 
		if (!st.empty()) ans+=st.top().second;
	}
	cout << ans << endl;
	return 0;
}

#include <iostream>

#include <stack>

#include <utility>

#include <algorithm>

using namespace std;

const long long mod=1000000;

stack <pair <long long, long long> > st;

int main() {

long long n, a, b, c, x, ans=0;

cin >> n >> a >> b >> c >> x;

while (n--) {

x=(a*x*x+b*x+c)/100%mod;

if (x%5<2) {

if (!st.empty()) st.pop();

}

else {

long long mini= st.empty() ? x : min(x, st.top().second);

st.push(make_pair(x, mini));

}

if (!st.empty()) ans+=st.top().second;

}

cout << ans << endl;

return 0;

}

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

На мой взгляд сложность задачи состояла только в том, чтобы реализовать взятие минимального элемента из стека за [latex]O\left(1 \right)[/latex].

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

Related Images:

e-olimp 6124. Стек неограниченного размера

18/03/2015 by Ілларіонова Марія Валеріївна

Стек неограниченного размера

Реализуйте структуру данных «стек«. Напишите программу, содержащую описание стека и моделирующую работу стека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:
push n
Добавить в стек число n (значение n задается после команды). Программа должна вывести ok.
pop
Удалить из стека последний элемент. Программа должна вывести его значение.
back
Программа должна вывести значение последнего элемента, не удаляя его из стека.
size
Программа должна вывести количество элементов в стеке.
clear
Программа должна очистить стек и вывести ok.
exit
Программа должна вывести bye и завершить работу.

Размер стека должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций back и pop программа должна проверять, содержится ли в стеке хотя бы один элемент. Если во входных данных встречается операция back или pop, и при этом стек пуст, то программа должна вместо числового значения вывести строку error.
Пояснение: Размер стека должен быть ограничен только размером доступной оперативной памяти.

Решение

Предлагается реализация стека через связные списки.

Положительные стороны:

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

Отрицательные стороны:

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

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

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

struct node {
   int value=0;
   node* prev=NULL;
   node(int val, node* prv): value(val), prev(prv) {} // конструктор нашего верхнего элемента в стеке
};

struct stack {
   int cnt=0;
   node* top=NULL;
   void push (int n) {
       top = new node(n, top); // когда создаём новую вершину, но присваиваем ей цену, а предыдущей записываем прошлую топовую вершину
       cnt++;
   }
   bool empty() {
       return cnt == 0;
   }
   int pop() {
       node* prev = top->prev; // записываем предыдущий узел во временную переменную
       int topVal = top->value;
       delete top; // удаляем последний элемент стека
       top = prev; // говорим, что он теперь равен прдыдущему
       cnt--;
       return topVal;
   }
   int back() {
       return top->value;
   }
   int size() {
       return cnt;
   }
   void clear() {
       while (!empty()) pop();
   }
};

int main() {
   ios::sync_with_stdio(false);
   string t;
   int val;
   stack s;
   while (1) {
       cin >> t;
       if (t=="push") {
           cin >> val;
           s.push(val);
           cout << "ok" << endl;
       }
       else if (t=="pop") {
           if (s.empty())
               cout << "error" << endl;
           else {
               val = s.pop();
               cout << val << endl;
           }
       }
       else if (t=="back") {
           if (s.empty())
               cout << "error" << endl;
           else
               cout << s.back() << endl;
       }
       else if (t=="size") cout << s.size() << endl;
       else if (t=="clear") {
           s.clear();
           cout << "ok" << endl;
       }
       else if (t=="exit") {
           cout << "bye" << endl;
           break;
       }
   }
   return 0;
}

#include <iostream>

#include <string>

using namespace std;

struct node {

int value=0;

node* prev=NULL;

node(int val, node* prv): value(val), prev(prv) {} // конструктор нашего верхнего элемента в стеке

};

struct stack {

int cnt=0;

node* top=NULL;

void push (int n) {

top = new node(n, top); // когда создаём новую вершину, но присваиваем ей цену, а предыдущей записываем прошлую топовую вершину

cnt++;

}

bool empty() {

return cnt == 0;

}

int pop() {

node* prev = top->prev; // записываем предыдущий узел во временную переменную

int topVal = top->value;

delete top; // удаляем последний элемент стека

top = prev; // говорим, что он теперь равен прдыдущему

cnt--;

return topVal;

}

int back() {

return top->value;

}

int size() {

return cnt;

}

void clear() {

while (!empty()) pop();

}

};

int main() {

ios::sync_with_stdio(false);

string t;

int val;

stack s;

while (1) {

cin >> t;

if (t=="push") {

cin >> val;

s.push(val);

cout << "ok" << endl;

}

else if (t=="pop") {

if (s.empty())

cout << "error" << endl;

else {

val = s.pop();

cout << val << endl;

}

else if (t=="back") {

if (s.empty())

cout << "error" << endl;

else

cout << s.back() << endl;

}

else if (t=="size") cout << s.size() << endl;

else if (t=="clear") {

s.clear();

cout << "ok" << endl;

}

else if (t=="exit") {

cout << "bye" << endl;

break;

}

return 0;

}

Related Images:

AA12

14/03/2015 by Ілларіонова Марія Валеріївна

Задача. В заданной строке заменить каждую точку или точку с запятой тремя точками подряд.

Ввод	Вывод
asgahra.agargarhah;rehaehraeh.arhreh agerge..sgsgg.g	asgahra…agargarhah…rehaehraeh…arhreh agerge……sgsgg…g
;;.grg . . ; ;	………grg … … … …

Код программы (C++):

#include <iostream>
#include <string>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    string s, t;
    getline(cin, s);
    for (int i=0; i<s.length(); i++) {
    	if (s[i]=='.'||s[i]==';') {
    		t+="...";
    	}
    	else {
    		t+=s[i];
    	}
    }
    cout << t << endl;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

ios::sync_with_stdio(false);

string s, t;

getline(cin, s);

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

if (s[i]=='.'||s[i]==';') {

t+="...";

}

else {

t+=s[i];

}

cout << t << endl;

return 0;

}

Java:

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

class Ideone {
	public static void main (String[] args) {
		Scanner in = new Scanner (System.in);
		String s, t="";
		s = in.nextLine();
		for (int i=0; i<s.length(); i++) {
			if (s.charAt(i)=='.'||s.charAt(i)==';') {
	    		t+="...";
	    	}
	    	else t+=s.charAt(i);
		}
		System.out.println(t);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) {

Scanner in = new Scanner (System.in);

String s, t="";

s = in.nextLine();

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

if (s.charAt(i)=='.'||s.charAt(i)==';') {

t+="...";

}

else t+=s.charAt(i);

}

System.out.println(t);

}

Алгоритм решения: пройдём по всем символам строки от её начала и до конца, в случае, если встреченный символ — ‘.’ или ‘;’, мы добавим в строку вывода ‘…’, иначе — текущий символ.

Related Images:

М3

26/11/2014 by Ілларіонова Марія Валеріївна

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

q	A	B	A+B	Комментарий.
10	126740	546.967	127286.967	Тест пройден.
8	2360	7521	12101	Тест пройден.
2	1011001	1101	100110	Тест пройден.
3	1210.012	1112.1	10022.112	Тест пройден.
10	4356.98	67.975	4424.955	Тест пройден.

Код программы (string):

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

unsigned int dot_position (const string &a, const string &b) {
	unsigned int dota=0, dotb=0;
	for (unsigned int i=0; a[i]; i++) {
		if (a[i]=='.') dota=i;
	}
	if (dota==0) dota=a.length();
	for (unsigned int i=0; b[i]; i++) {
		if (b[i]=='.') dotb=i;
	}
	if (dotb==0) dotb=b.length();
	return max (dota, dotb);
}

unsigned int length_before_dot (const string &a) {
	unsigned int i=0;
	for (; a[i]; i++) {
		if (a[i]=='.') break;
	}
	return i;
}

int length_after_dot (const string &a) {
	return a.length()-length_before_dot(a)-1;
}

int main() {
	const int d='0';
	int q;
	cin >> q;
	string a, b, c;
	cin >> a >> b;
	if (length_after_dot(a)<0) a.insert(a.length(),"."); // Если число без точки, то условно ставим её.
	if (length_after_dot(b)<0) b.insert(b.length(),".");
	if (length_after_dot(a)>length_after_dot(b)) {
		for (unsigned int i=a.length()-1; i>length_before_dot(a)+length_after_dot(b); i--) {
			c.insert(c.begin(),a[i]);
		}
	}
	else if (length_after_dot(a)<length_after_dot(b)) {
		for (unsigned int i=b.length()-1; i>length_before_dot(b)+length_after_dot(a); i--) {
			c.insert(c.begin(),b[i]);
		}
	}
	if (length_before_dot(a)<dot_position(a,b)) {
		a.insert(0,dot_position(a,b)-length_before_dot(a),'0');
	}
	else if (length_before_dot(b)<dot_position(a,b)) {
		b.insert(0,dot_position(a,b)-length_before_dot(b),'0');
	}
	int p=0;
	for (int i=min(a.length(),b.length())-1; i>=0; i--) {
		string k;
		if (a[i]=='.') {
			c.insert(0,"."); --i;
		}
		if (a[i]+b[i]-2*d+p-q<0) {
			k=to_string(a[i]+b[i]-2*d+p);
			p=0;
		}
		else {
			k=to_string(a[i]+b[i]-2*d+p-q);
			p=1;
		}
		c.insert(0,k);
	}
	if (p==1) { 
		c.insert(0,"1");
	}
	if (c.back()=='.') c.pop_back();
	cout << c << endl;
	return 0;
}

#include <iostream>

#include <string>

using namespace std;

unsigned int dot_position (const string &a, const string &b) {

unsigned int dota=0, dotb=0;

for (unsigned int i=0; a[i]; i++) {

if (a[i]=='.') dota=i;

}

if (dota==0) dota=a.length();

for (unsigned int i=0; b[i]; i++) {

if (b[i]=='.') dotb=i;

}

if (dotb==0) dotb=b.length();

return max (dota, dotb);

}

unsigned int length_before_dot (const string &a) {

unsigned int i=0;

for (; a[i]; i++) {

if (a[i]=='.') break;

}

return i;

}

int length_after_dot (const string &a) {

return a.length()-length_before_dot(a)-1;

}

int main() {

const int d='0';

int q;

cin >> q;

string a, b, c;

cin >> a >> b;

if (length_after_dot(a)<0) a.insert(a.length(),"."); // Если число без точки, то условно ставим её.

if (length_after_dot(b)<0) b.insert(b.length(),".");

if (length_after_dot(a)>length_after_dot(b)) {

for (unsigned int i=a.length()-1; i>length_before_dot(a)+length_after_dot(b); i--) {

c.insert(c.begin(),a[i]);

}

else if (length_after_dot(a)<length_after_dot(b)) {

for (unsigned int i=b.length()-1; i>length_before_dot(b)+length_after_dot(a); i--) {

c.insert(c.begin(),b[i]);

}

if (length_before_dot(a)<dot_position(a,b)) {

a.insert(0,dot_position(a,b)-length_before_dot(a),'0');

}

else if (length_before_dot(b)<dot_position(a,b)) {

b.insert(0,dot_position(a,b)-length_before_dot(b),'0');

}

int p=0;

for (int i=min(a.length(),b.length())-1; i>=0; i--) {

string k;

if (a[i]=='.') {

c.insert(0,"."); --i;

}

if (a[i]+b[i]-2*d+p-q<0) {

k=to_string(a[i]+b[i]-2*d+p);

p=0;

}

else {

k=to_string(a[i]+b[i]-2*d+p-q);

p=1;

}

c.insert(0,k);

}

if (p==1) {

c.insert(0,"1");

}

if (c.back()=='.') c.pop_back();

cout << c << endl;

return 0;

}

Программа выполнена с помощью методов класса <string>. Для работы мне понадобилось написать несколько вспомогательных функций, задачей которых является дополнить числа нулями таким образом, чтобы точки чисел оказались на одинаковых позициях.

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

Функции length_before_dot и length_after_dot возвращают количество цифр до и после точки соответственно.

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

После этого программа готова вычислить сумму двух чисел. Сложность реализации алгоритма сложения состояла лишь в том, что записать в строку элемент типа int — невозможно, а следовательно, его нужно было преобразовать в строку. Для этого потребовалась функция to_string() из класса <string>. Но при этом элементы a[i] и b[i] воспринимались как коды символов, поэтому каждый из них нужно было уменьшить на ‘0’.

Ещё одна сложность — это десятки, которые мы держим «в уме», а в моём случае — во вспомогательной переменной p.

Код можно посмотреть здесь.

Код программы (cstring):

#include <iostream>
#include <cstring>
#include <stdio.h>
using namespace std;
 
unsigned int dot_position (const char *a, const char *b) {
	unsigned int dota=0, dotb=0;
	for (unsigned int i=0; a[i]; i++) {
		if (a[i]=='.') dota=i;
	}
	if (dota==0) dota=strlen(a);
	for (unsigned int i=0; b[i]; i++) {
		if (b[i]=='.') dotb=i;
	}
	if (dotb==0) dotb=strlen(b);
	return max (dota, dotb);
}
 
unsigned int length_before_dot (const char *a) {
	unsigned int i=0;
	for (; a[i]; i++) {
		if (a[i]=='.') break;
	}
	return i;
}
 
int length_after_dot (const char *a) {
	return strlen(a)-length_before_dot(a)-1;
}
 
void insert (char *a, size_t position, char c) {
	for (unsigned int i=strlen(a); i>position; i--) {
		a[i]=a[i-1];
	}	
	a[position]=c;
}
 
 
int main() {
	const int d='0';
	int q;
	cin >> q;
	char *a;
	a = new char [100];
	char *b;
	b = new char [100];
	char *c;
	c = new char [101];
	cin >> a >> b;
	if (length_after_dot(a)<0) insert(a,strlen(a),'.'); // Если число без точки, то условно ставим её.
	if (length_after_dot(b)<0) insert(b,strlen(b),'.');
	if (length_after_dot(a)>length_after_dot(b)) {
		for (unsigned int i=strlen(a)-1; i>length_before_dot(a)+length_after_dot(b); i--) {
			insert(c,0,a[i]);
		}
	}
	else if (length_after_dot(a)<length_after_dot(b)) {
		for (unsigned int i=strlen(b)-1; i>length_before_dot(b)+length_after_dot(a); i--) {
			insert(c,0,b[i]);
		}
	}
	if (length_before_dot(a)<dot_position(a,b)) {
		for (unsigned int i=dot_position(a,b)-length_before_dot(a); i>0; i--) { 
			insert(a,0,'0');
		}
	}
	else if (length_before_dot(b)<dot_position(a,b)) {
		for (unsigned int i=dot_position(a,b)-length_before_dot(b); i>0; i--) {
			insert(b,0,'0');
		}
	}
	int p=0;
	for (int i=min(strlen(a),strlen(b))-1; i>=0; i--) {
		char *k;
		k = new char [1];
		if (a[i]=='.') {
			insert(c,0,'.'); --i;
		}
		if (a[i]+b[i]-2*d+p-q<0) {
			sprintf(k,"%d",a[i]+b[i]-2*d+p);
			p=0;
		}
		else {
			sprintf(k,"%d",a[i]+b[i]-2*d+p-q);
			p=1;
		}
		insert(c,0,k[0]);
	}
	if (p==1) { 
		insert(c,0,'1');
	}
	if (c[strlen(c)-1]=='.') c[strlen(c)-1]='';
	cout << c << endl;
	return 0;
}

#include <iostream>

#include <cstring>

#include <stdio.h>

using namespace std;

unsigned int dot_position (const char *a, const char *b) {

unsigned int dota=0, dotb=0;

for (unsigned int i=0; a[i]; i++) {

if (a[i]=='.') dota=i;

}

if (dota==0) dota=strlen(a);

for (unsigned int i=0; b[i]; i++) {

if (b[i]=='.') dotb=i;

}

if (dotb==0) dotb=strlen(b);

return max (dota, dotb);

}

unsigned int length_before_dot (const char *a) {

unsigned int i=0;

for (; a[i]; i++) {

if (a[i]=='.') break;

}

return i;

}

int length_after_dot (const char *a) {

return strlen(a)-length_before_dot(a)-1;

}

void insert (char *a, size_t position, char c) {

for (unsigned int i=strlen(a); i>position; i--) {

a[i]=a[i-1];

}

a[position]=c;

}

int main() {

const int d='0';

int q;

cin >> q;

char *a;

a = new char [100];

char *b;

b = new char [100];

char *c;

c = new char [101];

cin >> a >> b;

if (length_after_dot(a)<0) insert(a,strlen(a),'.'); // Если число без точки, то условно ставим её.

if (length_after_dot(b)<0) insert(b,strlen(b),'.');

if (length_after_dot(a)>length_after_dot(b)) {

for (unsigned int i=strlen(a)-1; i>length_before_dot(a)+length_after_dot(b); i--) {

insert(c,0,a[i]);

}

else if (length_after_dot(a)<length_after_dot(b)) {

for (unsigned int i=strlen(b)-1; i>length_before_dot(b)+length_after_dot(a); i--) {

insert(c,0,b[i]);

}

if (length_before_dot(a)<dot_position(a,b)) {

for (unsigned int i=dot_position(a,b)-length_before_dot(a); i>0; i--) {

insert(a,0,'0');

}

else if (length_before_dot(b)<dot_position(a,b)) {

for (unsigned int i=dot_position(a,b)-length_before_dot(b); i>0; i--) {

insert(b,0,'0');

}

int p=0;

for (int i=min(strlen(a),strlen(b))-1; i>=0; i--) {

char *k;

k = new char [1];

if (a[i]=='.') {

insert(c,0,'.'); --i;

}

if (a[i]+b[i]-2*d+p-q<0) {

sprintf(k,"%d",a[i]+b[i]-2*d+p);

p=0;

}

else {

sprintf(k,"%d",a[i]+b[i]-2*d+p-q);

p=1;

}

insert(c,0,k[0]);

}

if (p==1) {

insert(c,0,'1');

}

if (c[strlen(c)-1]=='.') c[strlen(c)-1]='';

cout << c << endl;

return 0;

}

Из-за отсутствия функции insert() в классе <cstring> я была вынуждена написать её самостоятельно. В остальном работа заключалась лишь в «переводе» кода из одного класса в другой.

Код можно посмотреть здесь.

Related Images:

А401

10/11/2014 by Ілларіонова Марія Валеріївна

Дана действительная квадратная матрица порядка [latex]n[/latex], натуральные числа [latex]i, j \left(1\leq i\leq n, 1\leq j\leq n \right)[/latex]. Из матрицы удалить [latex]i[/latex]-строку и [latex]j[/latex]-столбец.

[latex]n[/latex]	Матрица.	[latex]i[/latex]	[latex]j[/latex]	Полученная матрица.	Комментарий.
3	1 2 3 4 5 6 7 8 9	2	1	2 3 8 9	Тест пройден.
4	0,5 1 6 0 3 8 12 0,3 10 4,6 8 9 0 3,5 6,4 10	4	3	0,5 1 0 3 8 0,3 10 4,6 9	Тест пройден.
2	-40 87 9 -3	1	1	-3	Тест пройден.

Код программы (C++):

#include <iostream>
using namespace std;
 
int main() {
	int n;
	cin >> n;
	double **m;
	m=new double *[n];
	for (int i=0; i<n; i++)	m[i]=new double [n];
	double **m1;
	m1=new double *[n-1];
	for (int i=0; i<n-1; i++)	m1[i]=new double [n-1];
	for (int i=0; i<n; i++) {
		for (int j=0; j<n; j++) {
			cin >> m[i][j];
		}
	}
	int i0, j0;
	cin >> i0 >> j0;
	for (int i=0, tr=0; tr<n-1;) {
		if (i!=i0-1) {
			for (int j=0, td=0; td<n-1; j++, td++) {
				if (j==j0-1) j++;
				m1[tr][td]=m[i][j];
			}
			i++;
			tr++;
		}
		else i++;
	}
	delete []m;
	m=m1;
	for (int i=0; i<n-1; i++) {
		for (int j=0; j<n-1; j++) {
			printf ("%5.3lf\t", m[i][j]);
		}
		cout << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

double **m;

m=new double *[n];

for (int i=0; i<n; i++) m[i]=new double [n];

double **m1;

m1=new double *[n-1];

for (int i=0; i<n-1; i++) m1[i]=new double [n-1];

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

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

cin >> m[i][j];

}

int i0, j0;

cin >> i0 >> j0;

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

if (i!=i0-1) {

for (int j=0, td=0; td<n-1; j++, td++) {

if (j==j0-1) j++;

m1[tr][td]=m[i][j];

}

i++;

tr++;

}

else i++;

}

delete []m;

m=m1;

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

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

printf ("%5.3lf\t", m[i][j]);

}

cout << endl;

}

return 0;

}

Java:

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

class Ideone {
	public static void main (String[] args) {
		Scanner in = new Scanner (System.in);
		int n;
		n = in.nextInt();
		double [][]m = new double[n][n];
		double [][]m1 = new double[n-1][n-1];
		for (int i=0; i<n; i++) {
			for (int j=0; j<n; j++) {
				m[i][j] = in.nextDouble();
			}
		}
		int i0, j0;
		i0 = in.nextInt();
		j0 = in.nextInt();
		for (int i=0, tr=0; tr<n-1;) {
			if (i!=i0-1) {
				for (int j=0, td=0; td<n-1; j++, td++) {
					if (j==j0-1) j++;
					m1[tr][td]=m[i][j];
				}
				i++;
				tr++;
			}
			else i++;
		}
		m=m1;
		for (int i=0; i<n-1; i++) {
			for (int j=0; j<n-1; j++) {
				System.out.print(m[i][j]+"    ");
			}
			System.out.println();
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) {

Scanner in = new Scanner (System.in);

int n;

n = in.nextInt();

double [][]m = new double[n][n];

double [][]m1 = new double[n-1][n-1];

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

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

m[i][j] = in.nextDouble();

}

int i0, j0;

i0 = in.nextInt();

j0 = in.nextInt();

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

if (i!=i0-1) {

for (int j=0, td=0; td<n-1; j++, td++) {

if (j==j0-1) j++;

m1[tr][td]=m[i][j];

}

i++;

tr++;

}

else i++;

}

m=m1;

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

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

System.out.print(m[i][j]+" ");

}

System.out.println();

}

Сначала пользователю предлагается ввести порядок матрицы, затем элементы этой матрицы. После чего, по условию задачи, пользователь должен задать [latex]i[/latex]-строку и [latex]j[/latex]-столбец, которые программа должна изъять из матрицы.

Протестировать программу можно здесь (C++) и здесь (Java).

Related Images:

Ю11.15

29/10/2014 by Ілларіонова Марія Валеріївна

Метод парабол. Найти минимум заданной функции [latex]y=f(x)[/latex], двигаясь от заданной точки [latex]x_{0}[/latex] по методу парабол:

[latex]x_{i+1}=x_{i}-\frac{h}{2}\frac{f\left( x_{i}+h\right)-f\left( x_{i}-h\right)}{f\left( x_{i}+h\right)-2f\left( x_{i}\right)+f\left( x_{i}-h\right)}, i=0,1,\ldots[/latex], пока не будет достигнута заданная точность.

Функция [latex]x^{3}+10\sin (5x)[/latex]:

[latex]x_{0}[/latex]	[latex]\varepsilon[/latex]	Точка минимума по графику.	Точка минимума по программе.	Комментарий.
0	0,001	-0,315353	-0,315353	Тест пройден.
1	0,0001	0,932048	0,932048	Тест пройден.
2	0,0001	2,14327	2,14327	Тест пройден.
-3	0,01	-2,93616	-2,93616	Тест пройден.
-2	0,0001	-1,6017	-1,6017	Тест пройден.

Код программы (C++):

Для функции [latex]x^{3}+10\sin (5x)[/latex] (функцию всегда можно изменить, достаточно исправить строку 6):

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

double f(double x) {
    return x*x*x+10*sin(5*x);
}

int main() {
    double h=0.001;
    double x, pogr;
    cin >> x >> pogr;
    if (x==0) x+=0.1;
    while ((f(x+h)-2*f(x)+f(x-h))/(h*h)<=0) x+=0.1;
    double x1;
    x1=x-0.5*h*(f(x+h)-f(x-h))/(f(x+h)-2*f(x)+f(x-h));
    while (fabs(x1-x)>pogr) {
        x=x1;
        x1=x-0.5*h*(f(x+h)-f(x-h))/(f(x+h)-2*f(x)+f(x-h));
    }
    cout << x1;
    return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

double f(double x) {

return x*x*x+10*sin(5*x);

}

int main() {

double h=0.001;

double x, pogr;

cin >> x >> pogr;

if (x==0) x+=0.1;

while ((f(x+h)-2*f(x)+f(x-h))/(h*h)<=0) x+=0.1;

double x1;

x1=x-0.5*h*(f(x+h)-f(x-h))/(f(x+h)-2*f(x)+f(x-h));

while (fabs(x1-x)>pogr) {

x=x1;

x1=x-0.5*h*(f(x+h)-f(x-h))/(f(x+h)-2*f(x)+f(x-h));

}

cout << x1;

return 0;

}

Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
    public static double f (double x) {
        return x*x*x+10*Math.sin(5*x);
    }
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in =  new Scanner (System.in);
        double h=0.001;
        double x, pogr;
        x=in.nextDouble();
        pogr=in.nextDouble();
        if (x==0) x+=0.1;
        while ((f(x+h)-2*f(x)+f(x-h))/(h*h)<=0) x+=0.1;
        double x1;
        x1=x-0.5*h*(f(x+h)-f(x-h))/(f(x+h)-2*f(x)+f(x-h));
        while (Math.abs(x1-x)>pogr) {
            x=x1;
            x1=x-0.5*h*(f(x+h)-f(x-h))/(f(x+h)-2*f(x)+f(x-h));
        }
        System.out.format ("%f%n", x1);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static double f (double x) {

return x*x*x+10*Math.sin(5*x);

}

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

{

Scanner in = new Scanner (System.in);

double h=0.001;

double x, pogr;

x=in.nextDouble();

pogr=in.nextDouble();

if (x==0) x+=0.1;

while ((f(x+h)-2*f(x)+f(x-h))/(h*h)<=0) x+=0.1;

double x1;

x1=x-0.5*h*(f(x+h)-f(x-h))/(f(x+h)-2*f(x)+f(x-h));

while (Math.abs(x1-x)>pogr) {

x=x1;

x1=x-0.5*h*(f(x+h)-f(x-h))/(f(x+h)-2*f(x)+f(x-h));

}

System.out.format ("%f%n", x1);

}

Чтобы сделать программу, я почитала “Численные методы” Н. Н. Калиткина, где и было сказано, что в качестве вспомогательного шага [latex]h[/latex] при расчётах на ЭВМ обычно выбирают значение 0,001.

Далее пользователю предоставляется возможность ввести значение [latex]x_{0}[/latex] и задать точность [latex]\varepsilon[/latex]. Корень [latex]x[/latex] является минимумом функции тогда и только тогда, когда вторая производная этой функции больше 0. Поэтому мы запускаем цикл, который будет сдвигать наше [latex]x_{0}[/latex] в положительном направлении оси [latex]x[/latex], пока вторая производная функции не будет удовлетворять условию задачи.

Далее мы вычисляем значение [latex]x_{i+1}[/latex], и запускаем цикл, который будет продолжаться до тех пор, пока разница между [latex]x_{i}[/latex] и [latex]x_{i+1}[/latex] не будет меньше заданной погрешности [latex]\varepsilon[/latex].

Затем на экран выводится сама точка минимума функции.

Программу можно посмотреть здесь (C++) и здесь (Java).

Related Images:

e-olimp 2392. Интересная сумма

27/10/2014 by Ілларіонова Марія Валеріївна

Ссылка на задачу.

Дано трёхзначное натуральное число [latex]N[/latex]. Определить сумму наибольшего и наименьшего трёхзначных чисел, которые могут быть образованы из числа [latex]N[/latex] перестановкой цифр.

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

Натуральное число [latex]N[/latex] [latex]\left(100\leq N\leq 999 \right)[/latex].

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

Ответ к задаче.

Пройденные тесты (C++).

Java.

Код программы (C++):

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

int main() {
	int N, b[3], c[3];
	cin >> N;
	for (int i=0; i<3; i++) {
		b[i]=N%10; c[i]=N%10;
		N=N/10;
	}
	sort(b,b+3);
	sort(c,c+3); reverse (c,c+3);
	if ((b[0]==0)&&(b[1]!=0)) swap (b[0],b[1]);
	else if ((b[0]==0)&&(b[1]==0)) swap (b[0],b[2]);
	int b1=100*b[0]+10*b[1]+b[2];
	int c1=100*c[0]+10*c[1]+c[2];
	cout << b1+c1 << endl;
	return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int N, b[3], c[3];

cin >> N;

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

b[i]=N%10; c[i]=N%10;

N=N/10;

}

sort(b,b+3);

sort(c,c+3); reverse (c,c+3);

if ((b[0]==0)&&(b[1]!=0)) swap (b[0],b[1]);

else if ((b[0]==0)&&(b[1]==0)) swap (b[0],b[2]);

int b1=100*b[0]+10*b[1]+b[2];

int c1=100*c[0]+10*c[1]+c[2];

cout << b1+c1 << endl;

return 0;

}

Java:

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

class Main
{
	public static void swap (int []a, int i, int j) {
		int tmp=a[i];
		a[i]=a[j];
		a[j]=tmp;
	}
	public static void main (String[] args)
	{
		int N;
		int []b = new int [3];
		int []c = new int [3];
		Scanner in = new Scanner (System.in);
		N=in.nextInt();
		for (int i=0; i<3; i++) {
			b[i]=N%10; 
			c[i]=N%10;
			N/=10;
		}
		Arrays.sort(b);
		Arrays.sort(c);
		swap (c,0,2);
		if ((b[0]==0)&&(b[1]!=0)) swap(b,0,1);
		else if ((b[0]==0)&&(b[1]==0)) swap(b,0,2);
		int b1=100*b[0]+10*b[1]+b[2];
		int c1=100*c[0]+10*c[1]+c[2];
		System.out.println (b1+c1);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void swap (int []a, int i, int j) {

int tmp=a[i];

a[i]=a[j];

a[j]=tmp;

}

public static void main (String[] args)

{

int N;

int []b = new int [3];

int []c = new int [3];

Scanner in = new Scanner (System.in);

N=in.nextInt();

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

b[i]=N%10;

c[i]=N%10;

N/=10;

}

Arrays.sort(b);

Arrays.sort(c);

swap (c,0,2);

if ((b[0]==0)&&(b[1]!=0)) swap(b,0,1);

else if ((b[0]==0)&&(b[1]==0)) swap(b,0,2);

int b1=100*b[0]+10*b[1]+b[2];

int c1=100*c[0]+10*c[1]+c[2];

System.out.println (b1+c1);

}

Когда я увидела эту задачу, то мне в голову сразу пришло решение с применением массивов. Изначально пользователю предлагается ввести трёхзначное число, которое я впоследствии раскладываю на отдельные элементы массивов, один из которых определяет минимальное трёхзначное число, а второй, в свою очередь, — максимальное.

Затем я сортирую первый массив по возрастанию, а второй по убыванию.

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

После чего я перевожу элементы массива в одно трёхзначное число и наконец-то получаю сумму.

Сложность задачи 66%.

Related Images:

Ю4.27

20/10/2014 by Ілларіонова Марія Валеріївна

Задача Ю4.27. Сессия. Результаты сессии, состоящей из трёх экзаменов, для группы из [latex]n[/latex] студентов представлены матрицей [latex]K \left(n,3 \right)[/latex]. Оценка ставится по четырёхбалльной системе; неявка обозначена единицей. Подсчитать количество неявок, неудовлетворительных, удовлетворительных, хороших и отличных оценок по каждому экзамену.

[latex]n[/latex]	Оценки.	Результат.	Комментарий.
3	5 3 1 4 3 5 5 2 3	1: неявка (1), уд (1), отл (1). 2: уд (1), хор (1), отл (1). 3: неуд (1), уд (1), отл (1).	Тест пройден.
6	5 4 2 1 1 3 3 2 1 4 4 2 5 5 3 4 2 1	1: неявка (2), неуд (1), уд (1), хор (1), отл (1). 2: неявка (1), неуд (2), уд (1), хор (2). 3: неявка (1), неуд (1), уд (1), хор (1), отл (2).	Тест пройден.
2	2 4 1 5 3 3	1: неуд (1), хор (1). 2: неявка (1), отл (1). 3: уд (2).	Тест пройден.

Код программы (C++):

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int K[n][3];
	int o[5][3]={};
	for (int j=0; j<3; j++) {
		for (int i=0; i<n; i++) {
			cin >> K[i][j];
			o[K[i][j]-1][j]+=1;
		}
	printf ("Результаты %d-го экзамена: %d - неявок, %d - неудовлетворительно, %d - удовлетворительно, %d - хорошо, %d - отлично.\n", j+1, o[0][j], o[1][j], o[2][j], o[3][j], o[4][j]);
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int K[n][3];

int o[5][3]={};

for (int j=0; j<3; j++) {

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

cin >> K[i][j];

o[K[i][j]-1][j]+=1;

}

printf ("Результаты %d-го экзамена: %d - неявок, %d - неудовлетворительно, %d - удовлетворительно, %d - хорошо, %d - отлично.\n", j+1, o[0][j], o[1][j], o[2][j], o[3][j], o[4][j]);

}

return 0;

}

Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n;
		Scanner in = new Scanner (System.in);
		n=in.nextInt();
		int [][] K = new int[n][3];
		int [][] o = new int [5][3];
		for (int j=0; j<3; j++) {
			for (int i=0; i<n; i++) {
				K[i][j]=in.nextInt();
				o[K[i][j]-1][j]++;
			}
		System.out.format ("Результаты %d-го экзамена: %d - неявок, %d - неудовлетворительно, %d - удовлетворительно, %d - хорошо, %d - отлично.%n", j+1, o[0][j], o[1][j], o[2][j], o[3][j], o[4][j]);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

int n;

Scanner in = new Scanner (System.in);

n=in.nextInt();

int [][] K = new int[n][3];

int [][] o = new int [5][3];

for (int j=0; j<3; j++) {

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

K[i][j]=in.nextInt();

o[K[i][j]-1][j]++;

}

System.out.format ("Результаты %d-го экзамена: %d - неявок, %d - неудовлетворительно, %d - удовлетворительно, %d - хорошо, %d - отлично.%n", j+1, o[0][j], o[1][j], o[2][j], o[3][j], o[4][j]);

}

Изначально пользователю предлагается ввести количество студентов [latex]n[/latex]. Затем создаётся массив [latex]K \left(n,3\right)[/latex], в котором будут храниться оценки студентов, а так же двумерный массив [latex]o \left(5,3 \right)[/latex], который, собственно говоря, и будет хранить статистику по оценкам. Внешний цикл перебирает экзамены (по [latex]j[/latex]), а внутренний — студентов (по [latex]i[/latex]). Затем пользователю предлагается ввести оценки студентов (сначала вводятся все оценки за первый экзамен, затем за второй, а потом уж за третий). В этом цикле находится «счётчик», который подсчитывает количество определённых оценок (или неявок) в зависимости от массива [latex]K \left(n,3\right)[/latex] на данном этапе цикла. Затем на экран выводятся элементы массива (в дальнейшем все элементы сохранятся, то есть с оценками студентов можно будет работать и дальше).

Код программы можно посмотреть тут (C++) и тут (Java).

Related Images:

Puzzle — Temperatures

15/10/2014 by Ілларіонова Марія Валеріївна

Задача взята с этого сайта.

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

Ввод:

Строка 1: [latex]N[/latex], количество значений температуры.

Строка 2: собственно говоря, сами значения температуры, выраженные целыми числами в диапазоне от -273 до 5526.

Вывод:

Вывести 0 в том случае, если не введено ни одного значения.

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

	[latex]N[/latex]	Ввод	Вывод	Комментарий.
Простой тест	5	1 -2 -8 4 5	1	Пройден.
Сложный тест	10	-5 -4 -2 12 -40 4 2 18 11 5	2	Пройден.
Без температур	0	—	0	Пройден.
Дополнительный тест	14	7 -10 13 8 4 -7 -12 -3 3 -9 6 -1 -6 7	-1	Пройден.

Код программы (C++):

#include <iostream>
#include <string>
#include <math.h>

using namespace std;

int main() {
	int N;
	cin >> N;
	if (N!=0) {
	    int closest=5527, TEMPS;
        for (int i=0; i<N; i++) {
            cin >> TEMPS;
            if (abs(closest)>abs(TEMPS)||(abs(closest)==TEMPS)) {
                closest=TEMPS;
	        }
        }
        cout << closest << endl;
	}
	else {
        cout << 0 << endl;
    }
}

#include <iostream>

#include <string>

#include <math.h>

using namespace std;

int main() {

int N;

cin >> N;

if (N!=0) {

int closest=5527, TEMPS;

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

cin >> TEMPS;

if (abs(closest)>abs(TEMPS)||(abs(closest)==TEMPS)) {

closest=TEMPS;

}

cout << closest << endl;

}

else {

cout << 0 << endl;

}

Для первого теста нужно было найти ближайшее к нулю значение, когда все числа по модулю были попарно различными. Для этого достаточно было завести переменную типа int и положить в неё значение, которое заведомо больше всех возможных (это 5527, так как по условию задачи значения температур не выходят за пределы [-273;5527]). И в цикле сделать проверку того, что же больше — модуль нашего текущего значения или модуль только что введённого.

Задача 1.

#include <iostream>
#include <string>
#include <math.h>
 
using namespace std;
 
int main() {
	int N;
	cin >> N;
	int closest=5527, TEMPS;
    for (int i=0; i<N; i++) {
        cin >> TEMPS;
        if (abs(closest)>abs(TEMPS)) {
            closest=TEMPS;
	    }
    }
    cout << closest << endl;
}

#include <iostream>

#include <string>

#include <math.h>

using namespace std;

int main() {

int N;

cin >> N;

int closest=5527, TEMPS;

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

cin >> TEMPS;

if (abs(closest)>abs(TEMPS)) {

closest=TEMPS;

}

cout << closest << endl;

}

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

Задача 2.

#include <iostream>
#include <string>
#include <math.h>

using namespace std;

int main() {
	int N;
	cin >> N;
	int closest=5527, TEMPS;
    for (int i=0; i<N; i++) {
        cin >> TEMPS;
        if (abs(closest)>abs(TEMPS)||(abs(closest)==TEMPS)) {
            closest=TEMPS;
	    }
    }
    cout << closest << endl;
}

#include <iostream>

#include <string>

#include <math.h>

using namespace std;

int main() {

int N;

cin >> N;

int closest=5527, TEMPS;

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

cin >> TEMPS;

if (abs(closest)>abs(TEMPS)||(abs(closest)==TEMPS)) {

closest=TEMPS;

}

cout << closest << endl;

}

Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int N;
		Scanner in = new Scanner (System.in);
		N=in.nextInt();
		int closest=5527, TEMPS;
	    for (int i=0; i<N; i++) {
	        TEMPS=in.nextInt();
	        if (Math.abs(closest)>Math.abs(TEMPS)||(Math.abs(closest)==TEMPS)) {
	            closest=TEMPS;
		    }
	    }
	    System.out.format("%d%n", closest);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

int N;

Scanner in = new Scanner (System.in);

N=in.nextInt();

int closest=5527, TEMPS;

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

TEMPS=in.nextInt();

if (Math.abs(closest)>Math.abs(TEMPS)||(Math.abs(closest)==TEMPS)) {

closest=TEMPS;

}

System.out.format("%d%n", closest);

}

И для последней задачи, конечно, достаточно было ввести условие, что [latex]N[/latex] не равно нулю. В противном случае программа выведет на экран 0. Конечный код указан первым.

Related Images:

А165к

09/10/2014 by Ілларіонова Марія Валеріївна

Задача А165к. Даны действительные числа [latex]a_{1}, a_{2}, \ldots[/latex]. Известно, что [latex]a_{1} < 0[/latex] и что среди [latex]a_{2}, a_{3}, \ldots[/latex] есть хотя бы одно отрицательное число. Пусть
[latex]a_{1}, \ldots, a_{n}[/latex] – члены данной последовательности, предшествующие
первому отрицательному члену ( [latex]n[/latex] заранее неизвестно). Получить: [latex]\left|a_{1}-a_{n} \right|[/latex].

Введённые данные.	[latex]\left\|a_{1}-a_{n} \right\|[/latex]	Комментарий.
1 2 6 4 -8 0 6 8 -7	3	Пройден.
0,65 3,2 4 0 -3 2	0,65	Пройден.
0 -5 8 9	0	Пройден.
0,8 3 6 9 7,2 0 4 -2	3,2	Пройден.
1 -3 6	0	Пройден.

Код программы (C++):

#include <stdio.h>
#include <math.h>
int main(){
    
    double a, b1, b0; // a - первый член последовательности, который мы должны запомнить. b0 и b1 - последующие члены соответственно.
    scanf ("%lg", &a);
    b0=a;
    while (1) {
            scanf ("%lg", &b1);
            if (b1 < 0) break;
            b0=b1;
            }
    printf ("%lg", fabs(a - b0));
    return 0;
}

#include <stdio.h>

#include <math.h>

int main(){

double a, b1, b0; // a - первый член последовательности, который мы должны запомнить. b0 и b1 - последующие члены соответственно.

scanf ("%lg", &a);

b0=a;

while (1) {

scanf ("%lg", &b1);

if (b1 < 0) break;

b0=b1;

}

printf ("%lg", fabs(a - b0));

return 0;

}

Java:

import java.util.*;
import java.io.*;
 
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        double a, b1, b0;
        Scanner in = new Scanner (System.in);
        a=in.nextDouble();
        b0=a;
        while (true) {
            b1=in.nextDouble();
            if (b1<0) break;
            b0=b1;
        }
        System.out.format ("%f%n", Math.abs(a - b0));
    }
}

import java.util.*;

import java.io.*;

class Ideone

{

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

{

double a, b1, b0;

Scanner in = new Scanner (System.in);

a=in.nextDouble();

b0=a;

while (true) {

b1=in.nextDouble();

if (b1<0) break;

b0=b1;

}

System.out.format ("%f%n", Math.abs(a - b0));

}

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

Затем мне нужно было найти n-ый член моей последовательности. Для этого я создала 2 переменных, в одной из которых хранится настоящее значение n-ого члена независимо от его знака. Если этот член — число не отрицательное, то вспомогательной переменной присваивается его значение и цикл повторяется вновь. Если же условие неравенства не выполняется, то цикл заканчивается, и у нас остаётся значение нашей вспомогательной переменной (не отрицательное).

В том случае, если первый член последовательности является в то же время и n-ым, [latex]a_{n}[/latex] и вспомогательной переменной присваивается значение [latex]a_{1}[/latex]. И в этом случае модуль разницы будет равен 0.

После программа выводит модуль [latex]\left|a_{1}-a_{n} \right|[/latex].

Ознакомиться с кодом можно здесь (C++) и здесь (Java).

Related Images:

Ю3.45

25/09/2014 by Ілларіонова Марія Валеріївна

Ю3.45. Гуси и кролики. У гусей и кроликов вместе [latex]2n[/latex] лап. Сколько может быть гусей и кроликов (вывести все возможные сочетания)?

[latex]n[/latex]	Гусей.	Кроликов.	Комментарий.
4	0, 2, 4	2, 1, 0	Тест пройден.
3	1, 3	1, 0	Тест пройден.
0	0	0	Тест пройден.
7	1, 3, 5, 7	3, 2, 1, 0	Тест пройден.

Код программы (C++):

#include <stdio.h>

int main(void) {
	int g, k, n; // Выбран тип int, так как это животные, и их количество может быть только целым неотрицательным числом. Гуси и кролики названы g и k соответственно.
	scanf ("%d", &n); // Ввод данных с клавиатуры.
	for (g=0; g<=n; g++) {
		for (k=0; k<=n/2; k++) {
			if (2*g + 4*k == 2*n) {
				printf ("Гусей - %d. \nКроликов - %d.\n\n", g, k);
			}
		}
	}
	return 0;
}

#include <stdio.h>

int main(void) {

int g, k, n; // Выбран тип int, так как это животные, и их количество может быть только целым неотрицательным числом. Гуси и кролики названы g и k соответственно.

scanf ("%d", &n); // Ввод данных с клавиатуры.

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

for (k=0; k<=n/2; k++) {

if (2*g + 4*k == 2*n) {

printf ("Гусей - %d. \nКроликов - %d.\n\n", g, k);

}

return 0;

}

Второй вариант с 1 циклом (C++):

#include <stdio.h>
 
int main(void) {
	int g, k, n; // Выбран тип int, так как это животные, и их количество может быть только целым неотрицательным числом. Гуси и кролики названы g и k соответственно.
	scanf ("%d", &n); // Ввод данных с клавиатуры.
	for (k=0; k<=n/2; k++) {
		g=(2*n-4*k)/2;
		printf ("Гусей - %d. \nКроликов - %d.\n\n", g, k);
	}
	return 0;
}

#include <stdio.h>

int main(void) {

scanf ("%d", &n); // Ввод данных с клавиатуры.

for (k=0; k<=n/2; k++) {

g=(2*n-4*k)/2;

printf ("Гусей - %d. \nКроликов - %d.\n\n", g, k);

}

return 0;

}

Java:

import java.util.*;
import java.io.*;
 
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int g, k, n;
		Scanner in= new Scanner (System.in);
		n=in.nextInt();
		for (g=0; g<=n; g++) {
			for (k=0; k<=n/2; k++) {
				if (2*g + 4*k == 2*n) {
					System.out.format ("Гусей - %d. Кроликов - %d.%n", g, k);
				}
			}
		}
	}
}

import java.util.*;

import java.io.*;

class Ideone

{

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

{

int g, k, n;

Scanner in= new Scanner (System.in);

n=in.nextInt();

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

for (k=0; k<=n/2; k++) {

if (2*g + 4*k == 2*n) {

System.out.format ("Гусей - %d. Кроликов - %d.%n", g, k);

}

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

Для того, чтобы это сделать, программа использует 2 цикла. В первом исследуется количество гусей: изначально переменной присваивается значение 0, затем следует условие продолжения (количество гусей не должно превышать [latex]n[/latex], то есть количество лап, делённое на 2).

После запуска первого цикла программа проверяет условие продолжения вложенного второго цикла (количество кроликов не превышает [latex]\frac{n}{2}[/latex]), в котором переменной [latex]k[/latex] также изначально присваивается значение 0. В случае выполнения условий обоих циклов программа проверяет, действительно ли количество лап гусей и кроликов в сумме даёт [latex]2n[/latex], заданных по условию задачи пользователем.

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

Для тестов выбраны не слишком большие значения [latex]n[/latex], так как посчитать их вручную достаточно проблематично.

Протестировать решение можно по ссылкам: первое, второе (C++) и на Java.

Related Images:

Ю3.5

21/09/2014 by Ілларіонова Марія Валеріївна

Задача Ю3.5. Коммерция. Предприниматель, начав дело, взял кредит размером [latex]k[/latex] рублей, под [latex]p[/latex] процентов годовых и вложил его в своё дело. По прогнозам, его дело должно давать прибыль [latex]r[/latex] рублей в год. Сможет ли он накопить сумму, достаточную для погашения кредита, и если да, то через сколько лет?

[latex]k[/latex]	[latex]p[/latex]	[latex]r[/latex]	[latex]n[/latex]	Комментарий.
1800	50	1000	—	Кредит не будет погашен.
800000	15	40000	—	Кредит не будет погашен.
1000	5	400	3	Тест пройден.
1500	3,5	400	5	Тест пройден.

Код программы (C++):

#include <stdio.h>
#include <math.h>

int main() {
	double p; // Для процентов определён тип дробных чисел.
	int k, n, r; // Для количества денег и лет определяем целочисленные значения.
	scanf ("%d %lf %d", &k, &p, &r); // Ввод данных с клавиатуры.
		for (n=1; (n*r)<(k*pow(1+(p/100), n)); n++) {
			if (k*pow(1+p/100, n)-k>=r) {
				puts ("You can't pay back a loan.\n");
				return 0;
			}
		}
		printf ("%d\n", n);
		
	return 0;
}

#include <stdio.h>

#include <math.h>

int main() {

double p; // Для процентов определён тип дробных чисел.

int k, n, r; // Для количества денег и лет определяем целочисленные значения.

scanf ("%d %lf %d", &k, &p, &r); // Ввод данных с клавиатуры.

for (n=1; (n*r)<(k*pow(1+(p/100), n)); n++) {

if (k*pow(1+p/100, n)-k>=r) {

puts ("You can't pay back a loan.\n");

return 0;

}

printf ("%d\n", n);

return 0;

}

Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		double p, n=1.0, r; 
		int k;
		boolean f=false;
		Scanner in = new Scanner (System.in);
		k=in.nextInt();
		p=in.nextDouble();
		r=in.nextDouble();
		for (; (n*r)<(k*Math.pow(1+(p/100), n)); n++) {
			if (k*Math.pow(1+p/100, n)-k>=r) {
				System.out.println ("You can't pay back a loan.");
				f=true;
				break;
			}
		}
		if (f==false) {
			System.out.format ("%d%n", (int)n);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

double p, n=1.0, r;

int k;

boolean f=false;

Scanner in = new Scanner (System.in);

k=in.nextInt();

p=in.nextDouble();

r=in.nextDouble();

for (; (n*r)<(k*Math.pow(1+(p/100), n)); n++) {

if (k*Math.pow(1+p/100, n)-k>=r) {

System.out.println ("You can't pay back a loan.");

f=true;

break;

}

if (f==false) {

System.out.format ("%d%n", (int)n);

}

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

Изначально запускается цикл, который основан на сравнении дохода за несколько лет [latex]nr[/latex] и размера кредита, которого он достигнет за эти годы (вычисляется по формуле сложных процентов: [latex]k(1+\frac{p}{100})^{n}[/latex]).

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

Проверить код можно здесь (C++) и здесь (Java).

Related Images:

А50

18/09/2014 by Ілларіонова Марія Валеріївна

Задача А50. Даны действительные числа [latex]a_{1}[/latex], [latex]b_{1}[/latex], [latex]c_{1}[/latex], [latex]a_{2}[/latex], [latex]b_{2}[/latex], [latex]c_{2}[/latex]. Выяснить, верно ли что [latex]\left|a_{1} b_{2} -a_{2} b_{1} \right|\geq 0.0001[/latex], и если верно, то найти решение системы линейных уравнений

[latex]a_{1} x+b_{1} y+c_{1} =0[/latex],

[latex]a_{2} x+b_{2} y+c_{2} =0[/latex]

(при выполнении выписанного неравенства система заведомо совместна и имеет единственное решение).

[latex]a_{1}[/latex]	[latex]b_{1}[/latex]	[latex]c_{1}[/latex]	[latex]a_{2}[/latex]	[latex]b_{2}[/latex]	[latex]c_{2}[/latex]	[latex]x[/latex]	[latex]y[/latex]	Комментарий.
3,8	5	-2	6	8,4	3	16,5625	-12,1875	Тест пройден.
0	4	5	2	0	9	-4,5	-1,25	Тест пройден.
1	2	-3	3	2	-1	-1	2	Тест пройден.
1	0.00002	5	2	0.00005	8	—	—	Тест не пройден. Неравенство не выполняется.
1	4	5	2	8	3	—	—	Тест не пройден. Неравенство не выполняется.

Код программы (C++):

#include <stdio.h>
#include <math.h>

int main() {
	double a1, b1, c1, a2, b2, c2; // Переменные, предоставленные в условии.
	double x, y; // Переменные, которые нужно найти.
	double b0, c0; // Вспомогательные переменные.
	scanf ("%lf %lf %lf %lf %lf %lf", &a1, &b1, &c1, &a2, &b2, &c2); // Ввод данных с клавиатуры.
	if (fabs(a1*b2-a2*b1)>=0.0001) {
		if (a1!=0) {
			b0=b2-(b1/a1*a2);
			c0=-(c2-(c1/a1*a2));
			y=c0/b0;
			x=(-c1-((b1*c0)/b0))/a1;
			printf ("x=%lf \ny=%lf \n", x, y);
		}
		else {
			b0=b1-(b2/a2*a1);
			c0=-(c1-(c2/a2*a1));
			y=c0/b0;
			x=(-c2-((b2*c0)/b0))/a2;
			printf ("x=%lf \ny=%lf \n", x, y);
		}
		
	}
	else {
		puts ("Неравенство не выполняется.");
	}
	return 0;
}

#include <stdio.h>

#include <math.h>

int main() {

double a1, b1, c1, a2, b2, c2; // Переменные, предоставленные в условии.

double x, y; // Переменные, которые нужно найти.

double b0, c0; // Вспомогательные переменные.

scanf ("%lf %lf %lf %lf %lf %lf", &a1, &b1, &c1, &a2, &b2, &c2); // Ввод данных с клавиатуры.

if (fabs(a1*b2-a2*b1)>=0.0001) {

if (a1!=0) {

b0=b2-(b1/a1*a2);

c0=-(c2-(c1/a1*a2));

y=c0/b0;

x=(-c1-((b1*c0)/b0))/a1;

printf ("x=%lf \ny=%lf \n", x, y);

}

else {

b0=b1-(b2/a2*a1);

c0=-(c1-(c2/a2*a1));

y=c0/b0;

x=(-c2-((b2*c0)/b0))/a2;

printf ("x=%lf \ny=%lf \n", x, y);

}

else {

puts ("Неравенство не выполняется.");

}

return 0;

}

Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		double a1, b1, c1, a2, b2, c2, x, y, b0, c0;
		Scanner in = new Scanner (System.in);
		a1=in.nextDouble();
		b1=in.nextDouble();
		c1=in.nextDouble();
		a2=in.nextDouble();
		b2=in.nextDouble();
		c2=in.nextDouble();
		if (Math.abs(a1*b2-a2*b1)>=0.0001) {
			if (a1!=0) {
				b0=b2-(b1/a1*a2);
				c0=-(c2-(c1/a1*a2));
				y=c0/b0;
				x=(-c1-((b1*c0)/b0))/a1;
			}
			else {
				b0=b1-(b2/a2*a1);
				c0=-(c1-(c2/a2*a1));
				y=c0/b0;
				x=(-c2-((b2*c0)/b0))/a2;
			}
			System.out.format ("x=%f %ny=%f %n", x, y);
		}
		else {
			System.out.println("Неравенство не выполняется.");
		}
 
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

double a1, b1, c1, a2, b2, c2, x, y, b0, c0;

Scanner in = new Scanner (System.in);

a1=in.nextDouble();

b1=in.nextDouble();

c1=in.nextDouble();

a2=in.nextDouble();

b2=in.nextDouble();

c2=in.nextDouble();

if (Math.abs(a1*b2-a2*b1)>=0.0001) {

if (a1!=0) {

b0=b2-(b1/a1*a2);

c0=-(c2-(c1/a1*a2));

y=c0/b0;

x=(-c1-((b1*c0)/b0))/a1;

}

else {

b0=b1-(b2/a2*a1);

c0=-(c1-(c2/a2*a1));

y=c0/b0;

x=(-c2-((b2*c0)/b0))/a2;

}

System.out.format ("x=%f %ny=%f %n", x, y);

}

else {

System.out.println("Неравенство не выполняется.");

}

По условию задачи необходимо решить систему линейных уравнений и вывести на экран [latex]x[/latex], [latex]y[/latex].

Программа решает это уравнение по методу Гаусса.

Изначально она делает проверку на наличие ненулевого аргумента [latex]a_{1}[/latex]. Если таковой имеется, то программа решает задачу, исходя из первого уравнения системы, в противном случае — решение начинается со второго уравнения.

Далее я ввела в программу переменные [latex]b_{0}[/latex], [latex]c_{0}[/latex], чтобы не перегружать формулы большим количеством данных. Алгоритм действий таков:

1) Перенести [latex]c_{1}[/latex] и [latex]c_{2}[/latex] в правую часть уравнения, что автоматически меняет их знак на противоположный.

2) Если в программе присутствует ненулевой аргумент [latex]a_{1}[/latex], то она вычитает из второго уравнения первое, предварительно домножив второе на [latex]\frac{b_{1} a_{2} }{a_{1} }[/latex].

3) Из преобразованного второго уравнения находится [latex]y[/latex], который впоследствии подставляется в первое уравнение системы для нахождения [latex]x[/latex] .

Для выполнения программы и проверки тестов можно воспользоваться следующим объектом (C++) и этим (Java).

Related Images:

Ю2.22

18/09/2014 by Ілларіонова Марія Валеріївна

Задача Ю2.22. Голодная зима. Суточный рацион коровы составляет [latex]u[/latex] кг сена, [latex]v[/latex] кг силоса и [latex]w[/latex] кг комбикорма. В хозяйстве, содержащем стадо из [latex]k[/latex] голов, осталось [latex]s[/latex] центнеров сена, [latex]t[/latex] тонн силоса и [latex]f[/latex] мешков комбикорма по 50 кг. Сколько ещё дней хозяйство сможет кормить коров по полному рациону? Какой из кормов кончится раньше других?

[latex]u[/latex]	[latex]v[/latex]	[latex]w[/latex]	[latex]s[/latex]	[latex]t[/latex]	[latex]f[/latex]	[latex]k[/latex]	Результат.	Комментарий.
1	0,5	3	3	0,2	7	15	7. Комбикорм.	Тест пройден.
4	7	5	6	0,6	8	13	6. Комбикорм.	Тест пройден.
8	5	3,5	4	1	9	11	4. Сено.	Тест пройден.
1	1	1	1	0,1	2	2	50. Сено. Силос. Комбикорм.	Тест пройден.

C++:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(void) {
	double u, v, w; // Количество корма на 1 день 1 корове.
	double s, t, f; // Количество имеющегося корма. Измеряется в других единицах!
	int k; // Количество голов в стаде. Натуральное число.
	scanf ("%lf %lf %lf %lf %lf %lf %d", &u, &v, &w, &s, &t, &f, &k); // Ввод данных.
	
	double a, b, c; // Вспомогательные переменные для вычисления количества дней, на которое хватит каждого корма отдельно.
	a=(100*s)/(k*u);
	b=(1000*t)/(k*v);
	c=(50*f)/(k*w);
	
	if((lround(fmin (a, fmin (b, c)))-fmin (a, fmin (b, c)))>0){
		printf ("Полноценный рацион будет соблюдаться %d полных дней. \n", lround(fmin (a, fmin (b, c)))-1);
	}
	else {
		printf ("Полноценный рацион будет соблюдаться %d полных дней. \n", lround(fmin (a, fmin (b, c))));
	}
	
	if ((a<=b)&&(a<=c)) {
		if ((a==b)&&(a!=c)) {
			puts ("Сено. Силос.");
		}
		else if ((a==c)&&(a!=b)) {
			puts ("Сено. Комбикорм.");
		}
		else if ((a==b)&&(a==c)) {
			puts ("Сено. Силос. Комбикорм.");
		}
		else {
			puts ("Сено.");
		}
	}
	else if ((b<=a)&&(b<=c)) {
		if ((b==c)&&(b!=a)) {
			puts ("Силос. Комбикорм.");
		}
		else {
			puts ("Силос.");
		}
	}
	else {
		puts ("Комбикорм.");
	}
	
	return 0;
}

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

int main(void) {

double u, v, w; // Количество корма на 1 день 1 корове.

double s, t, f; // Количество имеющегося корма. Измеряется в других единицах!

int k; // Количество голов в стаде. Натуральное число.

scanf ("%lf %lf %lf %lf %lf %lf %d", &u, &v, &w, &s, &t, &f, &k); // Ввод данных.

double a, b, c; // Вспомогательные переменные для вычисления количества дней, на которое хватит каждого корма отдельно.

a=(100*s)/(k*u);

b=(1000*t)/(k*v);

c=(50*f)/(k*w);

if((lround(fmin (a, fmin (b, c)))-fmin (a, fmin (b, c)))>0){

printf ("Полноценный рацион будет соблюдаться %d полных дней. \n", lround(fmin (a, fmin (b, c)))-1);

}

else {

printf ("Полноценный рацион будет соблюдаться %d полных дней. \n", lround(fmin (a, fmin (b, c))));

}

if ((a<=b)&&(a<=c)) {

if ((a==b)&&(a!=c)) {

puts ("Сено. Силос.");

}

else if ((a==c)&&(a!=b)) {

puts ("Сено. Комбикорм.");

}

else if ((a==b)&&(a==c)) {

puts ("Сено. Силос. Комбикорм.");

}

else {

puts ("Сено.");

}

else if ((b<=a)&&(b<=c)) {

if ((b==c)&&(b!=a)) {

puts ("Силос. Комбикорм.");

}

else {

puts ("Силос.");

}

else {

puts ("Комбикорм.");

}

return 0;

}

Java:

import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;
 
class Ideone {
	public static void main (String[] args) {
		Scanner in = new Scanner (System.in);
		double u, v, w, s, t, f;
		int k;
		u=in.nextDouble();
		v=in.nextDouble();
		w=in.nextDouble();
		s=in.nextDouble();
		t=in.nextDouble();
		f=in.nextDouble();
		k=in.nextInt();
 
		double a, b, c;
		a=(100*s)/(k*u);
		b=(1000*t)/(k*v);
		c=(50*f)/(k*w);
 
		if ((Math.round(Math.min(a, Math.min(b,c)))-Math.min(a, Math.min(b,c)))>0) {
			System.out.format ("Полноценный рацион будет соблюдаться %d полных дней. %n", Math.round(Math.min(a, Math.min(b,c)))-1);
		}
		else {
			System.out.format ("Полноценный рацион будет соблюдаться %d полных дней. %n", Math.round(Math.min(a, Math.min(b,c))));
		}
		if ((a<=b)&&(a<=c)) {
			if ((a==b)&&(a!=c)) {
				System.out.println("Сено. Силос.");
			}
			else if ((a==c)&&(a!=b)) {
				System.out.println("Сено. Комбикорм.");
			}
			else if ((a==b)&&(a==c)) {
				System.out.println ("Сено. Силос. Комбикорм.");
			}
			else {
				System.out.println("Сено.");
			}
		}
		else if ((b<=a)&&(b<=c)) {
			if ((b==c)&&(b!=a)) {
				System.out.println ("Силос. Комбикорм.");
			}
			else {
				System.out.println("Силос.");
			}
		}
		else {
			System.out.println("Комбикорм.");
		}
 
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.math.*;

class Ideone {

public static void main (String[] args) {

Scanner in = new Scanner (System.in);

double u, v, w, s, t, f;

int k;

u=in.nextDouble();

v=in.nextDouble();

w=in.nextDouble();

s=in.nextDouble();

t=in.nextDouble();

f=in.nextDouble();

k=in.nextInt();

double a, b, c;

a=(100*s)/(k*u);

b=(1000*t)/(k*v);

c=(50*f)/(k*w);

if ((Math.round(Math.min(a, Math.min(b,c)))-Math.min(a, Math.min(b,c)))>0) {

System.out.format ("Полноценный рацион будет соблюдаться %d полных дней. %n", Math.round(Math.min(a, Math.min(b,c)))-1);

}

else {

System.out.format ("Полноценный рацион будет соблюдаться %d полных дней. %n", Math.round(Math.min(a, Math.min(b,c))));

}

if ((a<=b)&&(a<=c)) {

if ((a==b)&&(a!=c)) {

System.out.println("Сено. Силос.");

}

else if ((a==c)&&(a!=b)) {

System.out.println("Сено. Комбикорм.");

}

else if ((a==b)&&(a==c)) {

System.out.println ("Сено. Силос. Комбикорм.");

}

else {

System.out.println("Сено.");

}

else if ((b<=a)&&(b<=c)) {

if ((b==c)&&(b!=a)) {

System.out.println ("Силос. Комбикорм.");

}

else {

System.out.println("Силос.");

}

else {

System.out.println("Комбикорм.");

}

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

Так как изначально в условии задачи данные различались по единицам измерения, я перевела их все в килограммы. Так же было предусмотрено, что количество килограмм может быть дробным положительным, в то время как количество голов в стаде — только натуральным. Для удобства вычисления я ввела дополнительные переменные [latex]a[/latex], [latex]b[/latex], [latex]c[/latex].

Затем я столкнулась с проблемой округления полученного минимального дробного числа к целому количеству дней. Возьмём первый тест для примера. Минимальное дробное количество дней — 7,77. Функция lround округляет число лишь к ближайшему целому. Поэтому мне потребовалось ввести проверку. Если разница между округлённым минимальным и неокруглённым больше нуля, то программа вычитает из полученного значения единицу. Таким образом программа не считает дни, когда корма бы хватило лишь на определённую часть суток.

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

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

Для выполнения программы и проверки тестов можно воспользоваться следующим объектом (C++) и этим (Java).

Related Images:

А27

17/09/2014 by Ілларіонова Марія Валеріївна

Задача А27. Даны действительные положительные числа [latex]a[/latex], [latex]b[/latex], [latex]c[/latex]. По трём сторонам с длинами [latex]a[/latex], [latex]b[/latex], [latex]c[/latex] можно построить треугольник. Найти углы треугольника.

[latex]a[/latex]	[latex]b[/latex]	[latex]c[/latex]	[latex]\alpha[/latex]	[latex]\beta[/latex]	[latex]\gamma [/latex]	Комментарий
3	4	5	0,643501	0,927295	1,570796	Тест пройден.
6,8	5,2	9,3	0,801375	0,581525	1,758693	Тест пройден.
7,3	5	8,1	1,091967	0,653414	1,396212	Тест пройден.

Код программы (C):

#include <stdio.h>
#include <math.h>

int main() {
	
	double a, b, c; // Описание переменных для хранения входных данных. a, b, c - стороны треугольника.
	scanf ("%lf %lf %lf", &a, &b, &c); // Чтение из стандартного потока ввода.
	double au, bu, cu; // au, bu, cu - наименования углов, лежащих напротив соответствующих сторон.
	au = acos((pow(b, 2) + pow(c, 2) - pow(a, 2)) / (2 * b *c)); 
	bu = acos((pow(a, 2) + pow(c, 2) - pow(b, 2)) / (2 * a *c)); 
	cu = acos((pow(a, 2) + pow(b, 2) - pow(c, 2)) / (2 * a *b)); 
	printf ("%lf %lf %lf (в радианах)\n", au, bu, cu);
	
	return 0;
}

#include <stdio.h>

#include <math.h>

int main() {

double a, b, c; // Описание переменных для хранения входных данных. a, b, c - стороны треугольника.

scanf ("%lf %lf %lf", &a, &b, &c); // Чтение из стандартного потока ввода.

double au, bu, cu; // au, bu, cu - наименования углов, лежащих напротив соответствующих сторон.

au = acos((pow(b, 2) + pow(c, 2) - pow(a, 2)) / (2 * b *c));

bu = acos((pow(a, 2) + pow(c, 2) - pow(b, 2)) / (2 * a *c));

cu = acos((pow(a, 2) + pow(b, 2) - pow(c, 2)) / (2 * a *b));

printf ("%lf %lf %lf (в радианах)\n", au, bu, cu);

return 0;

}

Код программы (Java):

import java.io.*;
import java.util.*;
import java.math.*;

class Ideone {
	public static void main (String[] args)	{
		Scanner in=new Scanner(System.in);
		double a=in.nextDouble();
		double b=in.nextDouble();
		double c=in.nextDouble();
		double au = (b*b + c*c - a*a) / (2*b*c); 
		double bu = (a*a + c*c - b*b) / (2*a*c); 
		double cu = (a*a + b*b - c*c) / (2*a*b); 
		System.out.format("%f %f %f%n", Math.acos(au), Math.acos(bu), Math.acos(cu));
	}
}

import java.io.*;

import java.util.*;

import java.math.*;

class Ideone {

public static void main (String[] args) {

Scanner in=new Scanner(System.in);

double a=in.nextDouble();

double b=in.nextDouble();

double c=in.nextDouble();

double au = (b*b + c*c - a*a) / (2*b*c);

double bu = (a*a + c*c - b*b) / (2*a*c);

double cu = (a*a + b*b - c*c) / (2*a*b);

System.out.format("%f %f %f%n", Math.acos(au), Math.acos(bu), Math.acos(cu));

}

По условию задачи необходимо найти углы треугольника (программа высчитывает их в радианах).

Так как изначально в условии задачи сказано, что из отрезков с длинами [latex]a[/latex], [latex]b[/latex], [latex]c[/latex] можно построить треугольник, то решение задачи сводится к нахождению углов по следствию из «Теоремы косинусов»: [latex]\cos\alpha=\frac{b^{2}+c^{2}-a^{2}}{2bc}[/latex]. Затем, чтобы найти меру угла в радианах, достаточно просто взять [latex]\arccos(\cos\alpha)[/latex].

Аналогично вычислены меры двух других углов в радианах.

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

Для выполнения программы и проверки тестов можно воспользоваться следующим объектом (С) или этим (Java).