Сумма делителей

23/12/2018 by Алиса Ворохта

Данная задача является упрощенным вариантом задания олимпиады KPI-OPEN 2018.

Задача

Жил-был в тридевятом государстве мальчик по имени Костя. Он был старательным учеником и получал исключительно высокие баллы по всем предметам. И вот наш герой очень захотел стать отличником, но ему не хватало нескольких баллов по алгебре. Для того чтобы их набрать, профессор дал Косте следующую задачу:
Найти сумму делителей данного числа $n.$
Костя обратился к Вам как к опытному программисту, который знает алгебру, с просьбой о помощи решить данную задачу.

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

Одно целое число $n \left(1 \leqslant n < 10^{10}\right).$

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

Выведите сумму делителей числа $n.$

Тесты

Входные данные	Выходные данные
$12$	$28$
$239$	$240$
$1234$	$1854$
$6$	$12$
$1000000007$	$1000000008$
$44100$	$160797$
$223092870$	$836075520$
$2147483648$	$4294967295$
$678906$	$1471002$
$1111111$	$1116000$
$9876543210$	$27278469036$
$99460729$	$99470703$
$5988$	$14000$
$1$	$1$
$1348781387$	$1617960960$
$135792$	$406224$
$5402250$	$17041284$
$375844500$	$1259767236$
$1000000000$	$2497558338$
$2357947691$	$2593742460$

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		long sumOfDivisors = 1;
		Scanner in = new Scanner(System.in);
        long n = in.nextLong();
        HashMap<Long, Long> primeDivInPow = new HashMap<>();
        for(long i = 2; i * i <= n; i++){
	        while(n % i == 0){
	            if(primeDivInPow.containsKey(i) == false){
	                primeDivInPow.put(i, (long) 1);
	            }
	            primeDivInPow.put(i, primeDivInPow.get(i) * i);
	            n /= i;
	        }
        }
        if(n != 1){
        	primeDivInPow.put(n, n);
		}
		for (Map.Entry<Long, Long> entry : primeDivInPow.entrySet()) {
			 sumOfDivisors *= (entry.getValue() * entry.getKey() - 1) / (entry.getKey() - 1);
		}
		System.out.println(sumOfDivisors);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

long sumOfDivisors = 1;

Scanner in = new Scanner(System.in);

long n = in.nextLong();

HashMap<Long, Long> primeDivInPow = new HashMap<>();

for(long i = 2; i * i <= n; i++){

while(n % i == 0){

if(primeDivInPow.containsKey(i) == false){

primeDivInPow.put(i, (long) 1);

}

primeDivInPow.put(i, primeDivInPow.get(i) * i);

n /= i;

}

if(n != 1){

primeDivInPow.put(n, n);

}

for (Map.Entry<Long, Long> entry : primeDivInPow.entrySet()) {

sumOfDivisors *= (entry.getValue() * entry.getKey() - 1) / (entry.getKey() - 1);

}

System.out.println(sumOfDivisors);

}

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

Пусть $n$ имеет каноническое разложение $n = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots p_k^{\alpha_k},$ где $p_1 < p_2 < \ldots <p_k$ — простые делители числа $n$, $\alpha_1, \alpha_2,\ldots, \alpha_k \in \mathbb {N}$. Тогда сумма натуральных делителей числа $n$ равна $\sigma\left(n\right) = \left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\times$$\times\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right).$
Доказательство.
Рассмотрим произведение:
$\left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right)$
Если раскрыть скобки, то получим сумму членов ряда:
$p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\ldots\cdot p_k^{\beta_k},$ где $0\leqslant\beta_m\leqslant\alpha_m \left(m = 1, 2, \ldots, k\right)$
Но такие члены являются делителями $n$, причем каждый делитель входит в сумму только один раз. Поэтому рассмотренное нами произведение равно сумме всех делителей $n,$ т.е. равно $\sigma\left(n\right).$ Итак, $\sigma\left(n\right)$ можно вычислить по нашей формуле. С другой стороны, каждая сумма $1 + p_m + p_m^2+\ldots+p_m^{\alpha_m}$ является суммой геометрической прогрессии с первым членом $1$ и знаменателем $p_m$. Поэтому иначе данную формулу можно переписать так:
$$\sigma\left(n\right) = \frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdot\frac{p_2^{\alpha_2+1}-1}{p_2-1}\cdot\ldots\cdot\frac{p_k^{\alpha_k+1}-1}{p_k-1}.$$

Ссылки

Код решения

e-olymp 1108. Червячные дыры

23/12/2018 by Алиса Ворохта

Задача

В $2163$ году были обнаружены червячные дыры. Червячная дыра представляет собой тоннель сквозь пространство и время, соединяющий две звездные системы. Эти дыры имеют следующие свойства:

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

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

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

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

Первая строка содержит количество звездных систем $n$ $(1 ≤ n ≤ 1000)$ и количество червячных дыр $m$ $(0 ≤ m ≤ 2000)$. Звездные системы пронумерованы от $0$ (наша солнечная система) до $n — 1$. Каждая червячная дыра описывается в отдельной строке и содержит три целых числа $x$, $y$ и $t$. Эти числа указывают на возможность передвижения из звездной системы с номером $x$ в звездную систему с номером $y$, при этом время изменяется на $t$ $(-1000 ≤ t ≤ 1000)$ лет.

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

Cтрока содержит информацию, возможно ли в заданном множестве систем попасть в минус бесконечность во времени используя червячные дыры. Выводить следует строку «possible» или «not possible».

Тесты

Входные данные	Выходные данные
$3$ $3$ $0$ $1$ $1000$ $1$ $2$ $15$ $2$ $1$ $-42$	possible
$4$ $4$ $0$ $1$ $10$ $1$ $2$ $20$ $2$ $3$ $30$ $3$ $0$ $-60$	not possible
$3$ $3$ $0$ $1$ $-100$ $1$ $2$ $1$ $2$ $1$ $0$	not possible

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

class Main
{
	private static class Node {
        private int x;
        private int y;
        private int t;
 
        private Node(int x, int y, int t) {
            this.x = x;
            this.y = y;
            this.t = t;
        }
    }
	public static void main (String[] args) throws java.lang.Exception
	{
    	Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		Node r = null;
		Node[] canals = new Node[m + 1];
		for (int i = 0; i < m; i++) {
        	int x = in.nextInt();
			int y = in.nextInt();
			int t = in.nextInt();
			r = new Node(x, y, t);
        	canals[i] = r;
		}
		int INF = 2000000;
		int[] distance = new int[n + 1];
		int subs = -1;
		for (int i = 0; i < n; i++) {
        	subs = -1;
        	for (int j = 0; j  distance[canals[j].x] + canals[j].t) {
                	distance[canals[j].y] = Math.max (-INF, distance[canals[j].x] + canals[j].t);
                	subs = canals[j].y;
            	}
            }
    	}
    	if (subs == -1) {
    		System.out.println("not possible");
    	}
    	else {
        	System.out.println("possible");
    	}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

private static class Node {

private int x;

private int y;

private int t;

private Node(int x, int y, int t) {

this.x = x;

this.y = y;

this.t = t;

}

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

{

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int m = in.nextInt();

Node r = null;

Node[] canals = new Node[m + 1];

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

int x = in.nextInt();

int y = in.nextInt();

int t = in.nextInt();

r = new Node(x, y, t);

canals[i] = r;

}

int INF = 2000000;

int[] distance = new int[n + 1];

int subs = -1;

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

subs = -1;

for (int j = 0; j distance[canals[j].x] + canals[j].t) {

distance[canals[j].y] = Math.max (-INF, distance[canals[j].x] + canals[j].t);

subs = canals[j].y;

}

if (subs == -1) {

System.out.println("not possible");

}

else {

System.out.println("possible");

}

Описание решения

Решение данной задачи сводится к нахождению отрицательного цикла в ориентированном графе. Необходимо воспользоваться алгоритмом Форда-Беллмана.
Создадим массив на $n$ элементов и заполним его нулями. Алгоритм основан на том, что если в графе размерностью $n$ элементов нет отрицательных циклов, то после $n-1$ прохождения изменения в массиве кратчайших расстояний не будет. Поэтому, будем выполнять следующее $n$ раз:

Возьмем первое ребро из массива $canals$, и проведем сравнение: если исходная длина пути конца данного ребра из исходного массива $distance$ больше, чем сумма длины пути начала массива и стоимости прохода по данному ребру $canals[].t$, то изменим в массиве $distance$ элемент с номером конца исходного ребра, и изменим индикатор изменений $subs$, чтобы показать, что в ходе данного прохода были внесены изменения.
Переходим к следующему ребру.

Если после во время последнего прохода ни разу не была изменена переменная $subs$, то это значит, что в графе нет циклов отрицательной длины, и тогда выводим «not possible». Иначе, выводим «possible».

Ссылки

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

e-olymp 595. Новый Лабиринт Амбера

17/12/2018 by Алиса Ворохта

Задача

Как-то Корвину – принцу Амбера, по каким-то важным делам срочно понадобилось попасть в самую далекую тень, которую он только знал. Как всем известно, самый быстрый способ путешествия для принцев Амбера – это Лабиринт Амбера. Но у Корвина были настолько важные дела, что он не хотел тратить время на спуск в подземелье (именно там находится Амберский Лабиринт). Поэтому он решил воспользоваться Новым Лабиринтом, который нарисовал Дворкин. Но этот Лабиринт не так прост, как кажется…

Новый Лабиринт имеет вид последовательных ячеек, идущих друг за другом, пронумерованных от 1 до N. Из ячейки под номером i можно попасть в ячейки под номерами $i+2$ (если $i+2 ≤ N$) и $i+3$ (если $i+3 ≤ N$). На каждой ячейке лежит какое-то количество золотых монет $k_i$. Для того чтобы пройти лабиринт нужно, начиная ходить из-за границ лабиринта (с нулевой ячейки) продвигаться по выше описанным правилам, при этом подбирая все монетки на ячейках, на которых вы делаете промежуточные остановки. Конечная цель путешествия – попасть на ячейку с номером N. Дальнейшее путешествие (в любое место Вселенной) возможно лишь тогда, когда достигнув ячейки с номером N, вы соберете максимально количество монеток. Напишите программу, которая поможет Корвину узнать, какое максимальное количество монеток можно собрать, проходя Новый Лабиринт Амбера.

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

В первой строке входного файла содержится натуральное число $N$ $(2 ≤ N ≤ 100000)$, а во второй $N$ целых чисел, разделенных одним пробелом, $k_i$ – количество монеток лежащих в ячейке с номером $i (0 ≤ k_i ≤ 1000)$.

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

В выходной файл вывести одно целое число – максимальное количество монеток, которое можно собрать, проходя лабиринт.

Тесты

Входные данные	Выходные данные
$5$ $1000$ $2$ $3$ $1$ $3$	$6$
$2$ $1$ $2$	$5610$
$4$ $1$ $3$ $100$ $0$	$3$

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int n;
		Scanner in = new Scanner(System.in);
		n = in.nextInt();
		int[] dp = new int[n + 1];
		for(int i = 1; i <= n; ++i){
			dp[i] = in.nextInt();
		}
		dp[1] = -1;
		for(int i = 3; i<=n; ++i){
			dp[i] = dp[i] + Math.max(dp[i-2], dp[i-3]);
		}
		System.out.println(dp[n]);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

int n;

Scanner in = new Scanner(System.in);

n = in.nextInt();

int[] dp = new int[n + 1];

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

dp[i] = in.nextInt();

}

dp[1] = -1;

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

dp[i] = dp[i] + Math.max(dp[i-2], dp[i-3]);

}

System.out.println(dp[n]);

}

Описание

Для хранения количества монет в каждой ячейке лабиринта используем массив $dp$ длиной $n + 1$ элементов. При этом каждой ячейке лабиринта соответствует ячейка массива с тем же индексом, а нулевой элемент массива понимаем как точку перед входом в лабиринт. В цикле считываем количество монет в каждой ячейке, после чего значение первого элемента массива делаем отрицательным, поскольку в ячейку, соответствующую ему, невозможно попасть никаким образом. Далее в цикле для каждой ячейки лабиринта находим, какое максимальное количество монет может быть у Корвина после её посещения. В ячейку с номером $i$ он может попасть или из ячейки с номером $i — 2$, или из ячейки с номером $i — 3$. При этом он несёт с собой все собранные ранее монеты, и добавляет к ним те, что находятся в данной ячейке. Таким образом, формула для нахождения максимального количества монет после посещения $i$-й ячейки имеет вид $dp_i = dp_i + max\{dp_{i — 2}; dp_{i — 3}\}$, и ответ к задаче хранится в $n$-й ячейке массива.

Ссылки

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

e-olymp 4475. Часы

09/12/2018 by Алиса Ворохта

Задача

Жители планеты Олимпия любят летать в гости на другие планеты. Ученые планеты разработали часы, которые могут налаживаться для отсчета времени на любой планете. Эти часы состоят из шариков, лотка (очереди) и трех чаш: секундной, минутной и часовой. В каждый момент времени количество шариков в чашах показывает время (секунды, минуты и часы соответственно). Каждую секунду первый шарик из очереди попадает в секундную чашу. Если секундная чаша наполнилась (количество шариков равно количеству секунд в минуте на этой планете), то этот шарик переходит в минутную чашу, а остальные шарики переходят из секундной чаши в конец очереди в порядке, обратном к их попаданию в секундную чашу. Аналогично, при наполнении минутной чаши последний шарик переходит в часовую чашу, а остальные шарики из минутной чаши переходят в конец очереди в порядке, обратном к их попаданию в минутную чашу. Если заполняется часовая чаша, то все шарики из нее переходят в конец очереди в порядке, обратном к их попаданию в часовую чашу. Все шарики пронумерованы и в начальный момент времени находятся в очереди.

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

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

Входной файл содержит в единственной строке натуральные числа $S, M, H, K$ (количество секунд в минуте, минут в часе, часов в сутках и общее количество шариков соответственно), причем:

$S, M, H ≤ 60$;
$S+M+H-2≤K≤1000$

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

Выходной файл должен содержать в единственной строке вычисленное Вашей программой количество суток.

Тесты

Входные данные	Выходные данные
$5$ $12$ $12$ $30$	$380$
$7$ $10$ $40$ $70$	$5610$
$60$ $60$ $60$ $500$	$4560840$
$60$ $30$ $5$ $1000$	$4970$

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

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

class Main
{
	public static double gcd(double a, double b){
		double temp;
    	while(b > 0){
        	a = a - b*Math.floor(a/b);
        	temp = a;
			a = b;
	    	b = temp;
    	}
    	return a;
    }
    public static double lcm(double a, double b){
    	return a*(b/gcd(a,b));
    }
	public static void main (String[] args) throws java.lang.Exception
	{
    	int S, M, H, K;
		Scanner in = new Scanner(System.in);
		S = in.nextInt();
		M = in.nextInt();
		H = in.nextInt();
		K = in.nextInt();
		Deque clock = new ArrayDeque(); 
		for(int i = 1; i <= K; i++)
    		clock.addLast(i);
    	Stack s = new Stack();
    	Stack m = new Stack();
    	Stack h = new Stack();
    	while(h.size() != H){
    		s.push(clock.getFirst());  //первый шарик очереди падает
    		clock.removeFirst();       //на секундную чашу
    		if(s.size() == S){         //при переполнении чаши  
				m.push(s.peek());      //последний упавший шарик
    			s.pop();               //переходит на минутную чашу
    			while(!s.empty()){     //остальные шарики  
					clock.addLast((Integer)s.peek());   //переходят в конец очереди
					s.pop();           //в обратном порядке     
				}
				if(m.size() == M){     //аналогично при переполнении          
					h.push(m.peek());  //минутной чаши      
					m.pop();
					while(!m.empty()){
						clock.addLast((Integer)m.peek());
						m.pop();
					}
				}
			}
		}
		while(!h.empty()){
			clock.addLast((Integer)h.peek());
			h.pop();
		}
		/*суточная перестановка
		1  2  3  4  5  6  ... K
		a1 a2 a3 a4 a5 a6 ... ak*/
		int[] permutation = new int[K + 1];
		for(int i = 1; i <= K; i++){
			permutation[i] = clock.getFirst();
			clock.removeFirst();
		}
		//разложение перестановки в композицию непересекающихся циклов
		boolean[] used = new boolean[K+1]; 
		double permutationOrder = 1;    //метки на посещенных элементах
		for(int i = 1; i <= K; i++){    //порядок перестановки
		if(!used[i]){    //если элемент не принадлежит ни одному из обследованных циклов
				double cycleLength = 1;  //найти длину его цикла
				for(int x = i; permutation[x] != i; x = permutation[x]){
					used[x] = true;
					cycleLength++;
				}
				/*и воспользоваться тем, что порядок перестановки -
				произведение длин циклов из его разложения*/
				permutationOrder = lcm(permutationOrder, cycleLength);
			}
    	}
    	System.out.print(Math.round(permutationOrder));
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static double gcd(double a, double b){

double temp;

while(b > 0){

a = a - b*Math.floor(a/b);

temp = a;

a = b;

b = temp;

}

return a;

}

public static double lcm(double a, double b){

return a*(b/gcd(a,b));

}

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

{

int S, M, H, K;

Scanner in = new Scanner(System.in);

S = in.nextInt();

M = in.nextInt();

H = in.nextInt();

K = in.nextInt();

Deque clock = new ArrayDeque();

for(int i = 1; i <= K; i++)

clock.addLast(i);

Stack s = new Stack();

Stack m = new Stack();

Stack h = new Stack();

while(h.size() != H){

s.push(clock.getFirst()); //первый шарик очереди падает

clock.removeFirst(); //на секундную чашу

if(s.size() == S){ //при переполнении чаши

m.push(s.peek()); //последний упавший шарик

s.pop(); //переходит на минутную чашу

while(!s.empty()){ //остальные шарики

clock.addLast((Integer)s.peek()); //переходят в конец очереди

s.pop(); //в обратном порядке

}

if(m.size() == M){ //аналогично при переполнении

h.push(m.peek()); //минутной чаши

m.pop();

while(!m.empty()){

clock.addLast((Integer)m.peek());

m.pop();

}

while(!h.empty()){

clock.addLast((Integer)h.peek());

h.pop();

}

/*суточная перестановка

1 2 3 4 5 6 ... K

a1 a2 a3 a4 a5 a6 ... ak*/

int[] permutation = new int[K + 1];

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

permutation[i] = clock.getFirst();

clock.removeFirst();

}

//разложение перестановки в композицию непересекающихся циклов

boolean[] used = new boolean[K+1];

double permutationOrder = 1; //метки на посещенных элементах

for(int i = 1; i <= K; i++){ //порядок перестановки

if(!used[i]){ //если элемент не принадлежит ни одному из обследованных циклов

double cycleLength = 1; //найти длину его цикла

for(int x = i; permutation[x] != i; x = permutation[x]){

used[x] = true;

cycleLength++;

}

/*и воспользоваться тем, что порядок перестановки -

произведение длин циклов из его разложения*/

permutationOrder = lcm(permutationOrder, cycleLength);

}

System.out.print(Math.round(permutationOrder));

}

Алгоритм решения

Интуитивно понятно, что положение шариков в очереди ежесуточно изменяется по одному и тому же закону, в силу однообразия процесса. Отыскать конкретный вид перестановки можно прямым моделированием часов, используя дек для описания лотка и стеки — каждой из чаш (у очереди задействованы оба конца, у чаш — только один).
Определить порядок суточной перестановки можно и возведением её в степень, но это нерациональный способ. Используя теорему о разложении перестановки в композицию циклов (к слову, непересекающихся), можно заметить, что порядок каждого из циклов равен его длине. Если мысленно представить перестановку в виде ориентированного графа, то процесс поиска циклов сведётся к поиску в глубину: обойти каждую компоненту связности, зафиксировать число входящих в неё вершин (на илл.)
$\begin{pmatrix}
1& 2& 3& 4& 5& 6& 7& 8& 9& 10\\
1& 5& 8& 2& 4& 3& 7& 7& 6& 10
\end{pmatrix}$
Зная длины всех циклов, нетрудно заметить, что задача сводится к поиску НОК полученной последовательности длин. Обосновать такой переход можно индуктивно: порядок перестановки, представимой в виде композиции двух циклов, равен НОК их длин, а случай большего количества циклов в разложении сводится к рассмотренному последовательным рассмотрением пар циклов (результат не зависит от порядка рассмотрения в силу ассоциативности композиции).

Примечание

Операция взятия остатка для чисел с плавающей точкой не определена аппаратно, так что алгоритм Евклида вычисления НОД реализован в соответствии с его математическим описанием.

Ссылки

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

AA19

08/12/2018 by Алиса Ворохта

Задача

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

Тесты

Входные данные	Выходные данные
the more I code … better my coding becomes	the more I code the better my coding becomes
…what am I supposed to do?	…what am I supposed to do?
abc……..	abcabcabc..

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

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);
		String s = in.nextLine();
		String substr = s.substring(0, 3);
		String dots = "...";
		String ellipsis = "…";
		if (!substr.equals(dots) && !s.substring(0, 1).equals(ellipsis)) {
			s = s.replace(dots, substr);
			s = s.replace(ellipsis, substr);
		}
	System.out.print(s);
	}
}

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);

String s = in.nextLine();

String substr = s.substring(0, 3);

String dots = "...";

String ellipsis = "…";

if (!substr.equals(dots) && !s.substring(0, 1).equals(ellipsis)) {

s = s.replace(dots, substr);

s = s.replace(ellipsis, substr);

}

System.out.print(s);

}

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

Если строка не начинается с многоточия или трех точек, заменим все их вхождения на первые три символа строки.

Ссылки

Код решения

e-olymp 50. Разрезанное число

07/12/2018 by Алиса Ворохта

Задача

Василий на бумажке в виде полоски написал число, кратное $d$. Его младший брат Дмитрий разрезал число на $k$ частей. Василий решил восстановить написанное число, но столкнулся с проблемой. Он помнил только число $d$, а чисел, кратных $d$, можно сложить несколько.
Сколько чисел, кратных числу $d$, может составить Василий, если составляя исходное число, он использует все части.

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

В первой строке записано два числа $d$ и $k$ $\left(1 ≤ k < 9, 1 ≤ d ≤ 100\right)$. В следующих $k$ строках находятся части числа. Количество цифр в разрезанных частях не превышает $10.$

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

Количество разных чисел.

Тесты

Входные данные	Выходные данные
$5$ $3$ $13$ $85$ $45$	$4$
$11$ $2$ $1$ $111$	$1$
$11$ $3$ $11$ $8$ $11$	$0$
$71$ $8$ $4018916609$ $7495223237$ $3405637482$ $3166003637$ $8998228133$ $1141886496$ $9124347310$ $7736090711$	$584$

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

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

class Main
{
	public static int k, d, quantity = 0;
	public static long[] was = new long[40320];
	public static long[] nums = new long[9];
	public static boolean Was(long h) {
    	long c = 0;
    	for (int i = 0; i < quantity; i++) {
        	if (was[i] == h) c++;
    	}
    	if (c == 0) {
        	was[quantity] = h;
        	return true; 
    	}
    	else
    	return false;
	}
	public static void Swap(int a, int b) {
    	long t = nums[a];
    	nums[a] = nums[b];
    	nums[b] = t;
	}
	public static void Generate(int n) {
	    if (n == k) {
	        long sum = 0;
	        long p = 1;
	        long h = 0;
	        long hash = 1;
	        for (int i = k - 1; i >= 0; i--) {
	            long subs = nums[i];
	            sum += nums[i] % d * p;
	            p *= Math.pow(10, (long)Math.log10(nums[i]) + 1);
	            p = p%d;
	            while (subs!= 0) {
	                h += subs % 10 * hash;
	                hash *= 101;
	                subs /= 10;
	            }
	        }   
	        if (sum%d == 0 && Was(h) == true) {
	            quantity++; 
	        }
	    }
	    else { 
	        for(int j = n; j < k;j++) {
	            Swap(n,j);
	            Generate(n+1);
	            Swap(n,j);
	        }
	    }   
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		d = in.nextInt();
		k = in.nextInt();
    	for(int i = 0; i < k; i++) {
    		nums[i] = in.nextLong();
    	}
    	Generate(0);
    	System.out.println(quantity);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static int k, d, quantity = 0;

public static long[] was = new long[40320];

public static long[] nums = new long[9];

public static boolean Was(long h) {

long c = 0;

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

if (was[i] == h) c++;

}

if (c == 0) {

was[quantity] = h;

return true;

}

else

return false;

}

public static void Swap(int a, int b) {

long t = nums[a];

nums[a] = nums[b];

nums[b] = t;

}

public static void Generate(int n) {

if (n == k) {

long sum = 0;

long p = 1;

long h = 0;

long hash = 1;

for (int i = k - 1; i >= 0; i--) {

long subs = nums[i];

sum += nums[i] % d * p;

p *= Math.pow(10, (long)Math.log10(nums[i]) + 1);

p = p%d;

while (subs!= 0) {

h += subs % 10 * hash;

hash *= 101;

subs /= 10;

}

if (sum%d == 0 && Was(h) == true) {

quantity++;

}

else {

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

Swap(n,j);

Generate(n+1);

Swap(n,j);

}

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

{

Scanner in = new Scanner(System.in);

d = in.nextInt();

k = in.nextInt();

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

nums[i] = in.nextLong();

}

Generate(0);

System.out.println(quantity);

}

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

Согласно свойствам остатков от деления, остаток от деления суммы двух натуральных чисел на натуральное число $d$ совпадает с остатком от деления на $d$, который при делении на $d$ дает сумма их остатков. А также остаток от деления произведения двух натуральных чисел на натуральное число $d$ совпадает с остатком от деления на $d$, который при делении на $d$ дает произведение их остатков.
Значит, мы можем решить обычным перебором, но на каждом действии берем остаток от деления на $d$.
Также части чисел могут совпадать, в связи с чем необходима проверка на то, что мы составленное число еще не записывали. Для этого мы будем хешировать полученное число следующим образом: последнюю цифру умножим на $101^0$, предпоследнюю — на $101^1$ и так далее.
Если наш конечный результат делится на $d$ без остатка и если составленное число встречается в первый раз, то увеличиваем счетчик на $1$.

Ссылки

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

e-olymp 481. И опять: сколько можно?

02/12/2018 by Алиса Ворохта

Задача

Задано натуральное число [latex]N[/latex]. От данного числа вычтем сумму цифр этого числа, от полученного числа опять вычтем сумму цифр и т.д. Данную операцию будем продолжать до тех пор, пока полученное число положительно. Сколько раз будем выполнять данную операцию?

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

Во входной строке находится число [latex]N[/latex], которое не превышает [latex]2147483647[/latex].

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

Количество выполненных операций.

Тесты

Входные данные	Выходные данные
[latex]23[/latex]	[latex]3[/latex]
[latex]55555[/latex]	[latex]3000[/latex]
[latex]1234567[/latex]	[latex]49877[/latex]
[latex]999999999[/latex]	[latex]25632473[/latex]
[latex]2147483647[/latex]	[latex]54682584[/latex]

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		long N, sum, subsidiary = 0, quantity = 0;
    	Scanner in = new Scanner(System.in);
    	N = in.nextLong();
    	while (N > 999999999) {
        	sum = 0;
        	subsidiary = N;
        	while (subsidiary!=0) {
            	sum += subsidiary%10;
            	subsidiary /= 10;
        	}
        	N -= sum;
        	quantity++;
    	}
    	if (N == 999999999) {
        	N = 0;
        	quantity += 25632473;
    	}
    	while (N > 0) {
        	sum = 0;
        	subsidiary = N;
        	while (subsidiary != 0) {
            	sum += subsidiary%10;
            	subsidiary /= 10;
        	}
        	N -= sum;
        	quantity++;
    	}
    	System.out.println(quantity);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

long N, sum, subsidiary = 0, quantity = 0;

Scanner in = new Scanner(System.in);

N = in.nextLong();

while (N > 999999999) {

sum = 0;

subsidiary = N;

while (subsidiary!=0) {

sum += subsidiary%10;

subsidiary /= 10;

}

N -= sum;

quantity++;

}

if (N == 999999999) {

N = 0;

quantity += 25632473;

}

while (N > 0) {

sum = 0;

subsidiary = N;

while (subsidiary != 0) {

sum += subsidiary%10;

subsidiary /= 10;

}

N -= sum;

quantity++;

}

System.out.println(quantity);

}

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

Данную задачу можно решить, вычитая от данного числа [latex]N[/latex] суммы цифр, пока само число не станет равным [latex]0[/latex], с помощью циклов. Но этого нам не позволяет ограничение по времени.
Поэтому мы найдем максимально возможное число, которое мы можем получить при вычитании из больших чисел сумм цифр и которое проходит по времени. Это число — [latex]999999999[/latex] (найдено экспериментальным путем). Из него необходимо вычесть суммы цифр [latex]25632473[/latex] раз, чтобы получился [latex]0[/latex].
Тогда из чисел, которые больше данного, достаточно вычитать суммы цифр, пока они не станут равными [latex]999999999[/latex] и прибавить к количеству вычитаний [latex]25632473[/latex].
Если [latex]N[/latex] меньше найденного нами числа, то можно из него просто вычитать суммы цифр, пока оно не станет равным [latex]0[/latex].

Ссылки

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

e-olymp 1128. Проблема Лонги

02/12/2018 by Алиса Ворохта

Задача

Лонги хорошо разбирается в математике, он любит задумываться над трудными математическими задачами, которые могут быть решены при помощи некоторых изящных алгоритмов. И вот такая задачка возникла:
Дано целое число [latex]n[/latex] [latex](1 < n < 231)[/latex], Вы должны вычислить [latex]\sum\limits_{i=1}^n gcd [/latex] для всех [latex] 1 ≤ i ≤ n[/latex].
"О, я знаю, я знаю!" — воскликнул Лонги! А знаете ли Вы? Пожалуйста, решите её.

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

Каждая строка содержит одно число [latex]n[/latex].

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

Для каждого значения [latex]n[/latex] следует вывести в отдельной строке сумму [latex]\sum\limits_{i=1}^n gcd [/latex] для всех [latex] 1 ≤ i ≤ n[/latex].

Тесты

Входные данные	Выходные данные
[latex]2[/latex] [latex]6[/latex]	$3$ $15$
[latex]1[/latex] [latex]50[/latex] [latex]100[/latex]	$1$ $195$ $520$
[latex]7[/latex] [latex]4791[/latex] [latex]12345678[/latex] [latex]478900[/latex]	$13$ $15965$ $170994915$ $4980040$
[latex]123[/latex] [latex]7777[/latex] [latex]157423949[/latex] [latex]904573[/latex] $2147483648$	$405$ $54873$ $613124817$ $1809145$ $35433480192$

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

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

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		long n, gcd, primeNumInPow, power;
		Scanner in = new Scanner(System.in);
    	while(in.hasNextLong()){
    		n = in.nextLong();
        	gcd = 1;
        	for(long i = 2; i * i <= n; i++) {
            	if(n % i == 0) {
                	power = 0; primeNumInPow = 1;
                	while(n % i == 0) {
                    	power++;
                    	primeNumInPow *= i;
                    	n /= i;
                	}
                	gcd *= (power + 1)*primeNumInPow - power*primeNumInPow/i;
            	}
        	}       
        	if (n > 1) gcd *= (2*n - 1);
        	System.out.println(gcd);
    	}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

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

{

long n, gcd, primeNumInPow, power;

Scanner in = new Scanner(System.in);

while(in.hasNextLong()){

n = in.nextLong();

gcd = 1;

for(long i = 2; i * i <= n; i++) {

if(n % i == 0) {

power = 0; primeNumInPow = 1;

while(n % i == 0) {

power++;

primeNumInPow *= i;

n /= i;

}

gcd *= (power + 1)*primeNumInPow - power*primeNumInPow/i;

}

if (n > 1) gcd *= (2*n - 1);

System.out.println(gcd);

}

Согласно свойству НОД, если некоторые числа [latex]a_1[/latex] и [latex]a_2[/latex] взаимно просты, то [latex]\gcd \left(a_1 \cdot a_2, c\right) = \gcd \left(a_1, c\right) \cdot \gcd \left(a_2, c\right)[/latex], где [latex]c[/latex] — некоторая константа. Если же вместо [latex]c[/latex] взять [latex]i[/latex] ([latex] 1 ≤ i ≤ a_1 \cdot a_2[/latex]) и просуммировать по [latex]i[/latex] обе части равенства, получим:
[latex]\sum\limits_{i=1}^{a_1 \cdot a_2} \gcd \left(a_1 \cdot a_2, i\right) = \sum\limits_{i=1}^{a_1 \cdot a_2} \left(\gcd \left(a_1, i\right) \cdot \gcd \left(a_2, i\right)\right) = \sum\limits_{i=1}^{a_1} \gcd \left(a_1, i\right) \cdot \sum\limits_{i=1}^{a_2} \gcd \left(a_2, i\right)[/latex].
Значит мы можем данное число представить как произведение простых в некоторых степенях. Эти числа, очевидно, будут взаимно простыми, из чего следует возможность применения данного свойства и последующего суммирования по [latex]i[/latex].
Теперь докажем, что для любого простого числа [latex]p[/latex] в степени [latex]a\geqslant 1[/latex] верно следующее равенство:
[latex]\sum\limits_{i=1}^{p^a} \gcd\left(p^a, i\right) = \left(a + 1\right)\cdot p^a — a \cdot p^{a-1} [/latex].
Обозначим $\sum\limits_{i=1}^{r} \gcd\left(r, i\right)$ как $g\left(r\right)$.
База индукции:
[latex]a = 1[/latex]:
$$g\left(p\right) = \gcd\left(p, 1\right) + \gcd\left(p, 2\right) + \ldots + \gcd\left(p, p\right) = \left(p — 1 \right) + p = 2 \cdot p — 1.$$
Если [latex]a = 2[/latex]:
$$g\left(p^{2}\right) = \gcd\left(p^{2}, 1\right) + \gcd\left(p^{2}, 2\right) + \ldots + \gcd\left(p^{2}, p\right) + \gcd\left(p^{2}, p + 1\right) + \ldots + \\ + \gcd\left(p^{2}, 2 \cdot p\right) + \ldots + \gcd\left(p^{2}, p^{2}\right) = 1 + 1 + \ldots + p + 1 + \ldots + p + \ldots + p^{2} = \\ = \left( p^{2} — p \right) + p \cdot \left( p — 1 \right) + p^{2} = 3 \cdot p^{2} — 2\cdot p.$$
Для любых $a \geqslant 2$:
$$g\left(p^{a}\right) = \sum\limits_{j=1}^{p^{a-1}} \gcd\left(p^a, j\right) + \sum\limits_{j=p^{a — 1} + 1}^{p^{a} — 1} \gcd\left(p^a, j\right) + p^{a} =g\left(p^{a — 1}\right) + p^{a} + \\ + \sum\limits_{j=p^{a — 1} + 1}^{p^{a} — 1} \gcd\left(p^a — 1, j\right).$$
Причем:
$$\sum\limits_{j=p^{a — 1} + 1}^{p^{a} — 1} \gcd\left(p^a — 1, j\right) = \sum\limits_{j=1}^{p^{a} — p^{a-1} — 1} \gcd\left(p^{a — 1}, j\right) = \\ = \sum\limits_{j=1}^{p^{a} — p^{a-1}} \gcd\left(p^{a — 1}, j\right) — p^{a — 1} = \left( p — 1\right)\cdot g\left(p^{a-1}\right) — p^{a-1}.$$
Откуда следует:
$$g\left(p^{a}\right) = p^{a} — p^{a-1} + p\cdot g\left(p^{a-1}\right).$$
Предположение индукции:
Пусть [latex]a = b[/latex]:
$$g\left(p^{b}\right) = \left(b + 1\right) \cdot p^b — b \cdot p^{b-1}.$$
Шаг индукции:
Пусть [latex]a = b + 1[/latex]:
$$g\left(p^{b + 1}\right) = p^{b + 1} — p^{b} + p\cdot g\left(p^{b}\right) = p^{b + 1} — p^{b} + p\cdot \left[\left(b+1\right) \cdot p^{b} + b\cdot p^{b-1}\right] = \\ = \left(b + 2\right)\cdot p^{b+1} — \left(b + 1\right)\cdot p^{b}.$$

Ссылки

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

e-olymp 74. Паук и муха — 2

01/12/2018 by Алиса Ворохта

Задача

В пустой прямоугольной комнате длины [latex]А[/latex], ширины [latex]В[/latex] и высоты [latex]С[/latex] муха упала на пол и уснула. Паук, находящийся на одной из стен, или на полу, или на потолке, начал двигаться к ней по кратчайшему пути.

На какое расстояние он при этом переместится? Известно, что паук может передвигаться только по поверхности комнаты или же спускаться на паутине с потолка на пол, но только под прямым углом.

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

В первой строке заданы размеры комнаты [latex]A[/latex], [latex]B[/latex], [latex]C[/latex]. Во второй строке – координаты мухи на полу [latex]X1[/latex], [latex]Y1[/latex], [latex](0 ≤ X1 ≤ A[/latex], [latex]0 ≤ Y1 ≤ B)[/latex]. В третьей строке – координаты паука [latex]X2[/latex], [latex]Y2[/latex], [latex]Z2[/latex], [latex](0 ≤ X2 ≤ A[/latex], [latex]0 ≤ Y2 ≤ B[/latex], [latex]0 ≤ Z2 ≤ C)[/latex]. Все входные данные – целые не отрицательные числа, не превосходящие [latex]500[/latex].

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

Одно число – расстояние, на которое переместится паук, посчитанное с точностью до 2-х знаков после запятой.

Тесты

Входные данные								Выходные данные
[latex]A[/latex]	[latex]B[/latex]	[latex]C[/latex]	[latex]X1[/latex]	[latex]Y1[/latex]	[latex]X2[/latex]	[latex]Y2[/latex]	[latex]Z2[/latex]	[latex]S[/latex]
[latex]4[/latex]	[latex]7[/latex]	[latex]3[/latex]	[latex]2[/latex]	[latex]1[/latex]	[latex]3[/latex]	[latex]7[/latex]	[latex]2[/latex]	[latex]8.06[/latex]
[latex]145[/latex]	[latex]26[/latex]	[latex]306[/latex]	[latex]12[/latex]	[latex]24[/latex]	[latex]0[/latex]	[latex]0[/latex]	[latex]305[/latex]	[latex]309.34[/latex]
[latex]26[/latex]	[latex]18[/latex]	[latex]53[/latex]	[latex]24[/latex]	[latex]15[/latex]	[latex]24[/latex]	[latex]1[/latex]	[latex]53[/latex]	[latex]58.52[/latex]
[latex]89[/latex]	[latex]89[/latex]	[latex]189[/latex]	[latex]12[/latex]	[latex]24[/latex]	[latex]0[/latex]	[latex]89[/latex]	[latex]16[/latex]	[latex]70.77[/latex]
[latex]18[/latex]	[latex]26[/latex]	[latex]145[/latex]	[latex]14[/latex]	[latex]2[/latex]	[latex]17[/latex]	[latex]26[/latex]	[latex]141[/latex]	[latex]147.14[/latex]

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

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

class Main
{
	private static double distance(long X1, long Y1, long X2, long Y2) 
	{
    	return Math.sqrt((X1-X2)*(X1-X2) + (Y1-Y2)*(Y1-Y2));
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		Scanner in = new Scanner(System.in);
		long A = in.nextLong();
		long B = in.nextLong();
		long C = in.nextLong();
		long X1 = in.nextLong();
		long Y1 = in.nextLong();
		long X2 = in.nextLong();
		long Y2 = in.nextLong();
		long Z2 = in.nextLong();
		double S = 10000000;
		if (Z2 == 0)
    	{
    		S = distance(X1, Y1, X2, Y2);
    	}
		else
		{
			if (X2 == 0)
			{
				S = Math.min(distance(X1, Y1, -Z2, Y2), distance(X1, Y1, -Y2, -Z2));
				S = Math.min(S, distance(X1, Y1, Y2 - B, B + Z2));
			}
			if (X2 == A)
			{
				S = Math.min (distance(X1, Y1, Z2 + A, Y2), distance(X1, Y1, A + Y2, -Z2));
				S = Math.min(S, distance(X1, Y1, A + B - Y2, Z2 + B));
			}
			if (Y2 == 0)
			{
				S = Math.min(S, distance(X1, Y1, X2, -Z2));
				S = Math.min(S, distance(X1, Y1, -Z2, -X2));
				S = Math.min(S, distance(X1, Y1, A + Z2, X2 - A));
			}
			if (Y2 == B)
			{
				S = Math.min(S, distance(X1, Y1, X2, Z2 + B));
				S = Math.min(S, distance(X1, Y1, -Z2, X2 + B));
				S = Math.min(S, distance(X1, Y1, A + Z2, B + A - X2));
			}
			if ((Y2 != 0) && (Y2 != B) && (X2 != 0) && (X2 != A))
			{
				S = Math.min(C + distance(X1, Y1, X2, Y2), distance(X1, Y1, X2, -Y2 - C));
				S = Math.min(S, distance(X1, Y1, X2, 2*B - Y2 + C));
				S = Math.min(S, distance(X1, Y1, -X2 - C, Y2));
				S = Math.min(S, distance(X1, Y1, 2*A - X2 + C, Y2));
				S = Math.min(S, distance(X1, Y1, A + B + C - Y2, A + B - X2));
				S = Math.min(S, distance(X1, Y1, A + C + Y2, X2 - A));
				S = Math.min(S, distance(X1, Y1, -C - Y2, -X2));
				S = Math.min(S, distance(X1, Y1, Y2 - B - C, B + X2));
				S = Math.min(S, distance(X1, Y1, A + B - Y2, A + B + C - X2));
				S = Math.min(S, distance(X1, Y1, Y2 - B, B + C + X2));
				S = Math.min(S, distance(X1, Y1, -Y2, -C - X2));
				S = Math.min(S, distance(X1, Y1, A + Y2, -A - C + X2));
			}
		}
		System.out.printf("%.2f", S);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

private static double distance(long X1, long Y1, long X2, long Y2)

{

return Math.sqrt((X1-X2)*(X1-X2) + (Y1-Y2)*(Y1-Y2));

}

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

{

Scanner in = new Scanner(System.in);

long A = in.nextLong();

long B = in.nextLong();

long C = in.nextLong();

long X1 = in.nextLong();

long Y1 = in.nextLong();

long X2 = in.nextLong();

long Y2 = in.nextLong();

long Z2 = in.nextLong();

double S = 10000000;

if (Z2 == 0)

{

S = distance(X1, Y1, X2, Y2);

}

else

{

if (X2 == 0)

{

S = Math.min(distance(X1, Y1, -Z2, Y2), distance(X1, Y1, -Y2, -Z2));

S = Math.min(S, distance(X1, Y1, Y2 - B, B + Z2));

}

if (X2 == A)

{

S = Math.min (distance(X1, Y1, Z2 + A, Y2), distance(X1, Y1, A + Y2, -Z2));

S = Math.min(S, distance(X1, Y1, A + B - Y2, Z2 + B));

}

if (Y2 == 0)

{

S = Math.min(S, distance(X1, Y1, X2, -Z2));

S = Math.min(S, distance(X1, Y1, -Z2, -X2));

S = Math.min(S, distance(X1, Y1, A + Z2, X2 - A));

}

if (Y2 == B)

{

S = Math.min(S, distance(X1, Y1, X2, Z2 + B));

S = Math.min(S, distance(X1, Y1, -Z2, X2 + B));

S = Math.min(S, distance(X1, Y1, A + Z2, B + A - X2));

}

if ((Y2 != 0) && (Y2 != B) && (X2 != 0) && (X2 != A))

{

S = Math.min(C + distance(X1, Y1, X2, Y2), distance(X1, Y1, X2, -Y2 - C));

S = Math.min(S, distance(X1, Y1, X2, 2*B - Y2 + C));

S = Math.min(S, distance(X1, Y1, -X2 - C, Y2));

S = Math.min(S, distance(X1, Y1, 2*A - X2 + C, Y2));

S = Math.min(S, distance(X1, Y1, A + B + C - Y2, A + B - X2));

S = Math.min(S, distance(X1, Y1, A + C + Y2, X2 - A));

S = Math.min(S, distance(X1, Y1, -C - Y2, -X2));

S = Math.min(S, distance(X1, Y1, Y2 - B - C, B + X2));

S = Math.min(S, distance(X1, Y1, A + B - Y2, A + B + C - X2));

S = Math.min(S, distance(X1, Y1, Y2 - B, B + C + X2));

S = Math.min(S, distance(X1, Y1, -Y2, -C - X2));

S = Math.min(S, distance(X1, Y1, A + Y2, -A - C + X2));

}

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

}

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

Данная задача решается с помощью «разверток» комнаты: переход от трёхмерного пространства к двумерному.
Вид комнаты:

Рассмотрим такие случаи:

Паук находится на полу ([latex]Z_2 = 0[/latex]);
Паук находится на одной из стенок ([latex]X_2 = 0[/latex], или [latex]X_2 = A[/latex], или [latex]Y_2 = 0[/latex], или [latex]Y_2 = B[/latex] и [latex]Z_2 \neq 0[/latex]) либо на потолке ([latex]X_2 \neq 0[/latex], и [latex]X_2 \neq A[/latex], и [latex]Y_2 \neq 0[/latex], и [latex]Y_2 \neq B[/latex], и [latex]Z_2 = C[/latex]).

Первый случай тривиален и вычисляется по формуле [latex]\sqrt{(X_1 — X_2)^2 + (Y_1 — Y_2)^2}[/latex].
В случае, когда паук сидит на стенке, мы можем построить 3 развертки:
Допустим, паук находится на левой боковой стенке ([latex]X_2 = 0[/latex]). Остальные случаи аналогичны этому.

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

По этим разверткам мы можем вычислить координаты паука и кратчайшее расстояние от него до мухи. Если же паук находится в одном из углов комнаты, то мы находим наименьшее расстояние из двух вариантов развертки.
Когда же паук сидит на потолке, не соприкасаясь ни с одной из стенок, у него есть 13 вариантов:

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

По этим разверткам мы также можем вычислить координаты паука и кратчайшее расстояние от него до мухи.

Ссылки

Условие задачи на e-olymp
Задача Дьюдени о пауке и мухе
Код решения

e-olymp 8. Спички

28/10/2018 by Алиса Ворохта

Задача

Какое минимальное количество спичек необходимо для того, чтобы выложить на плоскости [latex]n[/latex] квадратов со стороной в одну спичку? Спички нельзя ломать и класть друг на друга. Вершинами квадратов должны быть точки, где сходятся концы спичек, а сторонами – сами спички.

Напишите программу, которая по количеству квадратов [latex]n[/latex], которое необходимо составить, находит минимальное необходимое для этого количество спичек.

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

Одно целое число [latex]n[/latex] [latex](1 ≤ n ≤ 10^9)[/latex].

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

Вывести минимальное количество спичек, требуемых для составления [latex]n[/latex] квадратов.

Тесты

Входные данные	Выходные данные
[latex]1[/latex]	[latex]4[/latex]
[latex]2[/latex]	[latex]7[/latex]
[latex]4[/latex]	[latex]12[/latex]
[latex]7[/latex]	[latex]20[/latex]
[latex]150[/latex]	[latex]325[/latex]
[latex]10000[/latex]	[latex]20200[/latex]

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);
		double n = in.nextDouble();
		double length = Math.floor(Math.sqrt(n));
		double width = Math.ceil(n / length);
		double k = 2 * n + length + width;
		System.out.print((int)(k));
	}
}

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);

double n = in.nextDouble();

double length = Math.floor(Math.sqrt(n));

double width = Math.ceil(n / length);

double k = 2 * n + length + width;

System.out.print((int)(k));

}

Один квадрат можно составить из [latex]4[/latex] спичек. Два квадрата — из [latex]7[/latex] спичек. Очевидно, что квадраты следует располагать так, чтобы они образовывали прямоугольник, “близкий” к квадрату.
Например, на рисунке 1 мы использовали меньшее количество спичек, чем на рисунке 2, хотя количество квадратов одинаковое:

Зададим размеры прямоугольника. Пусть [latex]w = \sqrt n[/latex] — его ширина. Округлим значение [latex]w[/latex] к наибольшему целому числу, не превышающему данное. Тогда его длина будет [latex]l = \displaystyle\frac {n} {w}[/latex]. Если округлить значение [latex]l[/latex] к наибольшему целому числу, не превышающему данное, то мы сможем построить лишь те квадраты, которые входят в наш прямоугольник. Округляя же значение [latex]l[/latex] к наименьшему целому числу, которое не меньше данного, мы сможем достроить квадраты, не поместившиеся в наш прямоугольник.
Если отложить вниз количество спичек, равное [latex]w[/latex], и вправо — [latex]l[/latex], получается следующий рисунок (разумеется, количество отложенных спичек меняется в зависимости от [latex]n[/latex]):

Очевидно, что достроить треубемые квадраты можно, положив «уголки» из двух спичек, начиная с левого верхнего угла и двигаясь сверху вниз и слева направо.
«Уголок»:

Отсюда и получается формула: [latex]k = 2 \cdot n + l + w[/latex], где [latex]k[/latex] — количество спичек, требуемое в задаче.

Ссылки

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