e-olimp 5077. Полуполный граф

27/04/2015 by Бронфен-Бова Роман

Решение

ссылка на ideone, засчитанное решение на e-olymp

#include<iostream>
using namespace std;

bool used[101][101];

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

#include<iostream>

using namespace std;

bool used[101][101];

int main(){

int n, m; cin >> n >> m;

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

int a,b; cin >> a >> b;

used[a][b] = used[b][a] = 1;

}

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

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

if(used[i][j] == false){

cout << "NO\n";

return 0;

}

cout << "YES\n";

return 0;

}

Решение на Java

ссылка на ideone, засчитанное решение на e-olymp

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
	static boolean[][] used = new boolean[101][101];
	static Scanner sc = new Scanner(System.in);
 
	public static void main (String[] args) throws java.lang.Exception
	{
		int n, m;
		n = sc.nextInt();
		m = sc.nextInt();
		for(int i = 0; i < m; i++){
	     	int a, b;
	     	a = sc.nextInt();
	     	b = sc.nextInt();
	    	used[a][b] = used[b][a] = true;
	  	}
		for(int i = 1; i <= n; i++){
	    	for(int j = i+1; j <= n; j++){
	    		if(used[i][j] == false){
	    			System.out.println("NO");
	           		return;
	        	}
	    	}
	  	}
	  	System.out.println("YES");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static boolean[][] used = new boolean[101][101];

static Scanner sc = new Scanner(System.in);

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

{

int n, m;

n = sc.nextInt();

m = sc.nextInt();

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

int a, b;

a = sc.nextInt();

b = sc.nextInt();

used[a][b] = used[b][a] = true;

}

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

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

if(used[i][j] == false){

System.out.println("NO");

return;

}

System.out.println("YES");

}

Идея решения

Считаем что граф неорентированный и проверяем, не полный ли наш граф. Если полный — выводим «YES», иначе «NO».

Related Images:

e-olimp 553. Рекурсия

20/03/2015 by Бронфен-Бова Роман

Задача: Рекурсия

Решение

ссылка на ideone, засчитанное решение на e-olimp

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

map<string,set<string>> G;
map<string,bool> used;
map<string,bool> rec;
vector<string> V;

void dfs(string cur, string aim){
   if(used[cur] || rec[aim]) return;
   used[cur] = 1;
   for(auto i = G[cur].begin(); i != G[cur].end(); i++){
      if(*i != aim){
         dfs(*i,aim);
      }else{
         rec[aim] = 1;
         return;
      }
   }
}

int main(){
   //input
   int n; cin >> n;
   for(int i = 0; i < n; i++){
      string curVert; cin >> curVert;
      V.push_back(curVert);
      int m; cin >> m;
      while(m--){
         string inp; cin >> inp;
         G[curVert].insert(inp);
      }
      if(i != n-1){
         string stars;
         cin >> stars;
      }
   }
   //work
   for(auto i : V){
      dfs(i, i);
      used.clear();
   }
   for(auto i : V){
      cout << i << (rec[i] ? ": YES" : ": NO") << endl;
   }
   return 0;
}

#include<iostream>

#include<vector>

#include<set>

#include<map>

#include<string>

using namespace std;

map<string,set<string>> G;

map<string,bool> used;

map<string,bool> rec;

vector<string> V;

void dfs(string cur, string aim){

if(used[cur] || rec[aim]) return;

used[cur] = 1;

for(auto i = G[cur].begin(); i != G[cur].end(); i++){

if(*i != aim){

dfs(*i,aim);

}else{

rec[aim] = 1;

return;

}

int main(){

//input

int n; cin >> n;

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

string curVert; cin >> curVert;

V.push_back(curVert);

int m; cin >> m;

while(m--){

string inp; cin >> inp;

G[curVert].insert(inp);

}

if(i != n-1){

string stars;

cin >> stars;

}

//work

for(auto i : V){

dfs(i, i);

used.clear();

}

for(auto i : V){

cout << i << (rec[i] ? ": YES" : ": NO") << endl;

}

return 0;

}

Идея решения

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

Было решено использовать map<string,set<string>> как структуру для описания графа: каждая вершина — это строка и у каждой вершины есть множество вершин (строк), смежных с ней.
А еще задача имеет классификацию — поиск в глубину, что как бы намекает.

Related Images:

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

19/03/2015 by Бронфен-Бова Роман

Задачи: Стек, Очередь и Дек

Решение:

Код для задачи на неограниченный стек:

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

struct Node{
	Node * prev;
	int x;
	Node(){prev = nullptr; x = 0;}
	Node(Node * a, int b){prev = a; x = b;}
};

struct stack{
	private:
		Node * Head = nullptr;
		int Size = 0;
	
	public: 
	int size(){
		return Size;
	}
	void push(int p){
		Node * NewHead = new Node(Head,p);
		Head = NewHead;
		Size++;
	}
	int back(){
		if(Size){return Head->x;}
		else{return 0;}
	}
	int pop(){
		if(Size){
			int x = Head->x;
			Node * NewHead = Head->prev;
			delete Head;
			Head = NewHead;
			Size--;
			return x;
		}else{
			return 0;
		}
	}
	void clear(){
		while(Size > 0){
			Node * NewHead = Head->prev;
			delete Head;
			Head = NewHead;
			Size--;
		}
	}
};

int main() {
	stack myStack;
	while(true){
		string s; cin >> s;
		if(s == "exit"){cout << "bye\n"; break;}
		else if(s == "push"){
			int inp; cin >> inp;
			myStack.push(inp);
			cout << "ok\n";
		}else if(s == "back"){
			if(myStack.size()){
				cout << myStack.back() << endl;
			}else{
				cout << "error\n";
			}
		}else if(s == "size"){
			cout << myStack.size() << endl;
		}else if(s == "pop"){
			if(myStack.size()){
				cout << myStack.pop() << endl;
			}else{
				cout << "error\n";
			}
		}else if(s == "clear"){
			cout << "ok\n";
			myStack.clear();
		}
	}
	return 0;
}

#include <iostream>

#include <string>

using namespace std;

struct Node{

Node * prev;

int x;

Node(){prev = nullptr; x = 0;}

Node(Node * a, int b){prev = a; x = b;}

};

struct stack{

private:

Node * Head = nullptr;

int Size = 0;

public:

int size(){

return Size;

}

void push(int p){

Node * NewHead = new Node(Head,p);

Head = NewHead;

Size++;

}

int back(){

if(Size){return Head->x;}

else{return 0;}

}

int pop(){

if(Size){

int x = Head->x;

Node * NewHead = Head->prev;

delete Head;

Head = NewHead;

Size--;

return x;

}else{

return 0;

}

void clear(){

while(Size > 0){

Node * NewHead = Head->prev;

delete Head;

Head = NewHead;

Size--;

}

};

int main() {

stack myStack;

while(true){

string s; cin >> s;

if(s == "exit"){cout << "bye\n"; break;}

else if(s == "push"){

int inp; cin >> inp;

myStack.push(inp);

cout << "ok\n";

}else if(s == "back"){

if(myStack.size()){

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

}else{

cout << "error\n";

}

}else if(s == "size"){

cout << myStack.size() << endl;

}else if(s == "pop"){

if(myStack.size()){

cout << myStack.pop() << endl;

}else{

cout << "error\n";

}

}else if(s == "clear"){

cout << "ok\n";

myStack.clear();

}

return 0;

}

Код для задачи на неограниченную очередь:

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

struct Node{
	Node * prev;
	int x;
	Node(){prev = nullptr; x = 0;}
	Node(Node * a, int b){prev = a; x = b;}
};

struct queue{
	private:
		Node * Front = nullptr;
		Node * Back = nullptr;
		int Size = 0;
		
	public: 
	
	int size(){
		return Size;
	}
	void push(int p){
		if(Size == 0){
			Node * NewNode = new Node(Back,p);
			Front = NewNode;
			Back = NewNode;
		}else{
			Node * NewNode = new Node(nullptr, p);
			Back->prev = NewNode;
			Back = NewNode;
		}
		Size++;
	}
	int front(){
		if(Size){return Front->x;}
		else{return 0;}
	}
	int pop(){
		if(Size){
			int x = Front->x;
			Node * NewNode = Front->prev;
			delete Front;
			Front = NewNode;
			Size--;
			return x;
		}else{
			return 0;
		}
	}
	void clear(){
		while(Size > 0){
			Node * NewNode = Front->prev;
			delete Front;
			Front = NewNode;
			Size--;
		}
		Front = nullptr;
		Back = nullptr;
	}
};

int main() {
	queue Q;
	while(true){
		string s; cin >> s;
		if(s == "exit"){cout << "bye\n"; break;}
		else if(s == "push"){
			int inp; cin >> inp;
			Q.push(inp);
			cout << "ok\n";
		}else if(s == "front"){
			if(Q.size()){
				cout << Q.front() << endl;
			}else{
				cout << "error\n";
			}
		}else if(s == "size"){
			cout << Q.size() << endl;
		}else if(s == "pop"){
			if(Q.size()){
				cout << Q.pop() << endl;
			}else{
				cout << "error\n";
			}
		}else if(s == "clear"){
			cout << "ok\n";
			Q.clear();
		}
		
		
	}

	return 0;
}

#include <iostream>

#include <string>

using namespace std;

struct Node{

Node * prev;

int x;

Node(){prev = nullptr; x = 0;}

Node(Node * a, int b){prev = a; x = b;}

};

struct queue{

private:

Node * Front = nullptr;

Node * Back = nullptr;

int Size = 0;

public:

int size(){

return Size;

}

void push(int p){

if(Size == 0){

Node * NewNode = new Node(Back,p);

Front = NewNode;

Back = NewNode;

}else{

Node * NewNode = new Node(nullptr, p);

Back->prev = NewNode;

Back = NewNode;

}

Size++;

}

int front(){

if(Size){return Front->x;}

else{return 0;}

}

int pop(){

if(Size){

int x = Front->x;

Node * NewNode = Front->prev;

delete Front;

Front = NewNode;

Size--;

return x;

}else{

return 0;

}

void clear(){

while(Size > 0){

Node * NewNode = Front->prev;

delete Front;

Front = NewNode;

Size--;

}

Front = nullptr;

Back = nullptr;

}

};

int main() {

queue Q;

while(true){

string s; cin >> s;

if(s == "exit"){cout << "bye\n"; break;}

else if(s == "push"){

int inp; cin >> inp;

Q.push(inp);

cout << "ok\n";

}else if(s == "front"){

if(Q.size()){

cout << Q.front() << endl;

}else{

cout << "error\n";

}

}else if(s == "size"){

cout << Q.size() << endl;

}else if(s == "pop"){

if(Q.size()){

cout << Q.pop() << endl;

}else{

cout << "error\n";

}

}else if(s == "clear"){

cout << "ok\n";

Q.clear();

}

return 0;

}

Код для задачи на неограниченный дек:

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

struct Node{
	Node * prev;
	Node * next;
	int x;
	Node(){prev = nullptr; next = nullptr; x = 0;}
	Node(Node * a, Node * b, int c){prev = a; next = b; x = c;}
};

struct deque{
	private:
		Node * Front = nullptr;
		Node * Back = nullptr;
		int Size = 0;
		
	public: 
	
	int size(){
		return Size;
	}
	void push_back(int p){
		if(Size == 0){
			Node * NewNode = new Node(Back,Front,p);
			Front = NewNode;
			Back = NewNode;
		}else{
			Node * NewNode = new Node(nullptr, Back, p);
			Back->prev = NewNode;
			Back = NewNode;
		}
		Size++;
	}
	void push_front(int p){
		if(Size == 0){
			Node * NewNode = new Node(Back,Front,p);
			Front = NewNode;
			Back = NewNode;
		}else{
			Node * NewNode = new Node(Front, nullptr, p);
			Front->next = NewNode;
			Front = NewNode;
		}
		Size++;
	}
	int back(){
		if(Size){return Back->x;}
		else{return 0;}
	}
	int front(){
		if(Size){return Front->x;}
		else{return 0;}
	}
	int pop_front(){
		if(Size){
			int x = Front->x;
			Node * NewNode = Front->prev;
			delete Front;
			Front = NewNode;
			Size--;
			return x;
		}else{
			return 0;
		}
	}
	int pop_back(){
		if(Size){
			int x = Back->x;
			Node * NewNode = Back->next;
			delete Back;
			Back = NewNode;
			Size--;
			return x;
		}else{
			return 0;
		}
	}
	void clear(){
		while(Size > 0){
			Node * NewNode = Front->prev;
			delete Front;
			Front = NewNode;
			Size--;
		}
		Front = nullptr;
		Back = nullptr;
	}
};

int main() {
	deque D;
	while(true){
		string s; cin >> s;
		if(s == "exit"){cout << "bye\n"; break;}
		else if(s == "push_back"){
			int inp; cin >> inp;
			D.push_back(inp);
			cout << "ok\n";
		}else if(s == "push_front"){
			int inp; cin >> inp;
			D.push_front(inp);
			cout << "ok\n";
		}else if(s == "front"){
			if(D.size()){
				cout << D.front() << endl;
			}else{
				cout << "error\n";
			}
		}else if(s == "back"){
			if(D.size()){
				cout << D.back() << endl;
			}else{
				cout << "error\n";
			}
		}else if(s == "size"){
			cout << D.size() << endl;
		}else if(s == "pop_front"){
			if(D.size()){
				cout << D.pop_front() << endl;
			}else{
				cout << "error\n";
			}
		}else if(s == "pop_back"){
			if(D.size()){
				cout << D.pop_back() << endl;
			}else{
				cout << "error\n";
			}
		}else if(s == "clear"){
			cout << "ok\n";
			D.clear();
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

#include <iostream>

#include <string>

using namespace std;

struct Node{

Node * prev;

Node * next;

int x;

Node(){prev = nullptr; next = nullptr; x = 0;}

Node(Node * a, Node * b, int c){prev = a; next = b; x = c;}

};

struct deque{

private:

Node * Front = nullptr;

Node * Back = nullptr;

int Size = 0;

public:

int size(){

return Size;

}

void push_back(int p){

if(Size == 0){

Node * NewNode = new Node(Back,Front,p);

Front = NewNode;

Back = NewNode;

}else{

Node * NewNode = new Node(nullptr, Back, p);

Back->prev = NewNode;

Back = NewNode;

}

Size++;

}

void push_front(int p){

if(Size == 0){

Node * NewNode = new Node(Back,Front,p);

Front = NewNode;

Back = NewNode;

}else{

Node * NewNode = new Node(Front, nullptr, p);

Front->next = NewNode;

Front = NewNode;

}

Size++;

}

int back(){

if(Size){return Back->x;}

else{return 0;}

}

int front(){

if(Size){return Front->x;}

else{return 0;}

}

int pop_front(){

if(Size){

int x = Front->x;

Node * NewNode = Front->prev;

delete Front;

Front = NewNode;

Size--;

return x;

}else{

return 0;

}

int pop_back(){

if(Size){

int x = Back->x;

Node * NewNode = Back->next;

delete Back;

Back = NewNode;

Size--;

return x;

}else{

return 0;

}

void clear(){

while(Size > 0){

Node * NewNode = Front->prev;

delete Front;

Front = NewNode;

Size--;

}

Front = nullptr;

Back = nullptr;

}

};

int main() {

deque D;

while(true){

string s; cin >> s;

if(s == "exit"){cout << "bye\n"; break;}

else if(s == "push_back"){

int inp; cin >> inp;

D.push_back(inp);

cout << "ok\n";

}else if(s == "push_front"){

int inp; cin >> inp;

D.push_front(inp);

cout << "ok\n";

}else if(s == "front"){

if(D.size()){

cout << D.front() << endl;

}else{

cout << "error\n";

}

}else if(s == "back"){

if(D.size()){

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

}else{

cout << "error\n";

}

}else if(s == "size"){

cout << D.size() << endl;

}else if(s == "pop_front"){

if(D.size()){

cout << D.pop_front() << endl;

}else{

cout << "error\n";

}

}else if(s == "pop_back"){

if(D.size()){

cout << D.pop_back() << endl;

}else{

cout << "error\n";

}

}else if(s == "clear"){

cout << "ok\n";

D.clear();

}

return 0;

}

Засчитанные решения на сайте e-olimp: Стек, Очередь и Дек.

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

Однако в каждой задаче требовалось возможность использования всей оперативной памяти под структуру. В моем решении каждый элемент занимает втрое больше памяти (я подозреваю) чем обычный int, а значит всю оперативную память под числа я использовать не смогу. Тогда можно использовать заранее созданный массив достаточно большого размера, чтобы занять всю выделенную память в 256 мб. Но это не будет считаться «неограниченным» размером. А если использовать ту же структуру с Node, но вместо одного элемента хранить массив? Тогда информацию о следующем и предыдущем массиве нужно так-же хранить, как и с отдельными элементами. Вроде бы меньше памяти будет тратится на хранение дополнительной информации, НО никто не может точно сказать, какого размера массивы должны быть. Если они будут слишком маленькие — большой выгоды такой способ не принесет. Если они будут слишком большими, то есть шанс, что мы не покроем большой кусок памяти, что тоже не очень хорошо.

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

Поэтому я реализовал всё без массивов (хотя вариант с маленькими массивами имеет место быть).

Related Images:

AA21

15/03/2015 by Бронфен-Бова Роман

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

Тесты:

Ввод	Результат	Комментарий
./main «({){«	«({){«	Пройдено
./main «({}){«	«({}){)»	Пройдено
./main «)]}]([[«	«)]}([[«	Пройдено

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

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

int main(int argc, char* argv[]) {
    if(argc == 2){
        string s(argv[1]);
        int counter = 0;
        for(int i = 0; i < s.size(); i++){
            if(s[i] == '[' || s[i] == '('  || s[i] == '{') counter++;
            else if(s[i] == ']' || s[i] == ')' || s[i] == '}') counter--;
        }
        if(counter == 1){ 
            s += ')';
        }else if(counter == -1){
            int _max = s.size();
            for(int i = 0; i < s.size(); i++)
                if(s[i] == ']' || s[i] == ')' || s[i] == '}') 
                    _max = i;
            string stemp;
            for(int i = 0; i < _max; i++) stemp += s[i];
            for(int i = _max+1; i < s.size(); i++) stemp += s[i];
            s = stemp;
        }
        cout << s << endl;
    }else{
        cout << "Ошибка ввода" << endl;
    }
	return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main(int argc, char* argv[]) {

if(argc == 2){

string s(argv[1]);

int counter = 0;

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

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

else if(s[i] == ']' || s[i] == ')' || s[i] == '}') counter--;

}

if(counter == 1){

s += ')';

}else if(counter == -1){

int _max = s.size();

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

if(s[i] == ']' || s[i] == ')' || s[i] == '}')

_max = i;

string stemp;

for(int i = 0; i < _max; i++) stemp += s[i];

for(int i = _max+1; i < s.size(); i++) stemp += s[i];

s = stemp;

}

cout << s << endl;

}else{

cout << "Ошибка ввода" << endl;

}

return 0;

}

Идея решения:
Сосчитать кол-во открывающих и закрывающих скобок в одну переменную. Если текущий символ — открывающая скобка, то прибавить к переменной единицу, если закрывающая скобка, то отнять единицу. Совершать проверку переменной на равенство 1 (если на одну открывающую скобку больше) или -1 (если на одну открывающую скобку меньше).

Скриншот:

Related Images:

А407

26/11/2014 by Бронфен-Бова Роман

Задача:
Даны натуральные числа n и m, действительное число r, действительная матрица размера nxm. Получить значение [latex]{b}_{1}{r}^{n-1}+{b}_{2}{r}^{n-2}+\dots+{b}_{n}[/latex], где [latex]{b}_{k}[/latex] — первый по порядку положительный элемент в k-й строке матрицы [latex](k=1,\dots,n)[/latex]; если в k-строке нет положительных элементов, то [latex]{b}_{k}=0.5[/latex].

Тесты:

nxm	r	Матрица	Результат	Комментарий
2х2	2.5	[latex]\begin{pmatrix} -1 & 1 \\ 1 & 0 \end{pmatrix}[/latex]	3.5	Пройдено
3×4	3.14	[latex]\begin{pmatrix}5.7 & 6.7 & -7.7 & 0.9\\-3.0 & 2.3 & -5.0 & -2.4\\6.7 & 3.5 & 0.0 & 4.4\end{pmatrix}[/latex]	70.1	Пройдено
2×4	2.71	[latex]\begin{pmatrix}-9.0 &-8.8 &-7.3 & 7.5\\-6.3 &-9.7 & 6.8 &-0.5\end{pmatrix}[/latex]	27.1	Пройдено

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

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

int main() {
	int n,m; scanf("%d %d",&n,&m);
	double r; scanf("%lf",&r);
	double a[n][m];
	for(int i = 0; i < n; i++)
		for(int j = 0; j < m; j++)
			scanf("%lf", &a[i][j]);
	double sum = 0;
	for(int i = 0; i < n; i++) {
		double b = 0.5;
		for(int j = 0; j < m; j++)
			if(a[i][j]>0) {
				b = a[i][j];
				break;
			}
		sum += b*pow(r,n-i-1);
	}
	printf("%lf",sum);
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

int n,m; scanf("%d %d",&n,&m);

double r; scanf("%lf",&r);

double a[n][m];

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

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

scanf("%lf", &a[i][j]);

double sum = 0;

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

double b = 0.5;

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

if(a[i][j]>0) {

b = a[i][j];

break;

}

sum += b*pow(r,n-i-1);

}

printf("%lf",sum);

return 0;

}

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

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

class Main
{
	static Scanner sc = new Scanner(System.in);
	
	public static void main (String[] args) throws java.lang.Exception
	{
		int n, m;
		n = sc.nextInt();
		m = sc.nextInt();
		double r = sc.nextDouble();
		double[][] a = new double[n][m];
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				a[i][j] = sc.nextDouble();
			}
		}
		double sum = 0;
		for(int i = 0; i < n; i++){
			double b = 0.5;
			for(int j = 0; j < m; j++){
				if(a[i][j] > 0){
					b = a[i][j];
					break;
				}
			}
			sum += b*Math.pow(r, n-i-1);
		}
		System.out.println(sum);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static Scanner sc = new Scanner(System.in);

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

{

int n, m;

n = sc.nextInt();

m = sc.nextInt();

double r = sc.nextDouble();

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

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

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

a[i][j] = sc.nextDouble();

}

double sum = 0;

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

double b = 0.5;

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

if(a[i][j] > 0){

b = a[i][j];

break;

}

sum += b*Math.pow(r, n-i-1);

}

System.out.println(sum);

}

Идея решения:
Считать n, m как целочисленные переменные. После этого считать r как переменную типа double. Следующим считать массив nxm созданный благодаря генератору матриц из случайных чисел заданного размера. Завести переменную [latex]sum = 0[/latex] для хранения результата. Проверять построчно каждый столбик на наличие положительного числа и прибавить первое положительное число в строке, умноженное на [latex]{r}^{n-i-1}[/latex], к результаты. В случает отсутствия положительного элемента в строке, брать 0.5. В конце вывести результат.

Related Images:

А165б

21/10/2014 by Бронфен-Бова Роман

Задача:
Даны действительные числа [latex]{a}_{1},{a}_{2},\dots[/latex] . Известно, что [latex]{a}_{1}>0[/latex] и что среди [latex]{a}_{2},{a}_{3},\dots[/latex] есть хотя бы одно отрицательное число. Пусть [latex]{a}_{1},\dots,{a}_{n}[/latex] – члены данной последовательности, предшествующие первому отрицательному члену (n заранее неизвестно). Получить:
б) [latex]{a}_{1}{a}_{2}\dots{a}_{n}[/latex];

Тесты:

Последовательность	[latex]{a}_{1}{a}_{2}\dots{a}_{n}[/latex]	Комментарий
1 2 3 4 -1 2	24	Пройден
0.5 0.4 0.3 0.2 0.1 -0.1 -0.2 -0.3	0.0012	Пройден
1.5 -1 50	1.5	Пройден
1 2 3 4 3 2 1 0 -1	0	Пройден

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

#include <iostream>
using namespace std;

int main() {
	double mul = 1; //Произведение
	double x;
	while(cin >> x && x>=0)	mul *= x;
	cout << mul;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double mul = 1; //Произведение

double x;

while(cin >> x && x>=0) mul *= x;

cout << mul;

return 0;

}

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

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

class Main
{
	static Scanner sc = new Scanner(System.in);
	
	public static void main (String[] args) throws java.lang.Exception
	{
		double mul = 1;
		double x;
		while(sc.hasNext()){
			x = sc.nextDouble();
			if(x < 0){
				break;
			}
			mul *= x;
		}
		System.out.println(mul);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static Scanner sc = new Scanner(System.in);

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

{

double mul = 1;

double x;

while(sc.hasNext()){

x = sc.nextDouble();

if(x < 0){

break;

}

mul *= x;

}

System.out.println(mul);

}

Идея решения:
Считывать числа с потока ввода. Если считанное число отрицательное, остановится и вывести накопленное произведение на экран. Иначе умножить произведение на очередное число.

Related Images:

Ю11.12

21/10/2014 by Бронфен-Бова Роман

Задача:
Интерполяционный многочлен Лагранжа. Значения функции [latex]y=f\left(x\right)[/latex] заданы таблично в массиве [latex]Y\left(x\right)[/latex] при соответствующих значениях аргумента в упорядоченном массиве [latex]X\left(x\right)[/latex]. Найти значение функции в произвольной точке [latex]x[/latex] по формуле Лагранжа:
[latex]y={L}_{n}\left(x\right)=\sum _{i=1}^{n}{{y}_{i}\prod _{\underset{j\neq i}{j=1}}^{n}{\frac{x-{x}_{j}}{{x}_{i}-{x}_{j}}}}[/latex]

Вводимые значения:

X:	-1	0	1	2
Y:	1	2	3	-1

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

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

double LP(double x, vector<double> xv, vector<double> yv) { //Lagrange polynomial
	int size = xv.size(); //Количество точек (для удобства)
	double sum = 0; //Значение функции
	for(int i = 0; i < size; i++){
		double mul = 1; //Произведение
		for(int j = 0; j < size; j++){
			if(i!=j) mul *= (x - xv[j])/(xv[i]-xv[j]);
		}
		sum += yv[i]*mul;
	}
	return sum;
}

int main() {
	int counter = 0;
	double a = -3; //Левая грань
	double b = 3; //Правая грань
	int fragments = 101; //Разбиение
	vector<double> xv {};
	vector<double> yv {};
	double inp;
	while(cin >> inp) counter++%2 ? yv.push_back(inp) : xv.push_back(inp); //Заполнение
	for(int i = 0; i < fragments; i++){
		double x = a + (b-a)/(fragments-1)*i;
		printf("%6.3lf\t%6.3lf\n", x, LP(x, xv, yv));
	}
	return 0;
}

#include <iostream>

#include <vector>

using namespace std;

double LP(double x, vector<double> xv, vector<double> yv) { //Lagrange polynomial

int size = xv.size(); //Количество точек (для удобства)

double sum = 0; //Значение функции

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

double mul = 1; //Произведение

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

if(i!=j) mul *= (x - xv[j])/(xv[i]-xv[j]);

}

sum += yv[i]*mul;

}

return sum;

}

int main() {

int counter = 0;

double a = -3; //Левая грань

double b = 3; //Правая грань

int fragments = 101; //Разбиение

vector<double> xv {};

vector<double> yv {};

double inp;

while(cin >> inp) counter++%2 ? yv.push_back(inp) : xv.push_back(inp); //Заполнение

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

double x = a + (b-a)/(fragments-1)*i;

printf("%6.3lf\t%6.3lf\n", x, LP(x, xv, yv));

}

return 0;

}

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
 
	static double LP(double x, double[] xv, double[] yv){
		int size = xv.length;
		double sum = 0;
		for(int i = 0; i < size; i++){
			double mul = 1;
			for(int j = 0; j < size; j++){
				if(i != j){
					mul *= (x-xv[j])/(xv[i]-xv[j]);
				}
			}
			sum += yv[i]*mul;
		}
		return sum;
	}
 
	static Scanner sc = new Scanner(System.in);
 
	public static void main (String[] args) throws java.lang.Exception
	{
		int counter = 0;
		double a = -3;
		double b = 3;
		int fragments = 101;
		ArrayList<Double> xvinp = new ArrayList<Double>();
		ArrayList<Double> yvinp = new ArrayList<Double>();
		double[] xv;
		double[] yv;
		while(sc.hasNext()){
			double inp = sc.nextDouble();
			if(counter%2 == 0){
				xvinp.add(inp);
			}else{
				yvinp.add(inp);
			}
			counter++;
		}
		xv = new double[xvinp.size()];
		yv = new double[yvinp.size()];
		for(int i = 0; i < xvinp.size(); i++){
			xv[i] = xvinp.get(i);
			yv[i] = yvinp.get(i);
		}
		for(int i = 0; i < fragments; i++){
			double x = a + (b-a)/(fragments-1)*i;
			System.out.println(x + "\t" + LP(x, xv, yv));
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

static double LP(double x, double[] xv, double[] yv){

int size = xv.length;

double sum = 0;

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

double mul = 1;

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

if(i != j){

mul *= (x-xv[j])/(xv[i]-xv[j]);

}

sum += yv[i]*mul;

}

return sum;

}

static Scanner sc = new Scanner(System.in);

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

{

int counter = 0;

double a = -3;

double b = 3;

int fragments = 101;

ArrayList<Double> xvinp = new ArrayList<Double>();

ArrayList<Double> yvinp = new ArrayList<Double>();

double[] xv;

double[] yv;

while(sc.hasNext()){

double inp = sc.nextDouble();

if(counter%2 == 0){

xvinp.add(inp);

}else{

yvinp.add(inp);

}

counter++;

}

xv = new double[xvinp.size()];

yv = new double[yvinp.size()];

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

xv[i] = xvinp.get(i);

yv[i] = yvinp.get(i);

}

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

double x = a + (b-a)/(fragments-1)*i;

System.out.println(x + "\t" + LP(x, xv, yv));

}

Идея решения:
Использование отдельной функции, которой надо передать 3 параметра: значение аргумента, массив исходных значений аргумента и массив исходных значений функции при соответствующих аргументах. Эта функция возвращает значение многочлена Лагранжа при подстановки вместо [latex]x[/latex] конкретного значения.

В функции был использован внешний цикл for для вычисления суммы в формуле и внутренний цикл for для вычисления произведения [latex]\prod _{\underset{j\neq i}{j=1}}^{n}{\frac{x-{x}_{j}}{{x}_{i}-{x}_{j}}}[/latex].

В программе мы разбиваем отрезок [-3, 3] на 101 отдельную точку и вычисляем значение полинома Лагранжа для каждой из этих точек. Выводим на экран.

График:

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

Related Images:

Skynet: the Virus

14/10/2014 by Бронфен-Бова Роман

SKYNET FINALE — LEVEL 1

Los Angeles 2029 — Resistance HQ — Review of facts:

В минувшую субботу, сотни отважных бойцов рисковали своей жизнью, чтобы уничтожить Skynet. СТОП

Используя зараженных мото-терминаторов, им удалось привить смертельный вирус к Skynet. СТОП

Проблема: Skynet борется. СТОП

Джон, ещё раз, нам нужна ваша помощь. СТОП

Задача:

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

Первичная инициализация:

Первая строка: 3 целых числа N L E

N — Количество узлов, включая шлюзы
L — Количество связей
E — Количество шлюзов

Следующие L строк: по два числа на строку (N1, N2), означающие, что между узлами с индексами N1 и N2 присутствует связь.
Следующие E строк: по одному числу на строку, означающие индексы шлюзов.

Инициализация за каждый игровой тик:

Одно число — индекс связи, на которой находится Skynet агент.

Вывод за каждый игровой тик:

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

Программа:

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

using namespace std;

int main()
{
    int N; //Количество узлов, включая шлюзы
    int L; //Количество связей
    int E; //Количество шлюзов
    cin >> N >> L >> E; cin.ignore();
    
    int N1[L][2]; // Массив для связей
    for (int i = 0; i < L; i++) {
        cin >> N1[i][0] >> N1[i][1]; cin.ignore();
    }
    
    int EI[E]; // Индексы шлюзов
    for (int i = 0; i < E; i++) {
        cin >> EI[i]; cin.ignore();
    }
    
    // Алгоритм сортировки (его достаточно)
    for(int i = 0; i < L; i++){
        for(int k =0; k < E; k++){
            if(N1[i][1] == EI[k]) swap(N1[i][1],N1[i][0]);
        }
    }

    // игровой цикл
    while (1) {
        int SI; //Индекс связи, на которой находится Агент
        cin >> SI; cin.ignore();

        bool AgentIsNear = false; //Агент возле шлюза!
        
        for(int i = 0; i < L; i++){
            bool T = false; //Для прерывания цикла
            for(int k = 0; k < E; k++){
                if(EI[k] == N1[i][0] && SI == N1[i][1]){
                    cout << EI[k] << ' ' << SI << endl;
                    N1[i][0] = -1;
                    AgentIsNear = true;
                    T = true;
                    break;
                }
            }
            if(T) break;
        }
        
        if(!AgentIsNear){
            for(int i = 0; i < L; i++){
                bool T = false; //Для прерывания цикла
                for(int k = 0; k < E; k++){
                    if(N1[i][0] == EI[k]){
                        cout << EI[k] << ' ' << N1[i][1] << endl;
                        N1[i][0] = -1;
                        T = true;
                        break;
                    }
                }
                if(T) break;
            }
        }
        
    }
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

int N; //Количество узлов, включая шлюзы

int L; //Количество связей

int E; //Количество шлюзов

cin >> N >> L >> E; cin.ignore();

int N1[L][2]; // Массив для связей

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

cin >> N1[i][0] >> N1[i][1]; cin.ignore();

}

int EI[E]; // Индексы шлюзов

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

cin >> EI[i]; cin.ignore();

}

// Алгоритм сортировки (его достаточно)

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

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

if(N1[i][1] == EI[k]) swap(N1[i][1],N1[i][0]);

}

// игровой цикл

while (1) {

int SI; //Индекс связи, на которой находится Агент

cin >> SI; cin.ignore();

bool AgentIsNear = false; //Агент возле шлюза!

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

bool T = false; //Для прерывания цикла

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

if(EI[k] == N1[i][0] && SI == N1[i][1]){

cout << EI[k] << ' ' << SI << endl;

N1[i][0] = -1;

AgentIsNear = true;

T = true;

break;

}

if(T) break;

}

if(!AgentIsNear){

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

bool T = false; //Для прерывания цикла

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

if(N1[i][0] == EI[k]){

cout << EI[k] << ' ' << N1[i][1] << endl;

N1[i][0] = -1;

T = true;

break;

}

if(T) break;

}

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

Переходы между узлами занесены в двумерный массив N1, далее этот массив был своеобразно отсортирован (для удобства). В игровом цикле объявляем булевую переменную AgentIsNear — агент вблизи шлюза.

Первый цикл: Проверяем каждую клетку вокруг каждого шлюза на присутствие там агента. И если он таки там есть, блокируем переход, меняем первую переменную (отвечающую за шлюз) в массиве переходов (N1) на -1 (значение, которое никогда не встретится), изменяем AgentIsNear на true и прерываем цикл.

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

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

Программа проходит все тесты на MEDIUM и, что удивительно, половину тестов на HARD! Взято с CodinGame

Related Images:

Ю3.39

12/10/2014 by Бронфен-Бова Роман

Задача: Численно убедиться в справедливости равенства [latex]\frac{1}{4}\ln{\frac{1+x}{1-x}}+\frac{1}{2}\arctan{x}=\quad x+\frac{{x}^{5}}{5}+\dots+\frac{{x}^{4n+1}}{4n+1}+\dots[/latex], для чего для заданного значения аргумента [latex]x[/latex] вычислить левую его часть и разложение, стоящее в правой части, с заданной погрешностью [latex]e[/latex]. Испытать разложение на сходимость при разных значениях аргумента, оценить скорость сходимости, для чего вывести число итераций [latex]n[/latex] слагаемых, необходимых, для достижения заданной точности. Интервал для этой задачи: [latex]-1<x<1[/latex].

Ввод		Вывод
[latex]x[/latex]	Погрешность	Output	Комментарий
-0.99	1e-4	148	Пройден
0.99	1e-4	148	Пройден
0.99	1e-14	685	Пройден
0.7	1e-10	14	Пройден
-0.3	1e-13	6	Пройден
0.001	1e-13	1	Пройден

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

int main() {
	double x, e; //Переменная и погрешность
	scanf("%lf %le", &x, &e);
	double curr = 1./4.*log((1.+x)/(1.-x)) + (1./2.)*atan(x);  //Левая часть выражения
	int count = 0; //Счетчик
	double y = x; //i-тое слагаемое
	double sum = x; //Сумма
	for(; fabs(sum-curr) > e; count++){
		double n = (4.*count+1.)/(4.*count+5.);
		y = y*x*x*x*x*n;
		sum += y;
	}
	count++;
	printf("%d", count);
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

double x, e; //Переменная и погрешность

scanf("%lf %le", &x, &e);

double curr = 1./4.*log((1.+x)/(1.-x)) + (1./2.)*atan(x); //Левая часть выражения

int count = 0; //Счетчик

double y = x; //i-тое слагаемое

double sum = x; //Сумма

for(; fabs(sum-curr) > e; count++){

double n = (4.*count+1.)/(4.*count+5.);

y = y*x*x*x*x*n;

sum += y;

}

count++;

printf("%d", count);

return 0;

}

Идея решения: Используем цикл for, в условие которого ставим проверку на превышение погрешности суммы. Левую часть выражения вычисляем и записываем в переменную [latex]curr[/latex]. Сумму (то что стоит в правой части выражения) объявим как [latex]sum[/latex], и инициализируем значением [latex]x[/latex] (Это делается для того, чтобы во время работы цикла не вычислялось одно лишнее слагаемое).

Каждую итерацию цикла инкрементируем счетчик [latex]count[/latex]. Переменную [latex]y[/latex], которая соответствует i-тому слагаемому суммы, увеличивают до значения следующего слагаемого и прибавляют к сумме. Далее проверяем разность частичной суммы и заданного значения [latex]curr[/latex]. Если эта разность будет удовлетворять нашей точности, то число [latex]count[/latex] и будет количеством слагаемых в правой части.

Замечание: После цикла значение [latex]count[/latex] вновь инкрементируется, это сделано по следующей причине: сумма изначально содержала в себе первое слагаемое. Если сумма бы изначально содержала в себе 0, то нам пришлось бы вычислять лишнее слагаемое.

Ideone

Related Images:

Ю3.17

09/10/2014 by Бронфен-Бова Роман

Задача: Сколько сомножителей надо взять в произведении: [latex]\prod_{k=1}^{\infty}{(1+\frac{{(-1)}^{k}}{2k+1})}=\frac{\sqrt{2}}{2}[/latex], чтобы равенство выполнялось до шестой значащей цифры, то есть с погрешностью не более [latex]{10}^{-6}[/latex]

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

int main() {
	double curr = sqrt(2.0)/2; //Переменная для сравнения
	double mul = 1;   //Произведение
	double e = 1.0e-6;  //Точность
	int count = 1; //Счетчик
	for(;fabs(mul - curr) > e;count++){
		mul *= (1. + (count % 2 ? (-1) : 1)/(2.*count + 1));
	}
	printf("%d",count); 
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

double curr = sqrt(2.0)/2; //Переменная для сравнения

double mul = 1; //Произведение

double e = 1.0e-6; //Точность

int count = 1; //Счетчик

for(;fabs(mul - curr) > e;count++){

mul *= (1. + (count % 2 ? (-1) : 1)/(2.*count + 1));

}

printf("%d",count);

return 0;

}

Идея решения: Используем цикл for, в качестве [latex]k[/latex] в формуле используем переменную [latex]count[/latex] в программе. Переменную, которая будет соответствовать произведению, назовем [latex]mul[/latex] (сокращенно от multiplication) и присвоим ей значение 1 как нейтральный элемент для операции умножения. Каждую итерацию цикла проверяем разность [latex]mul-curr[/latex], где [latex]curr=\frac{\sqrt{2}}{2}[/latex], на превышение погрешности [latex]{10}^{-6}[/latex].

Если разность больше точности, умножаем [latex]mul[/latex] на выражение под знаком произведения и увеличиваем [latex]count[/latex] на единицу.

Если разность меньше точности, число [latex]count[/latex] и будет количеством сомножителей в произведении.

Число сомножителей оказалось достаточно большим — 88390. Ideone

Related Images:

А34б

26/09/2014 by Бронфен-Бова Роман

Задача: Даны действительные числа [latex]x,y,z[/latex] Вычислить:
[latex]\min\left(x,y,z\right)[/latex] [latex]\max\left(x,y,z\right)[/latex]

Ввод			Вывод
[latex]x[/latex]	[latex]y[/latex]	[latex]z[/latex]	Output	Комментарий
0	0	0	Max — 0 Min — 0	Пройден
1	2	3	Max — 3 Min — 1	Пройден
3	2	1	Max — 3 Min — 1	Пройден
10.1	10.01	10.001	Max — 10.1 Min — 10.001	Пройден
12345.12345	12345.123445	12345.12346	Max — 12345.123456 Min — 12345.123445	Пройден
0.001	0.0009	0.00099	Max — 0.001 Min — 0.0009	Пройден

#include <iostream>

int main() {
	double x, y, z;
	scanf("%lf %lf %lf", &x, &y, &z);
	double min = (x<y) ? (x<z ? x : z) : (y<z ? y : z);
	double max = (x>y) ? (x>z ? x : z) : (y>z ? y : z);
	printf("Максимум - %lf, Минимум - %lf", max, min);
	return 0;
}

#include <iostream>

int main() {

double x, y, z;

scanf("%lf %lf %lf", &x, &y, &z);

double min = (x<y) ? (x<z ? x : z) : (y<z ? y : z);

double max = (x>y) ? (x>z ? x : z) : (y>z ? y : z);

printf("Максимум - %lf, Минимум - %lf", max, min);

return 0;

}

Идея решение: Сохранить в переменную [latex]\min[/latex] и [latex]\max[/latex] числа, соответствующие минимальному и максимальному из данного набора, полученных путем (довольно сложных) вычислений с применением вложенных в тернарные операции тернарных операций.

Related Images:

Ю2.13

26/09/2014 by Бронфен-Бова Роман

Задача: Проверить, лежит ли окружность [latex]{(x-{a}_{1})}^{2}+{(y-{b}_{1})}^{2}={r}_{1}^{2}[/latex] целиком внутри окружности [latex]{(x-{a}_{2})}^{2}+{(y-{b}_{2})}^{2}={r}_{2}^{2}[/latex] или наоборот.

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

Ввод						Вывод
[latex]a_{1}[/latex]	[latex]b_{1}[/latex]	[latex]r_{1}[/latex]	[latex]a_{2}[/latex]	[latex]b_{2}[/latex]	[latex]r_{2}[/latex]	Печать	Комментарий
0	0	0	0	0	0	2 в 1	Пройден
0	0	3	0	0	1	2 в 1	Пройден
0	0	2	0	0	5	1 в 2	Пройден
1	1	3	3	1	1	2 в 1	Пройден
2	2	3	6	2	4	——	Пройден
24	27	51	96	48	20	——	Пройден

Код:

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

int main() {
	int a1, b1, r1, a2, b2, r2;
	scanf("%d %d %d %d %d %d", &a1, &b1, &r1, &a2, &b2, &r2);
	double dist = sqrt((a1-a2)*(a1-a2)+(b1-b2)*(b1-b2));
	if(dist <= abs(r2 - r1)){
		printf((r1 < r2) ? "Окружность 1 лежит в окружности 2" : "Окружность 2 лежит в окружности 1");
	}
	else printf("Ничто ни в чем не лежит\n");
	return 0;
}

#include <iostream>

#include <math.h>

int main() {

int a1, b1, r1, a2, b2, r2;

scanf("%d %d %d %d %d %d", &a1, &b1, &r1, &a2, &b2, &r2);

double dist = sqrt((a1-a2)*(a1-a2)+(b1-b2)*(b1-b2));

if(dist <= abs(r2 - r1)){

printf((r1 < r2) ? "Окружность 1 лежит в окружности 2" : "Окружность 2 лежит в окружности 1");

}

else printf("Ничто ни в чем не лежит\n");

return 0;

}

Идея решение: Расстояние между центрами окружностей [latex]({a}_{1};{b}_{1})[/latex] и [latex]({a}_{2};{b}_{2})[/latex] должно быть меньше, чем модуль разности их радиусов [latex]\left|{r}_{1}-{r}_{2}\right|[/latex]. Это условие необходимо и достаточно для того, чтобы одна из окружностей была вложена в другую.

Related Images:

Ю1.5

19/09/2014 by Бронфен-Бова Роман

Задача: в такси одновременно сели три пассажира. Когда вышел первый пассажир, на счетчике было [latex]p_{1}[/latex] рублей; когда вышел второй — [latex]p_{2}[/latex] рублей. Сколько должен был заплатить каждый пассажир, если по окончании поездки счетчик показал [latex]p_{3}[/latex] рублей? Плата за посадку составляет [latex]p_{0}[/latex] рублей.

Ввод				Вывод
[latex]p_{0}[/latex]	[latex]p_{1}[/latex]	[latex]p_{2}[/latex]	[latex]p_{3}[/latex]	[latex]op_{1}[/latex]	[latex]op_{2}[/latex]	[latex]op_{3}[/latex]	Комментарий
0	0	0	0	0.00	0.00	0.00	Пройден
6	1	2	3	2.33	2.83	3.83	Пройден
7	2	5	16	3.00	4.50	15.50	Пройден
1	1	1	1	0,67	0,67	0,67	Пройден
150	1138	2590	5788	429.33	1155.33	4353.33	Пройден
3	0	0	6	1.00	1.00	7.00	Пройден

[latex]p_{0}[/latex], [latex]p_{1}[/latex], [latex]p_{2}[/latex], [latex]p_{3}[/latex] — целые числа, хоть и определены как double, всё равно это целые числа. У таксиста просто такой счетчик.

#include <iostream>

int main() {
	double p0, p1, p2, p3;		//Поездка
	double op1, op2, op3; 		//Оплата
	
	scanf("%lf %lf %lf %lf", &p0, &p1, &p2, &p3);
	
	op1 = p0/3 + p1/3;
	op2 = p0/3 + p1/3 + (p2-p1)/2;
	op3 = p0/3 + p1/3 + (p2-p1)/2 + (p3-p2);
	
	printf("Первый заплатил %5.3lf\n",op1);	
	printf("Второй заплатил %5.3lf\n",op2);
	printf("Третий заплатил %5.3lf\n",op3);
	
	return 0;
}

#include <iostream>

int main() {

double p0, p1, p2, p3; //Поездка

double op1, op2, op3; //Оплата

scanf("%lf %lf %lf %lf", &p0, &p1, &p2, &p3);

op1 = p0/3 + p1/3;

op2 = p0/3 + p1/3 + (p2-p1)/2;

op3 = p0/3 + p1/3 + (p2-p1)/2 + (p3-p2);

printf("Первый заплатил %5.3lf\n",op1);

printf("Второй заплатил %5.3lf\n",op2);

printf("Третий заплатил %5.3lf\n",op3);

return 0;

}

Идея решение: Первый участок проехали трое и расходы делятся на троих ([latex]\frac { { p }_{ 1 } }{ 3 }[/latex]). Второй участок – двое, значит за него двое платят поровну ([latex]\frac{{p}_{2}-{p}_{1}}{2}[/latex]). Последний участок проехал один, ему за него и платить ([latex]{p}_{3}-{p}_{2}[/latex]). Оплатой за поездку для каждого является сумма стоимости каждого пути до его остановки.