e-olymp 1868. Функция

27/12/2018 by Иван Василевский

Условие задачи
Вычислите функцию:
$$f(n)=\begin{cases} 1, \text{ если } n \leq 2 \\ f(\lfloor \frac{6\cdot n}{7} \rfloor)+f(\lfloor \frac{2\cdot n}{3} \rfloor), \text{ если } n \mod \; 2 = 1 \\ f(n-1)+f(n-3), \text{ если } n \mod \; 2 = 0 \end{cases}$$
Входные данные
Одно натуральное число $n$ $(1 \leq n \leq 10^{12})$
Выходные данные
Значение $f(n)$ , взятое по модулю $2^{32}$.
Тесты

Входные данные	Выходные данные
10	7
123	229966
1	1
100	136345
51	5092

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Map;
import java.util.HashMap;
import java.lang.Math;

class Main
{

    private static long mod = 1L << 32;
    public static Map<Long, Long> mp = new HashMap<Long, Long>();

    public static long f(long n) {
        if (n <= 2) {
            return 1;
        }
        if (mp.containsKey(n)) {
            return mp.get(n);
        }
        if (n % 2 == 1) {
            long d = (f(6 * n / 7) % mod + f(2 * n / 3) % mod) % mod;
            mp.put(n, d);
            return mp.get(n);
        }
        long o = (f(n - 1) % mod + f(n - 3) % mod) % mod;
        mp.put(n, o);
        return mp.get(n);
    }


    public static void main (String[] args) throws java.lang.Exception
    {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] params1 = bufferedReader.readLine().split(" ");
        long n;
        n = Long.parseLong(params1[0]);
        System.out.print(f(n));
    }
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

import java.util.Map;

import java.util.HashMap;

import java.lang.Math;

class Main

{

private static long mod = 1L << 32;

public static Map<Long, Long> mp = new HashMap<Long, Long>();

public static long f(long n) {

if (n <= 2) {

return 1;

}

if (mp.containsKey(n)) {

return mp.get(n);

}

if (n % 2 == 1) {

long d = (f(6 * n / 7) % mod + f(2 * n / 3) % mod) % mod;

mp.put(n, d);

return mp.get(n);

}

long o = (f(n - 1) % mod + f(n - 3) % mod) % mod;

mp.put(n, o);

return mp.get(n);

}

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

{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

String[] params1 = bufferedReader.readLine().split(" ");

long n;

n = Long.parseLong(params1[0]);

System.out.print(f(n));

}

Решение задачи
Решение данной задачи стоит начать с написания рекурсивной функции для вычисления функций по условию задачи. Так как рекурсия будет довольно таки сложной и много раз повторяются одни и те же результаты при вызове функции, следовательно, программа будет долгое время обрабатывать нашу задачу. То есть, к примеру, на 5 и 20 итерации, возвращаемые значения функции могут совпасть, что без оптимизации будет просчитываться еще раз, а с оптимизацией функция уже знает, чему равно значение с данными аргументами.Далее, по условию, мы пишем наконец нашу функцию:

Если число, которое ввел пользователь, меньше либо равно двум, то наша функция возвращает значение один.
Если есть значение с таким же ключом, то оно возвращает значение.
Если число, которое ввел пользователь, дает остаток от деления один, то наша функция возвращает значение $f(\lfloor \frac{6\cdot n}{7} \rfloor)+f(\lfloor \frac{2\cdot n}{3} \rfloor)$.
Во всех остальных случаях наша функция возвращает значение $f(n-1)+f(n-3)$.

Ссылки
Задача на сайте e-olymp
Код решения в Ideone

e-olymp 662. Налог

27/12/2018 by Иван Василевский

Условие задачи

«Курс валюты Зимбабве опустился накануне до рекордно низкого уровня — $1.2$ млрд. зимбабвийских долларов за один доллар США»
(Новости от $07.06.2009$ )

В некоторой стране инфляция достигла таких размеров, что доходы граждан стали выражаться числами, количество знаков в десятичной записи которых доходит до $200$. Это сильно усложнило задачу взимания налогов.

Один из налогов на доходы составляет $1$. Напишите программу, которая по введенному числу $D$ (величине дохода гражданина) вычислит этот налог.

При этом применяются следующие правила округления:

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

Входные данные
Вводится одно число $D$ (натуральное,$10^{5}⩽D<10^{200}$ ) – величина дохода гражданина.
Выходные данные
Выведите одно натуральное число – величину налога.
Тесты

Входные данные	Выходные данные
12345600	123456
158874554	1588746
1000001	10001
555555	5556

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

import java.io.BufferedReader;
import java.io.InputStreamReader;

class Main
{
  public static void main (String[] args) throws java.lang.Exception
  {
    BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    String s = bufferedReader.readLine().split(" ")[0];
    if (s.substring(s.length() - 2, s.length() - 2 + 2).equals("00"))
    {
      System.out.print(s.substring(0, s.length() - 2));
    }
    else
    {
      for (int i = s.length() - 3; i >= 0; --i)
      {
        if ((int)s.charAt(i) - 48 + 1 == 10)
        {
          s = s.substring(0, i) + "0" + s.substring(i + 1);
          if (i == 0)
          {
            System.out.print("1");
          }
          continue;
        }
        else
        {
        	s = s.substring(0, i) + (char)(s.charAt(i) + 1) + s.substring(i + 1);
          break;
        }
      }
      System.out.print(s.substring(0, s.length() - 2));
    }
    return;
  }
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

class Main

{

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

{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

String s = bufferedReader.readLine().split(" ")[0];

if (s.substring(s.length() - 2, s.length() - 2 + 2).equals("00"))

{

System.out.print(s.substring(0, s.length() - 2));

}

else

{

for (int i = s.length() - 3; i >= 0; --i)

{

if ((int)s.charAt(i) - 48 + 1 == 10)

{

s = s.substring(0, i) + "0" + s.substring(i + 1);

if (i == 0)

{

System.out.print("1");

}

continue;

}

else

{

s = s.substring(0, i) + (char)(s.charAt(i) + 1) + s.substring(i + 1);

break;

}

System.out.print(s.substring(0, s.length() - 2));

}

return;

}

Решение задачи
Так как у нас по условию $10^{200}$ нам нужно использовать String, ибо в long такое число не поместится. Поэтому, есть строка, каждый символ которой, это цифра. Округляем по условию, то есть если последние два символа — нули, то просто выдаем подстроку, без последних двух символов ( s.substring(0, s.length() - 2) ). В любом случае, нужно округлять вверх, для этого, к третей с конца цифре добавляем один. Если цифра была $9$, то она станет $0$, а к следующей по возрастанию цифре применим такое-же действие. Если текущая цифра последняя, то нужно добавить перед ней еще единицу.
Ссылки
Задача на сайте e-olymp
Код решения в Ideone

e-olymp 936. Формулы Крамера

27/12/2018 by Иван Василевский

Условие задачи
Решить систему двух линейных уравнений с двумя неизвестными по формулам Крамера. Система уравнений, приведенная во входных данных, имеет вид:
$\begin{cases} 5x_1+8x_2=11 \\ -3x_1+6x_2=15 \end{cases}$
Входные данные
Первая строка содержит коэффициенты первого уравнения, а вторая строка содержит коэффициенты второго. Все входные числа разделены одним пробелом и не превышают по модулю $100$.
Выходные данные
Первый корень системы уравнений вывести в первой строке, а второй корень во второй строке с точностью до $0.001$.
Тесты

Входные данные	Выходные данные
5 8 1 -3 6 15	-1.000 2.000
5 5 5 2 3 5	-2.000 3.000
1 2 3 3 3 3	-1.000 2.000
25 15 16 11 12 13	-0.022 1.104

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        double matrix[][] = new double[3][2];
        for (int i = 0; i < 2; ++i){
            String[] params1 = bufferedReader.readLine().split(" ");
            for (int j = 0; j < 3; ++j){
                matrix[j][i] = Float.parseFloat(params1[j]);
            }
        }
        double d = matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];
        double d1 = matrix[2][0] * matrix[1][1] - matrix[2][1] * matrix[1][0];
        double d2 = matrix[0][0] * matrix[2][1] - matrix[0][1] * matrix[2][0];
        System.out.printf("%.3f\n%.3f\n", d1 / d, d2 / d);
	}
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

class Main

{

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

{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

double matrix[][] = new double[3][2];

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

String[] params1 = bufferedReader.readLine().split(" ");

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

matrix[j][i] = Float.parseFloat(params1[j]);

}

double d = matrix[0][0] * matrix[1][1] - matrix[0][1] * matrix[1][0];

double d1 = matrix[2][0] * matrix[1][1] - matrix[2][1] * matrix[1][0];

double d2 = matrix[0][0] * matrix[2][1] - matrix[0][1] * matrix[2][0];

System.out.printf("%.3f\n%.3f\n", d1 / d, d2 / d);

}

Решение задачи
Создаем матрицу размером $3$ на $2$, так как у нас $3$ переменных в $2$ уравнениях. Создаем циклы для заполнения нашей матрицы. Дальше по формуле Камера перемножаем переменные. Выводим на экран ответы с точностью до $0.001$.
Ссылки
Задача на сайте e-olymp
Код решения в Ideone

e-olymp 922. Сдвинь элементы

27/12/2018 by Иван Василевский

Условие задачи
Задан массив целых чисел длины $n$. Сдвинуть элементы массива вправо циклически на $1$ шаг.
Входные данные
В первой строке задано количество элементов массива $n$$(n ≤ 100)$ . Во второй строке заданы сами элементы массива, значение каждого из которых по модулю не превышает $100$.
Выходные данные
В одной строке вывести $n$ чисел — новые значения элементов массива.
Тесты

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

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] params1 = bufferedReader.readLine().split(" ");
        int number;
        number = Integer.parseInt(params1[0]);
        int arr[] = new int[number];
        String[] params2 = bufferedReader.readLine().split(" ");
        for (int i = 0; i < number; i++)
        {
            arr[i] = Integer.parseInt(params2[i]);
        }
        int last = arr[number - 1];
        for (int i = number - 1; i > 0; i--)
        {
            arr[i] = arr[i - 1];
        }
        arr[0] = last;
        for (int i = 0; i < number; i++)
        {
            System.out.print(arr[i]);
            System.out.print(' ');
        }
	}
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

class Main

{

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

{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

String[] params1 = bufferedReader.readLine().split(" ");

int number;

number = Integer.parseInt(params1[0]);

int arr[] = new int[number];

String[] params2 = bufferedReader.readLine().split(" ");

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

{

arr[i] = Integer.parseInt(params2[i]);

}

int last = arr[number - 1];

for (int i = number - 1; i > 0; i--)

{

arr[i] = arr[i - 1];

}

arr[0] = last;

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

{

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

System.out.print(' ');

}

Решение задачи
Создаем динамический массив, размером в number элементов. Создаем переменную last, в которой записан последний элемент массива. Создаём цикл, в котором меняется каждый элемент массива с предыдущим. Кладем на $1$ место (точнее $0$ место) бывший последний элемент массива.
Выводим массив.
Ссылки
Задача на сайте e-olymp
Код решения в Ideone

e-olymp 176. Выбор вождя

27/12/2018 by Иван Василевский

Условие задачи
Орки – одна из рас, населяющих мир Драэнор. Не отличаясь высоким интелектом, орки все же славятся своею силой и отвагой в бою. Ежегодно орки из разных кланов собираются в Долине Силы для того, чтобы избрать вождя всей Орды. В отличие от глупых людей, орки презирают выборы посредством голосования (да и, скажем прямо, все эти бюлетени, урны и избирательные участки чужды и непонятны орку, не державшему в руках ничего, кроме дубины и топора). Кандидаты в вожди сражаются друг с другом в честных поединках. В каждом поединке участвуют два претендента, один из которых выходит из него победителем, а другой оказывается поверженным. Проигравший в одном поединке орк выбывает из числа претендентов и не может участвовать в последующих поединках. Оставшийся в конце концов после всех боев кандидат и становит вождем Орды.

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

Старейшины обратились к вам с просьбой написать программу для определения количества претендентов, которые могут стать вождями.
Входные данные
В первой строке входного файла записано количество $N$ претендентов на звание вождя в этом году $(1 ≤ N ≤ 1000000)$, а во второй – $N$ целых чисел в пределах от $1$ до $10000$, каждое из которых определяет силу соответствующего кандидата.
Выходные данные
Выходной файл должен содержать одно число – количество претендентов, которые могут стать вождями.
Тесты

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

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] params1 = bufferedReader.readLine().split(" ");
        int quantity, force, count = 0, max = 0;
        quantity = Integer.parseInt(params1[0]);
     
        String[] params2 = bufferedReader.readLine().split(" ");
        for(int i = 0; i < quantity; ++i)
        {
            force = Integer.parseInt(params2[i]);
            if (force > max)
            {
                max = force;
                count = 1;
            }
            else if (force == max) count++;
        }
        System.out.print(count);
	}
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

class Main

{

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

{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

String[] params1 = bufferedReader.readLine().split(" ");

int quantity, force, count = 0, max = 0;

quantity = Integer.parseInt(params1[0]);

String[] params2 = bufferedReader.readLine().split(" ");

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

{

force = Integer.parseInt(params2[i]);

if (force > max)

{

max = force;

count = 1;

}

else if (force == max) count++;

}

System.out.print(count);

}

Решение задачи
Так как задача на потоковую обработку создаем цикл, который работает пока у нас вводится число «Сила Орков». В самом цикле происходит следующее:

Если «Сила Орков» больше max, то мы в переменную max присваиваем значение из «Силы Орков» и счетчику присваиваем единицу.
Если «Сила Орков» равна max то мы прибавляем к счетчику $1$.

Выводим счетчик на экран.
Ссылки
Задача на сайте e-olymp
Код решения в Ideone

e-olymp 842. Разложение на простые множители

25/12/2018 by Иван Василевский

Условие задачи
Вывести представление целого числа $n$ в виде произведения простых чисел.
Входные данные
Единственное число $n (2 \leq n \leq 2^{31} — 1).$
Выходные данные
Вывести список простых множителей в порядке неубывания, разделённых знаком «$*$».
Тесты

Входные данные	Выходные данные
30	235
16	222*2
5	5

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

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String[] params1 = bufferedReader.readLine().split(" ");
        long numb, divisor = 2;
        numb = Integer.parseInt(params1[0]);
        while (divisor*divisor <= numb)
        {
            if (numb%divisor == 0)
            {
                System.out.print(divisor);
                numb = numb / divisor;
                System.out.print('*');
            }
            else if (divisor == 2) divisor = 3;
            else divisor = divisor + 2;
        }
        System.out.print(numb);
	}
}

import java.io.BufferedReader;

import java.io.InputStreamReader;

class Main

{

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

{

BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

String[] params1 = bufferedReader.readLine().split(" ");

long numb, divisor = 2;

numb = Integer.parseInt(params1[0]);

while (divisor*divisor <= numb)

{

if (numb%divisor == 0)

{

System.out.print(divisor);

numb = numb / divisor;

System.out.print('*');

}

else if (divisor == 2) divisor = 3;

else divisor = divisor + 2;

}

System.out.print(numb);

}

Решение задачи
Пока наше число больше либо равно divisor*divisor выполняется:

Если numb делится нацело на divisor, мы выводим наш делитель, следовательно numb делится на divisor;
В противном случае:

Если divisor равен $2$ , то присваиваем ему значение $3$ и повторяем;
В другом случае увеличиваем его на $2$;

Таким образом перебираются $2$,$3$ и $5$, которые являются делителем для всех чисел.
Ссылки
Задача на сайте e-olymp
Код решения в Ideone

e-olymp 519. Сумма квадратов

09/12/2018 by Иван Василевский

Условие задачи
Найти сумму квадратов двух чисел.
Входные данные
Два целых числа $a$ и $b$. Числа не превышают $10^9$ по абсолютной величине.
Выходные данные
Выведите одно целое число $a^2+b^2$
Тесты

Входные данные	Выходные данные
2 2	8
5 5	50
-5 -2	29
500 500	500000
1210 1250	3026600

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

import java.util.*;

public class Main
{
  public static void main(String []args)
  {
    Scanner scanner = new Scanner(System.in);
    long a = scanner.nextLong();
    long b = scanner.nextLong();
    System.out.println(a * a + b * b);
  }
}

import java.util.*;

public class Main

{

public static void main(String []args)

{

Scanner scanner = new Scanner(System.in);

long a = scanner.nextLong();

long b = scanner.nextLong();

System.out.println(a * a + b * b);

}

Решение задачи
Создаем 2 переменные a и b, в которые записываем данные, дальше выводим на экран одно целое число, которое равно $a^2+b^2$.
Ссылки
Задача на сайте e-olymp
Код решения в Ideone

10

7

123

229966

1

1

100

136345

51

5092

12345600

123456

158874554

1588746

1000001

10001

555555

5556

5 8 1 -3 6 15

-1.000 2.000

5 5 5 2 3 5

-2.000 3.000

1 2 3 3 3 3

-1.000 2.000

25 15 16 11 12 13

-0.022 1.104

4 1 2 3 4 5

4 1 2 3

6 3 3 3 3 3 1

1 3 3 3 3 3

2 1 2

2 1

5 1 2 3 4 5

1

6 2 2 2 2 2 2

6

6 3 2 1 3 1 1

2

30

2*3*5

16

2*2*2*2

5

5

2 2

8

5 5

50

-5 -2

29

500 500

500000

1210 1250

3026600

5 8 1
-3 6 15

-1.000
2.000

5 5 5
2 3 5

-2.000
3.000

1 2 3
3 3 3

-1.000
2.000

25 15 16
11 12 13

-0.022
1.104

4
1 2 3 4 5

6
3 3 3 3 3 1

2
1 2

5
1 2 3 4 5

6
2 2 2 2 2 2

6
3 2 1 3 1 1

235

222*2