e-olymp 107. Компакт-диски

14/09/2015 by Настя Панько

Чистые компакт-диски продают в трёх видах упаковок. Упаковка из 100 дисков стоит 100 грн., из 20 дисков — 30 грн., а один диск стоит 2грн. Какую минимальную сумму нужно истратить для покупки [latex]N[/latex] таких дисков?

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

Единственное число [latex]N[/latex] — количество дисков. Значение [latex]N[/latex] натуральное, не больше 1000.

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

Искомая минимальная сумма в гривнах.

Тесты

Вход	Выход
123	136
130	150
140	160
23	36
132	154
170	200
148	176

Код

#include<iostream>
using namespace std;

int main ()
{
    int N, price;
    cin >> N;
    if (N % 100 > 65)
        price += (N / 100 + 1) * 100;
    else
    {
        int a = N % 100;
        price += (N/100) * 100;
        if (a % 20 > 15)
            price += (a / 20 + 1) * 30;
        else
        {
            int b = (a % 20);
            price += (a / 20) * 30;
            price += b*2;
        }
    }
    cout << price;
    return 0;
}

#include<iostream>

using namespace std;

int main ()

{

int N, price;

cin >> N;

if (N % 100 > 65)

price += (N / 100 + 1) * 100;

else

{

int a = N % 100;

price += (N/100) * 100;

if (a % 20 > 15)

price += (a / 20 + 1) * 30;

else

{

int b = (a % 20);

price += (a / 20) * 30;

price += b*2;

}

cout << price;

return 0;

}

Решение

Пусть задано число N — количество дисков и цена N таких дисков. Используем if-блок, для того, чтобы вычислить минимальную сумму дисков. Присваиваем 100 дискам целочисленные значения N. Увеличиваем цену 100 дисков. Вводим а — упаковка из 20 дисков. Присваиваем числу а целочисленные значения N. С помощью if-блока увеличиваем цену 20-ти дисков. Вводим b — один диск. Увеличиваем цену одного диска.

Решение принято на сайте e-olymp.com.

Выполнить код программы можно здесь.

Related Images:

А412в

12/11/2014 by Карагяур Мілан Сергійович

Задача: Даны две целочисленные квадратные матрицы порядка 6. Найти последовательность из нулей и единиц [latex]b_{1},\ldots,b_{6}[/latex] такую, что [latex]b_{i}=1[/latex], когда:

в)[latex]i[/latex]-e строки первой и второй матриц содержат вместе не более трех положительных элементов;

Первая матрица	Вторая матрица	[latex]b_{1},\ldots,b_{6}[/latex]
2 4 5 -1 -2 -3 -1 -2 -3 1 -3 -2 2 4 5 -1 -2 -3 2 4 5 -1 -2 -3 -1 -2 -3 1 -3 -2 2 4 5 -1 -2 -3	2 4 5 -1 -2 -3 -1 -2 -3 1 -3 -2 2 4 5 -1 -2 -3 2 4 5 -1 -2 -3 -1 -2 -3 1 -3 -2 2 4 5 -1 -2 -3	010010
8 5 -2 -4 -2 -1 -1 -2 0 1 0 2 11 -4 6 0 0 -3 1 3 -5 0 2 -3 -11 0 -3 1 -3 -2 1 -4 4 0 0 0	0 0 0 0 0 0 -7 -4 -5 1 -4 -2 2 -4 0 -1 -2 -3 3 1 -5 9 -6 -7 -1 -2 -3 0 -3 2 2 4 5 5 7 8	111010

#include <iostream>
using namespace std;

const int n = 6 ;
 
int Read(int a[n][n])
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cin >> a[i][j];
		}	
	}
}
 
int main() {
	int a[n][n];
	int b[n][n];
	int c[n];
	int count = 0;
	Read(a);
	Read(b);
	for (int i = 0; i < n; i++)
	{
		count = 0;
		for (int j = 0; j < n; j++)
		{
			if (a[i][j]>0) count++;
			if (b[i][j]>0) count++;
		}	
		c[i] = count <= 3? 1: 0;
	}
	for (int j = 0; j < n; j++)
		{
			cout<<c[j];
		}	
	
	return 0;
}

#include <iostream>

using namespace std;

const int n = 6 ;

int Read(int a[n][n])

{

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

{

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

{

cin >> a[i][j];

}

int main() {

int a[n][n];

int b[n][n];

int c[n];

int count = 0;

Read(a);

Read(b);

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

{

count = 0;

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

{

if (a[i][j]>0) count++;

if (b[i][j]>0) count++;

}

c[i] = count <= 3? 1: 0;

}

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

{

cout<<c[j];

}

return 0;

}

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

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

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

class Main
{

	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int n = 6 ;
		int[][]a=new int[n][n];
		int[][]b=new int[n][n];
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				a[i][j]=in.nextInt();
			}	
		}
		for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < n; j++)
			{
				b[i][j]=in.nextInt();
			}	
		}
		int[]c=new int[n];
		int count = 0;
		for (int i = 0; i < n; i++)
		{
			count = 0;
			for (int j = 0; j < n; j++)
			{
				if (a[i][j]>0) count++;
				if (b[i][j]>0) count++;
			}	
			c[i] = count <= 3? 1: 0;
		}
		for (int j = 0; j < n; j++)
			{
				System.out.print(c[j]);
			}	
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

int n = 6 ;

int[][]a=new int[n][n];

int[][]b=new int[n][n];

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

{

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

{

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

}

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

{

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

{

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

}

int[]c=new int[n];

int count = 0;

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

{

count = 0;

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

{

if (a[i][j]>0) count++;

if (b[i][j]>0) count++;

}

c[i] = count <= 3? 1: 0;

}

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

{

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

}

Ideone.

Related Images:

А60д

30/10/2014 by Ковальський Олександр Дмитрович

Задача.

Пусть D — заштрихованная часть плоскости и пусть u определяется по x и y следующим образом :

[latex]u=\begin{cases} \sqrt{|x^{2}-1|} & \text{ if } (x, y)\epsilon D \\ x+y & \end{cases}[/latex]

Даны действительные числа x и y. Определить u.

Тесты.

Ввод		Вывод
x	y	u
0	0	1
0	0.5	1
-0.3	0.6	0.953939
0.3	0.6	0.953939
-0.2	-0.1	-0.3
0.8	0.6	1.4
0.5	-0.5	0

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

int main() 
	{
		double x,y;
		cin>>x>>y;
		cout<< (((x*x+y*y<=1)&&(y>=fabs(x))) ? sqrt(abs(x*x-1)):x+y) <<endl;
		return 0;
	}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double x,y;

cin>>x>>y;

cout<< (((x*x+y*y<=1)&&(y>=fabs(x))) ? sqrt(abs(x*x-1)):x+y) <<endl;

return 0;

}

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

class Ideone
{
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
        double x = in.nextDouble(),y = in.nextDouble();
		System.out.println(((x * x + y * y <= 1) && (y >= Math.abs(x))) ? Math.sqrt(Math.abs(x * x - 1)) : x + y);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

double x = in.nextDouble(),y = in.nextDouble();

System.out.println(((x * x + y * y <= 1) && (y >= Math.abs(x))) ? Math.sqrt(Math.abs(x * x - 1)) : x + y);

}

Решение.

Через переменные x, y обозначим координаты точки.

Мы имеем 3 графика функций:

[latex]y=-x[/latex]
[latex]y=x[/latex]
[latex]x^{2}+y^{2}=1[/latex]

Проверяем находится ли точка в заштрихованной области. Точка обязательно должна находиться над или на оси x.

Если точка принадлежит данной области то для расчёта u используем формулу:

[latex]\sqrt{|x^{2}-1|}[/latex]

В противном случае формулу:

[latex]u=x+y[/latex]

Related Images:

Ragnarök — Power of Thor

14/10/2014 by Вустянюк Ігор Дмитрович

Задача

Есть Тор. А у Тора был источник силы. Больше нет. Тор движется по прямоугольному полю и ему известны его координаты и координаты источника. Наша задача: за наименьшее количество ходов привести Тора к источнику. Допустимые варианты движения приведены на картинке ниже:

Инициализация

Одна строка, в которой даны четыре целых числа: LX, LY, TX, TY — соответственно абсцисса и ордината источника, абсцисса и ордината начального положения Тора.

Инициализация

Входные данные для одного игрового хода

Уровень энергии Тора. Нам он не понадобится.

Выходные данные для одного игрового хода

Одна из следующих строк: «N», «NE», «E», «SE», «S», «SW», «W», «NW», указывающая в каком направлении Тору нужно переместиться.

Решение

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

Во-первых, нужно учесть, что ордината растёт в южном, а не в северном направлении, как обычно:

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

Код на С++

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int LX; // абсцисса источника энергии
    int LY; // ордината источника энергии
    int TX; // абсцисса Тора
    int TY; // ордината Тора
    cin >> LX >> LY >> TX >> TY;

    while (1) {
        int E;
        cin >> E;
        string hor;     // Куда нужно двигаться Тору по оси абсцисс
        string ver;     // Куда нужно двигаться Тору по оси ординат
        // Определяем, куда нужно двигаться Тору по оси Х
        if (TX == LX)           // Если абсцисса Тора совпадает с абсциссой источника,
            hor = "";		// её менять не нужно
        else {				
            if (TX < LX) {	// Если абсцисса Тора МЕНЬШЕ абсциссы источника,
                hor = "E";	// УВЕЛИЧИМ её, т.е. двинемся на ВОСТОК
                TX++;		// Фиксируем изменение положения Тора
            }
            else {		// Если абсцисса Тора БОЛЬШЕ абсциссы источника, 
                hor = "W";	// УМЕНЬШИМ её, т.е. двинемся на ЗАПАД
                TX--;		// Фиксируем изменение положения Тора
            }
        }
        // Определяем, куда нужно двигаться Тору по оси Y
        if (TY == LY)		// Если ордината Тора совпадает с ординатой источника,
            ver = "";           // её менять не нужно
        else {
            if (TY < LY) {	// Если ордината Тора меньше ординаты источника,
                ver = "S";	// УВЕЛИЧИМ её, т.е. двинемся на ЮГ
                TY++;		// Фиксируем изменение положения Тора 
            }
            else {		// Если ордината Тора больше ординаты источника,
                ver = "N";	// УМЕНЬШИМ её, т.е. двинемся на СЕВЕР
                TY--;		// Фиксируем изменение положения Тора
            }
        }     
        cout << ver + hor << endl; // Склеиваем наши строки-"сдвиги" и выводим окончательный сдвиг
    }
}

#include <iostream>

#include <string>

using namespace std;

int main()

{

int LX; // абсцисса источника энергии

int LY; // ордината источника энергии

int TX; // абсцисса Тора

int TY; // ордината Тора

cin >> LX >> LY >> TX >> TY;

while (1) {

int E;

cin >> E;

string hor; // Куда нужно двигаться Тору по оси абсцисс

string ver; // Куда нужно двигаться Тору по оси ординат

// Определяем, куда нужно двигаться Тору по оси Х

if (TX == LX) // Если абсцисса Тора совпадает с абсциссой источника,

hor = ""; // её менять не нужно

else {

if (TX < LX) { // Если абсцисса Тора МЕНЬШЕ абсциссы источника,

hor = "E"; // УВЕЛИЧИМ её, т.е. двинемся на ВОСТОК

TX++; // Фиксируем изменение положения Тора

}

else { // Если абсцисса Тора БОЛЬШЕ абсциссы источника,

hor = "W"; // УМЕНЬШИМ её, т.е. двинемся на ЗАПАД

TX--; // Фиксируем изменение положения Тора

}

// Определяем, куда нужно двигаться Тору по оси Y

if (TY == LY) // Если ордината Тора совпадает с ординатой источника,

ver = ""; // её менять не нужно

else {

if (TY < LY) { // Если ордината Тора меньше ординаты источника,

ver = "S"; // УВЕЛИЧИМ её, т.е. двинемся на ЮГ

TY++; // Фиксируем изменение положения Тора

}

else { // Если ордината Тора больше ординаты источника,

ver = "N"; // УМЕНЬШИМ её, т.е. двинемся на СЕВЕР

TY--; // Фиксируем изменение положения Тора

}

cout << ver + hor << endl; // Склеиваем наши строки-"сдвиги" и выводим окончательный сдвиг

}

Код на Java

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

class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		int LX = in.nextInt(), LY = in.nextInt();
		int TX = in.nextInt(), TY = in.nextInt();
		while (true) {
			int E = in.nextInt();
			String hor, ver;
			if (TX == LX)
				hor = "";
			else {
				if (TX < LX) {
					hor = "E";
					TX++;
				}
				else {
					hor = "W";
					TX--;
				}
			}
			if (TY == LY)
				ver = "";
			else {
				if (TY < LY) {
					ver = "S";
					TY++;
				}
				else {
					ver = "N";
					TY--;
				}
			}
			System.out.println(ver + hor);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

int LX = in.nextInt(), LY = in.nextInt();

int TX = in.nextInt(), TY = in.nextInt();

while (true) {

int E = in.nextInt();

String hor, ver;

if (TX == LX)

hor = "";

else {

if (TX < LX) {

hor = "E";

TX++;

}

else {

hor = "W";

TX--;

}

if (TY == LY)

ver = "";

else {

if (TY < LY) {

ver = "S";

TY++;

}

else {

ver = "N";

TY--;

}

System.out.println(ver + hor);

}

Related Images:

А37

29/09/2014 by Оніщенко Олександр

Задача: Даны действительные числа [latex]a, b, c[/latex]. Удвоить эти числа, если [latex] a \geq b \geq c[/latex], и заменить их абсолютными значениями, если это не так.

[latex]a[/latex]	[latex]b[/latex]	[latex]c[/latex]	[latex]a_1[/latex]	[latex]b_1[/latex]	[latex]c_1[/latex]	Комментарий
26	16	-2	52.00	32.00	-4.00	Пройден
20	30	0	20.00	30.00	0	Пройден
-4	-16	-20	-8.00	-32.00	-40.00	Пройден
2.75	3.56	-1	2.75	3.56	1	Пройден
2	2	2	4.00	4.00	4.00	Пройден

#include <iostream>
#include <stdio.h>
#include<math.h>
using namespace std;
 
int main() {
	double a, b, c;
    cin >> a;
    cin >> b;               //Вводим нужные нам действительные числа.
    cin >> c;
    if((a >= b) && (b >= c))   //Если a >= b >= c, то удваиваем их.
    {
    	a*=2;
    	b*=2;
    	c*=2;
    }
    else    // Во всех иных случаях находим абсолютное значение данных чисел.
    {
        a = fabs(a);
        b = fabs(b);
        c = fabs(c);
    }	
    printf("a = %3.2f, b = %3.2f, c = %3.2f",  a, b, c); 
	return 0;
}

#include <iostream>

#include <stdio.h>

#include<math.h>

using namespace std;

int main() {

double a, b, c;

cin >> a;

cin >> b; //Вводим нужные нам действительные числа.

cin >> c;

if((a >= b) && (b >= c)) //Если a >= b >= c, то удваиваем их.

{

a*=2;

b*=2;

c*=2;

}

else // Во всех иных случаях находим абсолютное значение данных чисел.

{

a = fabs(a);

b = fabs(b);

c = fabs(c);

}

printf("a = %3.2f, b = %3.2f, c = %3.2f", a, b, c);

return 0;

}

В задача нужно проделать на введенными числами операции в зависимости от соблюдения неравенств. Если [latex] a \geq b \geq c[/latex], то мы удваиваем все введенные числа. Если же, неравенство [latex] a \geq b \geq c[/latex] не соблюдается, то находим модули каждого из чисел([latex]|a|, |b|, |c| [/latex] ) и выводим полученное как результат.

Ссылка на Ideone.

Код Java

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

class Depo
{
	public static void main (String[] args) throws java.lang.Exception
	{
		double a, b, c;
		Scanner in = new Scanner(System.in);
		a=in.nextDouble();
		b=in.nextDouble();
		c=in.nextDouble();
		if((a>=b)&&(b>=c)){
			a*=2;
			b*=2;
			c*=2;
		}
		else{
			a=Math.abs(a);
			b=Math.abs(b);
			c=Math.abs(c);
		}
		System.out.printf("a = %3.2f, b = %3.2f, c = %3.2f", a, b, c);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Depo

{

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

{

double a, b, c;

Scanner in = new Scanner(System.in);

a=in.nextDouble();

b=in.nextDouble();

c=in.nextDouble();

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

a*=2;

b*=2;

c*=2;

}

else{

a=Math.abs(a);

b=Math.abs(b);

c=Math.abs(c);

}

System.out.printf("a = %3.2f, b = %3.2f, c = %3.2f", a, b, c);

}

Ссылка на Ideone

Related Images:

Ю2.21

22/09/2014 by Іванов Вячеслав Володимирович

Задача: Имеются три раствора полезного вещества с концентрациями [latex]p_{1}, p_{2}, p_{3}[/latex] каждый и стоимостью [latex]s_{1}, s_{2}, s_{3}[/latex] соответственно. Можно ли смешать их так, чтобы получить раствор с заданной концентрацией [latex]p[/latex] наименьшей стоимости [latex]s[/latex]?
Указание. Пусть [latex]\alpha_{1}, \alpha_{2}, \alpha_{3}[/latex]- долевые содержания растворов в смеси. Тогда для получения заданной концентрации [latex]p[/latex] необходимо [latex]p_{1}\alpha_{1} + p_{2}\alpha_{2} + p_{3}\alpha_{3}=p[/latex].
Кроме того, нужно учесть условие «комплектности смеси»: [latex]\alpha_{1} + \alpha_{2} + \alpha_{3} = 1[/latex]; [latex]\alpha_{1} \ge 0; \alpha_{2} \ge 0; \alpha_{3} \ge 0;[/latex] При этих условиях необходимо найти наименьшее значение линейной функции: [latex]s = \min _{ \alpha_{1}, \alpha_{2}, \alpha_{3} } { ( s_{1} \alpha_{2} + s_{2} \alpha_{2} + s_{3} \alpha_{3} ) }[/latex].
С учётом ограничений задача сводится к минимизации линейной функции одного переменного на отрезке, однако искомые выражения и условия получаются достаточно громоздкими. Можно показать, что в решении будут участвовать не более двух растворов. Тогда достаточно среди вариантов:
а) [latex]\alpha_{1} = 0[/latex];
б) [latex]\alpha_{2} = 0[/latex];
в) [latex]\alpha_{3} = 0[/latex];
Выбрать оптимальный, и затем провести необходимые расчеты.
Тесты

	1	2	3	p	s	Комментарий
[latex]p_{i}[/latex]	0	0	0	0		10	Пройден
[latex]s_{i}[/latex]	10	12	14
[latex]p_{i}[/latex]	0	10	30	0		10	Пройден
[latex]s_{i}[/latex]	10	20	30
[latex]p_{i}[/latex]	15.3	49.2	51.6	37.4		29.56	Пройден
[latex]s_{i}[/latex]	40	10	20
[latex]p_{i}[/latex]	30	30	30	40		Impossible	Пройден
[latex]s_{i}[/latex]	25	14	40
[latex]p_{i}[/latex]	20.3	20.3	20.3	20.3		30	Пройден
[latex]s_{i}[/latex]	30	40	50
[latex]p_{i}[/latex]	30	40	50	20		Impossible	Пройден
[latex]s_{i}[/latex]	19	31	22
[latex]p_{i}[/latex]	20	60	80	40		40	Пройден
[latex]s_{i}[/latex]	60	20	100
[latex]p_{i}[/latex]	20	50	90	50		15.71	Пройден
[latex]s_{i}[/latex]	10	80	20
[latex]p_{i}[/latex]	10	60	90	62.5		62.5	Пройден
[latex]s_{i}[/latex]	190	10	20

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

#include <cstdio>
#include <algorithm>
using namespace std;
double c_price( double p, double p1, double s1, double p2, double s2 )
{
    //if given solutions' concentrations and the result are equal
    if ( p1 == p2 )
    {
        if( p1 == p ) return min( s1, s2 );
        return 0;
    }
    //else solve the system of equations
    double a1 = ( p - p1 ) / ( p2 - p1 );
    if ( a1 > 1 || a1 < 0 ) return 0;
    double a2 = 1 - a1;
    return s1*a1+s2*a2;
}

int main()
{
    double p1, p2, p3, f_p;
    double s1, s2, s3;

    scanf("%lf %lf %lf %lf", &p1, &p2, &p3, &f_p);
    scanf("%lf %lf %lf", &s1, &s2, &s3);

    if( f_p > max( p1, max( p2, p2 ) ) || f_p < min( p1, min( p2, p3 ) ) )
    {
        printf("Impossible!\n");
        return 0;
    }

    double s12 = c_price( f_p, p1, s1, p2, s2 );
    double s13 = c_price( f_p, p1, s1, p3, s3 );
    double s23 = c_price( f_p, p2, s2, p3, s3 );

    if( !s12 && !s13 && !s23 )
    {
       printf("Impossible!\n");
       return 0;
    }

    double min_price = s12;
    if ( min_price > s13 && s13 ) min_price = s13;
    if ( min_price > s23 && s23 ) min_price = s23;
    printf("%.2lf", min_price);
    return 0;
}

#include <cstdio>

#include <algorithm>

using namespace std;

double c_price( double p, double p1, double s1, double p2, double s2 )

{

//if given solutions' concentrations and the result are equal

if ( p1 == p2 )

{

if( p1 == p ) return min( s1, s2 );

return 0;

}

//else solve the system of equations

double a1 = ( p - p1 ) / ( p2 - p1 );

if ( a1 > 1 || a1 < 0 ) return 0;

double a2 = 1 - a1;

return s1*a1+s2*a2;

}

int main()

{

double p1, p2, p3, f_p;

double s1, s2, s3;

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

scanf("%lf %lf %lf", &s1, &s2, &s3);

if( f_p > max( p1, max( p2, p2 ) ) || f_p < min( p1, min( p2, p3 ) ) )

{

printf("Impossible!\n");

return 0;

}

double s12 = c_price( f_p, p1, s1, p2, s2 );

double s13 = c_price( f_p, p1, s1, p3, s3 );

double s23 = c_price( f_p, p2, s2, p3, s3 );

if( !s12 && !s13 && !s23 )

{

printf("Impossible!\n");

return 0;

}

double min_price = s12;

if ( min_price > s13 && s13 ) min_price = s13;

if ( min_price > s23 && s23 ) min_price = s23;

printf("%.2lf", min_price);

return 0;

}

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

class Ideone
{
    public static double c_price(double p, double p1, double s1, double p2, double s2){
        if(p1 == p2){ //if given solutions' concentrations are equal
            return p1 == p ? Math.min(s1, s2) : 0;
        }
        if(p1 == p || p2 == p){ //if some given concentration equals to needed
            return p1 == p ? s1 : s2;
        }
        double a1 = (p-p1)/(p2-p1);
        if(a1 > 1 || a1 < 0) return 0; //inconsistent data
        double a2 = 1-a1;
        return s1*a1 + s2*a2;
    }
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        double[] p = new double[3]; 
        double[] s = new double[3];
        for(int i = 0; i < 3; i++) p[i] = in.nextDouble();
        double f_p = in.nextDouble();
        for(int i = 0; i < 3; i++) s[i] = in.nextDouble();
        double s12 = c_price(f_p, p[0], s[0], p[1], s[1]);
        double s13 = c_price(f_p, p[0], s[0], p[2], s[2]);
        double s23 = c_price(f_p, p[1], s[1], p[2], s[2]);
        if(s[0] == 0 && s[1] == 0 && s[2] == 0)
            System.out.println("Impossible");
        else{
            double min_price = s12;
            if(s13 != 0) min_price = Math.min(min_price, s13);
            if(s23 != 0) min_price = Math.min(min_price, s23);
            System.out.printf("%.2f", min_price);
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.math.*;

class Ideone

{

public static double c_price(double p, double p1, double s1, double p2, double s2){

if(p1 == p2){ //if given solutions' concentrations are equal

return p1 == p ? Math.min(s1, s2) : 0;

}

if(p1 == p || p2 == p){ //if some given concentration equals to needed

return p1 == p ? s1 : s2;

}

double a1 = (p-p1)/(p2-p1);

if(a1 > 1 || a1 < 0) return 0; //inconsistent data

double a2 = 1-a1;

return s1*a1 + s2*a2;

}

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

{

Scanner in = new Scanner(System.in);

double[] p = new double[3];

double[] s = new double[3];

for(int i = 0; i < 3; i++) p[i] = in.nextDouble();

double f_p = in.nextDouble();

for(int i = 0; i < 3; i++) s[i] = in.nextDouble();

double s12 = c_price(f_p, p[0], s[0], p[1], s[1]);

double s13 = c_price(f_p, p[0], s[0], p[2], s[2]);

double s23 = c_price(f_p, p[1], s[1], p[2], s[2]);

if(s[0] == 0 && s[1] == 0 && s[2] == 0)

System.out.println("Impossible");

else{

double min_price = s12;

if(s13 != 0) min_price = Math.min(min_price, s13);

if(s23 != 0) min_price = Math.min(min_price, s23);

System.out.printf("%.2f", min_price);

}

Метод решения:
Задача сводится к решению системы уравнений:
[latex]\begin{cases} p_{1} \alpha_{2} + p_{2} \alpha_{2} + p_{3} \alpha_{3} = p,\\ \alpha_{1} + \alpha_{2} + \alpha_{3} = 1,\\ s = \min _{ \alpha_{1}, \alpha_{2}, \alpha_{3} } { ( s_{1} \alpha_{2} + s_{2} \alpha_{2} + s_{3} \alpha_{3} ) }; \end{cases}[/latex]

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

Аналитическое решение в данном случае тривиально:
[latex]\begin{cases} p_{i} \alpha_{i} + p_{j} \alpha_{j} = p,\\ \alpha_{i} + \alpha_{j} = 1; \end{cases} \Rightarrow \begin{cases} \alpha_{i} = \frac { p-p_{i} } { p_{j}-p_{i} },\\ \alpha_{j} = 1-\alpha_{i}; \end{cases} s = s_{i} \alpha_{i} + s_{j} \alpha_{j};[/latex]

Для большей наглядности применяется функция c_price (calculate price), в теле которой рассмотрены крайние случаи:
1) Если [latex]p_{1}=p_{2}=p[/latex], то нужно выбрать раствор наименьшей стоимости.
2) Если [latex]p_{1}=p_{2} \ne p[/latex], то решений нет.
3) Если [latex]p_{1}=p \ne p_{2}[/latex], то [latex]s = s_{1}[/latex]. Аналогично в случае [latex]p_{2}=p \ne p_{1}[/latex].
4) Если доля раствора в смеси [latex]\alpha 1[/latex], то решений нет.

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

Протестировать работу программы можно по ссылке.
Реализация на Java: http://ideone.com/qTQpMX

Related Images:

А47

18/09/2014 by Іванов Вячеслав Володимирович

Задача:
Даны действительные положительные числа [latex]x[/latex], [latex]y[/latex], [latex]z[/latex].
а) Выяснить существует ли треугольник с длинами сторон [latex]x[/latex], [latex]y[/latex], [latex]z[/latex].
б) Если треугольник существует, то ответить — является ли он остроугольным?

NA — «not acute» — существует, но не остроугольный
A — «acute» — остроугольный
DE — «doesn’t exist» — не существует

[latex]x[/latex]	[latex]y[/latex]	[latex]z[/latex]	Результат	Комментарий:
3	4	5	NA	Пройден: трегольник прямоугольный
1.30	3.86	5.14	NA	Пройден
1.67	2.29	8	NE	Пройден: нарушено условие (I)
811	22	790	NA	Пройден: треугольник тупоугольный
10	11	12	A	Пройден

#include 
#include 
using namespace std;

int main()
{
    double x, y, z;
	scanf( "%lf %lf %lf", &x, &y, &z );
	
	//find the longest side
	if ( x > y ) swap( x, y );
	if ( y > z ) swap( y, z );
	
    //if the triangle exists
    if( x + y > z )
    {
        //if it is acute
        double COS_VALUE = ( x*x + y*y - z*z ) / ( 2*x*y );
        if( COS_VALUE > 0 ) printf( "The triangle is acute." );
        else printf( "The triangle is not acute." );
    }
    else printf( "The triangle doesn't exist." );
    return 0;
}

#include

using namespace std;

int main()

{

double x, y, z;

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

//find the longest side

if ( x > y ) swap( x, y );

if ( y > z ) swap( y, z );

//if the triangle exists

if( x + y > z )

{

//if it is acute

double COS_VALUE = ( x*x + y*y - z*z ) / ( 2*x*y );

if( COS_VALUE > 0 ) printf( "The triangle is acute." );

else printf( "The triangle is not acute." );

}

else printf( "The triangle doesn't exist." );

return 0;

}

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

class Triangles
{
	public static double square(double num){ return num*num; }
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		double s[] = new double[3];		
		for(int i = 0; i < 3; i++)
			s[i] = in.nextDouble();
		java.util.Arrays.sort(s);
		if(s[0] + s[1] <= s[2]){
			System.out.println("The triangle doesn't exist.");
		}
		else{
			double cosValue = Math.cos((square(s[0]) + square(s[1]) + square(s[2]))/(2*s[0]*s[1]));	
			if(cosValue > 0) System.out.println("The triangle is acute.");
			else System.out.println("The triangle is not acute.");
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.math.*;

import java.text.*;

class Triangles

{

public static double square(double num){ return num*num; }

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

{

Scanner in = new Scanner(System.in);

double s[] = new double[3];

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

s[i] = in.nextDouble();

java.util.Arrays.sort(s);

if(s[0] + s[1] <= s[2]){

System.out.println("The triangle doesn't exist.");

}

else{

double cosValue = Math.cos((square(s[0]) + square(s[1]) + square(s[2]))/(2*s[0]*s[1]));

if(cosValue > 0) System.out.println("The triangle is acute.");

else System.out.println("The triangle is not acute.");

}

Алгоритм:
I. Необходимым и достаточным условием существования треугольника с тремя заданными сторонами является условие вида:
[latex] x + y > z[/latex] (вырожденный случай не рассматривается)

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

II. Вид треугольника определяется углом, лежащим против большей стороны:
[latex]\alpha \in [ 0; \frac{ \pi }{ 2 } ]\Leftrightarrow \cos{(\alpha)}>0[/latex]

Знак косинуса угла легко определить через теорему косинусов:
[latex]z^{ 2 }=x^{ 2 }+y^{ 2 }-2xy\cos { (\alpha ) } \\ \cos { (\alpha ) } =\frac { x^{ 2 }+y^{ 2 }-z^{ 2 } }{ 2xy }[/latex]

Если входные данные удовлетворяют вышеперечисленным условиям, то треугольник существует и является остроугольным.

Программное решение состоит из двух этапов:
0. Поиск наибольшей стороны.
1. Проверка условия (I).
2. Проверка условия (II).

Функция swap() взята из заголовочного файла algorithm.
В программе использован тип данных с плавающей точкой и двойной точностью (для отображения действительных чисел).
Для выполнения программы и проверки тестов можно воспользоваться следующим объектом. (реализация на Java)