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

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

Задача

Профессор из тридевятого царства решил, что посчитать сумму делителей числа $n$ до $10^{10}$ сможет любой троечник, поэтому усложнил для Кости задачу, дав числа с большим количеством цифр. Но наш герой не хотел сдаваться, уж больно он хотел стать отличником.
Костя очень просит Вас помочь ему в этом деле, ведь он помнит, как успешно Вы справились с предыдущей задачей.

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

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

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

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

Тесты

Входные данные	Выходные данные
$100000000000031$	$100000000000032$
$10000019$	$10000020$
$400001520001444$	$700002730002667$
$9$	$13$
$304250263527210$	$1281001468723200$
$94083986096100$	$457766517350961$
$1234567898765$	$1517681442816$
$100000000000000$	$249992370597277$
$562949953421312$	$1125899906842623$
$81795$	$161280$
$9999999999999$	$14903272088640$
$997$	$998$
$1325$	$1674$
$2468013$	$3290688$
$951641320$	$2447078400$
$71675429738641$	$71695352830464$
$1100000000033$	$1200000000048$
$6300088$	$11859480$
$98$	$171$
$9102837465$	$15799834440$

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

#include <iostream>
#include <map>
using namespace std;
int main ()
{
    long long n, sumOfDivisors = 1;
    cin >> n;
    map<long long, long long> primeDivInPow;
    for(long long i = 2; i * i <= n; i++){
        while(n % i == 0){
            if(primeDivInPow.find(i) == primeDivInPow.end()){
                primeDivInPow[i] = 1;
            }
            primeDivInPow[i] *= i;
            n /= i;
        }
    }
    if(n != 1){
        primeDivInPow[n] = n;
    }
    for(map<long long, long long>::iterator p = primeDivInPow.begin(); p != primeDivInPow.end(); p++){
        sumOfDivisors *= (p -> second - 1) / (p -> first - 1) + p -> second;
    }
    cout << sumOfDivisors;
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main ()

{

long long n, sumOfDivisors = 1;

cin >> n;

map<long long, long long> primeDivInPow;

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

while(n % i == 0){

if(primeDivInPow.find(i) == primeDivInPow.end()){

primeDivInPow[i] = 1;

}

primeDivInPow[i] *= i;

n /= i;

}

if(n != 1){

primeDivInPow[n] = n;

}

for(map<long long, long long>::iterator p = primeDivInPow.begin(); p != primeDivInPow.end(); p++){

sumOfDivisors *= (p -> second - 1) / (p -> first - 1) + p -> second;

}

cout << sumOfDivisors;

return 0;

}

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

Пусть $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}.$$
Для того, чтобы не вычислять $p_k^{\alpha_k+1}$, перепишем данную формулу в следующем виде:
$$\sigma\left(n\right) = \left(\frac{p_1^{\alpha_1}-1}{p_1-1}+p_1^{\alpha_1}\right)\cdot\left(\frac{p_2^{\alpha_2}-1}{p_2-1}+p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(\frac{p_k^{\alpha_k}-1}{p_k-1}+p_k^{\alpha_k}\right).$$

Ссылки

Код решения

Related Images:

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

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

Задача

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

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

#include <iostream>
#include <map>
using namespace std;
int main ()
{
    long long n, sumOfDivisors = 1;
    cin >> n;
    map<long long, long long> primeDivInPow;
    for(long long i = 2; i * i <= n; i++){
        while(n % i == 0){
            if(primeDivInPow.find(i) == primeDivInPow.end()){
                primeDivInPow[i] = 1;
            }
            primeDivInPow[i] *= i;
            n /= i;
        }
    }
    if(n != 1){
        primeDivInPow[n] = n;
    }
    for(map<long long, long long>::iterator p = primeDivInPow.begin(); p != primeDivInPow.end(); p++){
        sumOfDivisors *= (p -> second * p -> first - 1) / (p ->first - 1);
    }
    cout << sumOfDivisors;
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main ()

{

long long n, sumOfDivisors = 1;

cin >> n;

map<long long, long long> primeDivInPow;

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

while(n % i == 0){

if(primeDivInPow.find(i) == primeDivInPow.end()){

primeDivInPow[i] = 1;

}

primeDivInPow[i] *= i;

n /= i;

}

if(n != 1){

primeDivInPow[n] = n;

}

for(map<long long, long long>::iterator p = primeDivInPow.begin(); p != primeDivInPow.end(); p++){

sumOfDivisors *= (p -> second * p -> first - 1) / (p ->first - 1);

}

cout << sumOfDivisors;

return 0;

}

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

Ссылки

Код решения

Related Images:

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

25/06/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$

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

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
long long nums[9];
long long k;
long long d;
long long quantity = 0;
long long was[40320];
bool Was(long long h) {
    long 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;
}
void Swap(long long a,long long b)
{
    long long t = nums[a];
    nums[a] = nums[b];
    nums[b] = t;
}
void Generate(long long n)
{
    if (n==k)
    {
        long long sum = 0;
        long long p = 1;
        long long h = 0;
        long long hash = 1;
        for (long long i = k - 1; i >= 0; i--) {
            long long subs = nums[i];
            sum += nums[i]%d*p;
            p *= pow(10, long(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(long long j = n; j < k;j++) {
            Swap(n,j);
                    Generate(n+1);
                    Swap(n,j);
        }
    }   
}
 
int main()
{
    cin >> d >> k;
    for(long long i = 0; i < k; i++) {
        cin >> nums[i];
    }
    Generate(0);
    cout << quantity;
    return 0;
}

#include <iostream>

#include <cmath>

#include <algorithm>

using namespace std;

long long nums[9];

long long k;

long long d;

long long quantity = 0;

long long was[40320];

bool Was(long long h) {

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

}

void Swap(long long a,long long b)

{

long long t = nums[a];

nums[a] = nums[b];

nums[b] = t;

}

void Generate(long long n)

{

if (n==k)

{

long long sum = 0;

long long p = 1;

long long h = 0;

long long hash = 1;

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

long long subs = nums[i];

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

p *= pow(10, long(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(long long j = n; j < k;j++) {

Swap(n,j);

Generate(n+1);

Swap(n,j);

}

int main()

{

cin >> d >> k;

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

cin >> nums[i];

}

Generate(0);

cout << quantity;

return 0;

}

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

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

Ссылки

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

Related Images:

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

14/05/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$

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

#include <iostream>
using namespace std;
 
int main() {
    long long n, gcd, primeNumInPow, power;
    while(cin >> n)
    {
        gcd = 1;
        for(long 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);
        cout << gcd << endl;
    }
  return 0;
}

#include <iostream>

using namespace std;

int main() {

long long n, gcd, primeNumInPow, power;

while(cin >> n)

{

gcd = 1;

for(long 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);

cout << gcd << endl;

}

return 0;

}

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

Согласно свойству НОД, если некоторые числа [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
Код решения

Related Images:

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

24/12/2017 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]

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

#include <iostream>
using namespace std;
 
int main()
{
    unsigned long long N, sum, subsidiary = 0, quantity = 0;
    cin >> N;
    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++;
    }
    cout << quantity << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

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

cin >> N;

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

}

cout << quantity << endl;

return 0;

}

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

Данную задачу можно решить, вычитая от данного числа [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
Код решения

Related Images:

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

16/12/2017 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]

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

#include <iostream>
#include <cmath> //подключаем для возможности извлечения корня
#include <iomanip> //подключаем, чтобы округлить до определенного количества знаков
using namespace std;
 
double distance(long long X1, long long Y1, long long X2, long long Y2) 
{
    return sqrt((X1-X2)*(X1-X2) + (Y1-Y2)*(Y1-Y2));
}
int main() {
    long long A, B, C, X1, X2, Y1, Y2, Z2;
    double S = 1000000000;
    cin >> A >> B >> C >> X1 >> Y1 >> X2 >> Y2 >> Z2;
    if (Z2 == 0)
    {
        S = distance(X1, Y1, X2, Y2);
    }
    else
    {
        if (X2 == 0)
        {
            S = min(distance(X1, Y1, -Z2, Y2), distance(X1, Y1, -Y2, -Z2));
            S = min(S, distance(X1, Y1, Y2 - B, B + Z2));
        }
        if (X2 == A)
        {
            S = min (distance(X1, Y1, Z2 + A, Y2), distance(X1, Y1, A + Y2, -Z2));
            S = min(S, distance(X1, Y1, A + B - Y2, Z2 + B));
        }
        if (Y2 == 0)
        {
            S = min(S, distance(X1, Y1, X2, -Z2));
            S = min(S, distance(X1, Y1, -Z2, -X2));
            S = min(S, distance(X1, Y1, A + Z2, X2 - A));
        }
        if (Y2 == B)
        {
            S = min(S, distance(X1, Y1, X2, Z2 + B));
            S = min(S, distance(X1, Y1, -Z2, X2 + B));
            S = min(S, distance(X1, Y1, A + Z2, B + A - X2));
        }
        if ((Y2 != 0) && (Y2 != B) && (X2 != 0) && (X2 != A))
        {
            S = min(C + distance(X1, Y1, X2, Y2), distance(X1, Y1, X2, -Y2 - C));
            S = min(S, distance(X1, Y1, X2, 2*B - Y2 + C));
            S = min(S, distance(X1, Y1, -X2 - C, Y2));
            S = min(S, distance(X1, Y1, 2*A - X2 + C, Y2));
            S = min(S, distance(X1, Y1, A + B + C - Y2, A + B - X2));
            S = min(S, distance(X1, Y1, A + C + Y2, X2 - A));
            S = min(S, distance(X1, Y1, -C - Y2, -X2));
            S = min(S, distance(X1, Y1, Y2 - B - C, B + X2));
            S = min(S, distance(X1, Y1, A + B - Y2, A + B + C - X2));
            S = min(S, distance(X1, Y1, Y2 - B, B + C + X2));
            S = min(S, distance(X1, Y1, -Y2, -C - X2));
            S = min(S, distance(X1, Y1, A + Y2, -A - C + X2));
        }
    }
    cout << fixed << setprecision(2) << S;
    return 0;
}

#include <iostream>

#include <cmath> //подключаем для возможности извлечения корня

#include <iomanip> //подключаем, чтобы округлить до определенного количества знаков

using namespace std;

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

{

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

}

int main() {

long long A, B, C, X1, X2, Y1, Y2, Z2;

double S = 1000000000;

cin >> A >> B >> C >> X1 >> Y1 >> X2 >> Y2 >> Z2;

if (Z2 == 0)

{

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

}

else

{

if (X2 == 0)

{

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

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

}

if (X2 == A)

{

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

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

}

if (Y2 == 0)

{

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

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

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

}

if (Y2 == B)

{

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

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

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

}

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

{

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

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

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

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

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

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

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

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

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

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

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

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

}

cout << fixed << setprecision(2) << S;

return 0;

}

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

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

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

Паук находится на полу ([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] с помощью функции [latex]distance[/latex].
В случае, когда паук сидит на стенке, мы можем построить 3 развертки:
Допустим, паук находится на левой боковой стенке ([latex]X_2 = 0[/latex]). Остальные случаи аналогичны этому.

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

По этим разверткам мы можем вычислить координаты паука и кратчайшее расстояние от него до мухи с помощью функции [latex]distance[/latex]. Если же паук находится в одном из углов комнаты, то мы находим наименьшее расстояние из двух вариантов развертки.
Когда же паук сидит на потолке, не соприкасаясь ни с одной из стенок, у него есть 13 вариантов:

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

По этим разверткам мы также можем вычислить координаты паука и кратчайшее расстояние от него до мухи с помощью функции [latex]distance[/latex].

Ссылки

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

Related Images:

e-olymp 8. Спички

12/11/2017 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]

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    long long  n, k;
    long double length, width;
    cin >> n;
    length = floor(sqrt(n));
    width = ceil(n/length);
    k = 2*n + length + width;
    cout << k << endl;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

long long n, k;

long double length, width;

cin >> n;

length = floor(sqrt(n));

width = ceil(n/length);

k = 2*n + length + width;

cout << k << endl;

return 0;

}

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

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

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

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