e-olymp 9081. Автомобілі

10/09/2020 by Артем Рогулин

Завдання

Троє водіїв вирішили опробувати нове шосе. Перший їхав зі сталою швидкістю $v_1$ км/год. протягом $t_1$ годин. Другий їхав зі сталою швидкістю $v_2$ км/год. протягом $t_2$ годин, третій – зі сталою швидкістю $v_3$ км/год. протягом $t_3$ годин. Хто з них проїхав найдовший шлях?

Вхідні дані

В одному рядку через пропуск ввести на стандартний пристрій введення значення $v_1$ , $v_2$ , $v_3$ , $t_1$ , $t_2$ , $t_3$ . Інтервал значень швидкостей – від $30$ до $100$ км/год. включно. Час у дорозі – з інтервалу $[1;15]$ годин.

Вихідні дані

Якщо найдовший шлях проїхав один водій, вивести на стандартний пристрій введення номер водія. Якщо найдовший шлях проїхали два або три водія, треба ввести в одному рядку через пропуск їх номери у порядку зростання.

Тести

№	Вхідні дані	Вихідні дані
1.	38 9 54 5 62 3	1
2.	30 9 45 6 90 3	1 2 3
3.	30 15 45 5 50 9	1 3
4.	50 6 42 14 84 7	2 3

Код програми

public class Main {

    public static void main(String[] args) {
        java.util.Scanner jin = new java.util.Scanner(System.in);
            int v1, v2, v3; // Змінні, де будемо зберігати швидкості водіїв
            int t1, t2, t3; // Час, який вони їхали
            int s1, s2, s3; // І відстань
            int max_; // Також, змінну, де буде зберігатися максимальна відстань
            v1 = jin.nextInt(); t1 = jin.nextInt(); // Прочитуємо швидкість і час для кожного водія
            v2 = jin.nextInt(); t2 = jin.nextInt();
            v3 = jin.nextInt(); t3 = jin.nextInt();
            s1 = v1 * t1; // Знаходимо відстань, яку проїхав кожен з них
            s2 = v2 * t2;
            s3 = v3 * t3;
            max_ = Math.max(Math.max(s1, s2), s3); // Виявляємо максимальну відстань
            if ( s1 == max_ )  // Перевіряючи, чи є пройдена відстань максимальною
                System.out.print("1 "); // Виводимо номер відповідного водія
            if ( s2 == max_ )
                System.out.print("2 ");
            if ( s3 == max_ )
                System.out.print(3);
            
        }
}

public class Main {

public static void main(String[] args) {

java.util.Scanner jin = new java.util.Scanner(System.in);

int v1, v2, v3; // Змінні, де будемо зберігати швидкості водіїв

int t1, t2, t3; // Час, який вони їхали

int s1, s2, s3; // І відстань

int max_; // Також, змінну, де буде зберігатися максимальна відстань

v1 = jin.nextInt(); t1 = jin.nextInt(); // Прочитуємо швидкість і час для кожного водія

v2 = jin.nextInt(); t2 = jin.nextInt();

v3 = jin.nextInt(); t3 = jin.nextInt();

s1 = v1 * t1; // Знаходимо відстань, яку проїхав кожен з них

s2 = v2 * t2;

s3 = v3 * t3;

max_ = Math.max(Math.max(s1, s2), s3); // Виявляємо максимальну відстань

if ( s1 == max_ ) // Перевіряючи, чи є пройдена відстань максимальною

System.out.print("1 "); // Виводимо номер відповідного водія

if ( s2 == max_ )

System.out.print("2 ");

if ( s3 == max_ )

System.out.print(3);

}

Пояснення

Відповіддю до задачі є номери водіїв, що проїхали максимальну відстань. Для цього треба використати формулу, знайому всім ще зі школи: $S = Vt$ . Після знаходження відстані пройденої кожним водієм, ми знаходимо максимальну серед них. Далі нам залишається тільки виводити у порядку зростання номери водіїв, які пройшли максимальну відстань.

Примітка: Швидкість і час вводяться попарно для кожного водія.

Посилання

e-olymp 419. Задача 3n + 1

19/02/2019 by Александра Филистович

Задача

Рассмотрим следующий алгоритм генерации последовательности чисел:

input n
print n
if n = 1 then STOP
if n is odd then n = 3 * n + 1
else n = n / 2
GOTO 2

input n

print n

if n = 1 then STOP

if n is odd then n = 3 * n + 1

else n = n / 2

GOTO 2

Например, для $n = 22$ будет сгенерирована следующая последовательность чисел:

22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Полагают (но это еще не доказано), что этот алгоритм сойдется к $n = 1$ для любого целого $n$ . По крайней мере, это предположение верно для всех целых $n$ , для которых $0 < n < 1,000,000$ .
Длиной цикла числа $n$ будем называть количество сгенерированных чисел в последовательности включая $1$ . В приведенном примере длина цикла числа $22$ равна $16$ .
Для двух заданных чисел $i$ и $j$ необходимо найти максимальную длину цикла среди всех чисел между $i$ и $j$ включительно.

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

Каждый тест задается в отдельной строке и содержит пару целых чисел $i$ и $j$ . Входные числа будут меньше $1000000$ и больше $0$ . Считайте, что для вычислений достаточно использовать $32$ битный целочисленный тип.

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

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

Тесты

Входные данные	Выходные данные
1 10 100 200 201 210 900 1000	1 10 20 100 200 125 201 210 89 900 1000 174
1 10 10 1	1 10 20 10 1 20
5 25 70 54 38 250	5 25 24 70 54 113 38 250 128

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

import java.util.*;
import java.lang.*;
import java.io.*;
import static java.lang.Math.*;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int i, j, ait;
		Scanner scan = new Scanner(System.in);
		while(scan.hasNext()) {
			i = scan.nextInt();
			j = scan.nextInt();
			int it, maxIt;
			maxIt = 0;
			for (int a = min(i, j); a <= max(i, j); a++) {
				it = 1;
				ait = a;
				while(ait != 1){
					if(ait % 2 == 1){
						ait = ait * 3 + 1;
					}
					else{
						ait = ait / 2;
					}
					it++;
				}
				if (it > maxIt) {
					maxIt = it;
				}
			}
			System.out.println(i + " " + j + " " + maxIt);
		}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

import static java.lang.Math.*;

class Main

{

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

{

int i, j, ait;

Scanner scan = new Scanner(System.in);

while(scan.hasNext()) {

i = scan.nextInt();

j = scan.nextInt();

int it, maxIt;

maxIt = 0;

for (int a = min(i, j); a <= max(i, j); a++) {

it = 1;

ait = a;

while(ait != 1){

if(ait % 2 == 1){

ait = ait * 3 + 1;

}

else{

ait = ait / 2;

}

it++;

}

if (it > maxIt) {

maxIt = it;

}

System.out.println(i + " " + j + " " + maxIt);

}

Решение

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

Ссылки

Ссылка на e-olymp.
Ссылка на Ideone

А410е

27/12/2018 by Антон Джашимов

Задача

Дана целочисленная матрица $[a_{ij}], ij=1,\ldots,n.$ Получить $b_{1} \dots b_{n},$ где $b_{i}$ — это $\underset{1\leq j\leq n}{\max a_{ij}}\cdot \underset{1\leq j\leq n}{\min a_{ji}}$

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

Первая строка содержит число $n.$ Следующие строки содержат матрицу $n\times n.$

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

Вывести $b_i \; i=1\dots n.$

Тесты

Входные данные	Выходные данные
2 1 2 4 1	2 4
3 1 2 3 4 1 -6 1 -2 -1	3 -8 -6

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

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,maxa,mina;
		n=in.nextInt();
		int a[][];
		a = new int[n][];
    	for (int i = 0 ;i < n ; i++) {
			a[i] = new int [n];
		}
		for(int i=0;i<n;i++){
			for(int j=0;j<n;j++){
				a[i][j]=in.nextInt();
			}
		}
		int b[]= new int[n];
		for(int i=0;i<n;++i){
        	maxa=a[i][0]; //Присваиваем максимуму значение первого элемента i-й строки.
        	mina=a[0][i]; //Минимуму присваиваем значение первого элемента i-го столбца.
        	for(int j=0;j<n;++j){
            	maxa=(maxa>a[i][j]?maxa:a[i][j]); //Вычисляем максимум i-й строки.
            	mina=(mina<a[j][i]?mina:a[j][i]); //Минимум i-го столбца.
        	}
        	b[i]=maxa*mina;
    	}
    	for(int i=0;i<n;++i){
        	System.out.print(b[i]);
			System.out.print(" ");
    	}
	}
}

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,maxa,mina;

n=in.nextInt();

int a[][];

a = new int[n][];

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

a[i] = new int [n];

}

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

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

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

}

int b[]= new int[n];

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

maxa=a[i][0]; //Присваиваем максимуму значение первого элемента i-й строки.

mina=a[0][i]; //Минимуму присваиваем значение первого элемента i-го столбца.

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

maxa=(maxa>a[i][j]?maxa:a[i][j]); //Вычисляем максимум i-й строки.

mina=(mina<a[j][i]?mina:a[j][i]); //Минимум i-го столбца.

}

b[i]=maxa*mina;

}

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

System.out.print(b[i]);

System.out.print(" ");

}

Решение

Очевидно, что из заданной матрицы нужно взять максимальный элемент $i$ -й строки и умножить его на минимальный элемент $i$ -го столбца. Для нахождения максимума $a_{ij}$ , введем переменную и будем присваивать ей начальное значение первого элемента $i$ -й строки. Чтобы при расчете максимума проходя по элементам строки мы не сравнивали каждый $i$ -й элемент с первым, присваивать начальное значение максимуму будем в цикле по $i$ . Аналогично с минимумом, но начальное значение минимума будет равно первому элементу $i$ -го столбца.

Ссылки

Условие задачи
Код решения

e-olymp 7612. Алекс и квадраты оригами

20/12/2018 by Саша Рябова

Задача

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

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

В одной строке два целых числа $h$ и $w$ $(1 \leq h,w\leq 1000)$ — высота и ширина куска бумаги.

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

Выведите одно действительное число — наибольшую длину стороны квадратов. Всегда можно вырезать три одинаковых квадрата из листа бумаги размером $h \times w$ так, чтобы их стороны были параллельны сторонам листа.

Ответ следует вывести с точностью не меньше трех десятичных знаков.

Тесты

Входные данные	Выходные данные
$100$ $100$	$50.000$
$10$ $80$	$10.000$
$50$ $76$	$25.333$
$60$ $27$	$20.000$
$8$ $3$	$2.667$

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

import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner sc = new Scanner(System.in);
		double h = sc.nextDouble();
		double w = sc.nextDouble();
    	double b = Math.max(h, w);
    	double a = Math.min(w, h);
    	double c = Math.min(Math.min(w,h), Math.max(b/3, a/2));
    	System.out.printf("%.4f", c);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

Scanner sc = new Scanner(System.in);

double h = sc.nextDouble();

double w = sc.nextDouble();

double b = Math.max(h, w);

double a = Math.min(w, h);

double c = Math.min(Math.min(w,h), Math.max(b/3, a/2));

System.out.printf("%.4f", c);

}

Решение задачи

Существует два варианта оптимального расположения трех квадратов — три в один ряд,

или же два, соприкасающихся одной стороной, и третий над ними

Обозначим за $a$ меньшую сторону листа бумаги, а за $b$ — большую. Если a не больше $\frac{b}{3}$ , то оптимальным расположением квадратов в прямоугольнике будет первый вариант, а наибольшей возможной стороной квадратов является меньшая сторона листа бумаги $a$ . В противном случае рассмотрим два варианта:

Если $\frac{a}{2} < \frac{b}{3}$ , то квадраты будут располагаться в прямоугольнике первым способом, и ответом будет служить число $\frac{a}{2}$ .
Иначе квадраты будут располагаться в прямоугольнике вторым способом, и ответом будет служить число $\frac{b}{3}$ .

Таким образом, в случае $a > \frac{b}{3}$ ответом будет служить большее из двух чисел $\frac{a}{2}$ и $\frac{b}{3}$ . Mинимальное из $\max \left(\frac{a}{2},\frac{b}{3} \right)$ и $a$ число и будет ответом.
Проверим нашу формулу:если $a < \frac{b}{3}$ , то $\max \left(\frac{a}{2},\frac{b}{3} \right) = \frac{b}{3}$ , и тогда $\min \left( a,\max \left(\frac{a}{2},\frac{b}{3} \right) \right) = a$ . Иначе $\min \left( a,\max \left(\frac{a}{2},\frac{b}{3} \right) \right) = \max \left(\frac{a}{2},\frac{b}{3}\right)$ , что нам и требуется.

Ссылки

Условие задачи на сайте e-olymp
Код решения

e-olymp 7368. Средний балл для фигуристов

09/12/2018 by Валерия Ларикова

Задача

Спортсменам-фигуристам $n$ судей выставляют оценки. Технический работник соревнований изымает все максимальные и все минимальные оценки, а для остальных оценок вычисляет среднее арифметическое значение. Этот результат считается баллом, полученным спортсменом. Найти такой балл для каждого спортсмена.

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

В первой строке находятся два целых числа: количество судей $n$ и количество спортсменов $m$ . В следующих $m$ строках находятся $n$ целых чисел – оценки всех судей $(0 < n \leqslant 10, 0 < m \leqslant 100)$ для каждого из фигуристов.

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

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

Тесты

#	Входные данные	Выходные данные
1	5 4 7 8 9 8 10 6 5 5 4 7 9 9 10 7 7 7 7 10 9 8	8.33 5.33 9.00 8.50
2	6 3 6 7 6 5 4 3 9 8 5 5 6 5 7 6 4 1 2 2	5.25 7.00 3.50
3	4 5 6 7 8 6 9 8 5 4 7 6 7 5 4 3 9 3 7 8 7 6	7.00 6.50 6.00 4.00 7.00
4	4 4 7 7 2 3 9 8 3 3 5 4 9 7 4 3 2 6	3.00 8.00 6.00 3.50
5	8 5 4 5 6 7 7 4 9 8 3 5 6 6 7 8 5 9 7 6 3 9 3 7 9 7 5 6 4 3 7 7 5 7 9 8 4 6 7 9 9 4	6.60 6.17 6.75 5.00 7.00

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

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

public class Main
{
  public static void main (String[] args) throws java.lang.Exception
  {
    double n, m;
    double x, min = 100, max = -100, sum = 0, a = 0, b = 0;
    Scanner in = new Scanner(System.in);
    n = in.nextDouble();
    m = in.nextDouble();
    for (int i = 0; i < m; i++){
      for (int j = 0; j < n; j ++){
        x = in.nextDouble();
        if (max == x) a++;
        if (max < x) {
          if (max != min) sum += a*max;
          a = 1;
          max = x;
        }
        if ( min == x) b++;
        if (min > x) {
          if (max != min) sum += b*min;
          b = 1;
          min = x;
        }
      if (x!= min && x != max) sum += x;
      }
      if(i == m-1) System.out.printf("%.2f", sum / (n - a - b));
      else System.out.printf("%.2f ", sum / (n - a - b));
      sum = a = b = 0;
      min = 100;
      max = -100;
    }
  }
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

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

{

double n, m;

double x, min = 100, max = -100, sum = 0, a = 0, b = 0;

Scanner in = new Scanner(System.in);

n = in.nextDouble();

m = in.nextDouble();

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

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

x = in.nextDouble();

if (max == x) a++;

if (max < x) {

if (max != min) sum += a*max;

a = 1;

max = x;

}

if ( min == x) b++;

if (min > x) {

if (max != min) sum += b*min;

b = 1;

min = x;

}

if (x!= min && x != max) sum += x;

}

if(i == m-1) System.out.printf("%.2f", sum / (n - a - b));

else System.out.printf("%.2f ", sum / (n - a - b));

sum = a = b = 0;

min = 100;

max = -100;

}

Решение задачи

Для решения задачи нам необходимо изъять все минимальные и максимальные значения в каждой строчке. Переменные $a$ и $b$ — это количество вхождений максимума и минимума соответственно. Берем любой элемент строки, который обозначили переменной $x,$ и будем считать, что он минимальный и максимальный. Далее сравниваем элементы между собой и находим максимум и минимум и подсчитываем их количество. Ещё нам необходимо посчитать сумму оставшихся значений, а также их количество по формуле $n — a — b.$ А затем вычисляем среднее арифметическое для оставшихся значений по формуле $\displaystyle\frac{sum}{n — a — b}$ и выводим результат.

Ссылки

Ссылка на e-olymp

Ссылка на ideone

A406

06/07/2016 by Дарья Пиндус

Задача

С помощью $x_{ij}, i=1,2; j=1,\ldots,n.$ – действительной матрицы на плоскости задано n точек так, что $x_{1j}, x_{2j}$ – координаты $j$ – точки. Точки попарно соединены отрезками. Найти длину наибольшего отрезка.

Тест

n	Матрица $x_{ij}, i=1,2.$	Длина наибольшего отрезка	Комментарий
3	2 8 4 9 1 5	10	Пройдено
4	6 14 2 1 9 3 8 0	13.3417	Пройдено
5	1 8 4 3 7 2 9 5 0 11	11.7047	Пройдено

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

import java.util.*;
import java.lang.*;
import java.io.*;
 
class A406 {
    public static void main(String[] args) {
        int[][] matrix;
        double maxDistance = 0;
        double distance;
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt();
        matrix = new int[2][m];
 
        for (int i = 0; i < 2; i++)
            for (int j = 0; j < m; j++)
                matrix[i][j] = scanner.nextInt();
 
        for (int i = 0; i < m; i++) {
            for (int j = i + 1; j < m; j++) {
                distance = Math.sqrt((matrix[0][j] - matrix[0][i]) * (matrix[0][j] - matrix[0][i]) + (matrix[1][j] - matrix[1][i]) * (matrix[1][j] - matrix[1][i]));
                if (distance > maxDistance) {
                    maxDistance = distance;
                }
            }
        }
 
        System.out.println(maxDistance);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class A406 {

public static void main(String[] args) {

int[][] matrix;

double maxDistance = 0;

double distance;

Scanner scanner = new Scanner(System.in);

int m = scanner.nextInt();

matrix = new int[2][m];

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

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

matrix[i][j] = scanner.nextInt();

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

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

distance = Math.sqrt((matrix[0][j] - matrix[0][i]) * (matrix[0][j] - matrix[0][i]) + (matrix[1][j] - matrix[1][i]) * (matrix[1][j] - matrix[1][i]));

if (distance > maxDistance) {

maxDistance = distance;

}

System.out.println(maxDistance);

}

Ход решения:

Вводим матрицу.
Находим длину наибольшего отрезка.
С помощью вложенных циклов мы находим длины всех отрезков по формуле
$AB=\sqrt{(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}, A(x_{1},y_{1}), B(x_{2},y_{2}).$
По алгоритму нахождения максимума находим длину наибольшего отрезка.
Выводим матрицу.
Выводим длину наибольшего отрезка.
Ссылка на код