повторы | C++ для приматов

Код 1

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

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

int* a = new int[n];

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

{

cin >> a[i];

}

int diffNum = 0;

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

{

bool newNum = true;

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

{

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

{

newNum = false;

break;

}

if (newNum == true)

{

diffNum++;

}

cout << diffNum;

return 0;

}

Код 1(without break)

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

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

int* a = new int[n];

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

}

int diffNum = 0;

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

{

bool newNum = true;

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

{

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

{

newNum = false;

}

if (newNum == true)

{

diffNum++;

}

cout << diffNum;

return 0;

}

Решение

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

Код 2

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

#include <iostream>

using namespace std;

#include

int main() {

vector a(202, false);

int n, diffNum, curVal;

cin >> n;

diffNum = n;

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

{

cin >> curVal;

if(a[curVal + 100])

{

diffNum--;

}

else

{

a[curVal + 100] = true;

}

cout << diffNum << endl;

return 0;

}

Решение

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

Условие (OCPC-2015)

Дана последовательность из [latex]n[/latex] чисел: [latex]x_0[/latex], [latex]x_1[/latex], [latex]x_2, \ldots, x_{n-1}[/latex], где [latex]x_0[/latex] — кол-во чисел [latex]0[/latex] в данной последовательности, [latex]x_1[/latex] — кол-во чисел [latex]1[/latex], и так далее…

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

Число [latex]n[/latex] — количество членов последовательности.

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

Искомая последовательность.

Размышления над решением:

Обратим внимание, что сумма всех чисел данной последовательности является кол-вом используемых в ней чисел, что равно кол-ву членов последовательности. Иными словами, должно выполняться равенство:

[latex]x_0 + x_1 + [/latex]…[latex] + x_{n-1} = n[/latex] (1)

Далее заметим, что [latex]x_0[/latex] не может равняться нулю (ведь записав туда [latex]0[/latex], мы сразу же увеличиваем кол-во нулей до одного). Тогда [latex]x_0[/latex] равняется другому числу [latex]k[/latex], положим, большему чем 2. Тогда, [latex]x_k = 1[/latex].

Далее, положив [latex]x_1 = 2[/latex] и [latex]x_2 = 1[/latex], получаем последовательность, не нуждающуюся в дальнейших преобразованиях, в чем легко убедиться. Для наглядности:

Член последовательности	[latex]x_0[/latex]	[latex]x_1[/latex]	[latex]x_2[/latex]	…	[latex]x_k[/latex]	…
Чему равен	k	2	1	0	1	0
Комментарий	[latex]k[/latex] будет найдено ниже	Количество чисел [latex]1[/latex] равно двум	Количество чисел [latex]2[/latex] равно одному	На этом промежутке только нули	[latex]k[/latex] больше двух	На этом промежутке только нули

Теперь вычислим [latex]k[/latex]. По формуле (1):

[latex]k + 2 + 1 + 1 = n[/latex]; [latex]k = n — 4[/latex]

(Примечание: При попытки подставить другие значения вместо [latex]x_1[/latex] или [latex]x_2[/latex] получится нестабильная последовательность, членам которой не получится присвоить значения согласно условию. Положив, например, [latex]x_1 = 3[/latex], нам придется увеличить кол-во единиц, что приведет к необходимости использовать другие числа последовательности, что в итоге обязательно приведет к нарушению необходимого условия (1) — сумма уже присвоенных ненулевых чисел попросту превысит количество ее оставшихся членов. Аналогично, если присвоить [latex]x_2 = 2[/latex], и уж тем более, при внесении более «крупных» изменений в последовательность. Таким образом, найденное решение является единственным.)

Очевидно, минимальное «рабочее» значение [latex]n[/latex] равно семи (при [latex]k = 2 + 1 = 3[/latex]).

Тесты (1) :

[latex]n[/latex]	[latex]x_0[/latex]	[latex]x_1[/latex]	[latex]x_2[/latex]	[latex]x_3[/latex]	[latex]x_4[/latex]	[latex]x_5[/latex]	[latex]x_6[/latex]	[latex]x_7[/latex]	[latex]x_8[/latex]	…
7	3	2	1	1	0	0	0
8	4	2	1	0	1	0	0	0
9	5	2	1	0	0	1	0	0	0
…	[latex]n — 4[/latex]	2	1	0	…	…	…	…	…	…

Для [latex]n[/latex] меньше семи, решение (или их отсутствие) было найдено подбором.

Тесты (2) :

[latex]n[/latex]	[latex]x_0[/latex]	[latex]x_1[/latex]	[latex]x_2[/latex]	[latex]x_3[/latex]	[latex]x_4[/latex]	[latex]x_5[/latex]
1	Решений нет
2	Решений нет
3	Решений нет
4	1 2	2 0	1 2	0 0
5	2	1	2	0	0
6	Решений нет

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

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

#include <iostream>
using namespace std;

int main() 
{
	int n;
	cin >> n;
	if (n < 4 || n == 6) // особые случаи (1)
		cout << "Решений нет" << endl;
	else if (n == 4) // особые случаи (2)
    {
        cout << "1 2 1 0" << endl;
        cout << "2 0 2 0" << endl;
    }
	else if (n == 5) // особый случай (3)
		cout << "2 1 2 0 0" << endl;
	else // алгоритм для общего случая
	{
		int number[n]; // создаем массив членов последовательности
		for (int i = 0; i < n; i++) // приравниваем все числа к нулю
			number[i] = 0;
		number[0] = n - 4; // выставляем значения для ненулевых членов
		number[1] = 2;
		number[2] = 1;
		number[n - 4] = 1;
		for (int i = 0; i < n; i++) // выводим по очереди элементы последовательности на экран
			cout << number[i] << " ";
		cout << endl; 
	}
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

if (n < 4 || n == 6) // особые случаи (1)

cout << "Решений нет" << endl;

else if (n == 4) // особые случаи (2)

{

cout << "1 2 1 0" << endl;

cout << "2 0 2 0" << endl;

}

else if (n == 5) // особый случай (3)

cout << "2 1 2 0 0" << endl;

else // алгоритм для общего случая

{

int number[n]; // создаем массив членов последовательности

for (int i = 0; i < n; i++) // приравниваем все числа к нулю

number[i] = 0;

number[0] = n - 4; // выставляем значения для ненулевых членов

number[1] = 2;

number[2] = 1;

number[n - 4] = 1;

for (int i = 0; i < n; i++) // выводим по очереди элементы последовательности на экран

cout << number[i] << " ";

cout << endl;

}

return 0;

}

Также есть ссылка на рабочий код на Ideaone для желающих провести дополнительные тесты:

Ideaone.com

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

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Tag Archives: повторы

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

Задача

Вхідні дані

Вихідні дані

Тести

Код 1

Код 1(without break)

Решение

Ссылки

Код 2

Решение

Ссылки

Related Images:

Интересная последовательность

Related Images: