Валентина Андриеш

Условие задачи:
— Дядя Федор, Дядя Федор, я научился строить дерево отрезков.
— Подожди, Шарик, я занят.
— Ну Дядя Федор, ну смотри какой я код написал:

int build(int v, int left, int right) {
	if (left == right) {
		t[v] = a[left];
		return 0;

	}
	int mid = (left+right) / 2;
	build(v*2, left, mid);
	build(v*2+1, mid+1, right);
	t[v] = max(t[v*2], t[v*2+1]);
	return 0;
}

int get_max(int v, int left, int right, int lpos, int rpos) {
	if (left == lpos && right == rpos)
		return t[v];
	if (lpos > rpos)
		return -1;
	int mid = (left+right) / 2;
	return max(get_max(v*2, left, mid, lpos, min(rpos, mid)),
	get_max(v*2+1,mid+1,right,max(lpos,mid+1),rpos));
}

int build(int v, int left, int right) {

if (left == right) {

t[v] = a[left];

return 0;

}

int mid = (left+right) / 2;

build(v*2, left, mid);

build(v*2+1, mid+1, right);

t[v] = max(t[v*2], t[v*2+1]);

return 0;

}

int get_max(int v, int left, int right, int lpos, int rpos) {

if (left == lpos && right == rpos)

return t[v];

if (lpos > rpos)

return -1;

int mid = (left+right) / 2;

return max(get_max(v*2, left, mid, lpos, min(rpos, mid)),

get_max(v*2+1,mid+1,right,max(lpos,mid+1),rpos));

}

— Ну хорошо, Шарик, раз ты так хорошо разобрался с этой темой, давай я тебе дам массив из [latex]n[/latex] неотрицательных чисел и число [latex]k[/latex], а ты мне скажешь сколько существует таких пар [latex]l;r \left ( 1\leq l\leq r\leq n \right ),[/latex] что функция, вызванная следующим образом:

[latex]get[/latex]_[latex]max(1, 1, n, l, r)[/latex]
вернет значение равное [latex]k[/latex]. Можно считать, что перед этим была вызвана функция

[latex]build(1, 1, n)[/latex]

— Хорошо, Дядя Федор!

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

Выходные данные:
Выведите единственное число – ответ на задачу.

Тесты:

Входные данные			Выходные данные
[latex]n[/latex]	[latex]k[/latex]	[latex]elem[/latex]_[latex]tree[][/latex]	[latex]ans[/latex]
5	3	1 2 3 2 3	11
10	6	1 4 7 6 2 4 1 9 6 6	7
20	15	5 2 4 7 15 3 15 20 31 15 15 1 23 4 8 15 1 2 15 6	43

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

import java.util.*;

public class Main
{
  public static void main(String[] args) 
  {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int k = in.nextInt();
    int[] elem_tree = new int[n];
    int ans=0, left=0, right=0;
    for(int i=0; i<n; i++){
    	elem_tree[i]=in.nextInt();
    	if (elem_tree[i]==k){
    		ans+=i-left+1;
    		right=i;
    	}
    	else{
    		if(elem_tree[i]>k){
        			right=0;
        			left=i+1;
    		}
    		else if(elem_tree[i]<k && right!=0) ans+=right-left+1;
    	}
    }
    System.out.println(ans);
  }
}

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int k = in.nextInt();

int[] elem_tree = new int[n];

int ans=0, left=0, right=0;

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

elem_tree[i]=in.nextInt();

if (elem_tree[i]==k){

ans+=i-left+1;

right=i;

}

else{

if(elem_tree[i]>k){

right=0;

left=i+1;

}

else if(elem_tree[i]<k && right!=0) ans+=right-left+1;

}

System.out.println(ans);

}

Алгоритм решения:
Зададим отрезок массива, на котором обозначим границы [latex]\left [ left, right \right ][/latex]. Инициализируем изначально оба конца нулем. Рассмотрим некоторое [latex]elem\_tree\left [ i \right ][/latex] на нашем сегменте. Тогда если [latex]elem\_tree\left [ i \right ]=k[/latex], то на всем отрезке от [latex]left[/latex] до [latex]i[/latex] максимумом будет [latex]k[/latex]. Увеличим в таком случае [latex]left[/latex] и сделаем его равным [latex]i[/latex], причем [latex]right=0.[/latex] Если [latex]elem\_tree\left [ i \right ]\lt k[/latex], максимум будет также равен [latex]k[/latex]. В таком случае увеличиваем только [latex]right.[/latex] Если же [latex]elem\_tree\left [ i \right ]\gt k[/latex] , то [latex]left[/latex] устанавливаем равным [latex]i+1[/latex], а [latex]right[/latex] обнуляем.
Пройдя по всему массиву, мы должны получить значения [latex]left[/latex] равное количеству пар в которых максимум равен [latex]k[/latex], а [latex]right[/latex] должно стать равным нулю.

Код программы на Java
Условие задачи

Условие задачи:
Даны действительные числа [latex]a_{1}, \ldots, a_{n}, b_{1}, \ldots, b_{n}[/latex]. Члены последовательности [latex]c_{1}, \ldots, c_{n+1}[/latex] связаны с членами данных последовательностей соотношениями [latex]c_{n+1}=0, c_{\left (n+1\right )-i}=\frac{a_{\left (n+1\right )-i}}{b_{\left (n+1\right )-i}-c_{\left (n+1\right )-i+1}} \left (i=1, \ldots, n \right ).[/latex] Получить [latex]c_{1}, \ldots, c_{n+1}[/latex].

Входные данные:
В первой строке задано число [latex]n[/latex]. В последующих строках записано две числовые последовательности из n чисел.

Выходные данные:
Вывести результирующую последовательность [latex]c[/latex], найденную согласно условию задачи.

Тесты:

Входные данные		Выходные данные
28	100 23 45 62 17 873 46 927 64 5 8 9 3 0 89 73 12 53 62 7 12 35 64 50 227 23 100 80 12 34 23 6 7 8 9 25 10 9 73 24 27 8 4 3 2 0 9 1 45 62 100 104 5 6 14 21	8.89145197864941 0.7532429753739995 3.46536409638595 10.014351523139867 -0.19111480725820545 95.9517680178081 -1.0983211464949347 50.88210356032888 6.781413598577088 0.5624396639914702 0.11015755091584475 0.3767441860465116 0.1111111111111111 0.0 4.803215151847447 -14.529255339679752 8.024345590557227 0.5045509487875016 -105.04390117066583 9.590229411789153 0.2700904535823736 0.5704400476332376 0.6438589905891021 0.5993533748082496 20.57676071984004 -6.031862745098037 9.813084112149534 3.8095238095238093 0.0
10	2 -4 1 2 45.2 34 -23 34 56 7.09 -3.4 4 4 -5 2.4 34.04 23 567 -3 4	-0.8567913942992066 -1.0657095142326265 0.24663198875517678 -0.05462407795229777 31.61389033873605 0.9702487256173882 -1.0025608427005548 0.05874893533055214 -11.733892090099529 1.7725 0.0

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

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 n=in.nextInt();
		double[] A = new double[n];
		double[] B = new double[n];
		double[] C = new double[n+1];
		String ans = new String("");
		double inf = 1.0 / 0;
		C[n] = 0.0;
		int k=0;
		while(k<n){
			A[k] = in.nextDouble();
			k++;
		}
		String c=in.nextLine();
		int t=0;
		while(t<n){
			B[t]=in.nextDouble();
			t++;
		}
		for (int i=1; i<=n; i++){
			if(B[n-i]-C[n-i+1]!=0) C[n-i]=A[n-i]/(B[n-i]-C[n-i+1]);
			else C[n-i]=inf;
		}
		for (int i=0; i<=n; i++){
			ans+=Double.toString(C[i])+" ";	
		}
		System.out.println(ans);
	}
}

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 n=in.nextInt();

double[] A = new double[n];

double[] B = new double[n];

double[] C = new double[n+1];

String ans = new String("");

double inf = 1.0 / 0;

C[n] = 0.0;

int k=0;

while(k<n){

A[k] = in.nextDouble();

k++;

}

String c=in.nextLine();

int t=0;

while(t<n){

B[t]=in.nextDouble();

t++;

}

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

if(B[n-i]-C[n-i+1]!=0) C[n-i]=A[n-i]/(B[n-i]-C[n-i+1]);

else C[n-i]=inf;

}

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

ans+=Double.toString(C[i])+" ";

}

System.out.println(ans);

}

Алгоритм решения:
Узнаем количество необходимых элементов: считаем число [latex]n[/latex]. С помощью двух циклов также считаем все элементы массивов [latex]a[/latex] и [latex]b[/latex]. Заведем еще один счетчик для нахождения значений ячеек нового массива, воспользовавшись нашей заданной формулой [latex]c_{\left (n+1\right )-i}=\frac{a_{\left (n+1\right )-i}}{b_{\left (n+1\right )-i}-c_{\left (n+1\right )-i+1}} \left (i=1, \ldots, n \right )[/latex] при условии, что [latex]c_{n+1}=0.[/latex] Выведем все элементы единой строкой.

Код программы на Java
Условие задачи

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

Author Archives: Валентина Андриеш

e-olymp4491 Трое из Простоквашино

A281 Последовательные вычисления значений нового массива