Оператор множественного ветвления switch

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

switch (выражение) {

case значение_1: операторы_1; break;

case значение_2: операторы_2; break;

case значение_3: операторы_3; break;

…

case значение_n: операторы_n; break;

default: операторы;

}

Оператор default сработает, если будет выбран символ, не указанный ни в одном из case.

Рис. 12. Блок-схема оператора множественного ветвления switch в C++

Пример

По номеру дня недели определить его английское название (в англоязычных странах неделя начинается в воскресенье).

Решение

#include <iostream>

using namespace std;

int main() {

int day;

cin >> day;

switch(day){

  case 1: cout << "Sunday\n"; break;

  case 2: cout << "Monday\n"; break;

 case 3: cout << "Tuesday\n"; break;

  case 4: cout << "Wednesday\n"; break;

   case 5: cout << "Thursday\n"; break;

  case 6: cout << "Friday\n"; break;

   case 7: cout << "Saturday\n"; break;

   default: cout << "ERROR\n";

}

}

ВАЖНО: Если не использовать после операторов, заданных константным выражением в caseоператор break, то выполнится не только текущая группа операторов, но и следующая, вплоть до break или завершения case.

Пример

Создадим программу для кофе-машины, которая по выбору пользователя будет готовить соответствующий вариант кофе:

1. кофе с молоком и сахаром

2. кофе с сахаром

3. кофе

Решение

#include <iostream>

using namespace std;

int main() {

int coffee;

cout << "Ваш выбор:" << endl <<

      "1 - Кофе с молоком и сахаром" << endl <<

      "2 - Кофе с сахаром" << endl <<

      "3 - Кофе" << endl;

cin >> coffee;

switch (coffee) {

   case 1: cout << "добавить молоко" << endl;

   case 2: cout << "добавить сахар" << endl;

   case 3: cout << "засыпать кофе, залить водой" << endl;

}

return 0;

}

При выборе 1 программа выдаст:

добавить молоко

добавить сахар

засыпать кофе, залить водой

При выборе 2 будет выведено

добавить сахар

засыпать кофе, залить водой

Задача №24. Обмен

В рождественский вечер на окошке стояло три цветочка, слева на право: герань, крокус и фиалка. Каждое утро Маша вытирала окошко и меняла местами стоящий справа цветок с центральным цветком. А Таня каждый вечер поливала цветочки и меняла местами левый и центральный цветок. Требуется определить порядок цветов ночью по прошествии k дней.

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

Единственная строка содержит количество дней k (1 ≤ k ≤ 1000).

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

Вывести строку, содержащую три латинских буквы: "G", "C" и "V" (заглавные буквы без пробелов), описывающие порядок цветов на окошке по истечении k дней (слева направо). Обозначения: G – герань, C – крокус, V – фиалка.

Пример

Ввод	вывод
1	VGC
5	CVG

Решение

Легко заметить, что после первого дня оба преобразования приведут строку к виду VGC, после второго – CVG, а после третьего дня она вернётся к исходному состоянию GCV. Т.е. процесс является периодическим, повторяясь через каждые 2 дня.

#include <iostream>

using namespace std;

int main() {

int k;

cin >> k;

k %= 3;

switch (k) {

   case 0: cout << "GCV"; break;

   case 1: cout << "VGC"; break;

   case 2: cout << "CVG"; break;

}

}

Задача №25. Старояпонский календарь

В старояпонском календаре каждый из 12 годов носит имя зверя: крыса, бык, тигр, заяц, дракон, змея, лошадь, овца, обезьяна, петух, собака, кабан. Каждый из пяти имеет название цвета: зеленый, красный, желтый, синий, черный. Определить, какое название имеет год n, если 1984 год – год зеленой крысы.

Решение

Очевидно, т.к. цвета повторяются с периодичностью в 5 лет, а звери 12 лет, есть смысл рассмотреть остатки n-1984 на 5 и 12 соответственно

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

n -= 1984;

switch(n % 5) {

   case 0:cout << "green ";break;

   case 1:cout << "red ";break;

   case 2:cout << "yellow ";break;

   case 3:cout << "blue ";break;

   case 4:cout << "black ";break;

};

switch(n % 12) {

   case 0: cout << "rat\n"; break;

   case 1: cout << "bull\n"; break;

   case 2: cout << "tiger\n"; break;

   case 3: cout << "rabbit\n"; break;

   case 4: cout << "dragon\n"; break;

   case 5: cout << "snake\n"; break;

   case 6: cout << "horse\n"; break;

   case 7: cout << "sheep\n"; break;

   case 8: cout << "monkey\n"; break;

   case 9: cout << "rooster\n"; break;

   case 10: cout << "dog\n"; break;

   case 11: cout << "boar\n"; break;

}

}

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

Задача №26. Возраст

По введённому целому неотрицательному числу - возрасту объекта определить соответствующее правильное слово «год», «года» или «лет».

Решение

Очевидно, при выборе правильного слова играют роль только две последние цифры числа, т.е. его остаток от деления на сто. Если этот остаток 11, 12, 13 или 14, то правильным словом будет «лет». Во всех других случаях рассматривается последняя цифра (остаток от деления на 10). Для 1 – «год», 2, 3, 4 – «года», во всех других случаях «лет».

#include <iostream>

using namespace std;

int main() {

unsigned int age;

cin >> age;

age %= 100;      //выбрасываем всё, кроме двух последних цифр

if(10<age && age<15) cout << "лет"; // случаи-исключения

else

   switch(age % 10) {           // проверка последней цифры

       case 1:cout << "год"; break;

       case 2:

       case 3:

       case 4: cout << "года"; break;

       default: cout << "лет";

   }

return 0;

}

То же самое можно было получить без использования switch

#include <iostream>

using namespace std;

int main() {

int age, last;

cin >> age;

age %= 100;

last = age % 10;

if (10 < age  &&  age<15) cout << "лет";

else

   if (last == 1) cout << "год";

   else

        if (2 <= last  &&  last <= 4) cout << "года";

       else cout << "лет";

}

Циклы

Иногда мне кажется, что единственным универсумом в программировании является цикл.

Алан Перлис

Описание циклов

Цикл — управляющая конструкция языка программирования, предназначенная для организации многократного исполнения некоторого набора команд.

Цикл с параметром for

Когда кто-то говорит: «Я хочу язык программирования, который может делать все, что ему скажу», то я даю этому человеку леденец.

Алан Дж. Перлис

Цикл forиногда называют циклом с параметромили циклом со счетчиком. Чаще всего он используется в тех задачах, где известно, сколько повторений тех или иных действий (итераций) должна совершить программа.

Например, если требуется 5 раз написать слово «алгоритм»:

for(int i = 1; i <= 5; i++) cout << "Алгоритм";

Рассмотрим, что при этом происходит в программе

Параметр	Действие
i = 1;	cout << ”Алгоритм”;
i = 2;	cout << ”Алгоритм”;
i = 3;	cout << ”Алгоритм”;
i = 4;	cout << ”Алгоритм”;
i = 5;	cout << ”Алгоритм”;

Иначе говоря[12]:

       для i от1 до 5 cшагом +1 делать

                   вывод “Алгоритм”

На блок-схеме цикл с параметром можно представить так:

Рис. 13. Блок-схема цикла с параметром

Общая синтаксическая форма использования цикла for в С/С++

for(инициализация параметра; условие; изменение параметра) {

операторы;

}

Например, если требуется найти сумму всех натуральных чисел от 1 до 100, это можно сделать программой[13]:

#include <iostream>

int main(){

int sum = 0;

for(int i = 1; i <= 100; i++) sum += i;

std::cout << sum;

}

Программа выдаст ответ 5050. Т.е. i последовательно принимает значения от 1 до 100 с шагом +1. А в теле цикла sum на каждой итерации увеличивается на i. Цикл for в C/C++ не является столь жёсткой конструкцией, как, например, в языке Pascal. Те же самые действия в программе можно было выполнить и таким образом:

#include <iostream>

int main() {

int sum = 0, i = 1;

for(; i <= 100; sum += i++);

std::cout << sum;

}

В данном случае инициализация счетчика i произошла перед циклом, а в скобках после for она пропущена. А изменение счетчика в третьем параметре цикла происходит вместе с пересчётом суммы. Итерации цикла состоят из одного пустого оператора ; (точка с запятой). Но такой подход с «засовыванием» элементов цикла в другие блоки программы при написании кода использовать не рекомендуется по причине его нечитабельности. Это является плохим стилем программирования.

ВАЖНО: Принудительно выйти из цикла в программе можно с помощью оператора break. Например:

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

cout << i << ", ";

if (i == 1234) break; // выход при достижении счетчиком 1234

}

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

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

Например, если требуется ввести 100 целых чисел и нужно прервать цикл, если введено число 157.

bool stop = false;

for(int n = 100; n && !stop; n--) {

cin >> x;

stop = (x==157);

}

Задача №27. Баскетбол

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

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

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

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

Выведите номер выигравшей команды, в случае ничьей следует вывести «DRAW».

Примеры

№	Ввод	Вывод
1	26  17 13  15 19  11 14   16	1
2	14  15 17  18 20  20 15  17	2
3	15  16 18  17 10  12 14  12	DRAW

Решение

Результаты каждой игры будем считывать в переменные aи b, а в переменную sдобавлять их разность. Для повторения этого действия 4 раза применим цикл forсо счетчиком n.

#include <cstdio>

int a, b, s = 0, n = 4;

int main(){

for(; n--;){

   scanf("%d%d", &a, &b);

   s += a - b;

}

printf(s > 0 ? "1" : (s<0 ? "2" : "DRAW"));

}

Или то же самое с применением потокового ввода-вывода:

#include <iostream>

int a, b, s = 0, n = 4;

int main(){

for(; n--;){

   std::cin >> a >> b;

   s += a - b;

}

std::cout << (s > 0 ? "1" : (s < 0 ? "2" : "DRAW"));

}

Задача №28. Монетки

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

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

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

В первой строке входного файла INPUT.TXT записано натуральное число N (1 <= N <= 10000) – число монеток. В каждой из последующих N строк содержится одно целое число – 1 если монетка лежит решкой вверх и 0 если вверх гербом.

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

В выходной файл OUTPUT.TXT выведите минимальное количество монет, которые нужно перевернуть.

Пример

INPUT.TXT	OUTPUT.TXT
5 1 0 1 1 0	2

Решение

#include <fstream>

using namespace std;

int main() {

ifstream cin("input.txt");

ofstream cout("output.txt");

int n, x, count = 0;

cin >> n;

for (int m = n; m--;){

   cin >> x;

   count += x;

}

cout << min(count, n-count);

}

Задача №29. Прямоугольник с наименьшей площадью

Дано целое число N и набор из N прямоугольников, заданных своими сторонами — парами чисел (a,b). Найти минимальную площадь прямоугольника из данного набора.

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

В первой строке натуральное число N, не превосходящее 10⁹. В каждой из последующих Nстрок пара вещественных чисел a и b, разделенных пробелом.

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

Одно число – наибольшая из площадей прямоугольников.

Пример

Ввод	Вывод
3 1 2 3 4 5 2	12

Решение

#include <iostream>

int main(){

int n;

double a, b, area = 0;

std::cin >> n;

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

   std::cin >> a >> b;

   if(a * b > area) area = a * b;

}

std::cout << area;

}

Задача №30. Разбиение на части (acmp.ru)

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

Необходимо представить целое число N в виде суммы M примерно равных целых чисел. Будем считать, что числа примерно равны, если они отличаются друг от друга не более чем на единицу.

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

Два натуральных числа N и M через пробел, каждое из которых не превосходит 30000.

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

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

Примеры

№	Ввод	Вывод
1	13  4	3  3  3 4
2	72  8	9  9  9  9  9  9  9  9

Решение

#include <iostream>

 

int main(){

int n, m, i, p;

std::cin >> n >> m;

for(i = 1, p = n / m; i <= m; i++)

   std::cout << (i > m - n % m ? p + 1 : p) << ' ';

}

Задача №31. Пиратская добыча

Два пирата играли на золотые монеты. Игра состояла из трех партий:

· второй проиграл половину монет, имевшихся у него в начале игры;

· первый проиграл половину от количества монет, образовавшегося у него после первой партии;

· второй проиграл половину от количества монет, образовавшегося у него после второй партии.

В результате у первого оказалось 32 монет, а у второго – 13. Сколько монет было у первого пирата до начала игры?

Рассмотрим более общую формулировку этой же задачи:

Известно, что двое игроков сыграли N партий. В ходе каждой партии проигравший игрок отдаёт половину своих монет выигравшему игроку. Результаты всех партий известны. После всех игр у пиратов на руках A и B монет соответственно. Определить, сколько монет было на руках первого игрока перед началом первой партии.

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

В первой строке два натуральных числа A и B – количество монет у первого и второго пиратов после всех игр.

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

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

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

Пример

Ввод	Вывод
32  13 3  1  2  1	31

Решение

#include <iostream>

using namespace std;

int main(){

int a, b, n, game;

cin >> a >> b >> n;

for (; n--;){

   cin >> game;

   if (game == 1){

     a -= b;

     b += b;

   } else {

       b -= a;

       a+= a;

   }

}

cout << a;

}

Задача №32. Перепись

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

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

Во входном файле INPUT.TXT в первой строке задано натуральное число N – количество жильцов (N ≤ 100). В последующих N строках располагается информация обо всех жильцах: каждая строка содержит два целых числа: V и S – возраст и пол человека (1 ≤ V ≤ 100, S – 0 или 1). Мужскому полу соответствует значение S=1, а женскому – S=0.

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

Выходной файл OUTPUT.TXT должен содержать номер самого старшего мужчины в списке. Если таких жильцов несколько, то следует вывести наименьший номер. Если жильцов мужского пола нет, то выведите -1.

Пример

INPUT.TXT	OUTPUT.TXT
4 25  1 70  1 100  0 3  1	2

Решение

#include <fstream>

using namespace std;

int main() {

ifstream cin("input.txt");

ofstream cout("output.txt");

int n, v, s, maxage = -1, maxnum = -1;

cin >> n;

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

   cin >> v >> s;

   if(s  &&  maxage < v) {

       maxage = v;

       maxnum = i;

   }

}

cout << maxnum;

}

Задача №33. Big и little endian

При представлении целых чисел в памяти компьютера используется несколько подходов (моделей). При модели big endian вначале идут старшие байты, затем младшие, а в модели little endian всё наоборот.

Устройство, использующее big endian, записало число из 4 байт в файл (записав напрямую байты, а не представление числа в 10-чной системе счисления). Файл затем передали без изменений устройству, использующему little endian. Какое число считало второе устройство из этого файла, если изначальное число было равно K?

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

Единственное целое число K, для хранения которого в памяти компьютера используется 4 байта (со знаком).

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

Число, которое получилось из исходного при использовании модели little endian вместо исходной big endian.

Пример

Ввод	Вывод
1564357196	1278361181

Решение

#include <iostream>

int main() {

int n, byte, n1 = 0;

std::cin >> n;

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

  byte = n % 256;

  n >>= 8;           // сдвиг n на 8 бит вправо

(n1 <<= 8) += byte; // сдвиг на 8 бит влево и добавление

}                     // вычисленного значения байта

std::cout << n1;

}

Задача №34. Раскраска таблицы умножения

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

Таблицей умножения назовем таблицу размера n строк на m столбцов, в которой на пересечении i-ой строки и j-ого столбца стоит число i×j (строки и столбцы нумеруются с единицы).

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

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

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

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

Два натуральных числа n и m (1 ≤ n,m ≤ 1000).

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

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

Пример

№	INPUT.TXT	OUTPUT.TXT
1	10  10	RED : 21 GREEN : 39 BLUE : 36 BLACK : 4
2	5  2	RED : 5 GREEN : 2 BLUE : 2 BLACK : 1

Решение

#include <iostream>

#define DIV(a) (t%a==0)

int main() {

int n, m, t, i, j, red = 0, green = 0, blue = 0, black = 0;

std::cin >> n >> m;

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

   for(j = 1; j <= m; ++j){

       t = i * j;

       if (DIV(5)) blue++;

       else if(DIV(3)) green++;

           else if(DIV(2)) red++;

               else black++;

}

std::cout << "RED : " << red << "\nGREEN : " << green

     << "\nBLUE : " << blue<< "\nBLACK : " << black;

}

Задача №35. Числа Фибоначчи

Последовательность чисел Фибоначчи

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

определяется следующим образом: первые два числа 0 и 1, каждое следующее равно сумме двух предыдущих. По заданному номеру Nопределить значение члена последовательности F_N.

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

Одно целое неотрицательное число 0 < N ≤ 90.

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

Одно число F_N–член последовательности Фибоначчи с номером N.

Пример

Ввод	Вывод
81	23416728348467685

Решение

Задача достаточно проста, однако нужно учесть ограничения типов данных, а также, что пользователь может ввести 0 или 1.

#include <iostream>

using namespace std;

int main(){

unsigned long long a = 0, b = 1, c;

int n;

cin >> n;

if(n < 2) {cout << n; return 0;}

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

   c = a + b;

   a = b;

   b = c;

}

cout << c;

}

Задача №36. Снова Фибоначчи (acmp.ru)

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

Вам наверняка знакомы числа Фибоначчи: 1, 1, 2, 3, 5, 8, 13, 21... Они определяются рекуррентным соотношением: F_n = F_n-1 + F_n-2, F₀ = F₁ = 1.

Требуется найти последнюю цифру n-го числа Фибоначчи.

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

Одно целое число n (0 ≤ n ≤ 10⁸).

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

Одно число - последнюю цифру числа F_n.

Примеры

№	Ввод	Вывод
1	1	1
2	5	8

Решение

Очевидно, что нет нужды находить числа Фибоначчи целиком, т.к. это приведёт к необходимости использования длинной арифметики и существенно замедлит работу программы. Однако даже если брать только последние цифры чисел, которые определяются как остаток от деления на 10, программа всё равно не укладывается в отведённое время. В данном случае требуется проанализировать периодичность этого остатка. Период не может превышать 100 – цифры обязательно будут повторяться. Для чисел Фибоначчи установить длину периода несложно. Она составляет 60.

#include <cstdio>

int main() {

int n, a , b, c;

a = b = c = 1;

scanf("%d", &n);

(n %= 60)--;

if (n < 0) n = 59;

while(n--){

   c = a + b;

   if (c > 9) c -= 10;

   a = b;

   b = c;

}

printf("%d", c);

}

Задача №37. Бит-реверс (acmp.ru)

Целое положительное число m записывается в двоичной системе счисления, разряды (в этой записи) переставляются в обратном порядке и число переводится в десятичную систему счисления. Получившееся число принимается за значение функции B(m).

Требуется написать программу, которая для заданного m вычислит B(m).

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

Одно натуральное число m (m ≤ 10⁹).

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

Выведите значение B(m).

Примеры

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

Решение

Очевидно, последние нули двоичной записи m не учитываются в создании бит-реверсной перестановки B(m)

#include <cstdio>

int main() {

int m, b = 0;

scanf("%d", &m);

for(; m % 2 == 0; m /= 2);  //пропускаем последние нули

for(; m; m /= 2)

   (b *= 2) += m % 2;

printf("%d", b);

}

Задача №38. Ребус КТО + КОТ = ТОК

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

       КТО + КОТ = ТОК.

Разгадайте ребус.

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

Единственное число КОТ.

Решение

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

       КТО = К×100 + Т×10 + О

       КОТ = К×100 + О×10 + Т

       ТОК = Т×100 + О×10 + К

#include <iostream>

int main(){

int kto, kot, tok;

for(int k = 1; k <= 9; k++)

   for(int t = 1; t <= 9; t++)

       for(int o = 0; o <= 9; o++){

           kto = k*100 + t*10 + o;

           kot = k*100 + o*10 + t;

           tok = t*100 + o*10 + k;

           if(kto + kot == tok)

               std::cout << kot;

       }

}

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

 КТО

+КОТ

 ТОК

Очевидно, О + Т = 10 + К, т.к. если бы О + Т было равно К, то в ответе было бы ТКК.

Во втором справа столбце с учетом переноса 1 справа О + Т + 1 = 10 + О. Отсюда Т = 9. В третьем столбце К + К + 1 = Т. Значит, К = 4. Из известных соотношений находим Т = 5.

Задача №39. Гуси и кролики

У гусей и кроликов вместе N лап. Сколько может быть кроликов и гусей (указать все сочетания)?

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

Одно целое неотрицательное число N ≤ 10⁵

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

В каждой отдельной строке через пробел 2 числа – Ri, Gi- количество кроликов и количество гусей в i-ой комбинации (комбинации не должны повторяться). При отсутствии возможных комбинаций вывести 0 0 (два нуля через пробел)

Пример

Ввод	Вывод
8	0 4 1 2 2 0
17	0 0

Решение

Комбинаций нет, когда N нечетно. В других случаях упорядочим комбинации по кроликам.

#include <iostream>

using namespace std;

int main(){

int n, r, g;

cin >> n;

if (n % 2) cout << "0 0\n";

else

   for(r = 0; r <= n/4; r++){

       g = (n – 4 * r) / 2;

       cout << r << " " << g << endl;

   }            

}

Задача №40. Подарки Деда Мороза

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

Ириска весит X грамм, мандарин – Y грамм, пряник – Z грамм.

Требуется написать программу, которая определит, сколько различных вариантов подарков весом ровно W грамм может сделать Дед Мороз.

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

В единственной строке содержится четыре целых числа X, Y, Z и W (1 ≤ X, Y, Z ≤ 100, 1 ≤ W ≤ 1000).

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

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

Пример

Ввод	Вывод
10  25  15  40	3

Решение

Обозначим за a количество ирисок, за b – мандарин. Если оставшуюся часть веса в подарке удастся разделить без остатка на вес пряника, то добавляем к числу возможных комбинаций 1.

#include <iostream>

int main() {

int a, b, x, y, z, w, count = 0;

std::cin >> x >> y >> z >> w;

for(a = 0; a <= w/x; a++)

   for(b = 0; b <= (w - a*x) / y; b++)

       if ((w - a*x - b*y) % z == 0) count++;

std::cout << count;

}

Задача №41. Тест простоты

Натуральное число N называется простым, если оно делится без остатка только на себя и единицу. Определить для заданного натурального N, является ли оно простым. Лимит времени 0.1 секунда.

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

Одно целое 0 < N ≤ 4000000000.

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

Одно слово YES (без перевода строки), если N простое, либо слово NO, если N – составное.

Пример

Ввод	Вывод
1223	YES
5000001	NO

Решение

Заведём булеву переменную isprime, которая будет являться флагом (признаком) простоты N. Далее рассмотрим решение задачи и как его можно улучшить. Первое неоптимизированное решение получается достаточно просто:

#include <iostream>

int main(){

unsigned int n;

bool isprime = true;

std::cin >> n;

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

  if(n % i == 0) isprime = false; // число составное

std::cout << (isprime ? "YES" : "NO");

}

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

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

Улучшить решение задачи можно, если искать делители не в диапазоне до N-1, а до корня из N. В этом легко убедиться. Если у N есть делитель

то N представимо в виде m×k, причем для k обязательно

Иначе получаем противоречие

Крохотное исправление программы для N порядка миллиард, уменьшает время её работы в десятки тысяч раз

#include <iostream>

int main(){

unsigned int n;

bool isprime = true;

std::cin >> n;

for(int i = 2; i*i <= n; i++)    // можно исп-ть i<=sqrt(n),

   if(n%i ==0 )isprime = false; // sqrt описана в math.h

std::cout<<(isprime ? "YES" : "NO");

}

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

#include <iostream>

int main(){

unsigned int n;

std::cin >> n;

bool isprime = n%2 && n>2; //простое только нечетно

for(int i = 3; isprime && i*i<=n; i += 2)

     isprime=n % i;       //если остаток 0, прерываем цикл

std::cout << (isprime ? "YES" : "NO");

}

Задача №42. Количество простых

Для заданного натурального n найти количество простых чисел в диапазоне от 1 до n.

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

Одно число, не превышающее 10⁹

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

Одно число – количество простых чисел в заданном диапазоне.

Решение

#include <iostream>

#include <cmath>                          /* sqrt */

int main (){

int n;

std::cin >> n;

int cnt = n - 1;

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

   for (int j = sqrt(i); j>1; j--)

       if (i%j == 0) {cnt--; break;}

std::cout << cnt;

}

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

Задача №43. Олимпиада и Интернет

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

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

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

В первой строке задано 2 числа: количество участников олимпиады N и количество удлинителей K у них.

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

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

Единственное число - количество олимпиадников-"неудачников", которые останутся без постоянного подключения к сети.

Пример

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

Решение

Все удлинители дадут в сумме некоторое количество розеток. Но из K удлинителей K-1 придётся подключать к уже имеющимся.

#include <stdio.h>

 

main(){

int n, k, a, all = 0;

scanf("%d%d", &n, &k);

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

   scanf("%d", &a);

   all += a;

}

all -= k - 1;

printf("%d", n - all > 0 ? n - all : 0);

return 0;

}

Задача №44. Выравнивание холмов (acmp.ru)

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

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

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

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

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

Первая строка содержит количество N (1 < N <= 30000) точек, в которых была замерена высота. Вторая строка содержит результаты замеров – i-ое число строки содержит высоту над уровнем моря точки, находящейся на расстоянии (i-1) метр от начала участка. Все высоты – целые неотрицательные числа, не превосходящие 10000. Считайте, что между соседними точками измерений земная поверхность строго прямолинейна.

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

Выведите ответ на задачу с точностью, не меньшей 10^-5.

Примеры

№	Ввод	Вывод
1	4 0  1  1  0	0.6666666667
2	5 2  2  2  2  2	2.0000000000

Решение

Очевидно, что исходные данные описывают n-1 трапецию (см.рис), у каждой из которых высота равна единице, а основаниями являются соседние пары величин h_i. Таким образом, задача сводится к нахождению высоты прямоугольника с соснованием n-1, имеющего ту же самую площадь.

Для нахождения площади i-ой трапеции с высотой 1 воспользуемся формулой

Таким образом, общая сумма площадей всех трапеций:

Решение (синтаксис C++)	Решение (синтаксис C)
#include <iostream> #include <iomanip> using namespace std; int main(){ int n, h; double s; cin >> n >> s;     for(int i = 1; i < n; i++){    cin >> h;    s += 2 * h; }   (s -= h) /= 2 * (n - 1); cout << fixed     << setprecision(9) << s; }	#include <cstdio> int main(){ int n, h, i; double s; scanf("%d%lf", &n, &s);     for(i = 1; i < n; i++){    scanf("%d", &h);    s += 2 * h; }   (s -= h) /= 2 * (n - 1); printf("%.9lf", s); }

Задача №45. Космические захватчики (e-olymp)

Лимит времени 1 секунда. Лимит использования памяти 64 MiB

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

Рис. 14. Иллюстрация игры к задаче "Космические захватчики"

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

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