Category Archives: 3. Циклы

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

Циклы

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

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

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

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

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

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

e-olymp 8538. Калькулятор

07/08/2020 by Александр Розин

Условие

Калькулятор Ильи выполняет два действия: умножает текущее число на три и прибавляет к нему единицу. На калькуляторе сейчас число $1$. Помогите Илье определить наименьшее количество действий, после которой он получит число $n$.

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

Одно число $n$ $\left(10\leq n\leq 10^9\right)$.

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

Выведите наименьшее количество операций.

Тесты

№	Входные данные	Выходные данные
1	1447	16
2	18	3
3	111	6

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

#include <iostream>
using namespace std;
 
int main() {
    long long n;
    int k = 0;
    cin >> n;
    while (n > 0) {
        k += n%3 + 1;
        n /= 3;
    } 
    cout << k - 2;
}

#include <iostream>

using namespace std;

int main() {

long long n;

int k = 0;

cin >> n;

while (n > 0) {

k += n%3 + 1;

n /= 3;

}

cout << k - 2;

}

Решение

Решим данную задачу от обратного. Пусть нам дано число $n$ и нам надо из него получить $1$, задействовав как можно меньше операций. Для этого объявим цикл while(), который будет работать до тех пор, пока наше число $n$ будет строго больше $0$. Внутри цикла опишем следующее решение: пусть k будет счётчиком нажатий на кнопки калькулятора и изначально равняется $0$. Тогда, при каждом шаге цикла мы к счётчику будем прибавлять остаток от деления на $3$. n%3 — именно столько раз нам потребуется отнять $1$ от $n$ чтобы можно было нацело разделить на $3$. Далее, делим $n$ на $3$ и это потребует еще одного нажатия (что и происходит в строке $9$). Так как в условии цикла мы написали, что $n > 0$, то мы пройдём лишнюю итерацию и к счётчику прибавятся два лишних шага. Поэтому, при выводе ответа, от $k$ отнимаем $2$.

Related Images:

e-olymp 7843. Больше предыдущего

27/06/2020 by Андрей Мартынюк

Задача

Задан массив целых чисел. Выведите все его элементы, которые больше предыдущего.

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

В первой строке записано количество чисел [latex]N[/latex] в массиве. В следующей строке записано [latex]N[/latex] целых чисел. Все числа по модулю не превышают [latex]100[/latex].

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

Выведите элементы массива, которые больше предыдущих.

Тесты

№	Входные данные	Выходные данные
1.	7 14 16 3 7 17 19 9	16 7 17 19
2.	5 3 5 2 4 1	5 4

Код

#include <iostream>
using namespace std;

int main() {
    int n, a, b;
    cin >> n;
    cin >> a;
    for(int i = 0; i < n; i++) {
       cin >> b;
       if(b > a) {
          cout << b << " ";
       }
       a = b;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, a, b;

cin >> n;

cin >> a;

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

cin >> b;

if(b > a) {

cout << b << " ";

}

a = b;

}

return 0;

}

Решение

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

Ссылки

Related Images:

e-olymp 8946. Шаблон

28/05/2020 by Алина Зозуля

Условие

По заданному натуральному числу $n$ вывести изображение размером $n\times n$, образованное символами звездочка и пробел как показано в примере.

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

Одно натуральное число $n$.

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

Вывести изображение $n \times n$.

Тесты

№

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

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

* 
 *

* *

 *

* *

* *

* *

 * *

* *

* *

* * *

 * *

* * *

 * *

* * *

* * *

* *

* * *

* *

* * *

* * *

 * * *

* * *

 * * *

* * *

 * * *

* * *

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

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

int main() {
    long long n;
    string s1 = "", s2 = "";
    cin >> n;
    for (int i = 0; i < n; i++){//заполняем строки 
        if (i % 2 == 0){
            s1 += "*";
            s2 += " ";
        }
        else {
            s2 += "*";
            s1 += " ";
        }
    }
    for (int i = 0; i < n; i++){
        if (i % 2 == 0){//выводим s1, если строка имеет четный номер
            cout << s1 << endl;
        }
        else cout << s2 << endl;//выводим s2, если строка имеет нечетный номер
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

long long n;

string s1 = "", s2 = "";

cin >> n;

for (int i = 0; i < n; i++){//заполняем строки

if (i % 2 == 0){

s1 += "*";

s2 += " ";

}

else {

s2 += "*";

s1 += " ";

}

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

if (i % 2 == 0){//выводим s1, если строка имеет четный номер

cout << s1 << endl;

}

else cout << s2 << endl;//выводим s2, если строка имеет нечетный номер

}

return 0;

}

Решение

Для того, чтобы вывести изображение как на рисунке достаточно заметить, что выводятся строки только двух видов и то поочерёдно. Первый вид — первым символом строки является $\ast$ и затем чередуется $\ast$ и пробел. Второй вид — первым символом строки является пробелом и затем чередуется $\ast$ и пробел. Мы заполняем две строки, по одной каждого вида. Нам остается только выводить строку необходимого нам вида, сделаем это в цикле.

Ссылки

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

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

Related Images:

e-olimp 9536. Сумма матриц

16/05/2020 by Елизавета Савицкая

Задача

Заданы две матрицы $A$ и $B$. Найдите их сумму $C$ = $A$ + $B$.

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

Первая строка содержит размеры матриц $n$ и $m$ $(1 \leqslant n, m \leqslant 100)$. Следующие $n$ строк содержат по $m$ целых чисел и описывают матрицу $A$. Далее следует пустая строка, после чего в таком же формате задается матрица $B$.

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

Выведите матрицу $С$: $n$ строк по $m$ целых чисел.

Тесты

Входные данные	Выходные данные
1 1 2 3	5
1 5 4 3 7 2 1 3 2 2 1 6	7 5 9 3 7
2 2 0 4 2 3 5 4 1 6	5 8 3 9
3 4 3 4 5 6 1 2 3 4 7 6 5 4 0 0 -3 -2 -1 3 4 5 5 6 1 2	3 4 2 4 0 5 7 9 12 12 6 6
3 3 2 -128 47 -365 5 56 243 42 12 678 43 76 4 345 -23 97 -453 18	680 -85 123 -361 350 33 340 -411 30

Код

#include <iostream>
using namespace std;

int main() {
   int n, m;
   cin >> n >> m;
   int matrix1[n][m];
   int matrix2[n][m];
   int matrix_sum[n][m] = {0};
   for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
         cin >> matrix1[i][j];
      }
   }
   for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
         cin >> matrix2[i][j];
      }
   }
   for(int i = 0; i < n; i++){
      for(int j = 0; j < m; j++){
         matrix_sum[i][j] = matrix1[i][j] + matrix2[i][j];
         cout << matrix_sum[i][j] << " ";
      }
      cout << endl;
   }
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> n >> m;

int matrix1[n][m];

int matrix2[n][m];

int matrix_sum[n][m] = {0};

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

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

cin >> matrix1[i][j];

}

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

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

cin >> matrix2[i][j];

}

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

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

matrix_sum[i][j] = matrix1[i][j] + matrix2[i][j];

cout << matrix_sum[i][j] << " ";

}

cout << endl;

}

return 0;

}

Решение

Чтобы найти сумму двух матриц, необходимо сложить их соответствующие элементы.

Ссылки

Условие задачи на E-Olymp
Код задачи на Ideone

Related Images:

e-olimp 8536. Заповнення смуги $3 \times n$

03/05/2020 by Анна Цивинская

Внимание: Задача на сайте e-olymp была заменена на другую. Теперь такой задачи там нет.

Задача

Смугу висотою $3$ см і шириною $n$ см суцільно заповнено прямокутниками $3 \times 1$ та $1 \times 3$ см. Скількома способами можна її заповнити? Різні способи – це різні кількості вказаних прямокутників та їх різні розташування.

Вхідні дані

Одне натуральне число $n$ $(1 \leqslant n \leqslant 50)$.

Вихідні дані

Вивести кількість способів, якими можна заповнити смугу.

Тести

Вхідні дані	Вихідні дані
1	1
5	4
12	60
50	122106097

Код № 1

#include <iostream>
using namespace std;
 
int main() {
   int n;
   cin >> n;
   int F[51] = {0, 1, 1, 2, 3};
   for(int i = 5; i <= n; i++) {
      F[i] = F[i-2] + F[i-3] + F[i-4];
   }
   cout << F[n];
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int F[51] = {0, 1, 1, 2, 3};

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

F[i] = F[i-2] + F[i-3] + F[i-4];

}

cout << F[n];

return 0;

}

Рішення 1

Це завдання на динамічне програмування, тому спочатку нам потрібно розбити цю задачу на декілька простих. Треба порахувати кількість способів для чотирьох перших елементів масиву. Якщо рахувати далі, то ми помітимо, що кожне наступне значення отримується за формулою F[i] = F[i-2] + F[i-3] + F[i-4].

Код № 2

#include <iostream>
using namespace std;
 
int F[51] = {0, 1, 1, 2, 3};
 
int numberOfWays(int n) {
   if(F[n]) {
      return F[n];
   } else {
      F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);
   }
   return F[n];
}
 
int main() {
   int n;
   cin >> n;
   cout << numberOfWays(n);
   return 0;
}

#include <iostream>

using namespace std;

int F[51] = {0, 1, 1, 2, 3};

int numberOfWays(int n) {

if(F[n]) {

return F[n];

} else {

F[n] = numberOfWays(n-2) + numberOfWays(n-3) + numberOfWays(n-4);

}

return F[n];

}

int main() {

int n;

cin >> n;

cout << numberOfWays(n);

return 0;

}

Рішення 2

Також для рішення цієї задачі можна використати рекурсію. При виклику функції ми перевіряємо, чи є в пам’яті це значення. Якщо такого значення не має, то ми його рахуємо. Таким чином ми уникаємо використання зайвої пам’яті.

Посилання

Умова задачі на E-Olymp
Зараховане рішення № 1 на E-Olymp
Зараховане рішення № 2 на E-Olymp
Код задачі № 1 на Ideone
Код задачі № 2 на Ideone

Related Images:

e-olimp 8234. Сходинки

09/04/2020 by Елизавета Савицкая

Задача

Скількома способами можна потрапити на $n$-ту сходинку, якщо можна ступати на наступну, переступати через одну і через дві сходинки.

Вхідні дані

Одне число $n$ — номер сходинки $(n \leqslant 60)$.

Вихідні дані

Вивести кількість способів, якими можна потрапити на $n$-ту сходинку.

Тести

Вхідні дані	Вихідні дані
0	1
5	13
15	5768
32	181997601
60	4680045560037375

Код № 1

#include <iostream>
using namespace std;

int main() {
   int n;
   cin >> n;
   long long arr[61] = {0};
   arr[0] = 1;
   arr[1] = 1;
   arr[2] = 2;
   for(int i = 3; i <= n; i++) {
      arr[i] = arr[i-1] + arr[i-2] + arr[i-3];
   }
   cout << arr[n];
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

long long arr[61] = {0};

arr[0] = 1;

arr[1] = 1;

arr[2] = 2;

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

arr[i] = arr[i-1] + arr[i-2] + arr[i-3];

}

cout << arr[n];

return 0;

}

Рішення

Розіб’ємо задачу на декілька простих. Спочатку розрахуємо кількість способів для однієї сходинки (1 спосіб), потім для двох (2 способи: 0 $\rightarrow$ 1 $\rightarrow$ 2; 0 $\rightarrow$ 2) і також потрібно врахувати випадок, коли кількість сходинок дорівнює нулю (1 спосіб). Далі легко помітити, що кожне наступне значення дорівнює сумі трьох попередніх звідки і отримуємо формулу:
arr[i] = arr[i-1] + arr[i-2] + arr[i-3]
Також цю задачу можна вирішити за допомогою рекурсії. Я використала рекурсію з запам’ятовуванням для того, щоб уникнути переповнення стеку викликів (загальна ідея така: при кожному виклику функції перевіряємо, чи маємо ми вже це значення, і якщо ні, рахуємо його. Таким чином ми будемо використовувати кожне значення лише один раз).

Код № 2

#include <iostream>
using namespace std;

long long arr[61] = {0};

long long num_of_ways(int n) {
   if(arr[n]) {
      return arr[n];
   }
   else {
      arr[n] = num_of_ways(n-1) + num_of_ways(n-2) + num_of_ways(n-3);
   }
   return arr[n];
}
int main() {
   int n;
   cin >> n;
   arr[0] = 1;
   arr[1] = 1;
   arr[2] = 2;
   cout << num_of_ways(n);
   return 0;
}

#include <iostream>

using namespace std;

long long arr[61] = {0};

long long num_of_ways(int n) {

if(arr[n]) {

return arr[n];

}

else {

arr[n] = num_of_ways(n-1) + num_of_ways(n-2) + num_of_ways(n-3);

}

return arr[n];

}

int main() {

int n;

cin >> n;

arr[0] = 1;

arr[1] = 1;

arr[2] = 2;

cout << num_of_ways(n);

return 0;

}

Посилання

Related Images:

e-olymp 9066. Кружок стрельбы

03/03/2020 by Владислав Гринькив

Задача

После успешного обучения Атрея стрельбе из лука «Когтя» Фэй решила не останавливаться на достигнутом и открыть целый кружок стрельбы из лука.

На занятие кружка пришли $n$ учеников. Фэй пронумеровала их целыми числами от $1$ до $n$. В начале занятия ученики встали вдоль координатной прямой, заблаговременно нарисованной на полу, причем i-й ученик стоял в точке с координатой $x_i$. Получилось так, что координаты учеников строго возрастали, то есть $x_i \lt x_{i+1}$ для всех $i$ от $1$ до $n-1$.

У каждого из учеников есть свой волшебный лук, который характеризуется своей дальностью $r_i$ и силой $c_i$. Оба параметра — целые положительные числа. Когда ученик совершает выстрел из лука, магический снаряд начинает лететь вдоль координатной прямой в сторону увеличения координаты. Снаряд летит до тех пор, пока его сила положительна. В момент выстрела сила заряда равна силе лука, из которого совершается выстрел. Каждый раз, когда снаряд пролетает очередные $r_i$ единиц расстояния вдоль прямой, он теряет одну единицу силы.

Если ученик произвел выстрел, и снаряд, выпущенный им, достиг следующего по порядку вдоль прямой ученика, снаряд прекращает свой полет, а ученик, которого достиг снаряд, внезапно решает, что ему тоже надо произвести выстрел, и совершает его. Ученик совершит выстрел, даже если снаряд достиг его, имея силу $0$.

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

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

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

Первая строка содержит количество учеников $n$ $(1 \leqslant n \leqslant 1000)$ на кружке Фэй.

Каждая из следуюших $n$ строк содержит три целых числа $x_i$, $r_i$ и $c_i$ ($1 \leqslant x_i \leqslant 10^9$, $1 \leqslant r_i$, $c_i \leqslant 100$) — координату очередного ученика, а также дальность и силу его лука соответственно. Гарантируется, что $x_i \lt x_{i+1}$ для всех $i$ от $1$ до $n-1$.

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

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

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 1 3 3 5 1 2 8 2 3 10 1 2 11 3 2	2
2	6 1 3 5 4 2 2 7 4 3 10 1 2 11 3 2 13 4 3	1

Код

#include <iostream>
using namespace std;
struct archerProfile {
  unsigned long x;
  unsigned long r;
  unsigned int c;
}archer[1000];
int main(){ 
  int n;
  int commands = 1;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> archer[i].x >> archer[i].r >> archer[i].c;
  }
  for (int i = 0; i < n - 1; i++) {
    unsigned long long distanceBetweenArchers = archer[i + 1].x - archer[i].x;
    if (distanceBetweenArchers > archer[i].c * archer[i].r) {
      commands += 1;
    }
  }
  cout << commands;
  return 0;
}

#include <iostream>

using namespace std;

struct archerProfile {

unsigned long x;

unsigned long r;

unsigned int c;

}archer[1000];

int main(){

int n;

int commands = 1;

cin >> n;

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

cin >> archer[i].x >> archer[i].r >> archer[i].c;

}

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

unsigned long long distanceBetweenArchers = archer[i + 1].x - archer[i].x;

if (distanceBetweenArchers > archer[i].c * archer[i].r) {

commands += 1;

}

cout << commands;

return 0;

}

Решение

Для решения задачи, мы должны найти расстояние между лучниками, то есть $x_{i+1}-x_i$, после чего найти максимальное расстояние, которое пролетит стрела у $x_{i}$ лучника умножив силу его лука $c_i$ и расстояние $r_i$, после чего сделать проверку, если расстояние между лучниками больше чем максимальное расстояние которое пролетит стрела, то мы дадим команду совершить ещё один выстрел.

Ссылки

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

Related Images:

e-olymp 1462. Хитрая сортировка

26/02/2020 by Николай Жирко

Задача

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

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

Первая строка содержит число [latex] n [/latex] ([latex] 1 \leqslant n \leqslant 100 [/latex]), а вторая — сами натуральные числа, не превышающие [latex] 32000 [/latex].

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

Выведите последовательность чисел, упорядоченную согласно условию.

Тесты

№	Входные данные	Выходные данные
1	7 12 15 43 13 20 1 15	20 1 12 13 43 15 15
2	10 82 22 19 90 34 17 588 921 200 121	90 200 121 921 22 82 34 17 588 19
3	4 162 9801 37 14	9801 162 14 37

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

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

bool comp (const int& a, const int& b) {
    if (a % 10 == b % 10) return (a < b);
    else return a % 10 < b % 10;
}

int main() {
    int n, a;
    vector<int> array;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a;
        array.push_back(a);
    }
    
    sort (array.begin(), array.end(), comp);
    
    for (int a = 0; a < n; a++) {
        cout << array[a] << " ";
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

bool comp (const int& a, const int& b) {

if (a % 10 == b % 10) return (a < b);

else return a % 10 < b % 10;

}

int main() {

int n, a;

vector<int> array;

cin >> n;

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

cin >> a;

array.push_back(a);

}

sort (array.begin(), array.end(), comp);

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

cout << array[a] << " ";

}

return 0;

}

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

Для решения этой задачи необходимо объявить вектор, который будет хранить все числа, введенные пользователем, например, array.
Сортировку будем проводить с помощью функции sort. Для правильного упорядочивания чисел, напишем функцию компаратор comp, для сравнения чисел и решения, стоит ли их менять местами.
В конце выводим вектор array.

Ссылки

Условие на e-olymp

Решение на e-olymp

Решение на ideone.com

Related Images:

e-olymp 1462. Хитрая сортировка

25/02/2020 by Нина Хоробрых

Задача

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

Первая строка содержит число $n \ (1 \leqslant n \leqslant 1000)$, а вторая — сами натуральные числа, не превышающие $32000$.

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

Выведите последовательность чисел, упорядоченную согласно условию.

Тесты

№	Входные данные	Выходные данные
1	7 12 15 43 13 20 1 15	12 33 14 44 64 77
2	4 345 112 999 29	112 345 29 999
3	9 78 33 13 0 12 89 20 78 9990	0 20 9990 12 13 33 78 78 89

Код

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int mass[n];
    for (int i = 0; i < n; i++) {
        cin >> mass[i];
    }
    
    for (int i = 0; i < n; i++){
        for (int j = 1; j < (n - i);  j++) {
        if (mass[j] % 10 < mass[j-1] % 10) {
                swap (mass[j-1], mass[j]);
        } 
        else if ( mass[j] % 10 == mass[j-1] % 10 and mass[j] < mass[j-1]){
            swap (mass[j-1], mass[j]);
        }
        }
    }

    for (int i = 0; i < n; i++) {
        cout << mass[i] << " ";
    }
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int n;

cin >> n;

int mass[n];

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

cin >> mass[i];

}

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

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

if (mass[j] % 10 < mass[j-1] % 10) {

swap (mass[j-1], mass[j]);

}

else if ( mass[j] % 10 == mass[j-1] % 10 and mass[j] < mass[j-1]){

swap (mass[j-1], mass[j]);

}

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

cout << mass[i] << " ";

}

return 0;

}

Решение

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

Ссылки

Код на ideone
Задача на e-olymp
Засчитанное решение на e-olymp

Related Images:

e-olymp 2663. Сортировка пузырьком

28/01/2020 by Даниил Кадочников

Условие

Определите, сколько обменов сделает алгоритм пузырьковой сортировки по возрастанию для данного массива.

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

В первой строке содержится количество элементов $n$ ($1 \leqslant n \leqslant 1000$) в массиве. Во второй строке — сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю $10$^$9$.

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

Выведите одно число — количество обменов пузырьковой сортировки.

Тесты

№	Ввод	Вывод
1	3 1 3 2	1
2	2 2 1	1
3	4 4 1 5 3	3
4	5 5 4 1 100000 7	4
5	6 6 5 4 3 2 1	15

Решение

Используем простой алгоритм пузырьковой сортировки: проходим по массиву циклом, если два элемента стоят не в том порядке, то меняем их местами. Так как задача состоит в том, чтобы вывести число обменов, при каждом обмене прибавляем к счётчику $1$. При каждом выполнении цикла по j ставится на место хотя бы 1 элемент, поэтому с каждым полным проходом его длина сокращается на $1$.

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

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

int main() {
    cin >> n;
    int arr[n];

    for(int i=0; i<n; i++) cin >> arr[i];
    int counter=0;
    for(int u=0; u<n;u++) {
        for(int j=1; j<(n-u); j++) {
            if((arr[j]<arr[j-1])) {
                
                int prev;
                prev = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = prev;
                counter++;            
            }
        }
    }
    cout << counter;
    return 0;
}

#include <iostream>

using namespace std;

int n;

int main() {

cin >> n;

int arr[n];

for(int i=0; i<n; i++) cin >> arr[i];

int counter=0;

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

for(int j=1; j<(n-u); j++) {

if((arr[j]<arr[j-1])) {

int prev;

prev = arr[j-1];

arr[j-1] = arr[j];

arr[j] = prev;

counter++;

}

cout << counter;

return 0;

}

Ссылки

решение на e-olymp
код на ideone

Related Images:

e-olymp 1704. Умная черепашка

23/01/2020 by Виктория Крачилова

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

Имеется клетчатое поле размером $m\times n$. В левом нижнем углу сидит черепашка. Она умеет ходить только вправо или вверх. Перед тем как добраться до правого верхнего угла её заинтересовал вопрос: сколько существует способов добраться из исходной точки до правого верхнего угла?

Черепашка хотя и умная, но сама считать так много пока не умеет. Помогите черепашке найти ответ на свой вопрос.

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

Два натуральных числа $m$ и $n$, не превышающие 30.

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

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

Тесты

№	Ввод	Вывод
1	4 5	10
2	3 14	105
3	11 17	5311735
4	20 21	68923264410
5	30 30	30067266499541040

Код программы (циклы)

#include <iostream>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    if (m > n) swap(n, m);
    long long den = 1, ways = 1; // den - знаменатель, ways - количество способов.
    for (int i = 0; i < m - 1; i++) {
        ways *= n + i;
        if (ways % den == 0) {
            ways /= den;
            den++;
        }
    }
    cout << ways;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> n >> m;

if (m > n) swap(n, m);

long long den = 1, ways = 1; // den - знаменатель, ways - количество способов.

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

ways *= n + i;

if (ways % den == 0) {

ways /= den;

den++;

}

cout << ways;

return 0;

}

Решение

Для нахождения количества способов, которыми черепашка сможет добраться из левого нижнего угла в правый верхний, мы воспользуемся формулой из комбинаторики: $\frac{\left(n+m-2\right)!}{(n-1)!\times(m-1)!}$. Для того, чтобы избежать больших чисел, делим на наибольший множитель знаменателя (пусть это будет $\left(n-1\right)!$ ). Получаем: $ \frac{n\times(n+1)\times…\times(n+m-2)}{1\times2\times…\times(m-1)}$. Домножаем числитель, пока он не делится на очередной сомножитель знаменателя. Если делится, то делим и переходим к следующему сомножителю знаменателя.

Код программы (динамическое программирование)

#include <iostream>
#define N 30
int main() {
    // Создаем треугольную матрицу для хранения всех ответов
    long *x[N];
    for (int i=0; i < N; ++i) x[i] = new long[i+1];
    // Находим все ответы
    x[0][0] = 1;
    for (int i=1; i < N; ++i) {
        x[i][0] = 1;
        for (int j=1; j < i; ++j) x[i][j] = x[i-1][j] + x[i][j-1];
        x[i][i] = 2 * x[i][i-1];        
    }
    // Проходим все тесты
    int m, n; 
    std::cin >> m >> n;
    std::cout << x[std::max(n,m)-1][std::min(n,m)-1];
}

#include <iostream>

#define N 30

int main() {

// Создаем треугольную матрицу для хранения всех ответов

long *x[N];

for (int i=0; i < N; ++i) x[i] = new long[i+1];

// Находим все ответы

x[0][0] = 1;

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

x[i][0] = 1;

for (int j=1; j < i; ++j) x[i][j] = x[i-1][j] + x[i][j-1];

x[i][i] = 2 * x[i][i-1];

}

// Проходим все тесты

int m, n;

std::cin >> m >> n;

std::cout << x[std::max(n,m)-1][std::min(n,m)-1];

}

Решение

Заполним треугольную матрицу ответами для всех возможных значений $m$ и $n$ . Логика заполнения такая — если поле выглядит как полоска клеток, черепахе идти можно будет только вправо. Значит в первой строке (как и в столбце) будут все элементы равные 1. Поскольку в каждой клетке есть два варианта движения (вправо или вверх), остальные элементы будут заполняться как сумма ранее найденных значений для клеток справа текущей и над ней. Для диагональных элементов оба соседних расположены симметрично (то есть они равны), поэтому диагональный элемент будет равен удвоенному соседу справа. Решение намного быстрее, если нужно пройти много тестов, но тратит память на запоминание всех ответов.

Ссылки (циклы)

Ссылки (динамическое программирование)

Related Images:

e-olymp 8963. Наименьшие влево

19/01/2020 by Даниил Кадочников

Условие

Задан массив из [latex]n[/latex] целых чисел. Переместить все минимальные элементы в начало массива, не меняя порядок других.

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

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

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

Выведите элементы обновленного массива.

Тесты

№	Ввод	Вывод
1	7 6 -3 -7 4 -7 -4 5	-7 -7 6 -3 4 -4 5
2	2 100 -100	-100 100
3	6 -2 -2 7 3 99 -2	-2 -2 -2 7 3 99
4	5 1 1 1 1 1	1 1 1 1 1

Решение

Вместо обычных массивов будем использовать векторы, чтобы было удобнее добавлять элементы в конец. Минимальный элемент можно найти с помощью простого цикла: если какой-либо элемент вектора меньше min, то min присваивается значение этого элемента, и так пока не найдено наименьшее число. Подсчитаем, сколько раз оно встречается в векторе. Столько же раз его нужно добавить в новый вектор. Наконец, переносим в v2 все оставшиеся элементы, не равные min.

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

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

int main()
{
    int n;
    cin >> n;
    vector <int> v, v2;
    int x;
    while(cin>>x) v.push_back(x);
    int min = v[0];
    for(int q=1; q<n; q++) {
        if(v[q]<min) min = v[q];
    }

    int min_counter = 0;
    for(int w=0; w<n; w++) {
        if(v[w] == min) min_counter++;
    }

    for(int e=0; e<min_counter; e++) v2.push_back(min);
    for(int r=0; r<n; r++) {
        if(v[r]!=min) v2.push_back(v[r]);
    }
    for(int t=0; t<n; t++) cout << v2[t] << " ";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

int n;

cin >> n;

vector <int> v, v2;

int x;

while(cin>>x) v.push_back(x);

int min = v[0];

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

if(v[q]<min) min = v[q];

}

int min_counter = 0;

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

if(v[w] == min) min_counter++;

}

for(int e=0; e<min_counter; e++) v2.push_back(min);

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

if(v[r]!=min) v2.push_back(v[r]);

}

for(int t=0; t<n; t++) cout << v2[t] << " ";

return 0;

}

Ссылки

решение на E-olymp
код на ideone

Related Images:

e-olymp 123. Количество нулей у факториала

18/01/2020 by Владислав Гринькив

Задача

Найти количество нулей в конце записи факториала числа $n$.

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

Одно число $n$ $(1 \leqslant n \leqslant2\cdot10^9)$

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

Количество нулей в конце записи $n!$

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1	0
2	7	1
3	12	2
4	100	24
5	306	75
6	5000	1249

Код

#include <iostream> 
using namespace std;
int main() { 
    long long n, m = 5, s = 0; 
    cin >> n; 
    while(n >= m){
        s = s + (n / m); 
        m = m * 5;
    }
    cout << s;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long n, m = 5, s = 0;

cin >> n;

while(n >= m){

s = s + (n / m);

m = m * 5;

}

cout << s;

return 0;

}

Решение

Каждый нуль в конце искомого числа возникает от произведения чисел 2 и 5 — других вариантов нет. Очевидно, множителей 5 будет меньше множителей 2. Значит, количество нулей определяется исключительно количеством множителей-пятерок. Один такой множитель содержат числа 5, 10, 15, 20, 25, …, $n$ — всего их насчитывается $\frac{n}{5}$. Два множителя содержат числа 25, 50, …, $n$ всего их $\frac{n}{5^2}$.Три множителя содержат $\frac{n}{5^3}$.Складывая количество множителей с учетом их повторения, найдем общее их количество:

$\lfloor\frac{n}{5}\rfloor+\lfloor\frac{n}{5^2}\rfloor+\lfloor\frac{n}{5^3}\rfloor+\ldots+\lfloor\frac{n}{5^k}\rfloor$

Суммирование происходит до тех пор, пока очередное слагаемое не станет равным 0.

Ссылки

Формула разложения на простые множители

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

Код на Ideone

Засчитанное решение на e-olymp

Related Images:

e-olimp 7848. Переставить соседние

14/01/2020 by Елизавета Савицкая

Задача

Задан массив из $n$ целых чисел. Переставьте соседние элементы массива ($a_{0}$ с $a_{1}$, $a_{2}$ с $a_{3}$ и так далее). Если элементов нечетное количество, то последний элемент следует оставить на своем месте.

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

В первой строке записано число $n$. В следующей строке записано $n$ целых чисел. Все числа по модулю не превышают $100$.

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

Вывести обновленный массив.

Тесты

Входные данные	Выходные данные
7 3 5 -7 7 5 -9 -4	5 3 7 -7 -9 5 -4
8 -9 81 27 -38 2 6 -56 -21	81 -9 -38 27 6 2 -21 -56
2 25 -76	-76 25
3 55 44 33	44 55 33
1 99	99

Код

#include <iostream>
using namespace std;

int main() {
   int n;
   cin >> n;
   int arr[n];
   for(int i = 0; i < n; i++){
      cin >> arr[i];
   } 
   for(int i = 1; i < n; i+=2){
      int q = arr[i];
      arr[i] = arr[i-1];
      arr[i-1] = q;
   }
   for(int i = 0; i < n; i++){
      cout << arr[i] << " ";
   }
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int arr[n];

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

cin >> arr[i];

}

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

int q = arr[i];

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

arr[i-1] = q;

}

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

cout << arr[i] << " ";

}

return 0;

}

Решение

Будем переставлять соседние элементы массива следующим образом: arr[1] с arr[0], arr[3] с arr[2] и так далее до конца массива (т.е. каждый нечетный по счету элемент меняем местами с предыдущим). При этом совершенно неважно, четное кол-во элементов или нечетное.

Ссылки

Условие задачи на E-Olymp
Код задачи на Ideone

Related Images:

e-olymp 8916. Первые парные

14/01/2020 by Николай Жирко

Первые парные

Программа должна ввести с консоли натуральное число [latex] n [/latex] и вывести в порядке возрастания [latex] n [/latex] первых четных натуральных чисел.

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

Натуральное число [latex] n [/latex].

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

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

Тесты

№	Входные данные	Выходные данные
1	3	2 4 6
2	8	2 4 6 8 10 12 14 16
3	5	2 4 6 8 10

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

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    for (int i = 1; i < n + 1; i++) { 
        cout << i * 2 << " "; 
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

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

cout << i * 2 << " ";

}

return 0;

}

Решение

Решением этой задачи является вывод через пробел удвоенных чисел от 1 до [latex] n [/latex].

Ссылки

Условие на e-olymp
Решение на e-olymp
Решение на ideone.com

Related Images:

e-olymp 7847. Кількість різних елементів

12/01/2020 by Андрей Мартынюк

Задача

Дано масив з [latex]N[/latex] цілих чисел. Визначте, скільки в цьому масиві різних елементів.

Вхідні дані

В першому рядку записано число [latex]N[/latex]. В наступному рядку записано [latex]N[/latex] цілих чисел. Всі числа за модулем не перевищують [latex]100[/latex].

Вихідні дані

Кількість різних елементів в масиві.

Тести

№	Вхідні дані	Вихідні дані
1.	7 3 5 -7 7 5 -9 -4	6
2.	5 1 25 59 75 100	5
3.	6 1 2 3 1 2 4	4

Код 1

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int* a = new int[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int diffNum = 0;
    for (int i = 0; i < n; i++)
    {
        bool newNum = true;
        for (int j = 0; j < i; j++)
        {
            if (a[j] == a[i])
            {
                newNum = false;
                break;
            }
        }
        if (newNum == true)
        {
            diffNum++;
        }
    }
    cout << diffNum;
    
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

int* a = new int[n];

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

{

cin >> a[i];

}

int diffNum = 0;

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

{

bool newNum = true;

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

{

if (a[j] == a[i])

{

newNum = false;

break;

}

if (newNum == true)

{

diffNum++;

}

cout << diffNum;

return 0;

}

Код 1(without break)

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int* a = new int[n];
    for (int i = 0; i < n; i++) { cin >> a[i];
    }
    int diffNum = 0;
    for (int i = 0; i < n; i++)
    {
        bool newNum = true;
        for (int j = 0; j < i && a[i-1] != a[j]; j++)
        {
            if (a[j] == a[i])
            {
                newNum = false;
            }
        }
        if (newNum == true)
        {
            diffNum++;
        }
    }
    cout << diffNum;
    
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

int* a = new int[n];

for (int i = 0; i < n; i++) { cin >> a[i];

}

int diffNum = 0;

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

{

bool newNum = true;

for (int j = 0; j < i && a[i-1] != a[j]; j++)

{

if (a[j] == a[i])

{

newNum = false;

}

if (newNum == true)

{

diffNum++;

}

cout << diffNum;

return 0;

}

Решение

Ставим отметку числу как будто видим его впервые.
Далее задача пройти по всем предыдущим числам и проверить не встретится ли такое же число.
Если встретится, то отметку снимаем, а пройдя по всем предыдущим числам так и не встретив числа равного текущему, значит «видим его впервые» и отметка поставлена справедливо.
Считаем количество отметок.

Ссылки

Код 2

#include <iostream>
using namespace std;
#include 
int main() {
    vector a(202, false);
    int n, diffNum, curVal;
    cin >> n;
    diffNum = n;
    for(int i = 0; i < n; i++)
    {
        cin >> curVal;
        if(a[curVal + 100]) 
        {
            diffNum--;
        }
        else 
        {
            a[curVal + 100] = true;
        }
    }
    cout << diffNum << endl;
    return 0;
}

#include <iostream>

using namespace std;

#include

int main() {

vector a(202, false);

int n, diffNum, curVal;

cin >> n;

diffNum = n;

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

{

cin >> curVal;

if(a[curVal + 100])

{

diffNum--;

}

else

{

a[curVal + 100] = true;

}

cout << diffNum << endl;

return 0;

}

Решение

Сначала, предположим, что все числа разные. Т.е. количество различных чисел равно [latex]n.[/latex] Далее в цикле for отметим читаем числа из потока и отмечаем в векторе vector<bool> a, что число встретилось. Встретив число ранее уже отмеченное уменьшаем счетчик различных чисел.

Ссылки

Related Images:

e-olymp 8663. Задача про множення

09/01/2020 by Эвелина Алексютенко

Задача

На уроці математики Байтик навчився множити, і почав застосовувати цю операцію з різними числами. Наприклад, розкладав число на цифри і знаходив добуток цифр. І тут він задумався, який найбільший добуток цифр серед натуральних чисел, що не перевищує [latex]N[/latex]. Допоможіть розв’язати задачу.

Вхідні дані

Одне число [latex]N(1\leqslant N\leqslant 2\times 10^{9})[/latex].

Вихідні дані

Максимальний добуток цифр серед чисел, що не перевищують [latex]N[/latex].

Тести

Вхідні дані	Вихідні дані
57	36
1000	729
7999	5103
28994	10368
4876	2268

Код програми

#include <iostream>
using namespace std;

int multiplication(int x) {
    int mul = 1;
    while(x != 0) {
        mul *= x % 10;
        x /= 10;
    }
    return mul;
}
int main() {
  int n;
  cin >> n;
  int maxmul = multiplication(n);  
  int copy = n;
  int i = 10;
  while(n != 0) {
      int temporary_number = (copy / (i / 10)) % 10;
      int left = copy / i;
      int right = copy % (i / 10);
      if(temporary_number != 9) {
        temporary_number = 9;
        copy = ((left - 1) * 10 + temporary_number) * (i / 10) + right;
      }
      n /= 10;
      i *= 10;
      int mul = multiplication(copy);
      if(maxmul < mul) maxmul = mul;
    }  
    cout << maxmul; 
}

#include <iostream>

using namespace std;

int multiplication(int x) {

int mul = 1;

while(x != 0) {

mul *= x % 10;

x /= 10;

}

return mul;

}

int main() {

int n;

cin >> n;

int maxmul = multiplication(n);

int copy = n;

int i = 10;

while(n != 0) {

int temporary_number = (copy / (i / 10)) % 10;

int left = copy / i;

int right = copy % (i / 10);

if(temporary_number != 9) {

temporary_number = 9;

copy = ((left - 1) * 10 + temporary_number) * (i / 10) + right;

}

n /= 10;

i *= 10;

int mul = multiplication(copy);

if(maxmul < mul) maxmul = mul;

}

cout << maxmul;

}

Алгоритм

Складність задачі полягає в обмеженості у часі.

Знайдемо добуток цифр заданого числа.
Змінемо останню цифру на [latex]9[/latex] та віднімемо [latex]1[/latex] від попереднього розряду. Визначаємо поточний добуток цифр отриманого числа. Повторюємо цю операцію з наступними розрядами числа.
Порівнюємо поточний добуток з максимальним.

Приклад:

Приклад розкладу числа на різних етапах алгоритму:

Посилання

Задача на e-olymp
Зарахований розв’язок
Код на ideone

Related Images:

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

04/01/2020 by Владислав Гринькив

Задача

Вычислить значение $a^b$.

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

Два натуральных числа $a$ и $b$.

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

Выведите значение $a^b$, если известно что оно не превосходит $10^{18}$.

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1 100	1
2	2 10	1024
3	3 7	2187
4	8 9	134217728
5	10 10	10000000000
6	100 9	1000000000000000000

Код

#include <iostream>
using namespace std;

long pow(long a, long b) {
  if(b == 0){
    return 1;
  }
  if(b % 2 == 0){
    return pow(a * a, b / 2);
  }
  return a * pow(a, b - 1);
}

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

#include <iostream>

using namespace std;

long pow(long a, long b) {

if(b == 0){

return 1;

}

if(b % 2 == 0){

return pow(a * a, b / 2);

}

return a * pow(a, b - 1);

}

int main() {

long a, b;

cin >> a >> b;

cout << pow(a,b);

return 0;

}

Решение

Для решения задачи создадим функцию «pow()», заметим, что для любого числа $a$ и чётного числа $b$ выполнимо очевидное тождество (следующее из ассоциативности операции умножения):
$$a^b = \left(a^2\right)^{\frac{b}{2}}= \left(a\cdot a\right)^{\frac{b}{2}}$$
Оно и является основным в методе бинарного возведения в степень. Действительно, для чётного $b$ мы показали, как, потратив всего одну операцию умножения, можно свести задачу к вдвое меньшей степени.
Осталось понять, что делать, если степень b нечётна. Здесь мы поступаем очень просто: перейдём к степени b-1, которая будет уже чётной:
$$a^b = a^{b-1} \cdot a$$
Итак, мы фактически нашли рекуррентную формулу: от степени $b$ мы переходим, если она чётна, к $\frac{b}{2}$, а иначе — к $b-1$.

Примечание

Задача требует использование быстрого алгоритма, так как прямое умножение $b$ раз для возведение в $b$-ю слишком медленно, из-за большого количества перемножений. Алгоритм быстрого возведения в степень — это предназначенный для возведения числа в натуральную степень за меньшее число умножений, чем это требуется в определении степени.

Ссылки

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

Related Images:

e-olymp 8674. Игра

02/01/2020 by Александр Рапчинский

Задача

Мурад и Ибрагим играют в следующую игру. Изначально дается число $1$. На своем ходу каждый игрок должен умножить текущее число на одно из целых чисел от $2$ до $9$ включительно. Цель состоит в том, чтобы получить число не меньше заданного целого числа $n$. Игрок, получивший такой номер первым, объявляется победителем. Мурад всегда начинает первым. Выясните, кто победит, если Мурад и Ибрагим будут играть оптимально.

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

Первая строка содержит одно число $t$ $(1 \leqslant t \leqslant 2500)$ — количество тестов. Каждая из следующих $t$ строк содержит одно целое число $n$ $(2 \leqslant n \leqslant 10^9)$.

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

Для каждого теста выведите в отдельной строке $1$, если Мурад выиграет игру, и $2$ иначе.

Тесты

№	Входные данные	Выходные данные
1	4 9 10 1149729 999999999	1 2 2 1
2	3 6 163 1234567	1 2 2
3	3 42 100 1000	1 1 1

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

Решение с циклом для каждого отдельного теста:

#include <iostream>
using namespace std;
 
int main() {
    int k;
    double n;
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> n;
        bool p = true;
        while (n > 1) {
            n /= (p ? 9 : 2);
            p = !p;
        }
        cout << p + 1 << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int k;

double n;

cin >> k;

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

cin >> n;

bool p = true;

while (n > 1) {

n /= (p ? 9 : 2);

p = !p;

}

cout << p + 1 << "\n";

}

return 0;

}

Решение без цикла для каждого отдельного теста:

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

int main() {
    int t, n;
    cin >> t;
    int x = 0;
    for (int i = 0; i < t; i++) {
        cin >> n;
        double l = n / pow(18, ceil(log(n) / log(18)));
        cout << ((2 * l <= 1) ? 1 : 2) << "\n";
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int t, n;

cin >> t;

int x = 0;

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

cin >> n;

double l = n / pow(18, ceil(log(n) / log(18)));

cout << ((2 * l <= 1) ? 1 : 2) << "\n";

}

return 0;

}

Решение

Для начала заметим, что победит тот игрок, чей ход выпадет на число из промежутка $[\frac{n}{9},n)$, так как любое число из этого промежутка можно умножить на соответствующее целое число из $[2,9]$ и получить число не меньшее чем $n$. Назовем такой промежуток «зеленой зоной» (в общем виде будет $[\frac{2n}{18^k},\frac{n}{18^{k-1}})$, $k \in \mathbb {N}$). Тогда очевидно, что проиграет тот игрок, чей ход выпадает на число из промежутка $[\frac{n}{18},\frac{n}{9})$, так как при умножении числа из этого промежутка на любое целое число из $[2,9]$, приводит к тому, что получается число из «зеленой зоны». Назовем такой промежуток «красной зоной» (в общем виде будет $[\frac{n}{18^k},\frac{2n}{18^k})$, $k \in \mathbb {N}$). Получаем, что промежуток $(0,n)$ делится на «красные» и «зеленые зоны». Тогда задача сводится к нахождению вида «зоны» в которой находится $1$.

Используя в реализации цикл для каждого отдельного теста, получить результат достаточно несложно. Однако, для заданного $n$ можно получить исход игры используя лишь линейные вычисления.

Рассмотрим цепочку неравенств (учитывая, что $2 \leqslant n$ ): $$\lfloor \log _{18} n \rfloor \leqslant \log _{18} n \leqslant \lceil \log _{18} n \rceil$$

$$ 18^{\lfloor \log _{18} n \rfloor} \leqslant n \leqslant 18^{\lceil \log _{18} n \rceil}$$

$$\frac{1}{18^{\lceil \log _{18} n \rceil}} \leqslant \frac{1}{n} \leqslant \frac{1}{18^{\lfloor \log _{18} n \rfloor}}$$

$$\frac{n}{18^{\lceil \log _{18} n \rceil}} \leqslant 1 \leqslant \frac{n}{18^{\lfloor \log _{18} n \rfloor}}$$

Из общего вида «красной зоны» видно, что левый ее конец это число вида $\frac{n}{18^k}$, значит $\frac{n}{18^{\lceil \log _{18} n \rceil}}$ является левым концом «красной зоны», обозначим его как $l$. Тогда, $2l$ будет правым концом «красной зоны» исходя из её общего вида. Из полученного неравенства видно, что $1$ лежит между левыми концами соседних «красных зон». Получаем, что если $2l \leqslant 1$, то единица лежит в «зеленой зоне», а иначе — в «красной».

Ссылки

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

Решение с циклом для каждого отдельного теста на ideone

Решение без цикла для каждого отдельного теста на ideone

Related Images:

e-olymp 2098. Переворачиватель

30/12/2019 by Даниил Кадочников

Условие

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

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

Сначала задано число [latex]n[/latex] ([latex]0 \lt n \lt 100[/latex]), за ним идут [latex]n[/latex] целых чисел.

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

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

Тесты

№	Ввод	Вывод
1	7 2 4 1 3 5 3 1	1 3 5 3 1 4 2
2	1 5	5
3	10 1 1 1 9999 5 -1 7 3 0 9	9 0 3 7 -1 5 9999 1 1 1

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

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int arr[n];
    for(int i=0; i<n; i++) cin >> arr[i];
    for(int u=n-1; u>-1; u--) cout << arr[u] << " ";
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int arr[n];

for(int i=0; i<n; i++) cin >> arr[i];

for(int u=n-1; u>-1; u--) cout << arr[u] << " ";

return 0;

}

Решение

Введём переменную [latex]n[/latex], затем создадим массив из [latex]n[/latex] элементов. С помощью цикла for от [latex]0[/latex] до [latex]n[/latex] запишем в него числа. Теперь с помощью другого цикла от [latex]n-1[/latex] до [latex]-1[/latex] выводим их в обратном порядке.