Category Archives: 3. Циклы

Программы, основным элементом которых являются простые циклические вычисления.

Циклы

Опубликовано: 11/10/2014

Циклические, повторяющиеся много раз однотипные вычисления позволяют наилучшим образом продемонстрировать вычислительные возможности компьютеров. Ради этого их изначально и создавали. В задачах этого раздела желательно снова перечитать параграф 5.4 из праймера посвященный «итерационным операторам» (так они назвали семейство из нескольких операторов цикла). Часть 5.4.3 можете пока пропустить, поскольку мы еще не изучали структур данных для которых … Continue reading →

нет комментариев

В классе и дома решаются следующие тренировочные задачи (1 балл):

Цифры
Младший бит
Постоянная сумма цифр
Садовник
Большая точность
Дракон
Змей Горыныч
Уровень палиндромности
Нумерация
Битовое представление
Часы
Счастливые билеты
Роботы — сложная задача, предлагается всем желающим
Юный садовод
Максимум
Баксы в банке
Циклические сдвиги
Минимальная сумма цифр
Просто Фибоначчи
Превращение
Увеличить на 2
Двоичные числа
Интересное произведение
Кружок хорового пения
Очень просто!!!
Юные программисты
Коды Грея — только не перемудрите. Если выходит значительно больше 20 строчек кода,
то лучше остановиться и подумать.
Кубики — 3 —
используйте битовые операции для смены предположения о потере кубика для каждой из 52-х букв
Степень симметрии
Сколько можно?
«Зеркально простые» числа
Max — Min

Опубликованные решения

e-olymp 513. Проблема Николая

28/12/2017 by Данила Савчак

Задача

Николаю нужно доставить подарки для [latex]n[/latex] [latex](n ≤ 10^{18})[/latex] детей. Его интересует сколькими способами он может это сделать. Вам нужно дать ответ на этот простой вопрос. Так как это количество может быть очень большим, выведите результат по модулю [latex]m[/latex] [latex](m ≤ 2009)[/latex].

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

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

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

Вывести искомое количество способов.

Тесты

Входные данные	Выходные данные
[latex]500[/latex] [latex]2001[/latex]	[latex]0[/latex]
[latex]4[/latex] [latex]5[/latex]	[latex]4[/latex]
[latex]4[/latex] [latex]7[/latex]	[latex]3[/latex]
[latex]15[/latex] [latex]213[/latex]	[latex]147[/latex]
[latex]10[/latex] [latex]3[/latex]	[latex]0[/latex]

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

#include <iostream>
using namespace std;

int main() {
    int n, m, k = 1;
    cin >> n >> m;
    if ( n >= m) {
        cout << 0;
    }
    else {
        for ( int i = 2; i <= n; i++ ) {
            k = ( k * i ) % m;
        }
        cout << k; 
    }
    return 0; 
}

#include <iostream>

using namespace std;

int main() {

int n, m, k = 1;

cin >> n >> m;

if ( n >= m) {

cout << 0;

}

else {

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

k = ( k * i ) % m;

}

cout << k;

}

return 0;

}

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

Если [latex]m[/latex] является членом произведения [latex]n![/latex], то остаток от деления на [latex]m[/latex] равен [latex]0[/latex].В остальных случаях ищем [latex]n![/latex] с вычислением остатка от деления после каждого перемножения.

Ссылки

Условие задачи на e-olymp.com.

Код решения на ideone.com.

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 127. Баксы в банке

24/12/2017 by Яна Колчинская

Задача

Папа Карло подарил Буратино [latex]1[/latex] доллар в его первый день рождения, а экономный Буратино сложил подарок в банку. Каждый последующий год папа Карло удваивал свой предыдущий подарок и прибавлял к нему столько долларов, сколько лет исполнилось Буратино, а тот в свою очередь продолжал складывать баксы в банку. На какой [latex]N[/latex]-й день рождения в банке будет не менее чем [latex]S[/latex] долларов?

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

Единственное число — значение [latex]S[/latex]. [latex]1 ≤ S ≤ 240[/latex].

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

Искомое значение [latex]N[/latex].

Тесты

#	Входные данные	Выходные данные
1	1	1
2	98	5
3	99	5
4	100	6
5	549755813888	38

Код

#include <iostream>
using namespace std;

int main() {
    long long n;
    long long x=1; //подарок папы на данный день рождения
    long long k=1; //номер дня рождения
    long long s=1; //сумма, лежащая в банке
    cin>>n;
    while (s<n) {
        k++;
        x=x*2+k;
        s=s+x;
    }
    cout<<k;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long n;

long long x=1; //подарок папы на данный день рождения

long long k=1; //номер дня рождения

long long s=1; //сумма, лежащая в банке

cin>>n;

while (s<n) {

k++;

x=x*2+k;

s=s+x;

}

cout<<k;

return 0;

}

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

Для начала найдём формулу, по которому папа Карло дарит, а Буратино — складывает в банку доллары: [latex]x=2\cdot x+k[/latex].
А теперь установим допустимый предел суммы долларов в банке и начальные условия: [latex]s<n[/latex] и [latex]x=1[/latex], [latex]k=1[/latex], [latex]s=1[/latex].

Ссылки

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

Related Images:

D2549. Сумма ряда

24/12/2017 by Алла Марокко

Условие задачи:
Найти сумму сходящегося ряда:
[latex]\frac{1}{1 \cdot 2} + \frac{1}{2 \cdot 3} + \frac{1}{3 \cdot 4} + … + \frac{1}{n(n + 1)} + …[/latex]

Входные данные:
Целое число [latex]n[/latex] — номер искомой частичной суммы.

Выходные данные:
Искомая частичная сумма.

Тесты:

№	Вход	Выход
1	1	0.5
2	500	0.998004
3	100000	0.999965

Код на языке C++ (первый вариант):

#include <iostream>
using namespace std;
 
int main() {
    int n;
    double S = 0;
    cin >> n;
    for (int i = 1; i <= n; i++){
        S += 1.0/(i*(i + 1)); 
    }
    cout << S;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

double S = 0;

cin >> n;

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

S += 1.0/(i*(i + 1));

}

cout << S;

return 0;

}

Код на языке Java (первый вариант):

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);
        PrintWriter out = new PrintWriter(System.out);
        int n;
        n=in.nextInt();
        double S = 0;
        for (int i = 1; i <= n; i++){
            S += 1.0/(i*(i + 1)); 
        }
        System.out.println(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);

PrintWriter out = new PrintWriter(System.out);

int n;

n=in.nextInt();

double S = 0;

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

S += 1.0/(i*(i + 1));

}

System.out.println(S);

}

Код на языке C++ (второй вариант):

#include <iostream>
using namespace std;
 
int main() {
    int n;
    double S = 0;
    cin >> n;
    S = 1-(1/n); 
    cout << S;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

double S = 0;

cin >> n;

S = 1-(1/n);

cout << S;

return 0;

}

Код на языке Java (второй вариант):

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);
        PrintWriter out = new PrintWriter(System.out);
        int n;
        n=in.nextInt();
        double S = 0;
        S=1-(1/n);
        System.out.println(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);

PrintWriter out = new PrintWriter(System.out);

int n;

n=in.nextInt();

double S = 0;

S=1-(1/n);

System.out.println(S);

}

Решения:
Вариант первый (решение с циклом): Зададим цикл с счетчиком [latex]i[/latex] от 1 до заданного пользователем числа [latex]n.[/latex] Именно такое количество необходимых слагаемых [latex]\frac{1}{n(n + 1)}[/latex] будет найдено на каждом шаге цикла для последующего суммирования и нахождения искомой частичной суммы.

Вариант второй (решение без цикла): Ряд сводится к ряду: [latex](1 — \frac{1}{2}) + (\frac{1}{2} — \frac{1}{3}) + … + (\frac{1}{n} — \frac{1}{n + 1})[/latex]. От сюда имеем: [latex]1 — \frac{1}{n + 1}.[/latex]

Ссылки:
Условие задачи (стр.248).
Первый вариант C++ .
Первый вариант Java .
Второй вариант C++ .
Второй вариант Java .

Related Images:

e-olymp 109. Нумерация

23/12/2017 by Георгий Мартынюк

Задача

Для нумерации [latex]m[/latex] страниц книги использовали [latex]n[/latex] цифр. По заданному [latex]n[/latex] вывести [latex]m[/latex] или [latex]0[/latex], если решения не существует. Нумерация начинается с первой страницы.

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

Единственное число [latex]n[/latex]. В книге не более [latex]1001[/latex] страницы.

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

Вывести количество страниц в книге.

Тесты

Входные данные	Выходные данные
27	18
15	12
9	9
49	29
50	0

#include <iostream>
using namespace std;
int main() {
  int n, m, minus = 1;
  cin >> n;
  m = 1;
  for  (int a = 1; n> 0; a *= 10) {
    for  (int b = a; b < a*10; b++) {
      if ((n - minus) < 0) {
        cout << 0;
        return 0;
      }
      if ((n - minus) == 0) {
        cout << m;
        return 0;
      }
      n-= minus;
      m++;
    }
    minus++;
  }
  return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m, minus = 1;

cin >> n;

m = 1;

for (int a = 1; n> 0; a *= 10) {

for (int b = a; b < a*10; b++) {

if ((n - minus) < 0) {

cout << 0;

return 0;

}

if ((n - minus) == 0) {

cout << m;

return 0;

}

n-= minus;

m++;

}

minus++;

}

return 0;

}

Решение

Для решения этой задачи я описал [latex]3[/latex] переменные: n, mи minus, где n- количество цифр, использованных для нумерации страниц, m — количество страниц и minus — «счетчик», для определения количества цифр в числе [latex]a[/latex]. Использовал [latex]2[/latex] вложенных цикла, где счетчик [latex]a[/latex] — определяет разрядность числа страницы [latex]b[/latex]. Внутри вложенного циклы перед вычитанием minusиз n поставил проверку на выполнения условий: если n == 0, значит мы закончили считать страницы и если [latex]n — minus < 0[/latex], значит на следующей итерации мы запишем в [latex]n[/latex] отрицательное значение, значит во входных данных была ошибка.

Ссылки

e-olymp
Ideone

Related Images:

e-olymp 480. Возведение в степень — 2

22/12/2017 by Кирилл Волков

Задача

Для заданных $A$, $B$ и $M$ вычислить $A^B \mod M$.

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

Во входном файле даны три натуральных числа $A$, $B$, $M$ $(1 ≤ A, \, B ≤ 10^{18}, \, 2 ≤ M ≤ 2 \cdot 10^9)$, записанные в одной строке через пробел.

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

В выходной файл выведите одно число, равное $A^B \mod M$.

Тесты

Входные данные	Выходные данные
$531$ $348$ $1645$	$911$
$1784353$ $453345$ $463973$	$214457$
$39252362$ $345673$ $786536$	$302328$
$68790234$ $679643$ $789057$	$281232$
$324$ $8564$ $45074547$	$32984424$

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

#include <iostream>
#include 
#include 
using namespace std;

long long modPow(long long base, long long exponent, long long mod){
    base %= mod;
    long long pow;
    if(exponent == 0){
        pow = 1;
    }
    else if(exponent % 2 == 0){
        pow = modPow(base * base, exponent / 2, mod) % mod;
    }
    else{
        pow = (base * modPow(base, exponent - 1, mod)) % mod;
    }
    return pow;
}

int main(){
    long long a, b, m;
    cin >> a >> b >> m;
    cout << modPow(a, b, m);
    return 0;
}

#include <iostream>

#include

using namespace std;

long long modPow(long long base, long long exponent, long long mod){

base %= mod;

long long pow;

if(exponent == 0){

pow = 1;

}

else if(exponent % 2 == 0){

pow = modPow(base * base, exponent / 2, mod) % mod;

}

else{

pow = (base * modPow(base, exponent - 1, mod)) % mod;

}

return pow;

}

int main(){

long long a, b, m;

cin >> a >> b >> m;

cout << modPow(a, b, m);

return 0;

}

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

По свойствам операций со сравнениями по модулю:
$$C \equiv C \mod K \pmod K$$
$$CD \equiv (C \mod K) \cdot (D \mod K) \pmod K$$
$$C \equiv D \pmod K \Rightarrow C^n \equiv D^n \pmod K$$
Отсюда выводим рекуррентную формулу бинарного возведения в степень по модулю:
$$
A^B \mod M =
\begin{cases}
1 \text{ при } B = 0\\
\left ( \left (A \mod M \right ) \left ( (A \mod M)^{B-1} \mod M \right )\right )\mod M \\ \text{ при } B \equiv 1 \pmod 2\\
\left ( \left (A \mod M \right)^2 \right)^{\frac{B}{2}} \mod M \text{ при } B \equiv 0 \pmod 2 \wedge B \neq 0
\end{cases}
$$

Ссылки

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

Related Images:

e-olymp 165. Симметрия

21/12/2017 by Даниил Крутоголов

Задача

Предприимчивая и умелая рукодельница решила подзаработать изготовлением «фенечек» из бисера. Любительница симметрии в искусстве, она использовала в своих орнаментах бусинки разных цветов (будем обозначать цвет целым положительным числом) по следующим правилам:

1) при длине ряда рисунка равной [latex]1[/latex] использовала бусинку первого цвета;

2) при длине ряда рисунка равной [latex]3[/latex] использовала бусинки двух цветов: [latex]1 2 1[/latex];

3) при необходимости добавления в рисунок еще одного цвета строился ряд: [latex]1 2 1 3 1 2 1[/latex] и так всякий раз в зависимости от числа используемых цветов, например, при использовании четырех цветов: [latex]1 2 1 3 1 2 1 4 1 2 1 3 1 2 1[/latex].

Напишите программу, которая помогла бы автоматизировать подбор цвета бусинки в ряду по её порядковому номеру.

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

В первой строке целое число [latex]k[/latex] [latex] (1 ≤ k ≤ 10^9) [/latex] – номер бусинки, цвет которой нужно определить, в ряду рисунка. Нумерация бусинок в ряду начинается с единицы.

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

В первой строке одно целое число – номер цвета заданной бусинки.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	[latex]10[/latex]	[latex]2[/latex]
2	[latex]116[/latex]	[latex]3[/latex]
3	[latex]1[/latex]	[latex]1[/latex]
4	[latex]454[/latex]	[latex]2[/latex]
5	[latex]12301230[/latex]	[latex]2[/latex]

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

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int n, m;
    double k;
    cin >> n;
    m = log2(n);
    k = log2(n);
    while (m != k){
        n = n - (pow(2,m));
        m = log2(n);
        k = log2(n);
    }
    cout << m + 1;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

int n, m;

double k;

cin >> n;

m = log2(n);

k = log2(n);

while (m != k){

n = n - (pow(2,m));

m = log2(n);

k = log2(n);

}

cout << m + 1;

return 0;

}

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

Рассматривая ряды с большим количеством цветов можно заметить закономерность: каждый чётный элемент равен единице, каждый последующий новый цвет будет на месте [latex]n·2[/latex]. Отсюда следует соответствие [latex]n[/latex] и [latex]2^{n-1}[/latex]. Формула для нахождения среднего элемента — [latex]\log_{2}n[/latex]. Программа будет искать средний элемент всегда, пока не найдёт нужный нам. Для чисел, из которых целый логарифм извлечь нельзя, найдем ближайший к нему и от числа отнимем [latex]2[/latex] в степени [latex]\log_{2}n[/latex]. К полученному ответу добавляем единицу, из-за приведённой ранее формулы [latex]2^{n-1}[/latex], и получаем правильный ответ.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

Related Images:

e-olymp 7367. Спортсмен

21/12/2017 by Иван Мясоедов

Задача

Спортсмен в первый день пробежал 10 км. Каждого следующего дня он увеличивал норму на 10% от нормы предыдущего дня. Опредилить через какое найменьшее количество дней спортсмен пробежит сусмарный путь не меньший чем [latex]N[/latex] км.

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

Целое число [latex]N (0 < N≤ 1000)[/latex].

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

Единственное число – количество дней.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	9	1
2	45	4
3	324	16
4	1234	28
5	213213123	153

Код программы №1 (с использованием цикла):

#include <iostream>
#include <cmath>
using namespace std;
 
int main() 
{
   double k = 1, T = 10, N, S = 10;
   cin >> N;
   while (N > T) {
       S = S * 1.1;
       T = S + T;
       k++;
   }
   cout << k;
   return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double k = 1, T = 10, N, S = 10;

cin >> N;

while (N > T) {

S = S * 1.1;

T = S + T;

k++;

}

cout << k;

return 0;

}

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

Сначала вводим 4 переменные: [latex] k=1 [/latex] ( количество дней ), [latex] T=10 [/latex] ( количество километров которое спортсмен пробежал ), [latex] N [/latex] ( количество километров которое спортсмен должен пробежать ) и [latex] S [/latex] ( количество километров которое спортсмен пробегает в день ). Цикл каждый раз будет прибавлять к расстоянию которое пробежал спортсмен, количество километров которое спортсмен должен пробежать в течение следующего дня, с учетом того, что каждый день он будет пробегать на [latex] 10 [/latex] процентов больше, чем в прошлый день, параллельно увеличивая количество дней, пока [latex] N [/latex] будет больше [latex] T [/latex]. Если же [latex] N [/latex] при вводе изначально будет меньше [latex] T [/latex], то программа выведет, что спортсмену достаточно одного дня.

Время срабатывания программы при [latex]N = 1000[/latex] : [latex]65[/latex] [latex]ms[/latex]

Ссылки

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

Код программы №2(с использованием линейных вычислений):

#include <iostream>
#include <cmath>

using namespace std;

int main() 
{
   double s;
   cin >> s;
   cout << ceil (log(s / 100 + 1) / log(1.1));
   return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double s;

cin >> s;

cout << ceil (log(s / 100 + 1) / log(1.1));

return 0;

}

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

Также данную задачу можно решить с помощью формулы геометрической прогрессии [latex]S=\frac{b_1(q^n-1)}{q-1}[/latex] из которой нам нужно будет выразить степень [latex] n [/latex] через логарифм при условии того, что по условию задачи мы знаем, что [latex] q=1.1 [/latex] и [latex] b_1=1 [/latex]. И мы получаем, что [latex] \left(n=\log_{1.1}\left(\frac{s}{100}+1\right)\right) [/latex]. При записи логарифма по основанию в С++ мы пользуемся основным свойством логарифмов: [latex] \log_{a}\left(b\right)=\frac{\log_{c}\left(b\right)}{\log_{c}\left(a\right)} [/latex]. Также используем функцию сeil, которая округлит выходное число вверх, до ближайшего целого. ( [latex] S [/latex] — количество километров, которое должен пробежать спортсмен ).

Время срабатывания программы при [latex]N = 1000[/latex] : [latex]76[/latex] [latex]ms[/latex]

Ссылки

Задача на сайте e-olymp
Код решения в Ideone №2

Related Images:

e-olymp 7457. Max-Min в двійковій системі счислення

20/12/2017 by Александра Рябова

Умова

Вивчаючи двійкову систему числення, Василько вирішив попрактикуватися і придумав таку вправу. Він із бітів числа створював найбільше і найменше число, переставляючи біти, після чого знаходив їх різницю. Проте хлопець не знає, чи правильно виконує вправу. Допоможіть йому. Напишіть програму, яка за даним числом [latex]N[/latex] знаходить різницю між найбільшим і найменшим числом, які утворюються із бітів заданого числа. У найбільшого числа найбільший біт співпадає з найбільшим бітом заданого числа.

Пояснення

[latex]N = 13_{10}[/latex], в двійковій системі числення — [latex]1101_2[/latex], найбільше число [latex]1110_2[/latex] = [latex]14_{10}[/latex], найменше число [latex]0111_2[/latex] = [latex]7_{10}[/latex]. [latex]14-7=7[/latex].

Вхідні дані

В єдиному рядку записане число N ([latex]N<2^{31}[/latex]).

Вихідні дані

Єдине число — відповідь до вправи Василька.

Тести

Вхідні дані	Вихідні дані
$2$	$1$
$15$	$0$
$86$	$105$
$1000$	$945$
$40$	$45$

Код програми

#include <iostream>
#include <iomanip>
#include <cmath>

long long max_number(long long n1, long long n0)
{
    long long  number;
    for (int i=n0+n1-1; i>=n0; i--)
    {
        number+=pow(2, i);  
    }
    return(number);
}

long long min_number(long long n1, long long n0)
{
    long long  number;
    for (int i=n1-1; i>=0; i--)
    {
        number+=pow(2, i);  
    }
    return(number);
}

int main() 
{
    long long n;
    cin >> n;
    long long n1=0;
    long long n0=0;
    while (n>0)
    {
        if (n%2==1) n1++;
        else n0++;
        n/=2;
    }
    
    cout << max_number (n1, n0) - min_number (n1, n0);
    return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

long long max_number(long long n1, long long n0)

{

long long number;

for (int i=n0+n1-1; i>=n0; i--)

{

number+=pow(2, i);

}

return(number);

}

long long min_number(long long n1, long long n0)

{

long long number;

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

{

number+=pow(2, i);

}

return(number);

}

int main()

{

long long n;

cin >> n;

long long n1=0;

long long n0=0;

while (n>0)

{

if (n%2==1) n1++;

else n0++;

n/=2;

}

cout << max_number (n1, n0) - min_number (n1, n0);

return 0;

}

Рішення

Процес вирішення даної задачі поділяється на 4 кроки:

За допомогою циклу рахуємо кількість одиниць та нулів у двійковому вигляді поданого числа [latex]n[/latex].
Створимо функцію [latex]max\_number[/latex], яка за поданою кількістю нулів та одиниць буде повертати найбільше число, яке в двійковій формі складатиметься з цієї кількості одиниць та нулів. Очевидно, що отримати найбільше число в двійковому вигляді можна, якщо записати спочатку всі одиниці, а потім — усі нулі.
Створимо функцію [latex]min\_number[/latex], яка за поданою кількістю нулів та одиниць буде повертати найменше число, яке в двійковій формі складатиметься з цієї кількості одиниць та нулів. Зрозуміло, що найменше число буде виглядати навпаки — спочатку будуть стояти всі нулі, а потім — усі одиниці.
Виведемо на екран різницю підрахованих функціями [latex]max\_number[/latex] та [latex]min\_number[/latex] значень.

Посилання

Код програми на ideone
Умова на сайті E-Olymp

Related Images:

e-olymp 2612. Разрезание на квадраты

14/12/2017 by Александр Волынец

Задача

Полоска бумаги имеет размеры [latex]A×B[/latex]. Каждый раз от нее отрезается квадрат максимального размера до тех пор, пока не получится квадрат. Сколько квадратов получится?

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

Программе даны числа [latex]A[/latex] и [latex]B[/latex] [latex](1 ≤ A, B ≤ 10^9).[/latex]

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

Требуется вывести количество квадратов.

Тесты

Входные данные	Выходные данные
12 4	3
15 3	5
20 20	1
8 12	3

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

#include <iostream>
using namespace std;

int main() {
    int a, b, temp = 0;
    bool need = 1;
    cin >> a >> b;
    while (need) {
        if (a >= b) {
            temp = temp + a / b;
            a = a%b;
        }
        else
        {
            temp = temp + b / a;
            b = b%a;
        }
        if (a == 0 || b == 0) {
            need = 0;
        }
    }
    cout << temp;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b, temp = 0;

bool need = 1;

cin >> a >> b;

while (need) {

if (a >= b) {

temp = temp + a / b;

a = a%b;

}

else

{

temp = temp + b / a;

b = b%a;

}

if (a == 0 || b == 0) {

need = 0;

}

cout << temp;

return 0;

}

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

Нам было дана высота и ширина полоски бумаги. Есть три варианта:

Высота равна ширине
Высота больше ширины
Высота меньше ширины

В первом случае нам надо вывести на экран единицу. Во втором случаем начинаем вычитать a - b до того момента, как a не будет меньше b или a не будет равняться 0. В третьем случае начинаем вычитать b - a до того момента, как b не будет меньше a или b не будет равняться 0.

Ссылки

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

Related Images:

e-olymp 61. Уборка снега

13/12/2017 by Кирилл Волков

Задача

Зимой, когда дни стают короче, а ночи длиннее, необходимо задуматься об уборке снега с улиц. Поскольку бюджет нашего города очень маленький, у нас в распоряжении только один снегоход. Несмотря на это дороги должны быть прочищены. И каждый раз, когда выпадает много снега, ночью снегоход нашего города выезжает со своего гаража и объезжает весь город, очищая дороги. Какое минимальное время нужно снегоходу, чтобы очистить все проезжие полосы всех дорог и вернуться назад?

При этом известно, что:

Снегоход может очищать только одну проезжую полосу дороги за один проход.
Все дороги прямые с одной полосой движения в каждом направлении.
Снегоход может поворачивать на любом перекрестке в любую сторону, а также может развернуться в тупике.
Во время очистки снега снегоход двигается со скоростью $20$ км/час, и со скоростью $50$ км/час по уже очищенной дороге.
Возможность проехать все дороги всегда существует.

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

Первая строка содержит два числа $x$ и $y$ $(-30000 ≤ x, y ≤ 30000)$ — координаты ангара (в метрах), откуда начинает свое движение снегоход. Далее в каждой отдельной строке заданы координаты (в метрах) начала и конца улиц (по $4$ числа в строке). В городе может быть до $100$ улиц.

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

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

Тесты

Входные данные	Выходные данные
$0$ $0$ $0$ $0$ $-1000$ $2000$ $0$ $0$ $1000$ $2000$	$0:27$
$0$ $1000$ $0$ $0$ $0$ $3000$ $0$ $0$ $1000$ $1000$ $0$ $0$ $3000$ $0$ $3000$ $0$ $3000$ $3000$ $3000$ $3000$ $0$ $3000$ $0$ $3000$ $1000$ $2000$ $3000$ $0$ $2000$ $1000$ $3000$ $3000$ $2000$ $2000$	$1:46$
$-500$ $0$ $-1000$ $0$ $0$ $0$ $0$ $0$ $1000$ $0$ $-1000$ $1000$ $0$ $0$ $-1000$ $1000$ $0$ $2000$ $0$ $2000$ $1000$ $1000$ $1000$ $1000$ $0$ $1000$ $0$ $1000$ $0$ $0$	$0:49$
$1000$ $500$ $-1000$ $0$ $1000$ $0$ $-1000$ $1000$ $1000$ $1000$ $-1000$ $0$ $-1000$ $1000$ $1000$ $0$ $1000$ $1000$ $-1000$ $0$ $1000$ $1000$ $1000$ $0$ $-1000$ $1000$ $-1000$ $1000$ $0$ $2000$ $0$ $2000$ $1000$ $1000$	$1:20$
$500$ $-500$ $0$ $0$ $1000$ $-1000$ $1000$ $-1000$ $2000$ $0$ $2000$ $0$ $3000$ $-1000$ $3000$ $-1000$ $4000$ $0$ $4000$ $0$ $5000$ $-1000$ $5000$ $-1000$ $6000$ $0$ $0$ $0$ $8000$ $0$	$1:39$

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

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    double temp;
    cin >> temp >> temp;
    double lengthOfRoads = 0;
    double firstX, firstY, secondX, secondY;
    while (cin >> firstX >> firstY >> secondX >> secondY)
    {
        lengthOfRoads += sqrt((secondX - firstX)*(secondX - firstX)+(secondY - firstY)*(secondY - firstY));
    }
    int minutes = round(3 * lengthOfRoads / 500);
    cout<< minutes / 60 << ":" << minutes % 60;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double temp;

cin >> temp >> temp;

double lengthOfRoads = 0;

double firstX, firstY, secondX, secondY;

while (cin >> firstX >> firstY >> secondX >> secondY)

{

lengthOfRoads += sqrt((secondX - firstX)*(secondX - firstX)+(secondY - firstY)*(secondY - firstY));

}

int minutes = round(3 * lengthOfRoads / 500);

cout<< minutes / 60 << ":" << minutes % 60;

return 0;

}

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

Начало пути всегда находится на одной из данных дорог. Составим оптимальный алгоритм движения снегохода. По каждой из дорог необходимо проехать в одну и другую сторону. Снегоход может начинать движение в любую сторону. Во время движения ему необходимо двигаться прямо, не разворачиваясь, настолько долго, насколько это возможно. В случае, если на пути следования снегоходу встречается поворот, ему необходимо повернуть и далее работать по тому же алгоритму, принимая за начальную точку точку поворота. После возвращения из поворота снегоход должен продолжить движение по алгоритму. Когда снегоход попадает в тупик, возвращается на перекресток, на котором был совершен поворот или попадает в начальную точку, ему необходимо развернуться и двигаться обратно по той же траектории. По возвращении в начальную точку снегоход должен, в случае необходимости, двигаться во все оставшиеся стороны по такому же алгоритму. Таким образом, при движении по такому алгоритму, снегоход будет проезжать по каждой дороге по одному разу в каждую сторону, то есть не будет нигде проезжать «лишние» километры, следовательно время, за которое снегоход может объехать все дороги по одному разу в каждую сторону и есть искомым. Таким образом нам необходимо посчитать сумму длин всех дорог $L$, координаты начала и конца которых даны во входном потоке. Снегоход всегда двигается со скоростью $V = 20 км/час = \frac{1000}{3}м/мин$. По каждой из дорог снегоход проезжает два раза, таким образом общее искомое время минутах:
$t = \frac{2L}{V} = \frac{3L}{500}$.
Округлив полученное значение $t$ до целых минут и представив это время в виде часов и минут, получаем ответ.
Замечание. Как видно из алгоритма решения, не имеет значения, где конкретно расположена точка начала движения, главное, чтобы она располагалась на одной из улиц.

Ссылки

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

Related Images:

A321. Циклы

13/12/2017 by Сытников Дан

Задача

Даны натуральные числа [latex]m, n[/latex], действительные числа [latex] a_1, a_2, …, a_{mn}[/latex]. Вычислить [latex]a_1 a_2 … a_m + a_{m+1} a_{m+2} … a_{2m} + a_{(n – 1) m + 1} a_{(n – 1) m + 2} … a_{nm}[/latex].

Входные данные:
[latex]m, n[/latex] — натуральные числа.
В следующей строке содержится [latex]m \cdot n[/latex] действительных чисел.

Выходные данные
Действительное число, значение требуемого выражения.

Тесты:

№	Входные данные	Выходные данные
1	3 3 1.1342 2.82113 3.5431 4.541 5.081 6.761 7.35781 8.456451 9.6461 10.9321	767.5218903911781
2	5 4 23.2312 -13.016 0.78 1.0 73.48992 -3441.32150 39.94 87.04 0.1 -0.02 94.094 23.0001 0.005 -2.0 -1.0 0.004 -1.01 42.0 0.454 1.5	6593.637250058031
3	3 2 1.1 2.2 3.3 4.4 5.5 6.6	327.426

Код на языке C++:

#include <iostream>
#include <iomanip>
using namespace std;

int main()
{
    int m, n;
    cin >> m >> n;
    double a[m*n];
    double sum1 = 1, sum2 = 1, sum3 = 1;
    double sum = 0;
    for (int i = 1; i <= m*n; i++)
    {
        cin >> a[i];
        if (i <= m)
        {
            sum1 *= a[i];
        }
        if ((i > m) && (i <= 2*m))
        {
            sum2 *= a[i];
        }
        if ((i > (n - 1)*m) && (i <= n*m)) 
        {
            sum3 *= a[i];
        }
    }
    cout << setprecision(15) << sum1 + sum2 + sum3;
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main()

{

int m, n;

cin >> m >> n;

double a[m*n];

double sum1 = 1, sum2 = 1, sum3 = 1;

double sum = 0;

for (int i = 1; i <= m*n; i++)

{

cin >> a[i];

if (i <= m)

{

sum1 *= a[i];

}

if ((i > m) && (i <= 2*m))

{

sum2 *= a[i];

}

if ((i > (n - 1)*m) && (i <= n*m))

{

sum3 *= a[i];

}

cout << setprecision(15) << sum1 + sum2 + sum3;

return 0;

}

Код на языке Java:

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

class Ideone {
    public static void main(String[] args) throws java.lang.Exception {
        Scanner in = new Scanner(System.in);
        int m, n;
        m = in .nextInt();
        n = in .nextInt();
        double[] a = new double[m * n + 1];
        double sum1 = 1, sum2 = 1, sum3 = 1;
        for (int i = 1; i <= m * n; i++) {
            a[i] = in .nextDouble();
            if (i <= m) {
                sum1 *= a[i];
            }
            if ((i > m) && (i <= 2 * m)) {
                sum2 *= a[i];
            }
            if ((i > (n - 1) * m) && (i <= n * m)) {
                sum3 *= a[i];
            }
        }
        System.out.println(sum1 + sum2 + sum3);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

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

Scanner in = new Scanner(System.in);

int m, n;

m = in .nextInt();

n = in .nextInt();

double[] a = new double[m * n + 1];

double sum1 = 1, sum2 = 1, sum3 = 1;

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

a[i] = in .nextDouble();

if (i <= m) {

sum1 *= a[i];

}

if ((i > m) && (i <= 2 * m)) {

sum2 *= a[i];

}

if ((i > (n - 1) * m) && (i <= n * m)) {

sum3 *= a[i];

}

System.out.println(sum1 + sum2 + sum3);

}

Решение задачи:
Заведём массив для хранения чисел. Пользуясь циклом [latex]for[/latex] от [latex]1[/latex] до [latex]m \cdot n[/latex], по мере заполнения массива будем считать слагаемые нашего выражения. Для этого воспользуемся оператором [latex] if [/latex], проверяя индексы элементов массива.

Код программы на C++: Ideone
Код программы на Java: Ideone
Условия задачи(стр.134): 321

Related Images:

D2630. Сходимость ряда

13/12/2017 by Курьянов Павел

Задача
Исследовать сходимость ряда [latex]\sum_{n=1}^{\infty}\frac{ln(n!)}{n^{a}}[/latex] и вычислить его сумму при заданной точности.

Входные данные
Натуральное число [latex]a[/latex]

Выходные данные
Сумма ряда если она существует.

Тесты

входящие данные	выходящие данные
2	-nan
3	0.578615
6	0.0146958
12	0.000172786
22	1.65259e-07

#include <cmath>
#include <iostream>
using namespace std;
int poww(int a,int n) {
  return (!n)?1:a*poww(a,n-1);
}
int main() {
    int a;
    cin>>a; //ряд будет сходящимся только при a>2
    double s=0;
    long double f=1;
    double e=10;
    for(int n=2;e>0.000001;n++){
    f*=n;
    s+=log(f)/poww(n,a);
    e=log(f)/poww(n,a);
    }
    cout<<s;
    return 0;
    
}

#include <cmath>

#include <iostream>

using namespace std;

int poww(int a,int n) {

return (!n)?1:a*poww(a,n-1);

}

int main() {

int a;

cin>>a; //ряд будет сходящимся только при a>2

double s=0;

long double f=1;

double e=10;

for(int n=2;e>0.000001;n++){

f*=n;

s+=log(f)/poww(n,a);

e=log(f)/poww(n,a);

}

cout<<s;

return 0;

}

Решение задачи
Исследуем ряд на сходимость при различных значениях переменных [latex]a[/latex]. При [latex]a\leq 1[/latex] случай тривиальный — ряд будет расходиться.
Рассчитаем его при [latex]a\geq 2[/latex]. Как видно при [latex]a=2[/latex] ряд продолжает расходиться, а при [latex]a>2[/latex] он начинает сходиться и становиться возможным вычислить его сумму.

Ссылки
Условие задачи (стр. 257)
Код на ideone

Related Images:

D2550. Сумма ряда

10/12/2017 by Сытников Дан

Условие задачи:
Найти сумму сходящегося ряда:
[latex]\frac{1}{1 \cdot 4} + \frac{1}{4 \cdot 7} + … + \frac{1}{(3n — 2)(3n + 1)} + …[/latex]

Входные данные:
Целое число [latex]k[/latex] — номер искомой частичной суммы.

Выходные данные:
Искомая частичная сумма.

Тесты

№	Входные данные	Выходные данные
1	1	0.25
2	234	0.3328591749644379
3	10000	0.33332222259257893

Код на языке C++:

#include <iostream>
#include <iomanip> 
using namespace std;

int main() {
    int k;
    long double val = 0;
    cin >> k;
    for (int n = 1; n <= k; n++){
        val += 1.0/((3*n - 2)*(3*n + 1)); 
    }
    cout << setprecision(15) <<val;
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

int k;

long double val = 0;

cin >> k;

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

val += 1.0/((3*n - 2)*(3*n + 1));

}

cout << setprecision(15) <<val;

return 0;

}

Код на языке Java:

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

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {   
        Scanner in = new Scanner(System.in);
        int k;
        double val = 0;
        k = in.nextInt();
        for (int n = 1; n <= k; n++){
            val += 1.0/((3*n - 2)*(3*n + 1)); 
        }
        System.out.println(val);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

int k;

double val = 0;

k = in.nextInt();

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

val += 1.0/((3*n - 2)*(3*n + 1));

}

System.out.println(val);

}

Решение задачи:
Используем цикл for от 1 до заданного пользователем [latex]k[/latex] номера частичной суммы, в котором будем суммировать слагаемые ряда вида: [latex]\frac{1}{(3n — 2)(3n + 1)},[/latex] где [latex]n = \overline{1,k}[/latex].

Условие задачи (стр.248)
Код задачи на C++: Ideone
Код задачи на Java: Ideone

Related Images:

e-olymp 1210. Очень просто!!!

04/12/2017 by Вадим Гордийчук

Задача

По заданным числам [latex]n[/latex] и [latex]a[/latex] вычислить значение суммы: [latex]\sum\limits_{i=1}^{n} {i \cdot a^i}[/latex]

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

Два натуральных числа [latex]n[/latex] и [latex]a[/latex].

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

Значение суммы. Известно, что оно не больше [latex]10^{18}[/latex].

Тесты

Входные данные	Выходные данные
3 3	102
4 4	1252
9 3	250959
7 14	785923166
1009 1	509545

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

#include <iostream>
using namespace std;

int main()
{
    unsigned long long int n, a, answer;
    cin >> n >> a;
    if (a > 1)
    {
        answer = n*a;
        for(unsigned long long int i = n-1; i > 0; --i)
            answer = (answer+i)*a;
    }
    else
        answer = n*(n+1)/2;
    cout << answer;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

unsigned long long int n, a, answer;

cin >> n >> a;

if (a > 1)

{

answer = n*a;

for(unsigned long long int i = n-1; i > 0; --i)

answer = (answer+i)*a;

}

else

answer = n*(n+1)/2;

cout << answer;

return 0;

}

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

public class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        long n = in.nextInt(), a = in.nextInt(), ans;
        if (a > 1)
        {
            ans = n*a;
            for(long i = n-1; i > 0; --i)
                ans = (ans+i)*a;
        }
        else
            ans = n*(n+1)/2;
        System.out.println(ans);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

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

{

Scanner in = new Scanner(System.in);

long n = in.nextInt(), a = in.nextInt(), ans;

if (a > 1)

{

ans = n*a;

for(long i = n-1; i > 0; --i)

ans = (ans+i)*a;

}

else

ans = n*(n+1)/2;

System.out.println(ans);

}

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

Данную задачу можно решить прямым линейным вычислением значений элементов заданного ряда, то есть получать значение элемента ряда с индексом [latex]i[/latex] умножением [latex]a[/latex] (которое необходимо возвести в степень [latex]i[/latex]) на индекс [latex]i[/latex] и накапливать сумму этих значений в выделенной переменной.
Но безусловно такое решение не является качественным (даже если будет использован алгоритм бинарного возведения в степень).

Для получения качественного решения распишем ряд подробно:
[latex]A[/latex] [latex]=[/latex] [latex]\sum\limits_{i=1}^{n} {i \cdot a^i}[/latex] [latex]=[/latex] [latex]a+2a^2+3a^3+\ldots+\left( n-1 \right) a^{n-1}+na^{n}[/latex] [latex]=[/latex] [latex]na^{n}[/latex] [latex]+[/latex] [latex]\left( n-1 \right)a^{n-1}[/latex] [latex]+[/latex] [latex]\ldots[/latex] [latex]+[/latex] [latex]3a^{3}[/latex] [latex]+[/latex] [latex]2a^2[/latex] [latex]+[/latex] [latex]a[/latex].
Очевидно, что из полученного выражения можно вынести [latex]a[/latex] за скобки. Применим данную операцию:
[latex]A[/latex] [latex]=[/latex] [latex] \left( na^{n-1}+\left( n-1 \right)a^{n-2}+\ldots+3a^{2}+2a+1\right) \cdot a[/latex] Из полученной формулы видно, что аналогичное действие можно применить вновь, для внутреннего выражения [latex]na^{n-1}[/latex] [latex]+[/latex] [latex]\left( n-1 \right)a^{n-2}[/latex] [latex]+[/latex] [latex]\ldots[/latex] [latex]+[/latex] [latex]3a^{2}[/latex] [latex]+[/latex] [latex]2a[/latex]. Получим:
[latex]A[/latex] [latex]=[/latex] [latex] \left( \left( na^{n-2}+\left( n-1 \right)a^{n-3}+\ldots+3a+2 \right) \cdot a +1 \right) \cdot a[/latex].
После конечного количества вынесений за скобки, получим:
[latex]A[/latex] [latex]=[/latex] [latex]\left( \left( \ldots \left( \left(na+\left(n-1\right)\right) \cdot a + \left(n-2\right) \right) \ldots+2\right) \cdot a +1\right) \cdot a[/latex].

Таким образом, решение данной задачи сводится к вычислению суммы «изнутри» скобок.

Но из-за того, что в условии подано ограничение только на сумму, программа с реализованным вычислением суммы изнутри и асимптотикой [latex]O \left( n \right)[/latex] не пройдёт все тесты системы www.e-olymp.com в силу частного случая [latex]a = 1[/latex], так как значение [latex]n[/latex] может быть для него достаточно большим, ибо числа [latex]a[/latex] и [latex]n[/latex] компенсируют друг-друга по отношению к максимальному значению суммы. Но в случае [latex]a = 1[/latex] сумма данного ряда является суммой арифметической прогрессии, а именно — натурального ряда. Для вычисления этой суммы существует формула [latex]\sum\limits_{i=1}^{n} {i} = \frac{n \left( n+1 \right)}{2}[/latex]. Этот частный случай легко отсеять.

Асимптотика программы: [latex]const[/latex] при [latex]a = 1[/latex], и [latex]O \left( n \right)[/latex] иначе.

Ссылки

Related Images:

e-olymp 442. Построения

29/11/2017 by Данилов Андрей

Задача

Иван Петрович преподает в школе физкультуру, но интересуется также математикой, в основном, с практической точки зрения. Например, его интересует вопрос, сколько различных построений существует для группы из [latex]N[/latex] человек. Иван Петрович выяснил, что если [latex]N[/latex]– простое число, то получается только [latex]2[/latex] построения: в колонну по одному ([latex]1[/latex]×[latex]N[/latex]) и в шеренгу ([latex]N×1[/latex]). Эти тривиальные построения возможны для любого [latex]N[/latex] > [latex]1[/latex] (для [latex]N = 1[/latex] существует только одно построение ([latex]1×1[/latex]), которое не является ни шеренгой, ни колонной). Если [latex]N[/latex] – составное число, то существует и другие нетривиальные построения. Для [latex]100[/latex] человек существует девять построений: ([latex]1×100[/latex]), ([latex]2×50[/latex]), ([latex]4×25[/latex]), ([latex]5×20[/latex]), ([latex]10×10[/latex]), ([latex]20×5[/latex]), ([latex]25×4[/latex]), ([latex]50×2[/latex]) и ([latex]100×1[/latex]).

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

В первой строке ввода содержится одно целое число [latex]N[/latex] (1 ≤[latex]N[/latex]≤ 109).

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

Вывести одно целое число – количество различных построений для группы из [latex]N[/latex] человек.

Тесты

#	Входные данные	Выходные данные
1	100	9
2	1	1
3	6	4
4	999983	2
5	2	2

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

#include <iostream>
#include <cmath>
using namespace std;

int main () { 
    int NumberOfPeople;
    cin >> NumberOfPeople;
    if(NumberOfPeople == 1){
        cout << 1;
        return 0;
    } 
    else
    {
          int deviders = 0;
          for(int i = 1; i < sqrt(NumberOfPeople);i++){
                if(NumberOfPeople % i == 0) deviders++; // проверка на делимость
    }
    deviders *= 2;
    int Root = sqrt(NumberOfPeople);
    if(Root*Root == NumberOfPeople) deviders++; // проверка корня на делимость
    cout << deviders;
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main () {

int NumberOfPeople;

cin >> NumberOfPeople;

if(NumberOfPeople == 1){

cout << 1;

return 0;

}

else

{

int deviders = 0;

for(int i = 1; i < sqrt(NumberOfPeople);i++){

if(NumberOfPeople % i == 0) deviders++; // проверка на делимость

}

deviders *= 2;

int Root = sqrt(NumberOfPeople);

if(Root*Root == NumberOfPeople) deviders++; // проверка корня на делимость

cout << deviders;

}

return 0;

}

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

По условию задачи требуется найти все возможные построения. Это значит, что мы должны найти все возможные варианты разбиения числа на множители. Для этого можно обойтись перебором всех делителей числа от 1 до корня из этого числа, а затем умножить полученное значение на 2 так как для нас имеет значение порядок делителей. Если корень из числа есть делитель данного числа то увеличиваем счетчик на 1.

Ссылки

Ссылка на e-olymp
Ссылка на ideone

Related Images:

A 325. Простые делители числа

28/08/2017 by Курьянов Павел

Задача
Дано натуральное число [latex]n[/latex]. Получить все простые делители этого числа.

Входные данные
Натуральное число [latex]n[/latex]

Выходные данные
Все его простые делители напечатанные через пробел

Тесты

входные данные	выходные данные
2	2
7	7
50	2 5 5
169	13 13
583	11 53
2368	2 2 2 2 2 2 37
73890	2 3 3 5 821
885066	2 3 7 13 1621
6943960340	2 2 5 97 1787 2003

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main()
{
    unsigned long long n;
  cin>>n;
    
    for (unsigned long long i = 2; i < sqrt(n)+0.00001; )    {
        if ( n % i == 0 ){
            std::cout << i << ' ';
            n /= i;
        }
        else{
            ++i;
        }
    }
    if ( n > 1 )
        std::cout << n;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

unsigned long long n;

cin>>n;

for (unsigned long long i = 2; i < sqrt(n)+0.00001; ) {

if ( n % i == 0 ){

std::cout << i << ' ';

n /= i;

}

else{

++i;

}

if ( n > 1 )

std::cout << n;

return 0;

}

Решение задачи
Для решения задачи мы проверяем все числа от 2 до [latex]\sqrt{n}[/latex]. Если число является делителем [latex]n[/latex], то мы его выводим и делим [latex]n[/latex] на это число. Повторная проверка на простоту не требуется так как мы ведем поиск снизу, а значит число полученное после проверки уже не может делиться на составное. В конце, если остается простой делитель больше, то он выводиться так же.

Ссылки

Условие задачи(страница 135)
Код на ideone

Related Images:

A328

21/06/2017 by Алла Марокко

Задача:
Найти [latex]100[/latex] первых простых чисел.
Тесты:
Обобщим задачу и для тестов используем разное количество первых простых чисел.

№	Вход	Выход
1	25	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
2	50	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229
3	100	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541

Код:

#include <iostream>
using namespace std;

int main() { 
    printf("2"); 
    int n;
    cin>>n;
    for (int i=3; n; i+=2) { 
        for (int j = 3; j*j<=i ; ++j){
            if (i%j==0) goto next;
        }
        printf(", %d",i);
        --n; 
        next:;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

printf("2");

int n;

cin>>n;

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

for (int j = 3; j*j<=i ; ++j){

if (i%j==0) goto next;

}

printf(", %d",i);

--n;

next:;

}

return 0;

}

Решение:
Первое простое число печатаем сразу, остальные [latex]n-1[/latex] будем проверять циклами: проверим нечетные числа на нечетные делители(пройдём цикл по делителям). Число простое, если нет делителей. Если не простое, то переходим к следующему. Каждое простое число печатаем до [latex]n[/latex] включительно.
Ссылки:

Условие задачи.
Онлайн компилятор ideone.

Related Images:

Chuck Norris

11/05/2017 by Антон Куперман

A task from codingame.com

Task

Binary with 0 and 1 is good, but binary with only 0, or almost, is even better! Originally, this is a concept designed by Chuck Norris to send so called unary messages.

Write a program that takes an incoming message as input and displays as output the message encoded using Chuck Norris’ method.

Here is the encoding principle:

The input message consists of ASCII characters (7-bit)
The encoded output message consists of blocks of 0
A block is separated from another block by a space
Two consecutive blocks are used to produce a series of same value bits (only 1 or 0 values):
— First block: it is always 0 or 00. If it is 0, then the series contains 1, if not, it contains 0
— Second block: the number of 0 in this block is the number of bits in the series

Input

Line 1: the message consisting of N ASCII characters (without carriage return)

Output

The encoded message

Tests

Input	Output
C	0 0 00 0000 0 00
CC	0 0 00 0000 0 000 00 0000 0 00
%	00 0 0 0 00 00 0 0 00 0 0 0
Hello	0 0 00 00 0 0 00 000 0 00 00 00 0 0 00 0 0 000 00 0 0 00 00 00 0 00 00 0 0 00 00 00 0 00 00 0 0 0000

Code

#include <iostream>
#include <string>
using namespace std;


string binary(unsigned char x){
    unsigned char mask=64;
    string s;
    for(int i=0; i<7; i++) {
        s.push_back((x&mask)>0 ? '1':'0');
        mask=mask>>1;
    }
    return s;
}

int main() {
    string l;
    string a;
    unsigned char x;
    while(cin >> x){
        l+=binary(x);
    }
    for(int i=0;i<l.size();i++)
    {
        if(l.at(i)=='0')
        {
            if(i==0||l.at(i-1)=='1')
            {
                if(i!=0)
                {
            a+=" ";
            a.push_back('0');
            a.push_back('0');
            a+=" ";
                } else {
                    a.push_back('0');
                    a.push_back('0');
                    a+=" ";
                }
            } 
            a.push_back(l.at(i));
        } else if(l.at(i)=='1')
        {
            if(i==0||l.at(i-1)=='0')
            {
                if(i!=0)
                {
                a+=" ";
                a.push_back('0');
                a+=" ";
                } else{ 
                    a.push_back('0');
                    a+=" ";
                }
            } 
            a.push_back(l.at(i));
        }   
    }
    for(int i=0;i<a.size();i++)
    {
        if(a.at(i)=='1')
        {
            a.at(i)='0';
        }
    }
    cout<<a;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

string binary(unsigned char x){

unsigned char mask=64;

string s;

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

s.push_back((x&mask)>0 ? '1':'0');

mask=mask>>1;

}

return s;

}

int main() {

string l;

string a;

unsigned char x;

while(cin >> x){

l+=binary(x);

}

for(int i=0;i<l.size();i++)

{

if(l.at(i)=='0')

{

if(i==0||l.at(i-1)=='1')

{

if(i!=0)

{

a+=" ";

a.push_back('0');

a+=" ";

} else {

a.push_back('0');

a+=" ";

}

a.push_back(l.at(i));

} else if(l.at(i)=='1')

{

if(i==0||l.at(i-1)=='0')

{

if(i!=0)

{

a+=" ";

a.push_back('0');

a+=" ";

} else{

a.push_back('0');

a+=" ";

}

a.push_back(l.at(i));

}

for(int i=0;i<a.size();i++)

{

if(a.at(i)=='1')

{

a.at(i)='0';

}

cout<<a;

return 0;

}

Solution

First, we create a so called mask, which takes the symbol, transform it to a binary 7-bit number and return string. Then we add this string to another one, while transforming every symbol in the cin. Then we create a loop, where we check either symbol is 0 or 1 and add them to another string in the right order according to the encoding principle. In order to escape mistakes with ‘1’ in the first loop, we create another loop, where we change all ‘1’ to ‘0’.

Related Images:

Монстр

18/04/2017 by Антон Куперман

Задача 787A с сайта codeforces.com.

Задача

Монстр гонится за Риком и Морти на другой планете. Они настолько напуганы, что иногда кричат. Точнее, Рик кричит в моменты времени b, b + a, b + 2a, b + 3a, …, а Морти кричит в моменты времени d, d + c, d + 2c, d + 3c, ….

Монстр поймает их, если в какой-то момент времени они закричат одновременно. Так что он хочет знать, когда он поймает их (первый момент времени, когда они закричат одновременно) или они никогда не закричат одновременно.

Ввод

Первая строка входных данных содержит два целых числа a и b (1 ≤ a, b ≤ 100).

Вторая строка входных данных содержит два целых числа c и d (1 ≤ c, d ≤ 100).

Вывод

Выведите первый момент времени, когда Рик и Морти закричат одновременно, или - 1, если они никогда не закричат одновременно.

Тесты

Ввод	Вывод
20 2 9 19	82
2 1 16 12	-1

Код

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int a,b,c,d,n,m;
    vector <int> s;
    cin>>a>>b;
    cin>>c>>d;
    for(int i=0;i<=100;i++)
    {
        for(int j=0;j<=100;j++)
        {
            n=b+i*a;
            m=d+j*c;
            if(m==n)
            {   
                s.push_back(n);
            } 
        }
    }
    if(s.empty()==true)
    {
        cout<<-1;
    } else cout<<s.at(0);
    
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

int a,b,c,d,n,m;

vector <int> s;

cin>>a>>b;

cin>>c>>d;

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

{

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

{

n=b+i*a;

m=d+j*c;

if(m==n)

{

s.push_back(n);

}

if(s.empty()==true)

{

cout<<-1;

} else cout<<s.at(0);

return 0;

}

Решение

В этих моментах времени, заданных прогрессиями, изменяется только коэффициент при a и c. Создадим для них 2 цикла. Так как равных моментов времени может быть много, а нам нужен только первый, создаем вектор и ,когда моменты равны, добавляем в него этот момент. Затем, уже вне цикла, проверяем пустой ли вектор, и в таком случаем выводим -1, так как моменты на данном промежутке не были равны ни разу. Если же вектор непустой, выходим первый элемент вектора. Он и будет искомым первым одновременным криком.