KM210. Классы эквивалентности некоторой последовательности

14/10/2016 by Иванна Ялымова

Задача
Задача из журнала «Квант» №3, 1974 год (Задача составлена на основе задачи Гуревича)

Рассмотрим последовательности, состоящие из [latex]n[/latex] цифр 1 и 2. В такой последовательности разрешено поменять местами любые две соседние тройки цифр. Две последовательности называем эквивалентными, если одну из них можно перевести в другую несколькими такими перестановками. Сколько существует классов эквивалентности?

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

[latex]n[/latex] — целове число, [latex]k[/latex] — целое число ([latex]k \neq 0[/latex], [latex]k \leq n[/latex]).

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

[latex]m[/latex] — целое число, неполное частное от деления, [latex]q[/latex] — целое число, остаток от деления, [latex]N[/latex] — классы эквивалентности.

Тесты

[latex]n[/latex]	[latex]k[/latex]	[latex]m[/latex]	[latex]q[/latex]	[latex]N[/latex]
4	3	1	1	12
8	4	2	0	81

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

Код программы на С++

#include <iostream>
using namespace std;
long pow (long x, int n) {
    return (n == 0) ? 1 :
    (n % 2 == 0) ? pow(x*x, n/2) :
    pow(x, n-1)*x;
}
int main() {
    int n, m, k, q, N;
    cin >> n >> k;
    m=n/k;
    q=n%k;
    N=pow((m+1),k-q)*pow((m+2),q);
    cout << m << " " << q << " " << N << endl;
    return 0;
}

#include <iostream>

using namespace std;

long pow (long x, int n) {

return (n == 0) ? 1 :

(n % 2 == 0) ? pow(x*x, n/2) :

pow(x, n-1)*x;

}

int main() {

int n, m, k, q, N;

cin >> n >> k;

m=n/k;

q=n%k;

N=pow((m+1),k-q)*pow((m+2),q);

cout << m << " " << q << " " << N << endl;

return 0;

}

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

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

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int n, k, q, m;
        double N;
        Scanner in = new Scanner(System.in);
            
        n = in.nextInt();
        k = in.nextInt();
        
        m = n/k;
        q = n%k;
        N = Math.pow((m+1),k-q) * Math.pow((m+2),q);
        
        System.out.println(q + " " + m + " " + N);
    }
    public static long pow(long x, int n) {
        return (n == 0) ? 1 :
        (n % 2 == 0) ? pow(x*x, n/2) :
        pow(x, n-1)*x;
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

int n, k, q, m;

double N;

Scanner in = new Scanner(System.in);

n = in.nextInt();

k = in.nextInt();

m = n/k;

q = n%k;

N = Math.pow((m+1),k-q) * Math.pow((m+2),q);

System.out.println(q + " " + m + " " + N);

}

public static long pow(long x, int n) {

return (n == 0) ? 1 :

(n % 2 == 0) ? pow(x*x, n/2) :

pow(x, n-1)*x;

}

Решение

Решим задачу для последовательностей из [latex]3n[/latex] цифр. Чтобы не возникло путаницы, греческими буквами будем обозначать последовательности, а латинскими – элементы последовательностей. Пусть последовательность [latex]\alpha[/latex] состоит из [latex]3n[/latex] цифр [latex]{\alpha_1, \alpha_2,\ldots,\alpha_{3n}}[/latex]. Разобъем [latex]\alpha[/latex] на три подпоследовательности:
[latex]\alpha_1={\alpha_1,\alpha_4,\alpha_7,\ldots, \alpha_{3k+1},\ldots,\alpha_{3(n-1)+1}}[/latex],
[latex]\alpha_2={\alpha_2, \alpha_5, \alpha_8,\ldots, \alpha_{3k+2},\ldots,\alpha_{3(n-1)+2}}[/latex],
[latex]\alpha_3={\alpha_3, \alpha_6, \alpha_9,\ldots, \alpha_{3k},\ldots,\alpha_{3n}}[/latex].
Такое разбиение будем называть стандартным. Каждая из последовательностей [latex]\alpha_1[/latex], [latex]\alpha_2[/latex], [latex]\alpha_3[/latex] стандартного разбиения состоит из [latex]n[/latex] цифр. Пусть [latex]\beta[/latex] – произвольная последовательностей. Через [latex]|\beta|[/latex] обозначим число единиц в последовательности [latex]\beta[/latex]. Подсчет числа неэквивалентных последовательностей основывается на следующей теореме:
Теорема. Пусть [latex]\alpha[/latex] и [latex]\beta[/latex] – последовательности длины [latex]3n[/latex], ([latex]\alpha_1,\alpha_2,\alpha_3[/latex]) и ([latex]\beta_1,\beta_2,\beta_3[/latex]) – их стандартные разбиения. Для того чтобы последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] были эквивалентны, необходимо и достаточно, чтобы подпоследовательности [latex]\alpha_1[/latex] и [latex]\beta_1[/latex], [latex]\alpha_2[/latex] и [latex]\beta_2[/latex], [latex]\alpha_3[/latex] и [latex]\beta_3[/latex] содержали одинаковое число единиц соответственно, то есть чтобы выполнялось условие
[latex]|\alpha_1|=|\beta_1|[/latex], [latex]|\alpha_2|=|\beta_2|[/latex], [latex]|\alpha_3|=|\beta_3|[/latex].
Покажем сначала, как на основе этой теоремы подсчитывается число неэквивалентных последовательностей, а затем докажем теорему. В силу теоремы каждый класс эквивалентных последовательностей однозначно определяются упорядоченной тройкой чисел ([latex]|\alpha_1|, |\alpha_2|, |\alpha_3|[/latex]). Эти числа смогут принимать любые значения от 0 до [latex]n[/latex]. Следовательно, число неэквивалентных последовательностей длины [latex]3n[/latex] равно числу различных упорядоченных троек целых чисел от 0 до [latex]n[/latex]. Нетрудно видеть, что число таких троек равно [latex] \left(n+1\right)^{3} [/latex].
Доказательство теоремы. Необходимость. Пусть мы переставили в последовательности [latex]\alpha={\alpha_1, \alpha_2,\ldots,\alpha_{3n}}[/latex] две соседние тройки цифр: [latex]a_k, a_{k+1}, a_{k+2}[/latex] и [latex]a_{k+3}, a_{k+4}, a_{k+5}[/latex]. Эту перестановку можно представить следующим образом: сначала поменяли местами цифры [latex]a_k[/latex] и [latex]a_{k+3}[/latex], затем поменяли местами цифры [latex]a_{k+1}[/latex] и [latex]a_{k+4}[/latex] и, наконец, поменяли местами цифры [latex]a_{k+2}[/latex] и [latex]a_{k+5}[/latex]. Число [latex]a_k[/latex] и [latex]a_{k+3}[/latex] – соседние цифры одной и той же подпоследовательности стандартного разбиения [latex]\alpha[/latex]; числа [latex]a_{k+1}[/latex] и [latex]a_{k+4}[/latex] – другой, а числа [latex]a_{k+2}[/latex] и [latex]a_{k+5}[/latex] – третьей. Таким образом, в каждой из подпоследоваетльностей [latex]\alpha_1, \alpha_2, \alpha_3[/latex] стандартного разбиения [latex]\alpha[/latex] мы пeреставили два соседних члена. Значит, если последовательность [latex]\beta[/latex] получена из последовательности [latex]\alpha[/latex] конечным числом перестановок, то есть, если последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] эквивалентны, то подпоследовательности [latex]\beta_1, \beta_2, \beta_3[/latex] стандартного разбиения [latex]\beta[/latex] суть некоторые перестановки подпоследовательностей [latex]\alpha_1, \alpha_2, \alpha_3[/latex] соответственно. Отсюда вытекают равенства (1).
Достаточность. Нам надо доказать, что если последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] длины [latex]3n[/latex] удовлетворяют условию (1), то эти последовательности эквиваленты. Удобнее доказывать более общее утверждение: если последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] длины [latex]k[/latex] удовлетворяют условию (1), то эти последовательности эквивалентны. Доказательство будем вести индукцией по [latex]k[/latex].
1) При [latex]k=1[/latex] последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] содержит по одной цифре. Из условия (1) следует, что эти цифры равны, то есть что последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] просто совпадают.
2) Предположим, что в случае, когда [latex]k=p[/latex], утверждение уже доказано. Докажем его при [latex]k=p+1[/latex]. Итак, пусть [latex]\alpha[/latex] и [latex]\beta[/latex] – последовательности длины [latex]p+1[/latex] и пусть выполнено соотношение (1). Пусть далее, последовательность [latex]\alpha[/latex] состоит из цифр [latex]{\alpha_1, \alpha_2,\ldots,\alpha_{p+1}}[/latex], а последовательность [latex]\beta[/latex] — из цифр [latex]{\beta_1, \beta_2,\ldots,\beta_{p+1}}[/latex].
а) если [latex]\alpha_1 = \beta_1[/latex], то рассмотрим последовательности [latex]\alpha\prime={\alpha_2,\alpha_3,\ldots,\alpha_{p+1}}[/latex] и [latex]\beta\prime={\beta_2,\beta_3,\ldots,\beta_{p+1}}[/latex]. Ясно, что последовательности [latex]\alpha\prime[/latex] и [latex]\beta\prime[/latex] удовлетворяют условия (1). А так как длины этих последовательностей равны [latex]p[/latex], то можно воспользоваться индуктивным предположением. Таким образом, последовательности [latex]\alpha\prime[/latex] и [latex]\beta\prime[/latex] эквивалентны, то есть последовательность [latex]\alpha\prime[/latex] несколькими перестановками можно перевести в последовательность [latex]\beta\prime[/latex]. Эти же перестановки переводят [latex]\alpha[/latex] и [latex]\beta[/latex]. Значит, последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] эквивалентны.
б) Пусть [latex]a_1\neq b_1[/latex], и пусть для определенности [latex]a_1=1[/latex], а [latex]b_1=2[/latex]. Так как [latex]a_1=1[/latex], то [latex]|\alpha|>0[/latex]. Тогда в силу (1) и [latex]|\beta|>0[/latex]. Следовательно, найдется число [latex]q[/latex] такое, что [latex]b_{3q+1} = 1[/latex]. В последовательности [latex]\beta[/latex] поменяем местами соседние тройки цифр [latex]b_{3(q-1)+1}, b_{3q+2}, b_{3q+3}[/latex] и [latex]b_{3(q-1)+1}, b_{3(q-1)+2}, b_{3(q-1)+3}[/latex]. В результате этой перестановки тройка [latex]b_{3(q-1)+1}, b_{3q+2}, b_{3q+3}[/latex] сдвигается на 3 цифры влево. Затем поменяем местами эту тройку с рядом стоящей тройкой цифр [latex]b_{3(q-2)+1}, b_{3(q-2)+2}, b_{3(q-2)+3}[/latex] и так далее; после [latex]q[/latex] перестановок получим последовательность [latex]\beta\prime\prime[/latex], первой цифрой которой будет [latex]b_{3q+1}[/latex], то есть 1. Последовательность [latex]\beta[/latex] и [latex]\beta\prime\prime[/latex] эквивалентны и поэтому, как было доказано выше, удовлетворяют условию (1). Значит, последовательности [latex]\alpha[/latex] и [latex]\beta\prime\prime[/latex] удовлетворяют условию (1). Но первые элементы этих последовательностей совпадают. Таким образом, случай б) свелся к уже разобранному случаю а). Теорема доказана.
Следовательно, если [latex]n=mk+q[/latex], где [latex]0<=q<k[/latex], то число классов эквивалентных последовательностей равно [latex] \left(m+1\right)^{k-q}\left(k+1\right)^{q} [/latex].

Ссылки

Условие задачи (стр.40-41)
Решение задачи на сайте Ideone.com (C++)
Решение задачи на сайте Ideone.com (Java)

Related Images:

Вывод чисел в обратном порядке

07/10/2016 by Вадим Гордийчук

Задача

Вводятся некоторые числа вещественного типа. Вывести их в обратном порядке.

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

Некие числа вещественного типа.

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

Введённые числа в обратном порядке.

Тесты

Входные данные	Выходные данные	Входные данные	Выходные данные	Входные данные	Выходные данные
2 4 1	1 4 2	4 9 -6	-6 9 4	0.568 0.925 -0.056	-0.056 0.925 0.568

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

#include <iostream>
using namespace std;

void reverse()
{
    double x;
    if (cin >> x)
    {
        reverse();
        cout << x << "\n";
    }
}

int main()
{
    reverse();
    return 0;
}

#include <iostream>

using namespace std;

void reverse()

{

double x;

if (cin >> x)

{

reverse();

cout << x << "\n";

}

int main()

{

reverse();

return 0;

}

Идея программы

Основная суть программы заключается в использовании рекурсивной функции. Главная функция main обращается к функции reverse, которая будет считывать поток чисел. Если поток чисел продолжается, то функция будет заново обращаться сама к себе и считывать следующие числа. Когда поток закончится, функция прекратит считывать данные, после чего начнётся вывод.

Принцип работы рекурсивной функции reverse:

Решение задачи №1001 на acm.timus.ru, основанное на этом принципе

#include <iostream>
#include <cstdio>
#include <cmath>

void reverse()
{
    double x;
    if (scanf("%lf", &x) > 0)
    {
        reverse();
        printf("%.4f\n", sqrt(x));
    }
}

int main()
{
    reverse();
    return 0;
}

#include <iostream>

#include <cstdio>

#include <cmath>

void reverse()

{

double x;

if (scanf("%lf", &x) > 0)

{

reverse();

printf("%.4f\n", sqrt(x));

}

int main()

{

reverse();

return 0;

}

Ссылки

Related Images:

KM208(a). Наибольшая разность чисел последовательности

05/10/2016 by Вадим Гордийчук

Задача

Известно, что разность между наибольшим и наименьшим из вещественных чисел [latex]x_1[/latex], [latex]x_2[/latex], [latex]x_3[/latex], [latex]\ldots[/latex], [latex]x_{10}[/latex] равна [latex]1[/latex]. Какой наибольшей может быть разность между наибольшим и наименьшим из [latex]10[/latex] чисел [latex]x_1[/latex], [latex]\frac {x_1+x_2} {2}[/latex], [latex]\frac {x_1+x_2+x_3} {3}[/latex], [latex]\ldots[/latex], [latex]\frac {x_1+x_2+x_3+\ldots+x_{10}}{10}[/latex]?

Каков будет ответ, если чисел не [latex]10[/latex], а [latex]n[/latex]?

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

Количество элементов последовательности [latex]x_1[/latex], [latex]x_2[/latex], [latex]x_3[/latex], [latex]\ldots[/latex], [latex]x_n[/latex].

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

Наибольшая разность наибольшего и наименьшего элементов последовательности [latex]x_1[/latex], [latex]\frac {x_1+x_2} {2}[/latex], [latex]\frac {x_1+x_2+x_3} {3}[/latex], [latex]\ldots[/latex], [latex]\frac {x_1+x_2+x_3+\ldots+x_n} {n}[/latex].

Тесты

Входные данные	Выходные данные
2	0.5
4	0.75
6	0.833333
8	0.875

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

#include <iostream>
using namespace std;

int main()
{
    int amount_of_elements; double biggest_difference;
    cin >> amount_of_elements;
    biggest_difference = 1 - 1.0/amount_of_elements;
    cout << biggest_difference;
}

#include <iostream>

using namespace std;

int main()

{

int amount_of_elements; double biggest_difference;

cin >> amount_of_elements;

biggest_difference = 1 - 1.0/amount_of_elements;

cout << biggest_difference;

}

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

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

Обозначим через [latex]y_k[/latex] число [latex]\frac{x_1+x_2+ \ldots+x_k}{k}[/latex], где [latex]k=1, 2, 3, \ldots, n[/latex]. Если прибавить ко всем [latex]x_i[/latex] некоторое число [latex]a[/latex], то вместо чисел [latex]y_i[/latex] мы получим числа [latex]y_i+a[/latex]. Максимальные разности для чисел [latex]y_i[/latex] и для [latex]y_i+a[/latex] совпадают. Поэтому от набора [latex]f\{x_i\}[/latex] с помощью подходящего выбора [latex]a[/latex] можно перейти к такому набору [latex]f\{x_i’\}[/latex], что все [latex]x_i’\le0[/latex], наименьшие [latex]x_i[/latex] равны нулю, а наибольшие — единице. В дальнейшем мы будем рассматривать только такие наборы. Аналогично, если заменить числа [latex]x_i[/latex] на [latex]1-x_i[/latex], то [latex]y_i[/latex] заменятся на [latex]1-y_i[/latex]. Следовательно, от набора [latex]f\{x_i\}[/latex] можно перейти к набору [latex]f\{1-x_i\}[/latex]: максимальные разности между числами [latex]y_i[/latex] и числами [latex]1-y_i[/latex] одинаковы.

Решим задачу. Пусть [latex]y_k[/latex] — наименьшее, а [latex]y_t[/latex] — наибольшее из чисел [latex]f\{y_i\}[/latex].

Если [latex]k<l[/latex], то [latex]y_l-y_k=\frac{k y_k}{l}+\frac{x_{k+1}+\ldots+x_l}{l}-y_k[/latex][latex]=\frac{x_{k+1}+\ldots+x_l}{l}-\frac{l-k}{l} y_k[/latex][latex]\le\frac{x_{k+1}+\ldots+x_l}{l}\le\frac{l-k}{l}\le1-\frac{k}{l}\le1-\frac{1}{n}[/latex]

Если же [latex]k>l[/latex], то [latex]y_l-y_k=\frac{k-l}{k} y_l-\frac{y_{l+1}+\ldots+y_k}{k}\le1-\frac{l}{k}\le1-\frac{1}{n}[/latex].

Из вышесказанного следует, что максимальная разность не больше [latex]1-\frac{1}{n}[/latex]. Набор с такой разностью можно легко указать: [latex]x_1=0[/latex], [latex]x_2=x_3=\ldots=x_n=1[/latex].

Л. Г. Лиманов
Научно-популярный журнал «Квант», 1974 год, №3, страницы 38-39.

Итог:
Формула, которую необходимо использовать для решения этой задачи, это [latex]D=1-\frac{1}{n}[/latex], где D — наибольшая разность элементов последовательности [latex]x_1[/latex], [latex]\frac {x_1+x_2} {2}[/latex], [latex]\frac {x_1+x_2+x_3} {3}[/latex], [latex]\ldots[/latex], [latex]\frac {x_1+x_2+x_3+\ldots+x_n}{n}[/latex], а [latex]n[/latex] — их количество.

Ссылки

Условие задачи (страница 42);
Оригинал кода программы.

Related Images:

e-olymp 4082. Произведение на отрезке

27/06/2016 by Настя Филипчук

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

Это нормально чувствовать себя взволнованным и напряженным за день до олимпиады по программированию. Чтобы расслабиться, вы пошли выпить со своими друзьями в соседний паб. Для сохранения остроты ума до следующего дня, Вы решили сыграть в следующую игру. Для начала Ваши друзья написали последовательность [latex] n [/latex] целых чисел [latex] x_{1}, x_{2},\cdots , x_{n} [/latex]. Потом следует [latex] k [/latex] раундов, на каждом из которых выполняется одна из следующих команд:

команда изменения, когда необходимо изменить одно значение в последовательности;
команда умножения, когда по заданным значениям [latex] i [/latex] и [latex] j [/latex] необходимо определить, является ли произведение [latex] x_{i}\cdot x_{i+1} \cdot \; \; \cdots \; \; \cdot x_{j-1} \cdot x_{j} [/latex] положительным, отрицательным или равным нулю.

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

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

Каждый тест состоит из нескольких строк. Первая строка каждого теста содержит два числа [latex] n [/latex] и [latex] k [/latex] ([latex] 1\leq n,k\leq 10^{5}[/latex]) — количество элементов в последовательности и число раундов в игре. Вторая строка содержит [latex] n [/latex] целых чисел [latex] x_{i} [/latex] — начальные значения последовательности ([latex] -100\leq x_{i}\leq 100[/latex] для [latex]i=1,2, \cdots ,n[/latex]). Каждая из следующих [latex] k [/latex] строк описывает команду, начинающуюся заглавной буквой [latex] C [/latex] или [latex] C [/latex]. Если это буква [latex] C [/latex], то строка содержит команду замены, за буквой следуют два числа [latex] i [/latex] и [latex] v [/latex], указывающих на то что [latex] x_{i} [/latex] необходимо заменить на [latex] v [/latex] ([latex] 1\leq i\leq n[/latex] и [latex]-100\leq v\leq 100[/latex]). Если это буква [latex] P [/latex], то строка задает команду умножения, за буквой следуют два числа [latex] i [/latex] и [latex] j [/latex] — необходимо вычислить произведение от [latex] x_{i} [/latex] до [latex] x_{i} [/latex] включительно ([latex] 1\leq i\leq j\leq n [/latex]) . Каждый тест содержит как минимум одну команду умножения.

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

Для каждого теста вывести одну строку, содержащую ответы на все команды умножения. [latex] i [/latex]-ый символ строки является результатом [latex] i [/latex]-ой команды умножения. Если произведение положительно, то вывести символ [latex] + [/latex] (плюс); если произведение отрицательно, то вывести [latex] — [/latex] (минус); если произведение равно нулю, то вывести [latex] 0 [/latex] (ноль).

Тесты

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

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

4 6

-2 6 0 -1

C 1 10

P 1 4

C 3 7

P 2 2

C 4 -5

P 1 4

5 9

1 5 -2 4 3

P 1 2

P 1 5

C 4 -5

P 1 5

P 4 5

C 3 0

P 1 5

C 4 -5

0+-

+-+-0

5 5

10 -2 0 5 1

C 1 0

P 1 4

C 2 7

P 1 1

C 2 0

6 4

0 20 0 30 0 -10

P 2 2

P 2 3

P 3 6

P 2 6

4 3

0 -1 -2 0

P 2 3

C 1 9

P 1 2

3 3

5 2 0

C 1 7

C 3 0

C 1 0

6 5

100 10 55 11 0 -33

P 1 4

C 5 6

C 3 72

C 5 -20

P 5 6

+000

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

#include <iostream>
using namespace std;
 
void sequence(int* tree, int* given, int position, int i, int j) // посторение дерева
{
    if (i == j)
        tree[position] = given[i] > 0 ? 1 : (given[i] < 0 ? -1 : 0); // заменяем элементы последовательности на "1","-1","0" в соответсвии с условием для команды "P" 
    else if (i!=j)  // для остальных элементов воспользуемся следующим алгоритмом
    {
        int m = (i + j) / 2;
        sequence(tree, given, position * 2, i, m);
        sequence(tree, given, position * 2 + 1, m + 1, j);
        tree[position] = tree[position * 2] * tree[position * 2 + 1]; // элемент с номером (pos * 2) – левый потомок, а с (pos * 2 + 1) - правый потомок
    }
}

void For_C_command(int* tree, int position, int i, int j, int nposition, int v) // функция изменения элемента (для выполнения команлы "С")
{
    if (i == j)
        tree[position] = v > 0 ? 1 : (v < 0 ? -1 : 0);
    else if (i!=j)
    {
        int m = (i + j) / 2;
        if (nposition <= m)
            For_C_command(tree, position * 2, i, m, nposition, v);
        else
            For_C_command(tree, position * 2 + 1, m + 1, j, nposition, v);
        tree[position] = tree[position * 2] * tree[position * 2 + 1];
    }
}
 
int For_P_command(int* tree, int position, int i, int j, int qi, int qj) // функция для выполнения команды "Р"
{
    if (i == qi && j == qj)
        return tree[position];
    else
    {
        int m = (i + j) / 2;
        if (qj <= m)
            return For_P_command(tree, position * 2, i, m, qi, qj);
        else if (qi >= m + 1)
            return For_P_command(tree, position * 2 + 1, m + 1, j, qi, qj);
        else
            return For_P_command(tree, position * 2, i, m, qi, m) * For_P_command(tree, position * 2 + 1, m + 1, j, m + 1, qj);
    }
}
 
int main() 
{
    ios::sync_with_stdio(false); // ускоряем чтение
    int n, k;
    while (cin >> n >> k)
    {
        int given[n];
        for (int i = 0; i < n; i++)
            cin >> given[i];
        int tree[n * 4];
        sequence(tree, given, 1, 0, n - 1);
        for (int i = 0; i < k; i++)
        {
            char command;
            int xi, xj;
            cin >> command >> xi >> xj;
            if (command == 'P')
            {   
                int x = For_P_command(tree, 1, 0, n - 1, xi - 1, xj - 1); // применяем функцию для команды "Р" и выполняем сравнения, соответствующие условию задачи
                if (x < 0)
                    printf("-");
                else if (x > 0)
                    printf("+");
                else 
                    printf("0");
            }
            else
                For_C_command(tree, 1, 0, n - 1, xi - 1, xj);
        }
        printf("\n");
    }
}

#include <iostream>

using namespace std;

void sequence(int* tree, int* given, int position, int i, int j) // посторение дерева

{

if (i == j)

tree[position] = given[i] > 0 ? 1 : (given[i] < 0 ? -1 : 0); // заменяем элементы последовательности на "1","-1","0" в соответсвии с условием для команды "P"

else if (i!=j) // для остальных элементов воспользуемся следующим алгоритмом

{

int m = (i + j) / 2;

sequence(tree, given, position * 2, i, m);

sequence(tree, given, position * 2 + 1, m + 1, j);

tree[position] = tree[position * 2] * tree[position * 2 + 1]; // элемент с номером (pos * 2) – левый потомок, а с (pos * 2 + 1) - правый потомок

}

void For_C_command(int* tree, int position, int i, int j, int nposition, int v) // функция изменения элемента (для выполнения команлы "С")

{

if (i == j)

tree[position] = v > 0 ? 1 : (v < 0 ? -1 : 0);

else if (i!=j)

{

int m = (i + j) / 2;

if (nposition <= m)

For_C_command(tree, position * 2, i, m, nposition, v);

else

For_C_command(tree, position * 2 + 1, m + 1, j, nposition, v);

tree[position] = tree[position * 2] * tree[position * 2 + 1];

}

int For_P_command(int* tree, int position, int i, int j, int qi, int qj) // функция для выполнения команды "Р"

{

if (i == qi && j == qj)

return tree[position];

else

{

int m = (i + j) / 2;

if (qj <= m)

return For_P_command(tree, position * 2, i, m, qi, qj);

else if (qi >= m + 1)

return For_P_command(tree, position * 2 + 1, m + 1, j, qi, qj);

else

return For_P_command(tree, position * 2, i, m, qi, m) * For_P_command(tree, position * 2 + 1, m + 1, j, m + 1, qj);

}

int main()

{

ios::sync_with_stdio(false); // ускоряем чтение

int n, k;

while (cin >> n >> k)

{

int given[n];

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

cin >> given[i];

int tree[n * 4];

sequence(tree, given, 1, 0, n - 1);

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

{

char command;

int xi, xj;

cin >> command >> xi >> xj;

if (command == 'P')

{

int x = For_P_command(tree, 1, 0, n - 1, xi - 1, xj - 1); // применяем функцию для команды "Р" и выполняем сравнения, соответствующие условию задачи

if (x < 0)

printf("-");

else if (x > 0)

printf("+");

else

printf("0");

}

else

For_C_command(tree, 1, 0, n - 1, xi - 1, xj);

}

printf("\n");

}

Решение

Данная задача решается при помощи стандартного алгоритма по теме «Дерево отрезков» (данный алгоритм можно посмотреть на сайте e-maxx). Следовательно, при построении дерева сначала считывается массив, а после выполняется построение дерева (от корня). В том случае, если функция, строящая дерево, вызывалась от листа, все значения элементов массива записываются в дерево как [latex]1[/latex], если элемент больше нуля, если меньше нуля, то записывается как [latex]-1[/latex], а в случае равенства элемента нулю, он записывается [latex]0[/latex] (нулём). В ином случае (если функция вызывалась не от листа), она начинает вызываться рекурсивно от каждого из двух сыновей и перемножает вычесленные значения.

Для выполнения функции изменения элемента ей (функции) передаётся текущая вершина. Затем выполняется вызов из сына, сожержащего элемент с данным номером. Таким образом процесс доходит до листа, которому и присваевается значение. При чём, аналогично построению дерева, элементы записываются как [latex]1[/latex],[latex]-1[/latex] или же [latex]0[/latex].

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

Далее (в программе) идёт процесс построения дерева и выполнение действий, удовлетворяющих команды, описанные в уловии задачи.

Ссылки

Рабочий код на Ideone.com
Засчитанное решение на e-olymp.com
При ришении данной задачи был использован материал по структурам данных «дерево отрезков» с сайта e-maxx.ru
Задача взята с сайта e-olymp.com

Related Images:

A285

01/06/2016 by Максим Носов

Задача

Даны действительные числа [latex]{ a }_{ 1 }[/latex]…[latex]{ a }_{ n }[/latex] . Если в результате замены отрицательных членов последовательности [latex]{ a }_{ 1 }[/latex]…[latex]{ a }_{ n }[/latex] их квадратами члены будут образовывать неубывающую последовательность, то получить сумму членов исходной последовательности ; в противном случае получить их произведение.

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

Последовательность

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

Сумма членов, если последовательность неубывающая и их произведение в противном случае.

Тесты

№	Последовательность	Результат
1	1 2 3 4	10
2	1 2 -3 4	-24
3	1 -2 5 6 7 8	25
4	-1 -1 -2 -3 -4 -5	-16

Код

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector <double> x; //задаем элемент типа vector
    double a,m=0,k=0,n=0;
    while(cin>>a){     //вводим последовательность
        x.push_back(a);  //для дальнейшего преобразования последовательности
    }
    for(int i=0;i<x.size();i++)n+=x[i]; //находим сумму
    for(int i=0;i<x.size();i++){
        if(i==0)k=x[0];
        else k*=x[i];
    } //и произведение исходной последовательности
    for(int i=0;i<x.size();i++){   //задаем цикл, в котором заменяем все отрицательные элементы их квадратами
        if(x[i]<0)x[i]=x[i]*x[i];
        if(x[i]<m){  //проверяем возрастаемая последовательность или нет
            m=0;
            break;
        }
        m=x[i];
    }
    if(m!=0){    //если возрастающая - то выводим сумму
        cout<<n;
    }
    else {
        cout<<k; //если нет - то произведение
    }
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <double> x; //задаем элемент типа vector

double a,m=0,k=0,n=0;

while(cin>>a){ //вводим последовательность

x.push_back(a); //для дальнейшего преобразования последовательности

}

for(int i=0;i<x.size();i++)n+=x[i]; //находим сумму

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

if(i==0)k=x[0];

else k*=x[i];

} //и произведение исходной последовательности

for(int i=0;i<x.size();i++){ //задаем цикл, в котором заменяем все отрицательные элементы их квадратами

if(x[i]<0)x[i]=x[i]*x[i];

if(x[i]<m){ //проверяем возрастаемая последовательность или нет

m=0;

break;

}

m=x[i];

}

if(m!=0){ //если возрастающая - то выводим сумму

cout<<n;

}

else {

cout<<k; //если нет - то произведение

}

Решение

Предлагаю следующее решение. Записываем каждый член последовательности в элемент типа vector. Сразу находим их сумму и произведение. Затем заменяем каждый отрицательный элемент его квадратом и проверяем возрастающая ли последовательность. Если да — то выводим сумму, если нет — то произведение.

Код на ideone.

Related Images:

A287

31/03/2016 by Настя Филипчук

Задача A287

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

Даны целые числа [latex] a_{1}\dots a_{n} [/latex]. Все члены последовательности с четными номерами, предшествующие первому по порядку члену со значением [latex] max(a_{1}\dots a_{n}) [/latex], домножить на [latex] max(a_{1}\dots a_{n}) [/latex].

Тестирование

№	Входные данные	Выходные данные
1.	1 2 3 4 3 2 1	1 8 3 4 3 2 1
2.	1 2 3 4 4 2 5 5 3 3 2 1	1 10 3 20 4 10 5 5 3 3 2 1
3.	11 4 6 7 9	11 4 6 7 9
4.	9 8 10 1 2 4 5 4 6 13	9 104 10 13 2 52 5 52 6 13
5.	-10 -4 -6 -7 -3 0 -1 -20	-10 0 -6 0 -3 0 -1 -20

Реализация

#include "iostream"
#include <vector>
using namespace std;
 
int main()
{
	vector <int> a;
	int n;
	int max_i = 0; //номер максимального элемента
	while (cin >> n) 
		a.push_back(n); 
	for (int i=0; i < a.size(); i++)
	{
		if (a[i] > a[max_i])
			 max_i=i;
	}
	for (int i=0; i<max_i; i++)
	{
		if (i % 2 != 0)
			a[i] *= a[max_i];			
	}
	for (int i = 0; i < a.size(); i++)
		cout << a[i] << " ";
	return 0;
}

#include "iostream"

#include <vector>

using namespace std;

int main()

{

vector <int> a;

int n;

int max_i = 0; //номер максимального элемента

while (cin >> n)

a.push_back(n);

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

{

if (a[i] > a[max_i])

max_i=i;

}

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

{

if (i % 2 != 0)

a[i] *= a[max_i];

}

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

cout << a[i] << " ";

return 0;

}

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

Считываем все целые числа до конца входного потока и записываем их в вектор [latex] a [/latex]. Затем:

Сравниваем между собой каждый элемент вектора, и если находится большее значение, то запоминается номер данного элемента.
Далее проходим все члены последовательности, предшествующие первому по порядку члену с максимальным значением.
Умножаем все элементы с четными номерами на [latex] max(a_{1}\dots a_{n}) [/latex].

Ссылки

Код на ideaone.

Related Images:

A294

30/03/2016 by Кондратюк Настя

С.А.Абрамов. Задачи по программированию.

Задача

Даны действительные числа [latex]r_{1},\ldots,r_{n}[/latex], среди которых заведомо есть как отрицательные, так и не отрицательные. Получить [latex]x_{1}y_{1}+\ldots+x_{s}y_{s}[/latex], где [latex]x_{1},\ldots,x_{p}[/latex] — отрицательные члены последовательности [latex]r_{1},\ldots,r_{n}[/latex], взятые в порядке следования, [latex]y_{1},\ldots,y_{q}[/latex] — неотрицательные члены, взятые в обратном порядке, [latex]s=min\left ( p,q \right )[/latex] .

Тесты

Входные данные	Выходные данные
-1 1	-1
-1	0
-1 -1	0
1 2 -5 10 -2	-54
4 6 3 4 -8 2 7 5	-40

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

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

int main() {
	double r, sum=0;
	int s;
	vector <double> x;
	vector <double> y;
	while(cin >> r){
		if(r<0){
			x.push_back(r);
		}
		else y.push_back(r);
	}
	s = min(x.size(), y.size());
	for(int i=0; i < s; i++){
		sum += x[i] * y.back();/* умножение отрицательных чисел в порядке 
                следования на неотрицательные в обратном порядке */
		y.pop_back();
	}
	cout << sum;
	return 0;
}

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int main() {

double r, sum=0;

int s;

vector <double> x;

vector <double> y;

while(cin >> r){

if(r<0){

x.push_back(r);

}

else y.push_back(r);

}

s = min(x.size(), y.size());

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

sum += x[i] * y.back();/* умножение отрицательных чисел в порядке

следования на неотрицательные в обратном порядке */

y.pop_back();

}

cout << sum;

return 0;

}

ideone.com

Решение

Считывая числа из входного потока, выполняем проверку и записываем положительные в вектор [latex]y[/latex], отрицательные — в вектор [latex]x[/latex]. Затем вычисляем [latex]s[/latex]. Вычисляем [latex]x_{1}y_{1}+\ldots+x_{s}y_{s}[/latex].

Related Images:

A293

29/03/2016 by Алина Гончарова

Задача

Даны целые числа [latex]a_1,\ldots,a_n[/latex].

Если в данной последовательности ни одно четное число не расположено после нечетного,

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

Тесты

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

Алгоритм

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

Код

#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    vector <int> a, b;
    int element;
    while (cin >> element) {
        a.push_back(element);
    }
    bool getNegative = true;
    for (int i = 0; i < a.size() - 1; i++) {
        if (abs(a[i]) % 2 == 1 && a[i + 1] % 2 == 0) {
            getNegative = false;
            break;
        }
    }
    if (getNegative) {
        for (int i = a.size() - 1; i >= 0; i--) {
            if (a[i] < 0) {
                b.push_back(a[i]);
            }
        }
    } else {
        for (int i = a.size() - 1; i >= 0; i--) {
            if (a[i] > 0) {
                b.push_back(a[i]);
            }
        }
    }
    for (int i = 0; i < b.size(); i++) {
        cout << b[i] << " ";
    }
    return 0;
}

#include <cmath>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

vector <int> a, b;

int element;

while (cin >> element) {

a.push_back(element);

}

bool getNegative = true;

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

if (abs(a[i]) % 2 == 1 && a[i + 1] % 2 == 0) {

getNegative = false;

break;

}

if (getNegative) {

for (int i = a.size() - 1; i >= 0; i--) {

if (a[i] < 0) {

b.push_back(a[i]);

}

} else {

for (int i = a.size() - 1; i >= 0; i--) {

if (a[i] > 0) {

b.push_back(a[i]);

}

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

cout << b[i] << " ";

}

return 0;

}

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

Related Images:

A299

26/03/2016 by Сплошнов Кирилл

Условие

Дана последовательность действительных чисел [latex]a_1, a_2, \dots, a_n[/latex]. Требуется домножить все члены последовательности на квадрат её наименьшего члена, если [latex]a_1 \geq 0[/latex], в противном случае — на квадрат наибольшего.

Решение

Для решения воспользуемся стандартным классом vector. Для этого заведем переменную данного типа, заполним её числами со входного потока. Далее, в зависимости от первого (нулевого) элемента вектора, воспользуемся стандартной функцией min_element() или max_element() (библиотека algorithm). Далее умножим каждый элемент на (соответственно) минимум/максимум и выведем последовательность.

Тесты

№	Входные данные	Выходные данные
1	-2 2 43 5 -10 12 0 -1	-3698 3698 79507 9245 -18490 22188 0 -1849
2	0 100 99 0 -1 1	0 100 99 0 -1 1
3	42 1 1 1 0 -1 24 -24 -42	74088 1764 1764 1764 0 -1764 42336 -42336 -74088

Код

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

int main() 
{
	vector<int> x;
	int a;
	while (cin >> a)
		x.push_back(a);
	if (x.at(0) >= 0)
	{
		int min = *min_element(x.begin(), x.end());
		for (int &i : x)
			i *= min * min;
	}
	else
	{
		int max = *max_element(x.begin(), x.end());
		for (int &i : x)
			i *= max * max;
	}
	for (int i : x)
		cout << i << " ";
	return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

vector<int> x;

int a;

while (cin >> a)

x.push_back(a);

if (x.at(0) >= 0)

{

int min = *min_element(x.begin(), x.end());

for (int &i : x)

i *= min * min;

}

else

{

int max = *max_element(x.begin(), x.end());

for (int &i : x)

i *= max * max;

}

for (int i : x)

cout << i << " ";

return 0;

}

Замечание

Перед изменением значения членов последовательности и их выводом нам необходимо найти минимум или максимум, для чего необходимо знать значения всех её членов. В связи с этим, решить задачу в формате «считал — вывел» (потоковой обработкой) невозможно.

Ссылки

Код на ideaone (vector).

Related Images:

А282б

16/03/2016 by Антон Локтев

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

Даны действительные числа [latex]a_{1}[/latex], [latex]a_{2}[/latex], [latex]\ldots[/latex], [latex]a_{2n}[/latex]. Получить [latex]a_{1}[/latex], [latex]a_{2n}[/latex], [latex]a_{2}[/latex], [latex]a_{2n-1}[/latex], [latex]a_{3}[/latex], [latex]\ldots[/latex], [latex]a_{n}[/latex], [latex]a_{n+1}[/latex].

Данную задачу можно найти здесь.

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

Последовательность действительных чисел [latex]a_{1}[/latex], [latex]a_{2}[/latex], [latex]\ldots[/latex], [latex]a_{2n}[/latex].

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

Последовательность действительных чисел [latex]a_{1}[/latex], [latex]a_{2n}[/latex], [latex]a_{2}[/latex], [latex]a_{2n-1}[/latex], [latex]a_{3}[/latex], [latex]\ldots[/latex], [latex]a_{n}[/latex], [latex]a_{n+1}[/latex] .

Тесты

№	Входные данные	Выходные данные
1	1 2 3 4 5 6	1 6 2 5 3 4
2	0 0 0 0 0 1	0 1 0 0 0 0
3	3 12 42 -6 15 0 0 0 501 20 20 20	3 20 12 20 42 20 -6 501 15 0 0 0
4	42 0 17 -2.6 -54 41888 0.25 13 1.3333 -284.73	42 -284.73 0 1.3333 17 13 -2.6 0.25 -54 41888
5	0 1 -1 0 1 -1 97 113 -7.777 0 48 -69	0 -69 1 48 -1 0 0 -7.777 1 113 -1 97

Код

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector <double> sequence, result_sequence;
    double term_of_sequence;
    while (cin >> term_of_sequence){
        sequence.push_back(term_of_sequence);
    }
    for (int i = 0; i < sequence.size() / 2; i++){
        result_sequence.push_back(sequence[i]);
        result_sequence.push_back(sequence[sequence.size() - 1 - i]);
    }
    for (int i = 0; i < result_sequence.size(); i++){
        cout << result_sequence[i] << " ";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <double> sequence, result_sequence;

double term_of_sequence;

while (cin >> term_of_sequence){

sequence.push_back(term_of_sequence);

}

for (int i = 0; i < sequence.size() / 2; i++){

result_sequence.push_back(sequence[i]);

result_sequence.push_back(sequence[sequence.size() - 1 - i]);

}

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

cout << result_sequence[i] << " ";

}

return 0;

}

Код на ideone можно найти здесь.

Ход решения

Считываем все числа из входного потока и записываем их в вектор исходной последовательности sequence. Результатом работы нашей программы должна быть новая последовательность действительных чисел result_sequence, которая задаётся по следующему правилу: первый член новой последовательности совпадает с первым членом исходной, второй член новой последовательности является последним членом исходной, третий – второй член исходной и так далее до исчерпания чисел. Иными словами, новая последовательность из [latex]2n[/latex] чисел на нечётных номерах имеет члены исходной последовательности (от первого и до [latex]n[/latex]-го включительно), чётным же номерам новой последовательности соответствуют члены исходной с номерами от [latex]n+1[/latex] до [latex]2n[/latex] включительно, записанные в обратном порядке.

Related Images:

A295

12/03/2016 by Женя Максимова

Задача. Даны целые числа [latex]a_{1},\ldots, a_{n}[/latex]. Наименьший член последовательности [latex]a_{1}, \ldots, a_{n}[/latex] заменить целой частью среднего арифметического всех членов, остальные члены оставить без изменения. Если в последовательности несколько членов со значением min [latex](a_{1}, \ldots, a_{n})[/latex], то заменить последний по порядку.

Тесты

Test	Input	Output
1	2 4 8 16 2 4	2 4 8 16 6 4
2	1 1 1 1	1 1 1 1
3	-5 5 -10 10 -10 5 5	-5 5 -10 10 0 5 5
4	2 6 9 -4 -5 7 13	2 6 9 -4 4 7 13
5	0 0 0 0 0 1	0 0 0 0 0 1
6	0 1 0 0 2 0 25	0 1 0 0 2 4 25

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

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

int main()
{
  vector<int>a;
  int el; //supporting variable for saving input values
  while(cin >> el)
    {
      a.push_back(el); //adding value to the vector
    }
  int min = a[0]; // minimal value
  int num = 0; // number of the minimal value
  double sum = 0; 
  for(int i=0; i<a.size(); i++)
    {
      if(a[i]<=min) //finding the number of the minimal value
        {
          min = a[i]; 
          num = i;
        }
      sum += a[i];
    }
  int average = floor(sum/a.size()); //calculing the average of vector elements
  a[num] = average; //replacing minimal value by the average
  for(int i = 0; i < a.size(); i++)
    {
      cout << a[i] << " ";
    }
  return 0;
}

#include<iostream>

#include<cmath>

#include<vector>

using namespace std;

int main()

{

vector<int>a;

int el; //supporting variable for saving input values

while(cin >> el)

{

a.push_back(el); //adding value to the vector

}

int min = a[0]; // minimal value

int num = 0; // number of the minimal value

double sum = 0;

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

{

if(a[i]<=min) //finding the number of the minimal value

{

min = a[i];

num = i;

}

sum += a[i];

}

int average = floor(sum/a.size()); //calculing the average of vector elements

a[num] = average; //replacing minimal value by the average

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

{

cout << a[i] << " ";

}

return 0;

}

Алгоритм

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

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

Related Images:

MLoops 18

27/12/2015 by Александр Димитриев

Условие

1123581321345589144233377
1235813213455891442333776
2358132134558914423337761
3581321345589144233377610
5813213455891442333776109

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

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

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

Вывести таблицу размерностью [latex]n\times m[/latex].

Тесты

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

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

1 1

2 2

11
12

5 5

11235

12358

23581

35813

58132

9 18

112358132

123581321

235813213

358132134

581321345

813213455

132134558

213455891

345589144

558914423

891442333

144233377

233377610

377610987

610987159

987159725

159725844

258441816

418167651

25 5

1123581321345589144233377
1235813213455891442333776
2358132134558914423337761
3581321345589144233377610
5813213455891442333776109

1123581321345589144233377

1235813213455891442333776

2358132134558914423337761

3581321345589144233377610

5813213455891442333776109

Код

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

int f(int a) {
	int b=1;
	for (int i=0; i<a; i++) {
		 b*=10;
	}
	return b;
}
 
int g(int a) {
	return (a==0 ? 1 : floor(log10(a))+1);
}
 
void h(int &i, int &j, int &a, int &b, int &a1, int &b1) {
	cout << endl; 
	a=a1;
	b=b1;
	i++;
	j=0; 
}
 
int main() {
	int n, m, a=1, b=0, c, a1=0, b1=1;
	cin >> n >> m;
	int i=1, j=0;
	while (i<=m) {
		if (j==n) {
		   	h(i, j, a, b, a1, b1);
		}
		c=a+b;
		a=b;
		b=c;
		if (j==0) {
		    a1=a;
		   	b1=b;
		}
		if (j+g(c)>n) { // если текущее число Фибоначчи выходит за предел строки
		    cout << c/f(g(c)-n+j); // печатаем ту часть что не выходит за ее предел
		 	h(i, j, a, b, a1, b1);
		} 
		else if (i<=m) {
		 	cout << c;
		 	j+=g(c); 
		} 
	}
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int f(int a) {

int b=1;

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

b*=10;

}

return b;

}

int g(int a) {

return (a==0 ? 1 : floor(log10(a))+1);

}

void h(int &i, int &j, int &a, int &b, int &a1, int &b1) {

cout << endl;

a=a1;

b=b1;

i++;

j=0;

}

int main() {

int n, m, a=1, b=0, c, a1=0, b1=1;

cin >> n >> m;

int i=1, j=0;

while (i<=m) {

if (j==n) {

h(i, j, a, b, a1, b1);

}

c=a+b;

a=b;

b=c;

if (j==0) {

a1=a;

b1=b;

}

if (j+g(c)>n) { // если текущее число Фибоначчи выходит за предел строки

cout << c/f(g(c)-n+j); // печатаем ту часть что не выходит за ее предел

h(i, j, a, b, a1, b1);

}

else if (i<=m) {

cout << c;

j+=g(c);

}

return 0;

}

Решение

Несложно догадаться что данная последовательность чисел это числа Фибоначчи. Для того чтобы построить таблицу надо сначала найти числа Фибоначчи (у меня это — [latex]a,b,c[/latex]), после печатаем их в строку далее переходим на новую строку и начинаем со 2 элемента относительно предыдущей строки это выполняет функция [latex]h[/latex], и так пока [latex]i \le m[/latex]. Но может возникнуть проблема с выходом за предел строки и для того чтобы этого не произошло нам нужны функции [latex]f[/latex], которая возводит 10 в заданную степень, это нам надо чтобы отрезать то что выходит за предел строки, для этого используем целочисленное деление на 10 в нужной степени, и [latex]g[/latex], которая считает количество цифр в данном числе Фибоначчи, для того чтобы определить в какую степень нам надо возвести 10, чтобы оставить только ту часть что не выходит за предел строки.
Код программы

Related Images:

Mloop 21

21/12/2015 by Максим Носов

Задача

Вычислить с точностью [latex]\varepsilon [/latex] сумму ряда [latex]\sum _{i=1}^{\infty }{\frac{i}{fib(i)}}[/latex]

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

Точность [latex]\varepsilon [/latex].

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

Сумма ряда.

Тесты

№	Точность [latex]\varepsilon [/latex]	Сумма ряда	Количество членов
1	1	3	2
2	0.5	8.502	8
3	0.1	9.156	12
4	0.01	9.307	18

Код

#include <iostream>
using namespace std;

int main() {
	double fib1=1,fib2=1,fib3,sum=3,E,a=1; //задаем переменные
	int k=2;
	cin>>E; //вводим точность, с которой будут происходить вычисления //если точность равна 1 то сумма последовательности 
	if(E==2 || E==1)cout<<2<<endl<<3; //если точность равна 1 или 2 по сумма будет равнна сумме двух первых членов последовательности
	else if(E<1){
		for(int i=3;a>=E;i++){ //задаем цикл:пока следующее слагаемое больше точности
			fib3=fib1+fib2;
			a=i/fib3; //слагаемое
			sum+=a;
			fib1=fib2;
			fib2=fib3;
			//k++;  //считаем количество слагаемых, для того чтобы потом проверить результат
		}
	//cout<<k<<endl;
        cout<<sum;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double fib1=1,fib2=1,fib3,sum=3,E,a=1; //задаем переменные

int k=2;

cin>>E; //вводим точность, с которой будут происходить вычисления //если точность равна 1 то сумма последовательности

if(E==2 || E==1)cout<<2<<endl<<3; //если точность равна 1 или 2 по сумма будет равнна сумме двух первых членов последовательности

else if(E<1){

for(int i=3;a>=E;i++){ //задаем цикл:пока следующее слагаемое больше точности

fib3=fib1+fib2;

a=i/fib3; //слагаемое

sum+=a;

fib1=fib2;

fib2=fib3;

//k++; //считаем количество слагаемых, для того чтобы потом проверить результат

}

//cout<<k<<endl;

cout<<sum;

}

return 0;

}

Решение

Предлагаю следующее решение. Вычисляем первые два члена суммы:[latex]\sum _{i=1}^{2}{\frac{i}{fib(i)}}=1+\frac{1}{2}[/latex]. Каждое следующее слагаемое находим по формуле [latex]\frac{i}{fib(i)}[/latex] и записываем в переменную [latex]a[/latex], которую прибавляем к переменной [latex]sum[/latex], где хранится сумма, известная нам на данный момент (изначально это сумма первых двух членов) . [latex]fib_1[/latex] и [latex]fib_2[/latex] это два последних числа Фибоначчи, которые нам нужны для вычисления следующего [latex]fib_3[/latex]. Продолжаем искать слагаемые пока следующее слагаемое больше точности [latex]\varepsilon [/latex]. Вводим дополнительную переменную [latex]k[/latex] для того чтоб сосчитать количество слагаемых. Затем можно проверить правильность вычислений тут, подставляя [latex]k[/latex] как количество слагаемых.

Ссылка на код.

Related Images:

MLoops 16

01/12/2015 by Кондратюк Настя

Задача

123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123
231231231231231231231231231
132132132132132132132132132
123123123123123123123123123
231231231231231231231231231

Тесты

[latex]m[/latex] [latex]n[/latex]
4 3	123 231 132 123
8 8	12312312 23123123 13213213 12312312 23123123 13213213 12312312 23123123
10 27	123123123123123123123123123 231231231231231231231231231 132132132132132132132132132 123123123123123123123123123 231231231231231231231231231 132132132132132132132132132 123123123123123123123123123 231231231231231231231231231 132132132132132132132132132 123123123123123123123123123

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

#include <iostream>
using namespace std;

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

#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> m >> n;

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

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

if((i+j)%3==0) cout << 2;

else{

if(j%3==0){

if((i+j+1)%3==0) cout << 1;

else cout << 3;

}

else if((j-1)%3==0) cout << 1;

else cout << 3;

}

cout << endl;

}

return 0;

}

ideone.com

Решение

Пронумеруем строки от [latex]1[/latex] до [latex]m[/latex] , столбцы — от [latex]1[/latex] до [latex]n[/latex].

	1	2	3	4	5	6	7	…	n
1	1	2	3	1	2	3	1	…	…
2	2	3	1	2	3	1	2	…	…
3	1	3	2	1	3	2	1	…	…
4	1	2	3	1	2	3	1	…	…
5	2	3	1	2	3	1	2	…	…
6	1	3	2	1	3	2	1	…	…
7	1	2	3	1	2	3	1	…	…
…	…	…	…	…	…	…	…	…	…
m	…	…	…	…	…	…	…	…	…

Положение символа [latex]2[/latex] определяется однозначно для всей таблицы [latex]\left (n+m \right )\vdots 3[/latex]. В столбцах, где [latex]n\vdots 3[/latex], положение символа [latex]1[/latex] — [latex]\left ( n+m+1 \right )\vdots 3[/latex] , на оставшихся свободных местах — символ [latex]3[/latex] . В столбцах, где [latex]\left ( n-1\right )\vdots 3[/latex], на свободных местах стоит символ [latex]1[/latex]. В оставшихся столбцах на свободных местах стоит символ [latex]3[/latex].

Related Images:

MLoops 17

16/11/2015 by Павел Загинайло

Задача

+++++++++++++++++++++++++++++++
+....^....+....^....+....^....+
+....|....+....|....+....|....+
+<-- k -->+<-- k -->+<-- k -->+
+....|....+....|....+....|....+
+....v....+....v....+....v....+
+++++++++++++++++++++++++++++++
+....^....+....^....+....^....+
+....|....+....|....+....|....+
+<-- k -->+<-- k -->+<-- k -->+
+....|....+....|....+....|....+
+....v....+....v....+....v....+
+++++++++++++++++++++++++++++++

+++++++++++++++++++++++++++++++

+....^....+....^....+....^....+

+....|....+....|....+....|....+

+<-- k -->+<-- k -->+<-- k -->+

+....|....+....|....+....|....+

+....v....+....v....+....v....+

+++++++++++++++++++++++++++++++

+....^....+....^....+....^....+

+....|....+....|....+....|....+

+<-- k -->+<-- k -->+<-- k -->+

+....|....+....|....+....|....+

+....v....+....v....+....v....+

+++++++++++++++++++++++++++++++

Тесты

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

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

+++++++++++++++++++++++++++++++
+.........+.........+.........+
+.........+.........+.........+
+.........+.........+.........+
+.........+.........+.........+
+.........+.........+.........+
+++++++++++++++++++++++++++++++
+.........+.........+.........+
+.........+.........+.........+
+.........+.........+.........+
+.........+.........+.........+
+.........+.........+.........+
+++++++++++++++++++++++++++++++

+++++++++++++++++++++++++++++++

+.........+.........+.........+

+++++++++++++++++++++++++++++++

+.........+.........+.........+

+++++++++++++++++++++++++++++++

++++++++
+....+..
+....+..
+....+..
+....+..

++++++++

+....+..

++++++++++++++++++++
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
++++++++++++++++++++
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
++++++++++++++++++++
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
++++++++++++++++++++
+...+...+...+...+...

++++++++++++++++++++

+...+...+...+...+...

++++++++++++++++++++

+...+...+...+...+...

++++++++++++++++++++

+...+...+...+...+...

++++++++++++++++++++

+...+...+...+...+...

Алгоритм

Программа выполняется с помощью двух циклов. Первый цикл отвечает за строки, второй за столбцы. Метод заключается в том, чтобы узнать, когда мы записываем именно ‘+’, а уже в остальные места записываем ‘.’. Для начала проверяем делится ли номер строки, уменьшенный на 1, нацело на 6. Если да, то записываем +. Далее проверяем, делится ли номер столбца, уменьшенный на 1, на число [latex]k+1[/latex], где [latex]k[/latex] — вводимый параметр. Во всех остальных случаях пишем ‘.’.

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

#include <iostream>
using namespace std;

int main() {
	int m, n, k; //m-строки, n - столбцы
	cin >> m >> n >> k;
	for (int i = 0; i < m; i++){
		for (int j = 0; j < n; j++){
			if (i%6 == 0) cout << '+';
			else if (j%(k+1) == 0) cout << '+';
			else cout << '.';
		}
	cout << endl;	
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int m, n, k; //m-строки, n - столбцы

cin >> m >> n >> k;

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

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

if (i%6 == 0) cout << '+';

else if (j%(k+1) == 0) cout << '+';

else cout << '.';

}

cout << endl;

}

return 0;

}

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

Related Images:

Mloops 21

11/11/2015 by Женя Максимова

Задача.Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex]n>0[/latex] (количество столбцов) и [latex]m>0[/latex] (количество строк).
Совет. Если закономерность разгадать не получается, попробуйте воспользоваться Онлайн-энциклопедией целочисленных последовательностей.

1+12+33+64+105+156+217+288
12+33+64+105+156+217+288+1
33+64+105+156+217+288+1+12
64+105+156+217+288+1+12+33
105+156+217+288+1+12+33+64
156+217+288+1+12+33+64+105
217+288+1+12+33+64+105+156

Тесты

№	[latex]m[/latex]	[latex]n[/latex]	Результат
1	5	13	1+12+33+64+10 12+33+64+105+ 33+64+105+1+1 64+105+1+12+3 105+1+12+33+6
2	8	11	1+12+33+64+ 12+33+64+1+ 33+64+1+12+ 64+1+12+33+ 1+12+33+64+ 12+33+64+1+ 33+64+1+12+ 64+1+12+33+
3	11	20	1+12+33+64+105+156+2 12+33+64+105+156+217 33+64+105+156+217+1+ 64+105+156+217+1+12+ 105+156+217+1+12+33+ 156+217+1+12+33+64+1 217+1+12+33+64+105+1 1+12+33+64+105+156+2 12+33+64+105+156+217 33+64+105+156+217+1+ 64+105+156+217+1+12+

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

#include <iostream>
#include <stdio.h>
#include<cmath>
using namespace std;
int m, n, max_q; // длина и ширина таблицы, максимальное количество чисел в строке

int element(int i) // формула для i-того элемента последовательности
{
 i++;
 return i*i+4*(i*i-i); 
}
int length_of_element(int el) // длина i-того элемента
{
 if( el==0|| el==1 ) 
   return 1;
 return ceil(log10(el));
}

int max_quantity() // максимальное количество чисел в строке
{
 int max_q=0;
 int length=0;
 for(int j=0; true; j++) 
  {
	 int elem = element(j);
	 int  length_el = length_of_element(elem);
	 if(length + length_el <= n) // проверяем, "поместится" ли в строку очередное число 
    {
      length += length_el;
      max_q++;
      if(length == n)
        return max_q;
    }
	 else // если число не "влезает", добавляем "+"
	{
	  max_q++;
	  return max_q;
	}
   if(length+1 <= n) // если число "поместилось", но осталось место еще для одного символа, тоже добавляем "+"
    {
     length += 1;
     if(length == n)
      return max_q;
    }
  }
 return max_q; // такая ситуация невозможна
}

int line(int i) // печать i-той строки
{
 int length=0;
 for(int jj=i; true; jj++)
    {
     int j = jj % max_q; // формула циклического сдвига чисел в строке
     int  elem = element(j); // число которое мы будем выводить
     int  length_el = length_of_element(elem); // длина числа
     if(length + length_el <= n) // если полученная нами длина все еще меньше заданного количества столбцов, мы выводим число 
        {
         length += length_el;
         cout << elem;
         if(length == n)
            {
             cout << endl;
             return length;
            }
        }
     else // если длина получается больше, мы "отрезаем" от числа нужное количество символов
        {
         int excess = length+length_el-n;
         for(int z = 0; z < excess; ++z) elem /= 10;
         cout << elem << endl;
         return length;
        }

     if(length + 1 <= n) // проверяем, нужно ли выводить "+"
      {
        length += 1; cout << "+";
        if(length == n)
        {
          cout << endl;
          return length;
        }
      }
    }
return 0;
}

int main()
{
 cin >> m >> n; // параметры таблицы
 max_q = max_quantity(); // вычисляем максимально возможное количество чисел в строке
 for(int i=0; i<m; i++) line(i); // вывод таблицы
 return 0;
}

#include <iostream>

#include <stdio.h>

#include<cmath>

using namespace std;

int m, n, max_q; // длина и ширина таблицы, максимальное количество чисел в строке

int element(int i) // формула для i-того элемента последовательности

{

i++;

return i*i+4*(i*i-i);

}

int length_of_element(int el) // длина i-того элемента

{

if( el==0|| el==1 )

return 1;

return ceil(log10(el));

}

int max_quantity() // максимальное количество чисел в строке

{

int max_q=0;

int length=0;

for(int j=0; true; j++)

{

int elem = element(j);

int length_el = length_of_element(elem);

if(length + length_el <= n) // проверяем, "поместится" ли в строку очередное число

{

length += length_el;

max_q++;

if(length == n)

return max_q;

}

else // если число не "влезает", добавляем "+"

{

max_q++;

return max_q;

}

if(length+1 <= n) // если число "поместилось", но осталось место еще для одного символа, тоже добавляем "+"

{

length += 1;

if(length == n)

return max_q;

}

return max_q; // такая ситуация невозможна

}

int line(int i) // печать i-той строки

{

int length=0;

for(int jj=i; true; jj++)

{

int j = jj % max_q; // формула циклического сдвига чисел в строке

int elem = element(j); // число которое мы будем выводить

int length_el = length_of_element(elem); // длина числа

if(length + length_el <= n) // если полученная нами длина все еще меньше заданного количества столбцов, мы выводим число

{

length += length_el;

cout << elem;

if(length == n)

{

cout << endl;

return length;

}

else // если длина получается больше, мы "отрезаем" от числа нужное количество символов

{

int excess = length+length_el-n;

for(int z = 0; z < excess; ++z) elem /= 10;

cout << elem << endl;

return length;

}

if(length + 1 <= n) // проверяем, нужно ли выводить "+"

{

length += 1; cout << "+";

if(length == n)

{

cout << endl;

return length;

}

return 0;

}

int main()

{

cin >> m >> n; // параметры таблицы

max_q = max_quantity(); // вычисляем максимально возможное количество чисел в строке

for(int i=0; i<m; i++) line(i); // вывод таблицы

return 0;

}

Алгоритм

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

[latex]n^2+4\cdot(n^2-n)[/latex]

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

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

Чтобы число столбцов [latex]n[/latex] соответствовало числу символов в каждой строке, мы выводим числа по одному, каждый раз проверяя, не превысила ли общая длина строки заданное число [latex]n[/latex]. Если длина все-таки получается больше, мы выводим то количество символов, которое помещается в данную строку, а остальные отбрасываем.

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

Related Images:

MLoops8

07/11/2015 by Настя Филипчук

Задача

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

Два числа:количество столбцов и строк.

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

Таблица размером n*m со следующей закономерностью:

+21++21++21++21++21++21++
1++21++21++21++21++21++21
+21++21++21++21++21++21++
1++21++21++21++21++21++21
+21++21++21++21++21++21++
1++21++21++21++21++21++21
+21++21++21++21++21++21++
1++21++21++21++21++21++21

Код

#include <iostream>
using namespace std;
int main(){
	int m,n; 
	cin>>n>>m;
	for(int i=1;i<m+1;i++){ 
		for(int j=1;j<n+1;j++){  
			if(i%2==0){
				if ((j+3)%4==0) 
					cout<< "1"; 
				else 
					cout<<(j%4==0?"2":"+");
			}
			else{
				if ((j+1)%4==0)
					cout<<"1";
				else 
					cout<<((j+2)%4==0?"2":"+");
			}
		}
	cout<<endl;
	}	
	return 0;
}

#include <iostream>

using namespace std;

int main(){

int m,n;

cin>>n>>m;

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

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

if(i%2==0){

if ((j+3)%4==0)

cout<< "1";

else

cout<<(j%4==0?"2":"+");

}

else{

if ((j+1)%4==0)

cout<<"1";

else

cout<<((j+2)%4==0?"2":"+");

}

cout<<endl;

}

return 0;

}

Упрощенный вариант

#include <iostream>
using namespace std;
int main()
{
	int m,n; 
	cin>>n>>m;
	for(int i=1;i<m+1;i++)
	{ 
		for(int j=1;j<n+1;j++)
		{  
			if( ((i%2==0) && ((j+3)%4==0))||((i%2!=0) && ((j+1)%4==0)))
			{
				cout<< "1"; 
			}
			if ((j+3-2*(i%2))%4!=0)
			{
				cout<<((j+2*(i%2))%4==0?"2":"+");
			}
		}
		cout<<endl;
	}	
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int m,n;

cin>>n>>m;

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

{

for(int j=1;j<n+1;j++)

{

if( ((i%2==0) && ((j+3)%4==0))||((i%2!=0) && ((j+1)%4==0)))

{

cout<< "1";

}

if ((j+3-2*(i%2))%4!=0)

{

cout<<((j+2*(i%2))%4==0?"2":"+");

}

cout<<endl;

}

return 0;

}

Тесты

[latex]n[/latex]	[latex]m[/latex]	Выходные данные
1	1	+
7	7	+21++21 1++21++ +21++21 1++21++ +21++21 1++21++ +21++21
15	6	+21++21++21++21 1++21++21++21++ +21++21++21++21 1++21++21++21++ +21++21++21++21 1++21++21++21++
25	8	+21++21++21++21++21++21++ 1++21++21++21++21++21++21 +21++21++21++21++21++21++ 1++21++21++21++21++21++21 +21++21++21++21++21++21++ 1++21++21++21++21++21++21 +21++21++21++21++21++21++ 1++21++21++21++21++21++21

Решение

Для решения сначала нужно найти закономерность чередования символов в таблице. Пусть нумерация столбцов и строк будет начинаться с единицы, тогда, если строка [latex]i \vdots 2[/latex], то символы в ней чередуются по такому принципу: если результат от прибавления номера столбца к 1 кратен 4 ([latex] (j+1)\vdots 4 [/latex]), то в данной строке и столбце находится «1», если же результат от прибавления номера столбца к 2 кратен 4([latex] (j+2)\vdots 4 [/latex]), то в данной строке и столбце находится «2», если ни одно из этих условий не выполняется, значит на данном месте находится «+».

Если же строка [latex]i\vdots 2[/latex], то символы в ней чередуются по такому принципу: если результат от прибавления номера столбца к 3 кратен 4 ([latex] (j+3)\vdots 4[/latex]), то в данной строке и столбце находится «1», а если номер столбца кратен 4([latex] j\vdots 4 [/latex]), то в данной строке и столбце находится «2», если ни одно из этих условий не выполняется, значит на данном месте находится «+».

Ссылки

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

Упрощенный код

Related Images:

MLoops 14

02/11/2015 by Александр Коломеец

MLoops14.

Постановка задачи

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex]n > 0[/latex] (количество столбцов) и [latex]m > 0[/latex] (количество строк).
Замечание 1. В некоторых задачах появляется дополнительный параметр [latex]k < n[/latex].
Замечание 2. Многоточие означает продолжение последовательности.

123...k123...k123...k123...k
++++++1++++++1++++++1++++++1
++++++2++++++2++++++2++++++2
++++++3++++++3++++++3++++++3
++++++.++++++.++++++.++++++.
++++++.++++++.++++++.++++++.
++++++.++++++.++++++.++++++.
++++++k++++++k++++++k++++++k
123...k123...k123...k123...k
++++++1++++++1++++++1++++++1
++++++2++++++2++++++2++++++2

123...k123...k123...k123...k

++++++1++++++1++++++1++++++1

++++++2++++++2++++++2++++++2

++++++3++++++3++++++3++++++3

++++++.++++++.++++++.++++++.

++++++k++++++k++++++k++++++k

123...k123...k123...k123...k

++++++1++++++1++++++1++++++1

++++++2++++++2++++++2++++++2

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

Легко заметить, что строки с номерами [latex]1 + i \left( k + 1 \right), i \in \mathbb{N}_0[/latex] состоят из натуральных чисел от 1 до k. Также в таблице есть столбцы, совпадающие с первой строкой. Все остальные клетки заполнены символом «+».

Тесты

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

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

[latex]n[/latex]

[latex]m[/latex]

[latex]k[/latex]

1
1

11111

121
+1+
+2+
121

121

+1+

+2+

121

1234123412
+++1+++1++
+++2+++2++
+++3+++3++
+++4+++4++
1234123412
+++1+++1++
+++2+++2++
+++3+++3++
+++4+++4++

1234123412

+++1+++1++

+++2+++2++

+++3+++3++

+++4+++4++

1234123412

+++1+++1++

+++2+++2++

+++3+++3++

+++4+++4++

123456789101112345678910111234567
++++++++++++1++++++++++++1+++++++
++++++++++++2++++++++++++2+++++++
++++++++++++3++++++++++++3+++++++
++++++++++++4++++++++++++4+++++++
++++++++++++5++++++++++++5+++++++
++++++++++++6++++++++++++6+++++++
++++++++++++7++++++++++++7+++++++
++++++++++++8++++++++++++8+++++++
++++++++++++9++++++++++++9+++++++
+++++++++++10+++++++++++10+++++++
+++++++++++11+++++++++++11+++++++
123456789101112345678910111234567
++++++++++++1++++++++++++1+++++++
++++++++++++2++++++++++++2+++++++
++++++++++++3++++++++++++3+++++++
++++++++++++4++++++++++++4+++++++
++++++++++++5++++++++++++5+++++++
++++++++++++6++++++++++++6+++++++
++++++++++++7++++++++++++7+++++++
++++++++++++8++++++++++++8+++++++
++++++++++++9++++++++++++9+++++++

123456789101112345678910111234567

++++++++++++1++++++++++++1+++++++

++++++++++++2++++++++++++2+++++++

++++++++++++3++++++++++++3+++++++

++++++++++++4++++++++++++4+++++++

++++++++++++5++++++++++++5+++++++

++++++++++++6++++++++++++6+++++++

++++++++++++7++++++++++++7+++++++

++++++++++++8++++++++++++8+++++++

++++++++++++9++++++++++++9+++++++

+++++++++++10+++++++++++10+++++++

+++++++++++11+++++++++++11+++++++

123456789101112345678910111234567

++++++++++++1++++++++++++1+++++++

++++++++++++2++++++++++++2+++++++

++++++++++++3++++++++++++3+++++++

++++++++++++4++++++++++++4+++++++

++++++++++++5++++++++++++5+++++++

++++++++++++6++++++++++++6+++++++

++++++++++++7++++++++++++7+++++++

++++++++++++8++++++++++++8+++++++

++++++++++++9++++++++++++9+++++++

Реализация

ideone: ссылка

#include <iostream>
using namespace std;

struct point {
	
	int abscissa, ordinate;
	
	point() {
	    abscissa = 0;
	    ordinate = 0;
	}
	
	point(int x, int y) {
		abscissa = x;
		ordinate = y;
	}
	
	void setX(int x) {
	    abscissa = x;
	}
	
	void setY(int y) {
	    ordinate = y;
	}
	
	int getX() {
		return abscissa;
	}
	
	int getY() {
		return ordinate;
	}
	
};

struct size {
	
	int width, height;
	
	size() {
	    width = 0;
	    height = 0;
	}
	
	size(int w, int h) {
		width = w;
		height = h;
	}
	
	int getWidth() {
		return width;
	}
	
	int getHeight() {
		return height;
	}
	
};

struct screen {
	
	size dimension; // dimension of the screen
	point cursor; // position of the cursor
	char **arr; // array that represents characters on the screen
	
	// allocates the memory for the array and sets its dimension
	screen(size d) {
		dimension = d;
		arr = new char*[dimension.getWidth()];
		for(int i = 0; i < dimension.getWidth(); i++) {
			arr[i] = new char[dimension.getHeight()];
		}
	}
	
	// deallocates the memory for the array
	void deallocate() {
		for(int i = 0; i < dimension.getWidth(); i++) {
    		delete[] arr[i];
		}
		delete[] arr;
	}
	
	// fills each cell by character c
	void fill(char c) {
	    for(int i = 0; i < dimension.getWidth(); i++) {
	        for(int j = 0; j < dimension.getHeight(); j++) {
	            arr[i][j] = c;
	        }
	    }
	}
	
	// print integer where cursor is located and returns position of the cursor
	point print(int i) {
	    return print(to_string(i));
	}
	
	// print string where cursor is located and returns position of the cursor
	point print(string s) {
		for(int i = 0; i < s.length(); i++) {
		    arr[cursor.getX()][cursor.getY()] = s.at(i);
		    moveCursor();
		}
		return cursor;
	}
	
	// moves cursor to the right
	void moveCursor() {
		cursor.setX(cursor.getX() + 1 == dimension.getWidth() ? 0 : cursor.getX() + 1);
		cursor.setY(cursor.getX() == 0 ? cursor.getY() + 1 : cursor.getY());
	}
	
	
	// moves cursor to the point p
	void moveCursor(point p) {
		cursor.setX(p.getX());
		cursor.setY(p.getY());
	}
	
	// returns char located at point p
	char getChar(point p) {
	    return arr[p.getX()][p.getY()];
	}
	
	// returns dimension of the screen
	size getSize() {
		return dimension;
	}
	
};

// returns length of integer
int length(int number) {
    int result = 1;
    while((number /= 10) > 0) {
        result++;
    }
    return result;
}

// returns sum of lengths of integers from from to to
int length(int from, int to) {
    int result = 0;
    for(int i = from; i <= to; i++) {
        result += length(i);
    }
    return result;
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    screen screen(size(length(1, k), k + 1));
    screen.fill('+');
    for(int i = 1; i <= k; i++) {
        screen.print(i);
    }
    for(int i = 1; i <= k; i++) {
    	screen.moveCursor(point(screen.getSize().getWidth() - length(i), i));
    	screen.print(i);
    }
    for(int row = 0; row < m; row++) {
        for(int col = 0; col < n; col++) {
            cout << screen.getChar(point(col % screen.getSize().getWidth(), row % screen.getSize().getHeight()));
        }
        cout << endl;
    }
    screen.deallocate();
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

#include <iostream>

using namespace std;

struct point {

int abscissa, ordinate;

point() {

abscissa = 0;

ordinate = 0;

}

point(int x, int y) {

abscissa = x;

ordinate = y;

}

void setX(int x) {

abscissa = x;

}

void setY(int y) {

ordinate = y;

}

int getX() {

return abscissa;

}

int getY() {

return ordinate;

}

};

struct size {

int width, height;

size() {

width = 0;

height = 0;

}

size(int w, int h) {

width = w;

height = h;

}

int getWidth() {

return width;

}

int getHeight() {

return height;

}

};

struct screen {

size dimension; // dimension of the screen

point cursor; // position of the cursor

char **arr; // array that represents characters on the screen

// allocates the memory for the array and sets its dimension

screen(size d) {

dimension = d;

arr = new char*[dimension.getWidth()];

for(int i = 0; i < dimension.getWidth(); i++) {

arr[i] = new char[dimension.getHeight()];

}

// deallocates the memory for the array

void deallocate() {

for(int i = 0; i < dimension.getWidth(); i++) {

delete[] arr[i];

}

delete[] arr;

}

// fills each cell by character c

void fill(char c) {

for(int i = 0; i < dimension.getWidth(); i++) {

for(int j = 0; j < dimension.getHeight(); j++) {

arr[i][j] = c;

}

// print integer where cursor is located and returns position of the cursor

point print(int i) {

return print(to_string(i));

}

// print string where cursor is located and returns position of the cursor

point print(string s) {

for(int i = 0; i < s.length(); i++) {

arr[cursor.getX()][cursor.getY()] = s.at(i);

moveCursor();

}

return cursor;

}

// moves cursor to the right

void moveCursor() {

cursor.setX(cursor.getX() + 1 == dimension.getWidth() ? 0 : cursor.getX() + 1);

cursor.setY(cursor.getX() == 0 ? cursor.getY() + 1 : cursor.getY());

}

// moves cursor to the point p

void moveCursor(point p) {

cursor.setX(p.getX());

cursor.setY(p.getY());

}

// returns char located at point p

char getChar(point p) {

return arr[p.getX()][p.getY()];

}

// returns dimension of the screen

size getSize() {

return dimension;

}

};

// returns length of integer

int length(int number) {

int result = 1;

while((number /= 10) > 0) {

result++;

}

return result;

}

// returns sum of lengths of integers from from to to

int length(int from, int to) {

int result = 0;

for(int i = from; i <= to; i++) {

result += length(i);

}

return result;

}

int main() {

int n, m, k;

cin >> n >> m >> k;

screen screen(size(length(1, k), k + 1));

screen.fill('+');

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

screen.print(i);

}

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

screen.moveCursor(point(screen.getSize().getWidth() - length(i), i));

screen.print(i);

}

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

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

cout << screen.getChar(point(col % screen.getSize().getWidth(), row % screen.getSize().getHeight()));

}

cout << endl;

}

screen.deallocate();

return 0;

}

Related Images:

MLoops 23

01/11/2015 by Сплошнов Кирилл

Условие

0, 1, 8, 27, 64, 125, 216
, 343, 512, 729, 1000, 13
31, 1728, 2197, 2744, 337
5, 4096, 4913, 5832, 6859
, 8000, 9261, 10648, 1216
7, 13824, 15625, 17576, 1
9683, 21952, 24389, 27000
, 29791, 32768, 35937, 39

0, 1, 8, 27, 64, 125, 216

, 343, 512, 729, 1000, 13

31, 1728, 2197, 2744, 337

5, 4096, 4913, 5832, 6859

, 8000, 9261, 10648, 1216

7, 13824, 15625, 17576, 1

9683, 21952, 24389, 27000

, 29791, 32768, 35937, 39

Тесты

[latex]n \times {m}[/latex]	Выходные данные
[latex]2 \times {2}[/latex]	0, _1
[latex]2 \times {10}[/latex]	0, _1 , 8, _2 7, _6 4, _1 25
[latex]5 \times {5}[/latex]	0, 1, _8, 2 7, 64 , 125 , 216
[latex]20 \times {1}[/latex]	0, 1, 8, 27, 64, 125
[latex]22 \times {10}[/latex]	0, 1, 8, 27, 64, 125, 216, 343, 512, 729, 10 00, 1331, 1728, 2197, 2744, 3375, 4096, 4913 , 5832, 6859, 8000, 92 61, 10648, 12167, 1382 4, 15625, 17576, 19683 , 21952, 24389, 27000, _29791, 32768, 35937, 39304, 42875, 46656, 5

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

Решение

Нетрудно заметить, что данная последовательность содержит кубы натуральных чисел, разделенные запятой с пробелом (единственное отличие, первое число — ноль). Очевидно, понадобится использовать 2 цикла, внешний (для строк) и внутренний (для столбцов). Для простоты я попробовал составить алгоритм так, чтобы:

а) во внешнем цикле не было ничего, кроме перехода на новую строку;

б) за один шаг внутреннего цикла печатался ровно 1 символ.

Проанализируем ключевые моменты. Во первых, числа надо будет выводить по одной цифре за раз. Так как мы не знаем длину числа, можно воспользоваться функцией [latex]log10[/latex], но намного проще выводить число в обратном порядке (используя деление по модулю 10), поэтому при вычислении очередного куба будем сохранять его во временную переменную, а в печатаемую переменную [latex]cube[/latex] будем сохранять это число, записанное в обратном порядке, и выводить его на экран также в обратном порядке (таким образом, получая исходный порядок).

Как только число стало ноль, нужно вывести запятую, затем пробел. Запятую будем выводить сразу вместо очередной цифры числа, для пробела заведем логическую переменную [latex]addSpacebar[/latex], которую будем проверять вначале каждого шага внутреннего цикла.

Единственный недочет — числа вроде 1000, так как при инверсии получим 0001, то есть число 1. Я решил эту проблему, заведя переменную [latex]zeros[/latex], хранящую кол-во таких нулей. Начальное число ноль тоже учтено в коде (см. комментарии).

Код

#include <iostream>
using namespace std;

int main() 
{
	int n, m;
	cin >> n >> m;
	long num = 0, cube = 0;
	bool addSpacebar = false;
	int zeros = 0;
	for (int i = 0; i < m; i ++)
	{
		for (int j = 0; j < n; j ++)
		{
			if (addSpacebar) //если необходим пробел
			{
				cout << " ";
				addSpacebar = false;
			}
			else if (cube > 0 || num + j == 0) //печатаем текущую цифру пока число больше нуля, num + j == 0 позволяют напечатать число 0
			{
				cout << cube % 10;
				cube /= 10;
			}
			else if (zeros > 0) //если закончили печатать число, но у него остались "потерянные" нули, выводим их пока не закончатся
			{
				cout << 0;
				zeros --;
			}
			else //иначе
			{
				cout << ","; //печатаем запятую
				addSpacebar = true; //запоминаем, что нужен пробел
				num ++;
				long L = num * num * num; //получаем куб следующего числа
				while (L > 0) //записываем его в обратного порядке
				{
					cube *= 10;
					cube += L % 10;
					if (cube == 0) 
						zeros ++; //если число L заканчивалось на ноль, запоминаем его (ноль)
					L /= 10;
				}
			}
		}
		cout << endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n, m;

cin >> n >> m;

long num = 0, cube = 0;

bool addSpacebar = false;

int zeros = 0;

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

{

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

{

if (addSpacebar) //если необходим пробел

{

cout << " ";

addSpacebar = false;

}

else if (cube > 0 || num + j == 0) //печатаем текущую цифру пока число больше нуля, num + j == 0 позволяют напечатать число 0

{

cout << cube % 10;

cube /= 10;

}

else if (zeros > 0) //если закончили печатать число, но у него остались "потерянные" нули, выводим их пока не закончатся

{

cout << 0;

zeros --;

}

else //иначе

{

cout << ","; //печатаем запятую

addSpacebar = true; //запоминаем, что нужен пробел

num ++;

long L = num * num * num; //получаем куб следующего числа

while (L > 0) //записываем его в обратного порядке

{

cube *= 10;

cube += L % 10;

if (cube == 0)

zeros ++; //если число L заканчивалось на ноль, запоминаем его (ноль)

L /= 10;

}

cout << endl;

}

return 0;

}

Ссылки

Рабочий код на Ideaone.

Тут можно посмотреть саму последовательность.

Related Images:

MLoops24

01/11/2015 by Таран Таня

0 10 1110 3110 132110 1113122110
311311222110 13211321322110 1113
122113121113222110 3113112221131
1123113322110 132113213221133112
132123223110 1113122113121113222

0 10 1110 3110 132110 1113122110

311311222110 13211321322110 1113

122113121113222110 3113112221131

1123113322110 132113213221133112

132123223110 1113122113121113222

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

Количество столбцов ([latex]n > 0[/latex]) и количество строк ([latex] m > 0[/latex]) в таблице.

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

Построенная для данной последовательности таблица с соответствующим количеством столбцов и строк.

Тесты

[latex]n[/latex]

[latex]m[/latex]

Результат работы программы

0
10

0 10

1110

3110

1321

0 10

1110

3110

13211

0 111

0 10 1110 3110 132110 1113122110
311311222110 13211321322110 1113
122113121113222110 3113112221131
1123113322110 132113213221133112
132123223110 1113122113121113222

0 10 1110 3110 132110 1113122110

311311222110 13211321322110 1113

122113121113222110 3113112221131

1123113322110 132113213221133112

132123223110 1113122113121113222

0 10 1110 3110 132110 1113122110 311311222110 1321
1321322110 1113122113121113222110 3113112221131112
3113322110 132113213221133112132123222110 11131221
131211132221232112111312111213322110 3113112221131
1123113321112131221123113111231121123222110 132113
21322113311213212312311211131122211213211331121321
12211213322110 11131221131211132221232112111312111
21311121321123113213221121113122123211211131221222
1121123222110 311311222113111231133211121312211231
13111231121113311211131221121321131211132221123113

0 10 1110 3110 132110 1113122110 311311222110 1321

1321322110 1113122113121113222110 3113112221131112

3113322110 132113213221133112132123222110 11131221

131211132221232112111312111213322110 3113112221131

1123113321112131221123113111231121123222110 132113

21322113311213212312311211131122211213211331121321

12211213322110 11131221131211132221232112111312111

21311121321123113213221121113122123211211131221222

1121123222110 311311222113111231133211121312211231

13111231121113311211131221121321131211132221123113

0 10 1110

3110 13211

0 11131221

10 3113112

22110 1321

1321322110

1113122113

1211132221

Алгоритм

Для начала определим алгоритм построения предоставленной последовательности. Перед нами так называемая Look-and-Say sequence, начинающаяся с 0. Чтобы получить последующий член последовательности, нам потребуется обратиться к предыдущему и выполнить следующее:

Посчитать количество одинаковых подряд идущих цифр и записать его.
Записать саму эту цифру.

Разберем на примере:

Первый член последовательности — [latex]0[/latex] («Основание» последовательности);
Второй член последовательности — [latex]10[/latex] («Вижу» один ноль);
Третий член последовательности — [latex]1110[/latex] («Вижу» одну единицу и один ноль);
Четвертый член последовательности — [latex]3110[/latex] («Вижу» три единицы и один ноль).
…

Реализуем данное построение на практике. Создадим два вектора для хранения предыдущего и текущего члена последовательности (previousTerm и currentTerm соответственно), а также переменные для хранения номера элемента с которым ведется сравнение (изначально start [latex] = 0[/latex]) и счетчик количества совпадающих элементов (изначально quantity [latex] = 0[/latex]). Запустим цикл от первого до последнего элемента массива previousTerm и выполним ряд действий, а именно:

Пока последующие элементы совпадают с текущим сравниваемым, инкрементируем счетчик.
Как только находиться элемент не совпадающий с текущим сравниваемым, выполняем вывод количества вхождений и само число, также записываем данные значения в вектор currentTerm. Переходим к следующей цифре для сравнения и присваиваем счетчику значение [latex]1[/latex].
Отдельно выполняем предыдущий пункт для последней последовательности цифр или одной цифры, так как нет возможности сравнения с последующими.
Как только один член последовательности полностью построен, обнуляем значения индекса сравниваемой цифры и счетчика. Также очищаем вектотр previousTerm и передаем ему значения вектора currentTerm, очищаем вектор currentTerm.

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

При запуске метода сразу же увеличиваем текущий номер столбца, в который записывается символ, на [latex]1[/latex].
Далее проверяем не превышает ли номер текущего столбца возможный. Если это так, то выполняем перевод курсора на новую строку, присваиваем текущему столбцу значение [latex]1[/latex] и инкрементируем значение номера текущей строки.
Если количество строк превышает заданное, заканчиваем работу программы.
В противном же случае выполняем печать символа, если это не пробел в начале строки (если это все же пробел в начале строки, то ничего не печатаем и уменьшаем значение текущего столбца для печати). Для упрощения вывода пробел передается в метод по его коду в таблице ASCII — [latex]32[/latex]. Мы имеем полное право использовать число [latex]32[/latex] без угрозы ошибки, так как передавать мы будем только цифры [latex]0, 1, 2, 3[/latex].

Таким образом общий алгоритм работы программы можем сформулировать так:

Считываем заданное количество столбцов ([latex]n > 0[/latex]) и количество строк ([latex] m > 0[/latex]).
Для последующей работы объявляем переменные хранящие значения номера текущего столбца и строки (currentNumberColumn и currentNumberRow соответственно), два вектора для хранения предыдущего и текущего члена последовательности (previousTerm и currentTerm соответственно), а также переменные для хранения номера элемента с которым ведется сравнение (start) и счетчик количества совпадающих элементов (quantity) .
Отправляем в вектор previousTerm значение «основания» последовательности — [latex]0[/latex].
Выводим первый член последовательности и пробел после него (если потребуется).
Далее запускаем бесконечный цикл, так как окончание работы программы предусмотрено в методе ToPrint.
И выполняем последовательное построение членов последовательности (описано выше) и тут же вывод, пока количество строк не превышает заданное.

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

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

void ToPrint(int n, int m, int *currentNumberColumn, int *currentNumberRow, int symbolToPrint) {
	(*currentNumberColumn)++; // Инкрементируем значение номера столбца, так как есть символ на печать
	if (*currentNumberColumn > n) {
		cout << endl; // Переходим на новую строку
	  	(*currentNumberRow)++;
	  	*currentNumberColumn = 1; 
	} // Если следует выполнить переход на следующую строку, выполняем этот переход по всем индексам
	if (*currentNumberRow > m)
	    exit(0); // Заканчиваем работу программы, как только количество строк превышает заданное
	else if (symbolToPrint == 32 && *currentNumberColumn == 1) // В таблице ASCII 32 - пробел
	    (*currentNumberColumn)--; // Возвращаем предыдущее значение номера столбца, так как ничего не было напечатано
    else if (symbolToPrint == 32)
        cout << char(symbolToPrint); // Выводим пробел, если это не начало строки
    else
      	cout << symbolToPrint;
}

int main() {
	int n, m; // Количество столбцов и строк соответственно
	cin >> n >> m;
	int start = 0; // Индекс элемента текущей цифры с которой ведется сравнение
    int quantity = 0; // Количество идущих подряд одинаковых элементов в данном члене
    int currentNumberRow = 1; // Номер текущей строки, в которой будет записан символ
    int currentNumberColumn = 0; // Номер текущего столбца, в который будет записан символ
    vector <short> currentTerm; // Вектор, хранящий значение текущего члена последовательности
    vector <short> previousTerm; // Вектор, хранящий значение предыдущего члена последовательности
	previousTerm.push_back(0); // Записываем в вектор предыдущего члена значение первого члена последовательности
    ToPrint(n, m, &currentNumberColumn, &currentNumberRow, 0); // Выводим первый член последовательности
    ToPrint(n, m, &currentNumberColumn, &currentNumberRow, 32); // Выводим пробел после него (если он не понадобится его уберет метод ToPrint)
    while (true) {
           for (int i = 0; i < previousTerm.size(); i++) { 
    	        if (previousTerm[i] == previousTerm[start]) 
    	 	        quantity++; // Считаем количество идущих подряд одинаковых цифр
    	        else {
    		      	currentTerm.push_back(quantity); // Записываем в вектор количество текущих цифр
    	          	currentTerm.push_back(previousTerm[start]); // Записываем саму цифру
    	          	ToPrint(n, m, &currentNumberColumn, &currentNumberRow, quantity);
    	          	ToPrint(n, m, &currentNumberColumn, &currentNumberRow, previousTerm[start]); // Печатаем полученные данные
    	          	start += quantity; // Переходим к следующей цифре для сравнения
    	          	quantity = 1; // Присваиваем количеству одинаковых идущих подряд цифр 1, так как мы перешли к следующей цифре
    	        } // Если значение текущей цифры не совпадает с предыдущим, выполняем вывод и заполнение вектора следующего члена
    	        if (i == (previousTerm.size() - 1)) {
    	            currentTerm.push_back(quantity); 
    	            currentTerm.push_back(previousTerm[start]);
    	            ToPrint(n, m, &currentNumberColumn, &currentNumberRow, quantity);
    	            ToPrint(n, m, &currentNumberColumn, &currentNumberRow, previousTerm[start]);
    	        } // Отдельный вывод для последнего элемента данного члена
           } // Цикл для прохода по всем цифрам предыдущего члена последовательности
           start = 0;      
           quantity = 0; // Обнуляем все параметры для подсчета, так как дальше будем работать со следующим членом последовательности
           ToPrint(n, m, &currentNumberColumn, &currentNumberRow, 32); // Печатаем пробел после текущего члена последовательности
           previousTerm.clear(); 
           previousTerm = currentTerm; // Записываем в вектор предыдущего члена текущий построенный член последовательности
           currentTerm.clear();
    } // Бесконечный цикл, так как условие окончание работы программы задано в методе печати
}

#include <iostream>

#include <vector>

using namespace std;

void ToPrint(int n, int m, int *currentNumberColumn, int *currentNumberRow, int symbolToPrint) {

(*currentNumberColumn)++; // Инкрементируем значение номера столбца, так как есть символ на печать

if (*currentNumberColumn > n) {

cout << endl; // Переходим на новую строку

(*currentNumberRow)++;

*currentNumberColumn = 1;

} // Если следует выполнить переход на следующую строку, выполняем этот переход по всем индексам

if (*currentNumberRow > m)

exit(0); // Заканчиваем работу программы, как только количество строк превышает заданное

else if (symbolToPrint == 32 && *currentNumberColumn == 1) // В таблице ASCII 32 - пробел

(*currentNumberColumn)--; // Возвращаем предыдущее значение номера столбца, так как ничего не было напечатано

else if (symbolToPrint == 32)

cout << char(symbolToPrint); // Выводим пробел, если это не начало строки

else

cout << symbolToPrint;

}

int main() {

int n, m; // Количество столбцов и строк соответственно

cin >> n >> m;

int start = 0; // Индекс элемента текущей цифры с которой ведется сравнение

int quantity = 0; // Количество идущих подряд одинаковых элементов в данном члене

int currentNumberRow = 1; // Номер текущей строки, в которой будет записан символ

int currentNumberColumn = 0; // Номер текущего столбца, в который будет записан символ

vector <short> currentTerm; // Вектор, хранящий значение текущего члена последовательности

vector <short> previousTerm; // Вектор, хранящий значение предыдущего члена последовательности

previousTerm.push_back(0); // Записываем в вектор предыдущего члена значение первого члена последовательности

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, 0); // Выводим первый член последовательности

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, 32); // Выводим пробел после него (если он не понадобится его уберет метод ToPrint)

while (true) {

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

if (previousTerm[i] == previousTerm[start])

quantity++; // Считаем количество идущих подряд одинаковых цифр

else {

currentTerm.push_back(quantity); // Записываем в вектор количество текущих цифр

currentTerm.push_back(previousTerm[start]); // Записываем саму цифру

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, quantity);

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, previousTerm[start]); // Печатаем полученные данные

start += quantity; // Переходим к следующей цифре для сравнения

quantity = 1; // Присваиваем количеству одинаковых идущих подряд цифр 1, так как мы перешли к следующей цифре

} // Если значение текущей цифры не совпадает с предыдущим, выполняем вывод и заполнение вектора следующего члена

if (i == (previousTerm.size() - 1)) {

currentTerm.push_back(quantity);

currentTerm.push_back(previousTerm[start]);

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, quantity);

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, previousTerm[start]);

} // Отдельный вывод для последнего элемента данного члена

} // Цикл для прохода по всем цифрам предыдущего члена последовательности

start = 0;

quantity = 0; // Обнуляем все параметры для подсчета, так как дальше будем работать со следующим членом последовательности

ToPrint(n, m, &currentNumberColumn, &currentNumberRow, 32); // Печатаем пробел после текущего члена последовательности

previousTerm.clear();

previousTerm = currentTerm; // Записываем в вектор предыдущего члена текущий построенный член последовательности

currentTerm.clear();

} // Бесконечный цикл, так как условие окончание работы программы задано в методе печати

}

Ссылки

Код программы
Дополнительная информация о «Look-and-Say» sequence:
Источник 1; Источник 2; Источник 3; Источник 4;

	1	2	3	4	5	6	7	…	n
1	1	2	3	1	2	3	1	…	…
2	2	3	1	2	3	1	2	…	…
3	1	3	2	1	3	2	1	…	…
4	1	2	3	1	2	3	1	…	…
5	2	3	1	2	3	1	2	…	…
6	1	3	2	1	3	2	1	…	…
7	1	2	3	1	2	3	1	…	…
…	…	…	…	…	…	…	…	…	…
m	…	…	…	…	…	…	…	…	…

	1	2	3	4	5	6	7	…	n
1	1	2	3	1	2	3	1	…	…
2	2	3	1	2	3	1	2	…	…
3	1	3	2	1	3	2	1	…	…
4	1	2	3	1	2	3	1	…	…
5	2	3	1	2	3	1	2	…	…
6	1	3	2	1	3	2	1	…	…
7	1	2	3	1	2	3	1	…	…
…	…	…	…	…	…	…	…	…	…
m	…	…	…	…	…	…	…	…	…

	1	2	3	4	5	6	7	…	n
1	1	2	3	1	2	3	1	…	…
2	2	3	1	2	3	1	2	…	…
3	1	3	2	1	3	2	1	…	…
4	1	2	3	1	2	3	1	…	…
5	2	3	1	2	3	1	2	…	…
6	1	3	2	1	3	2	1	…	…
7	1	2	3	1	2	3	1	…	…
…	…	…	…	…	…	…	…	…	…
m	…	…	…	…	…	…	…	…	…