Понятие массива. Одномерные массивы.

Массив - именованная совокупность переменных одного типа, расположенных в памяти компьютера подряд.

Объявление статического массива аналогично объявлению простой переменной, но в квадратных скобках указывается размер массива[18] (количество элементов).

int a[5];

При этом в памяти компьютера будет выделено 5 ячеек – a[0], a[1], a[2], a[3], a[4] (индексы начинаются от нуля). Каждая из этих ячеек является переменной типа int.

int a[0]

int a[1]

int a[2]

int a[3]

int a[4]

байты

…

…

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

a[0] = a[1] = 3;     // a[0] и a[1] получают значения 3

a[2] = a[0]++;  // a[2] получает значение 3, затем a[0] - 4

a[3] = ++a[1] + 1; // a[1] получает значение 4, a[3] - 5

a[4]= a[1] + a[2]; // a[4]=7

Массивы могут быть инициализированы при объявлении:

// инициализация одномерного массива

int x[6] = {5.1, -1.2, -12.3, 9, 10.4, 0};

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

Если надо установить при инициализации все элементы в нулевое значение, то можно использовать простую конструкцию

int arr[10000] = {0,};

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

// инициализация без определения размера массива

int x[] = {5.1, -1.2, -12.3, 9, 10.4, 0};

При желании размер такого массива, если лень считать вручную, легко определить по формуле:

sizeof(x)/sizeof(int)

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

Задача №71. Подмассив массива

Пусть задан массив целых чисел а₁, а₂, ..., а_n. Назовем его подмассивом f(i, j) массив, составленный из чисел массива а_i, a_i+1,..., a_j-1, a_j. Напишите программу, которая будет выводить подмассивы массива a.

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

Первая строка входного файла INPUT.TXT содержит число n (1 ≤ n ≤ 1000) - количество элементов в массиве а. Во второй строке содержатся числа a₁, a₂, … , а_n разделенные пробелом. Все а_i находятся в диапазоне от -2³¹ до 2³¹ - 1. В третьей строке находится m (1 ≤ m ≤ 100) — количество подмассивов, которые необходимо вывести. Следующие m строк содержат пары чисел i_k, j_k (1 ≤ i_k ≤ j_k ≤ n).

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

В выходной файл OUTPUT.TXT для каждой пары (i_k, j_k) в отдельной строке выведите подмассив f(i_k, j_k).

Пример

INPUT.TXT	OUTPUT.TXT
6 1  2  3  4  5  6 5 1  1 2  6 3  4 5  6 2  4	1 2  3  4  5  6 3  4 5  6 2  3  4

Решение

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

#include <fstream>

#define SIZE 1001

using namespace std;

int main() {

ifstream fin("input.txt");

ofstream fout("output.txt");

int n, m, a[SIZE], ik, jk;

fin >> n;

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

fin >> m;

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

   fin >> ik >> jk;

   for (int j = ik; j <= jk; j++) fout << a[j-1] << " ";

   fout << endl;

} 

}

Задача №72. Типовая задача с массивом

Заполнить массив из 9 произвольных целых чисел, введенных с клавиатуры через пробел. Найти:

1. среднее арифметическое всех элементов;

2. среднее арифметическое положительных элементов;

3. значение и индекс наибольшего элемента.

 Ответ на каждую подзадачу вывести в отдельной строке.

Пример

Ввод	Вывод
12  -1  4  5  -90  -3  -8  2  1	-8.66667 4.8 12 0
-8  -1  0  -4  -2  0  -100  -31  -6	-16.8889 NO 0 2

Решение

#include <iostream>

#define SIZE 9

using namespace std;

int main(){

int a[SIZE], sum = 0, sump = 0, countp = 0, imax = 0;

for(int i = 0; i < SIZE; i++)    //заполнение массива

   cin >> a[i];

for(int i = 0; i < SIZE; i++){   // обработка массива

   sum += a[i];            // подсчет суммы

   if(a[i]>0){             // подсчет положительных

       countp++;                // количества

       sump += a[i]; // и суммы

    }

     if(a[i] > a[imax]) imax = i; // ищем максимум (и его индекс)

}

cout << (float)sum / SIZE << endl;// вывод результата

if(countp > 0) cout << (float)sump / countp;

else cout << "NO";

cout << endl << a[imax] << ' ' << imax;

}

Задача №73. Сдвиг перестановки

(Время: 1 сек. Память: 16 Мб)

Перестановкой порядка n называется последовательность из попарно различных целых положительных чисел p₁, p₂, ... , p_n, где каждое 1 ≤ p_i ≤ n. Будем говорить, что перестановка

                   q₁, q₂, ..., q_n

лексикографически меньше перестановки

                   p₁, p₂, . . . , p_n,

если существует такое i, что q_i < p_i, а для любого j < i  p_j = q_j .

Циклическим сдвигом на k перестановки p₁, p₂, ... , p_n называется последовательность

                    p_k+1, p_k+2, ..., p_n, p₁, ... , p_k.

Отметим, что любой циклический сдвиг перестановки также является перестановкой.

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

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

Первая строка входного файла INPUT.TXT содержит порядок n (1 ≤ n ≤ 10⁵) заданной перестановки. Вторая строка содержит числа p1, p2, ... , pn, отделенные друг от друга пробелами.

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

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

Пример

INPUT.TXT	OUTPUT.TXT
3 3  2  1	1  3  2

Решение

Очевидно, наименьшей лексикографической перестановкой чисел из набора 1..n будет та, которая начинается с единицы. Т.е задача сводится к тому, чтобы вначале вывести все элементы массива от 1 и до конца, а затем те, которые до единицы.

#include <cstdio>

#define SIZE 100000

#define ALL(a,b) for(i=a; i<b; i++)

 

int main() {

freopen("input.txt", "r", stdin);

freopen("output.txt", "w", stdout);

int n, i, x, a[SIZE];

scanf("%d", &n);

ALL(0,n){

     scanf("%d", &a[i]);

     if (a[i]==1) x = i;

}

ALL(x,n) printf("%d ",a[i]);

ALL(0,x) printf("%d ",a[i]);

return 0;

}

ВАЖНО: Идентификатор массива является константным указателем на его нулевой элемент. Например, для массива x[10] имя x — то же самое, что &x[0] (адрес начального элемента), а к i-му элементу массива можно обратиться, используя выражение *(x+i). Например,

float p = *(x+2);    // то же самое, что float p = x[2];

ВАЖНО: В С/C++ выполнение a[i] не включает проверку того, что i не выходит за пределы объявленного размера массива, в то время как для Паскаля она существует. Таким образом, данный фрагмент на Pascal:

m := a[i];            // := присваивание на Pascal

эквивалентен следующему на Си:

if (i>= 0 && i<n) // n – размер массива

     m = a[i];

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

int a[3];

произвести обращение к элементу, которого не существует, например a[3], то будет взято значение из 4-ой по счету от начала массива четырёхбайтной ячейки, что может дать непредсказуемый результат.

вызов

int a[0]

int a[1]

int a[2]

int a[3]

байты

…

…

массив

*(a+3)

Задача №74. NEERC (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

В полуфинале студенческого чемпионата мира по программированию NEERC (http://neerc.ifmo.ru) участвуют команды из n институтов. Участники для проведения соревнований распределяются по k залам, каждый из которых имеет размеры, достаточные для размещения всех команд от всех институтов. При этом по правилам соревнований в одном зале может находиться не более одной команды от института.

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

Напишите программу, определяющую максимальное количество команд, которые можно допустить до участия в полуфинале.

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

Первая строка содержит число n - число институтов, подавших заявки. Вторая строка входного файла содержит n чисел a₁, …, a_n (a_i - это количество команд, заявленных от института номер i). Последняя строка входного файла содержит число k - количество залов, в которых проходят соревнования.

Все числа во входном файле целые, положительные и не превосходят 10000.

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

Одно целое число - ответ на задачу.

Примеры

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

Решение

#include <iostream>

using namespace std;

int main () {

int cnt = 0, n, a[10000], k;

cin >> n;

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

   cin >> a[i];

cin >> k;

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

   cnt += min(a[i], k);

cout << cnt;

}

Задача №75. Сбор черники (acmp.ru)

(Время: 0,1 сек. Память: 16 Мб)

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

Эти кусты обладают разной урожайностью, поэтому ко времени сбора на них выросло различное число ягод – на i-ом кусте выросло a_i ягод.

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

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

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

Первая строка содержит целое число N (3 ≤ N ≤ 1000) – количество кустов черники. Вторая строка содержит N целых положительных чисел a₁, a₂, ..., a_N – число ягод черники, растущее на соответствующем кусте. Все a_i не превосходят 1000.

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

Выведите ответ на задачу.

Примеры

№	Ввод	Вывод
1	4 1  2  3  4	9
2	3 1  2  3	6

Решение

Для каждого куста найдем величину M – сколько в сумме можно собрать черники с этого куста, а также предыдущего и следующего. Очевидно, для куста с номером 0 предыдущим будет куст с номером N-1, а для куста N-1 следующим будет куст с номером 0.

#include <iostream>

int main() {

int a[1000], n, s = 0, m;

std::cin >> n;

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

   std::cin >> a[i];

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

   m = a[i] + a[i==0 ? n-1 : i-1] + a[i==n-1 ? 0 : i+1];

   if (s < m) s = m;

}

std::cout << s;

}

Задача №76. Равномерное распределение

Имеется массив, в котором 2k целых неотрицательных чисел. Из них ровно k четные и ровно k нечетные. Определите, за какое наименьшее количество перестановок можно в массиве распределить их равномерно

       {ч, н, ч, н, …} или {н, ч, н, ч, …}

За одну перестановку разрешается поменять местами два любые элемента массива.

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

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

N ≤ 100. Во второй строке через пробел N целых чисел a₁, a₂, … a_N

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

Одно число – наименьшее количество перестановок.

Решение

Очевидно, искомая величина может находиться в диапазоне от 0 до N/2. Попробуем определить величину cnt - сколько пар чисел уже на своих местах, и для которых перестановка не требуется. Такими числами будем считать те из них, у кого четность самого элемента совпадает с четностью его индекса.

#include <iostream>

#define SIZE 100

using namespace std;

int main(){

int a[SIZE], n, cnt = 0;

cin >> n;

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

   cin >> a[i];

   cnt += (a[i] % 2) && (i % 2);

}

cout << min(cnt, n/2 - cnt);

}

Порой бывают очень полезны в использовании итераторы, которые облегчают обработку (вывод, перебор и т.д.) однотипных наборов данных, таких как массивы, множества, деки, стеки, очереди… Сама по себе задача очень проста и приводится лишь для знакомства с итераторами. Приведенные итераторы описаны в библиотеках iterator и algorithm. однако вместо них мы подключим заголовочный файл bits/stdc++.h, который реализует подключение сразу практически ко всем стандартным библиотекам GNU C++, правда при этом увеличивая время компиляции программы.

Задача №77. Разворот

(Время: 1 сек. Память: 16 Мб)

Дано натуральное число N и последовательность из N элементов. Требуется вывести эту последовательность в обратном порядке.

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

В первой строке записано натуральное число N (N ≤ 10³). Во второй строке через пробел идут N целых чисел, по модулю не превосходящих 10³ - элементы последовательности.

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

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

Пример

Ввод	Вывод
3 1  2  3	3  2  1

Решение

#include <bits/stdc++.h>

#define N 1000

using namespace std;

int main() {

int a[N], n;

cin >> n;

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

     cin >> a[i];

reverse(a, a + n);

copy(a, a + n, ostream_iterator <int> (cout, " "));

}

Задача №78. Изношенная клавиатура

(Время 1 с, память 64 Мб)

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

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

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

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

Первая строка входного файла keyboard.in содержит целое число n (1 ≤ n ≤ 100) – количество клавиш на клавиатуре. Вторая строка содержит n целых чисел – с₁, с₂, … , с_n, где с_i (1 ≤ с_i ≤ 100000) – количество нажатий, выдерживаемых i-ой клавишей. Третья строка содержит целое число k (1 ≤ k ≤ 100000) – общее количество нажатий клавиш, и последняя строка содержит k целых чисел p_j (1 ≤ p_j ≤ n) – последовательность нажатых клавиш.

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

В выходной файл keyboard.out необходимо вывести n строк, содержащих информацию об исправности клавиш. Если i-ая клавиша сломалась, то i-ая строка должна содержать слово “yes” (без кавычек), если же клавиша работоспособна – слово “no”.

Пример

keyboard.in	keyboard.out
5 1  50  3  4  3 16 1  2  3  4  5  1  3  3  4  5  5  5  5  5  4  5	yes no no no yes

Решение

Для каждой клавиши с номером i поставим в соответствие число a_i – количество нажатий, через которое она будет сломана.

#include <fstream>

using namespace std;

 

int main(){

ifstream cin("keyboard.in");

ofstream cout("keyboard.out");

int a[101], n, m, i;

cin >> n;

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

     cin >> a[i];

for (cin >> m; cin >> i;)

     --a[--i];

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

     cout << (a[i] < 0 ? "yes" : "no") << endl;

}

Задача №79. Ежеминутные автобусы

(Время: 1 сек. Память: 16 Мб)

На автобусную остановку каждую минуту подходит автобус одного из маршрутов. Диспетчерская служба собрала данные за N минут – номера маршрутов каждого автобуса.

Требуется определить максимально возможное время ожидания для пассажира, желающего уехать определенным маршрутом. Т.е. в данной последовательности номеров маршрутов нужно найти два самых удаленных числа, равных между собой, между которыми нет равных им. Например, для последовательности 2, 11, 2, 2, 25, 11, 25, 11 максимальное время ожидания равно 4 (для маршрута номер 11).

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

В первой строке число N (2 ≤ N ≤ 10⁶). Во второй строке записаны N чисел – номера маршрутов. Все числа натуральные и не превышают 100. Каждый номер маршрута встречается не менее двух раз.

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

Выведите ответ на задачу.

Примеры

№	Ввод	Вывод
1	8 2  11  2  2  25  11  25  11	4
2	4 23  23  41  41	1

Решение

В массиве A_k будем запоминать, на какой минуте проходил предыдущий автобус с номером k.

#include <stdio.h>

int n, a[101], i, k, r;

int main(){

scanf("%d", &n);

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

   scanf("%d", &k);

   if(a[k])

       if(r < i - a[k]) r = i - a[k];

   a[k] = i;

}

printf("%d", r);

}

Задача №80. Две последовательности[19]

(Время: 1 сек. Память: 16 Мб)

Определим последовательности a_n и b_n следующим образом: a₁ = 2, a₂ = 3, a₃ = 4, a₄ = 7, a₅ = 13, a_n = b_n−1 + b_n−3, n > 5, b_n — последовательность чисел, не входящих в a_n, записанных в возрастающем порядке.

Таким образом, последовательность a_n будет выглядеть следующим образом: 2, 3, 4, 7, 13, 15,..., а последовательность b_n – 1, 5, 6, 8, 9, 10,....

Ваша задача состоит в том, чтобы найти a_n и b_n.

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

Целое число n (1 ≤ n ≤ 10000).

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

В первой строке выведите a_n, во второй – b_n.

Примеры

№	Ввод	Вывод
1	4	7 8
2	10	25 16
3	6578	19731 9868

Решение

Будем последовательно для каждого i до n находить A_i и B_i, при этом отслеживая величину k – индекс ближайшего к B_i элемента массива A, такого что A_k > B_i. Массивы A и B не могут содержать одинаковых элементов.

#include <iostream>

int a[10000] = {2, 3, 4, 7, 13,},

b[10000] = {1, 5, 6, 8, 9,}, n, k, i;

int main () {

std::cin >> n;

for(i = 5, k = 4; i < n; i++){

   a[i] = b[i-1] + b[i-3];

   b[i] = b[i-1] + 1;

   if(b[i] == a[k]){

       b[i]++;

       k++;

   }

}

n--;

std::cout << a[n] << '\n' << b[n];

}

Задача №81. Светофорчики

В подземелье M тоннелей и N перекрестков, каждый тоннель соединяет какие-то два перекрестка. Мышиный король решил поставить по светофору в каждом тоннеле перед каждым перекрестком. Напишите программу, которая посчитает, сколько светофоров должно быть установлено на каждом из перекрестков. Перекрестки пронумерованы числами от 1 до N.

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

Два числа N и M (0 ≤ N ≤ 100, 0 ≤ M ≤ N×(N-1)/2). В следующих M строках записаны по два числа i и j (1 ≤ i, j ≤ N), которые означают, что перекрестки i и j соединены тоннелем. Можно считать, что любые два перекрестка соединены не более, чем одним тоннелем. Нет тоннелей от перекрестка i до него самого.

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

Вывести N чисел через пробел: k-ое число означает количество светофоров на k-ом перекрестке.

Пример

Ввод	Вывод
7    10 5 1 3 2 7 1 5 2 7 4 6 5 6 4 7 5 2 1 5      3	3  3  2  2  5  2  3

Решение

#include <iostream>

int main(){

int n, m, i, j, a[100] = {0,};

std::cin >> n >> m;

while(m--) {

   std::cin >> i >> j;

   a[--i]++;

   a[--j]++;

}

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

   std::cout << a[i] << ' ';

}

Задача №82. Произведение цифр (acmp.ru)

Требуется найти наименьшее натуральное число Q такое, что произведение его цифр равно заданному числу N.

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

В единственной строке входного файла INPUT.TXT записано одно целое число N (0 ≤ N ≤ 10⁹).

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

В выходной файл OUTPUT.TXT нужно вывести искомое число Q. В том случае, если такого числа не существует, следует вывести -1.

Примеры

INPUT.TXT	OUTPUT.TXT
10	25
13	-1
90	259

Решение

#include <fstream>

#define OUT(p) {cout << p; return 0;}

using namespace std;

int main(){      

ifstream cin("input.txt");

ofstream cout("output.txt");

int n, i;

cin >> n;

short digit[10] = {0,};

if(!n) OUT(10);

if(n <= 9) OUT(n);

for(i = 9; i >= 2; i--)

   while(n % i == 0){

       digit[i]++;

       n /= i;

   }

if(n != 1) OUT(-1);

for(i = 2; i <= 9; i++)

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

       cout << i;

}

Задача №83. Нечётно повторяемый

Задан набор чисел, о которых известно, что все элементы в нем встречаются четное число раз. За исключением одного, который либо не повторяется, либо встречается нечетное число раз. Найдите этот элемент.

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

В первой строке одно целое неотрицательное число N≤10⁵– общее количество элементов в наборе.

Во второй строке N целых чисел, по модулю не превосходящих 10⁹.

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

Единственное число x, повторяющееся нечетное количество раз.

Пример

Ввод	Вывод
7 82  11  82  82  11  14  82	14

Решение

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

Но ключом к решению задачи является знание битовых операций, точнее, исключающего «или». Эта операция, примененная к двум одинаковым элементам, вернет 0. Тогда задачу становится возможным решить вообще без массива в один цикл.

#include <iostream>

int main(){

int n, a, s = 0;

std::cin >> n;

while(n--){

   std::cin >> a;

   s ^= a;

}

std::cout << s;

}

Задача №84. Статистика (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

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

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

В первой строке входного записано единственное число N – количество элементов целочисленного массива (1 ≤ N ≤ 100). Вторая строка содержит N чисел, представляющих заданный массив. Каждый элемент массива – натуральное число от 1 до 31. Все элементы массива разделены пробелом.

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

В первую строку нужно вывести числа, которые соответствуют дням месяцев, в которые Вася получил тройки, а во второй строке соответственно расположить числа месяца, в которые Вася получил четверки. В третьей строке нужно вывести «YES», если Вася может рассчитывать на четверку и «NO» в противном случае. В каждой строчке числа следует выводить в том же порядке, в котором они идут во входных данных. При выводе, числа отделяются пробелом.

Примеры

№	Ввод	Вывод
1	5 4  16  19  31  2	19  31 4  16  2 YES
2	8 29  4  7  12  15  17  24  1	29  7  15  17  1 4  12  24 NO

Решение

Самапосебезадачадостаточнотривиальна. Рассмотрим, как можно уменьшить объем кода с помощью макросов. Макрос ALL используется для организации цикла по всем индексам массива, а макрос OUT с параметром p – для вывода четных либо нечетных элементов массива соответственно. Для проверки нечетности элемента можно использовать любую из двух операций

       a[i] & 1 (побитовое «И») или a[i] % 2 (остаток от деления на 2).

Они обе будут возвращать 1 для нечетных чисел и 0 для четных.

#include <iostream>

#define SIZE 101

#define ALL for(i = 0; i < n; i++)

#define OUT(p) if(p(a[i] & 1)) cout << a[i] <<' '; cout << endl;

using namespace std;

int main() {

int n, a[SIZE], count = 0, i;

cin >> n;

ALL {

   cin >> a[i];

   count += a[i] & 1;

}

ALL OUT();

ALL OUT(!);

cout << (count > n/2 ? "NO" : "YES");

}

Задача №85. Поле чудес (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

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

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

В первой строке записано число N – количество чисел, которое назвал ведущий (2 ≤ N ≤ 30000). Во второй строке записано N чисел, на которые указывала стрелка в процессе вращения барабана. Первое число всегда совпадает с последним (в конце стрелка указывает на тот же сектор, что и в начале). Числа, записанные в секторах барабана – натуральные, не превышающие 32000.

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

Необходимо вывести одно число – минимальное число секторов, которое может быть на барабане.

Примеры

№	Ввод	Вывод
1	13 5  3  1  3  5  2  5  3  1  3  5  2  5	6
2	4 1  1  1  1	1
3	4 1  2  3  1	3

Решение

Для всех элементов массива определим периодичность, с которой набор секторов повторяется. Если такой период равен i, то для всех индексов j массива A выполняется:

где операция mod означает остаток от деления.

#include <cstdio>

#define SIZE 30000

int n, a[SIZE], i, j, r;

int main(){

scanf("%d", &n);

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

   scanf("%d", &a[i]);

r = --n;

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

   if (!(n%i)){

       for(j = 0; a[j%i]==a[j] && j<n; j++);

       if(j==n) {r = i; break;}

   }

printf("%d", r);

}

Задача №86. Билетики (acmp.ru)

(Время: 1 сек. Память: 16 Мб)

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

Информация, записанная на билете, кодируется K числами (0 или 1). При этом непосредственно на билете записывается последовательность из N чисел (N ≥ K) так, что числа, записанные на расстоянии K, совпадают. Таким образом, для проверки подлинности билета достаточно проверить, что все числа на расстоянии K совпадают. К сожалению, при считывании информации с билета иногда могут происходить ошибки — считается, что одно из чисел может исказиться (то есть 0 замениться на 1, или 1 — на 0). Такой билет все равно нужно считать подлинным. Во всех остальных случаях билет считается поддельным.

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

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

В первой строке записаны числа N и K (1 ≤ N ≤ 50000, 1 ≤ K ≤ 1000, K ≤ N). Во второй строке записано N чисел, каждое из которых является 0 или 1 — информация, считанная с билета.

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

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

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	6  2 1  0  1  0  1  0	OK 0
2	8  5 0  1  1  0  1  0  0  1	OK 2
3	6  2 1  1  1  0  0  0	FAIL

Решение

Назовём разрядом номер элемента билета, не превышающий K, а также все другие элементы, стоящие от него на кратном K расстоянии. Очевидно, что в разряде должны совпадать все числа, кроме, возможно, одного. Вначале найдём такой разряд r, в котором есть несовпадающие элементы. Если таких разрядов более одного, то билет поддельный. Если ни одного – подлинный, который был считан без ошибок. Если же такой разряд ровно один, то заведём вспомогательные массивы P0, P1– наименьшая позиция нуля и единицы, счетчики C0, C1– количество нулей и единиц в этом разряде. Далее возможны варианты

· более 1 нуля и более 1 единицы – билет поддельный

· 1 ноль и 1 единица – нужно взять MIN( P0, P1)

· ровно 1 единица и более одного нуля или наоборот – нужно взять позицию элемента, который в единственном числе.

#include <iostream>

#define SIZE 50000

#defineEND {cout<< "FAIL"; return 0;}

using namespace std;

int n, k, i, r = -1, p[] = {-1, -1}, c[] = {0, 0};

bool a[SIZE];

int main() {

cin >> n >> k;

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

   cin >> a[i];

   if(a[i] != a[i%k])

       if (r < 0) r = i % k;

       else if(r != i % k) END; //более 1 разряда не совпадает

}

if(r >= 0){                 // проверяем разряд, где есть

   for(i = r; i < n; i += k) { // не одинаковые элементы

       if(p[a[i]] < 0) p[a[i]] = i;

       c[a[i]]++;

       if(c[0]>1 && c[1]>1) END;

   }

   r = (c[0]==c[1] ? min(p[0], p[1]) : (c[0]==1 ? p[0] : p[1]));

}    

cout << "OK\n" << (r<0 ? 0 : ++r);

}

Задача №87. Решето Эратосфена

Вполне вероятно, что алгоритм, придуманный более 2000 лет назад греческим математиком Эратосфеном Киренским, был первым в своем роде. Его единственная задача – нахождение всех простых чисел до некоторого заданного числа N. Термин «решето» подразумевает фильтрацию, а именно фильтрацию всех чисел за исключением простых. Так, обработка алгоритмом числовой последовательности оставит лишь простые числа, все составные же отсеются.

Рассмотрим в общих чертах работу метода. Дана упорядоченная по возрастанию последовательность натуральных чисел. Следуя методу Эратосфена, возьмем некоторое число P изначально равное 2 – первому простому числу, и вычеркнем из последовательности все числа кратные P: 2P, 3P, 4P, …, iP (iP ≤ N). Далее, из получившегося списка в качестве P берется следующее за двойкой число – тройка, вычеркиваются все кратные ей числа (6, 9, 12, …). По такому принципу алгоритм продолжает выполняться для оставшейся части последовательности, отсеивая все составные числа в заданном диапазоне.

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

Список всех простых чисел, полученных по методу Эратосфена, от 1 до 10000 через пробел

Решение

В массиве composite[i] булевских величин будем определять истинное значение, если число i составное. По умолчанию будем полагать все числа простыми.

Для некоторого числа i имеет смысл проверять кратные ему 2×i, 3×i, 4×i, …и т.д. только если i не было отмечено как составное. В противном случае, если оно составное и имеет некоторый отличный от i делитель, то все числа, кратные i, также будут делиться на это число без остатка.

В итоге получим следующее решение

#include <iostream>

#define N 10000

int main (){

bool composite[N+1] = {false,}; // полагаем все простыми

for(unsigned int i = 2; i <= N; i++)

     if(!composite[i])         // проверка кратных

     for(unsigned int j = i; j*i <= N; j++)

           composite[i*j] = true;// помечаем составное число

 

// печатаем список простых чисел от 1 до N

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

     if(!composite[i]) std::cout << ' ' << i;

}

Следующую задачу также можно достаточно лаконично решить при помощи «решета Эратосфена»

Задача №88. Гипотеза Гольдбаха

(Время: 1 сек. Память: 16 Мб)

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

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

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

Одно чётное число N (4 ≤ N ≤ 998).

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

Необходимо вывести два простых числа, сумма которых равна числу N. Первым выводится наименьшее число.

Примеры

№	Ввод	Вывод
1	6	3  3
2	992	73  919

Решение

#include <iostream>

bool c[1000];

int n, i, j, r;

int main(){

std::cin >> n;

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

   if(!c[i]){

       if(!c[n-i]) r = i;

       for(j = 2; j * i < n; j++)

           c[i*j] = true;

   }

}

std::cout << n - r << ' ' << r;   

}

Задача №89. Робот-погрузчик

На складе имеется Nконтейнеров массой A₁, A₂, … , A_N. Робот-погрузчик может двигать контейнеры с массой, не превышающей M. Требуется переставить контейнеры на складе так, чтобы вначале были контейнеры, с которыми может работать робот-погрузчик.

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

В первой строке два натуральных числа N ≤ 1000 и M ≤ 100000.

Во второй строке N натуральных чисел A₁, A₂, … , A_N – массы контейнеров от начала склада. Каждое число не превышает 100000.

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

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

Пример

Ввод	Вывод
10 15 3 12 6 40 13 11 80 90 1 2	2

Пояснение к примеру: переставить можно контейнеры 1 и 40, 2 и 80.

Решение

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

#include <iostream>

int n, m, a[100];

int main(){

std::cin >> n >> m;

int possible = 0, moved = 0, i;

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

     std::cin >> a[i];

     if(a[i] <= m) possible++;

}

for(i = 0; i < possible; i++)

     if(a[i] > m) moved++;

std::co