Ликбез для подготовки учащихся к работе с системами проверки олимпиадных задач (Язык C++). Занятие №1. Ввод/вывод данных. Арифметика.

#1. Простейшие задачиЧайка К.В.Разбор задач на C++ 1. Ввод/вывод (консоль)#include <iostream>using namespace std;int main() { int a, b; cin >> a >> b; cout << a + b << endl; return 0;} 2. Ввод/вывод (файлы)#include <fstream>using namespace std;int main() { // переопределяем потоки cin, cout ifstream cin("input.txt"); ofstream cout("output.txt"); int a, b; cin >> a >> b; // чтение cout << a + b << endl; // запись return 0;} 3. Чтение до конца файла Сумма чисел в файлеВ текстовый файл записано некоторое заранее не известное количество целых чисел, разделённых между собой пробелами или переводом строки.Вывести в другой текстовый файл сумму всех этих чисел.Входные данныеТекстовый файл input.txt содержит некоторое заранее не количество целых чисел.Выходные данныеТекстовый файл output.txt содержит одно целое число – сумму чисел из предыдущего файлаПримерВвод 3 197 8 914 5Вывод56 4. Чтение до конца файла#include <fstream>using namespace std;int main() { ifstream fin("input.txt"); ofstream fout("output.txt"); int sum = 0, x; while(fin >> x) sum += x; fout << sum;} 5. Простейшая арифметикаСчастливый туристКак только Счастливый Гарри въезжает в свой любимый кемпинг со всей семьей, он замечает знак: "Палаточное размещение ограничено 5 днями в течение любого 8 дневного периода. Гарри только начинает свой 20 - дневный отдых. Каково максимальное количество дней, когда Гарри может провести свой отпуск в лагере?Сформулируем задачу в более общем виде. Пусть l, p, v (1 < l < p < v) - целые числа. Палаточное размещение ограничено l днями в течение любого p-дневного периода. Счастливый Гарри начинает свой v-дневный отдых. Какое наибольшее число дней своего отпуска Гарри сможет провести в лагере? Входные данныеКаждый тест состоит из одной строки, содержащей числа l, p и v. Все числа являются 32-битовыми знаковыми целыми. Выходные данныеДля каждого теста вывести в одной строке количество дней, когда Счастливый Гарри может разместиться в палатке во время своего отпуска. Следуйте формату, приведенному в примере.Пример№ Ввод Вывод1 5 8 20 142 5 8 17 11 6. Счастливый турист - решениеВ общем случае задача решается формулойdays = v%p + v/p * lЭто решение не проходит при частном случае l < v < p. Например, для l = 5, v = 8, p = 6 программа выдаст 6, что неверно – правильный ответ 5. Внесём соответствующие исправления#include <iostream>using namespace std; int main() { int l, p, v, days; cin >> l >> p >> v; days = min(v % p, l) + v / p * l; cout << days;} 7. Читабельность кодаЗарплатаВ отделе работают 3 сотрудника, которые получают заработную плату в рублях. Требуется определить: насколько зарплата самого высокооплачиваемого из них отличается от самого низкооплачиваемого. Входные данныеВ единственной строке записаны размеры зарплат всех сотрудников через пробел. Каждая заработная плата – это натуральное число, не превышающее 105. Выходные данныеНеобходимо вывести одно целое число — разницу между максимальной и минимальной зарплатой. Примеры№ Ввод Вывод1 100 500 1000 9002 36 11 20 25 8. Зарплата – решение с макросомнеобходимо найти max(a, b, c) – min(a, b, c)Но шаблоны min и max в C++ предполагают использование только двух аргументов. min(a, b, c) = min(a, min(b, c)max(a, b, c) = max(a, max(b, c))#include <iostream>#define F(f) f(a,f(b,c))using namespace std;int main(){ int a, b, c; cin >> a >> b >> c; cout << F(max) - F(min);} 9. ХолодильникЧтобы поднять на N-й этаж M-этажного дома новый холодильник, Витя вызвал бригаду грузчиков. Оплата работы грузчиков производится так: за подъем холодильника на один этаж требуется заплатить 200 рублей, за спуск на один этаж — 100 рублей. За подъем и спуск на лифте плата не взимается. Несмотря на то, что в Витином доме есть лифт, ему,возможно, все же придется заплатить грузчикам, поскольку лифт останавливается только на каждом K-м этаже, начиная с первого (то есть на этажах с номерами 1, K+1, 2K+1, 3K+1, …). Требуется вычислить, какой минимальной суммы денег достаточно, чтобы грузчики доставили холодильник с первого этажа на N-й.Входные данныеВ единственной строке через пробел записаны три числа N, M, K ≤ 109.Выходные данныеЕдинственное число S– необходимая минимальная сумма для доставки холодильника. 10. Холодильник – идея решенияРазобьем дом на отдельные секции по K этажей каждая. Для заданной квартиры в секции холодильник можно поднять за сумму S1 с этажа R1 или спустить за сумму S2 с этажа R2.Выбрать S = min(S1; S2). Для верхней группы S = S1#include <iostream>using namespace std;int main(){ int n, m, k; cin >> n >> m >> k; int r1 = (n-1)/k * k + 1; //ближний снизу int r2 = r1 + k; //ближний сверху int s1 = (n-r1) * 200; //за подъем int s2 = (r2-n) * 100; //за спуск cout << (r2>m ? s1 : min(s1,s2));} 11. День программиста (acmp.ru)День программиста отмечается в 255-й день года (при этом 1 января считается нулевым днем). Требуется написать программу, которая определит дату (месяц и число григорианского календаря), на которую приходится День программиста в заданном году. В григорианском календаре високосным является: • год, номер которого делится нацело на 400• год, номер которого делится на 4, но не делится на 100Входные данныеВ единственной строке входного файла INPUT.TXT записано целое число от 1 до 9999 включительно - номер года н.э.. Выходные данныеВывести дату Дня программиста в формате DD/MM/YYYY, где DD — число, MM — номер месяца (01 — январь, 02 — февраль, ..., 12 — декабрь), YYYY — год в десятичной записи. Примеры№ Ввод Вывод1 2000 12/09/20002 2009 13/09/2009 12. День программиста - решениеНомер дня будет 12 для високосных годов и 13 для обычных. Номер месяца всегда 9. Для вывода года в требуемом формате воспользуемся флагами вывода setw– количество символов (4) и setfill– задаёт символ-заполнитель (0)#include <iostream>#include <iomanip>#define DIV(p) (year % p == 0)using namespace std;int main() { int year; cin >> year; bool leap = DIV(400) || (DIV(4) && !DIV(100)); cout << 13 - leap << "/09/" << setw(4) << setfill('0') << year;} 13. Шахматная задачаВ альтернативной Вселенной в городе Нью-Москоу (бывшие Васюки, Москва переименована в Старые Васюки) готовится межпланетный шахматный турнир. Отличие шахмат альтернативной Вселенной состоит в том, что доска для игры в шахматы является неограниченной, а координаты каждой клетки задаются в виде пары чисел (x,y). Определите, сколько из шахматных фигур (ладья, слон, ферзь, король, конь) смогут сделать ход из клетки (x1,y1) в клетку (x2,y2).…………………………-2,-2-1,-20,-21,-22,-23,-24,-2……-2,-1-1,-10,-11,-12,-13,-14,-1……-2,0-1,00,01,02,03,04,0……-2,1-1,10,11,12,13,14,1……-2,2-1,20,21,22,23,24,2……-2,3-1,30,31,32,33,34,3……-2,4-1,40,41,42,43,44,4………………………… 14. Шахматная задача - решение#include <iostream>#include <cstdlib> //описание функции absint main(){ int x1, y1, x2, y2; std::cin >> x1 >> y1 >> x2 >> y2; int dx = abs(x1-x2), dy = abs(y1-y2); bool tower = !dx || !dy ; bool elephant = (dx == dy); bool queen = tower || elephant; bool king = (dx<=1 && dy<=1); bool horse = (dx * dy == 2); std::cout << tower + elephant + queen + king + horse;} 15. Побитовые операцииBig и little endianПри представлении целых чисел в памяти компьютера используется несколько подходов (моделей). При модели big endian вначале идут старшие байты, затем младшие, а в модели little endian всё наоборот.Устройство, использующее big endian, записало число из 4 байт в файл (записав напрямую байты, а не представление числа в 10-чной системе счисления). Файл затем передали без изменений устройству, использующему little endian. Какое число считало второе устройство из этого файла, если изначальное число было равно K?Входные данныеЕдинственное целое число K, для хранения которого в памяти компьютера используется 4 байта (со знаком).Выходные данныеЧисло, которое получилось из исходного при использовании модели little endian вместо исходной big endian.ПримерВвод Вывод1564357196 1278361181 16. Big и little endian - решение#include <iostream>int main() { int n, byte, n1 = 0; std::cin >> n; for (int i = 0; i < 4; i++){ byte = n % 256; n >>= 8; // на 8 бит вправо (n1 <<= 8) += byte; // на 8 бит влево и } // и добавление байта std::cout << n1;} 17. Быстрый НОД (алгоритм Евклида)Найти наибольший общий делитель (НОД) двух целых неотрицательных чиселОписание алгоритма нахождения НОД делением1. Большее число делим на меньшее.2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла).3. Если есть остаток, то большее число заменяем на остаток от деления.4. Переходим к пункту 1.ПримерНайти НОД для 30 и 18.30 / 18 = 1 (остаток 12)18 / 12 = 1 (остаток 6)12 / 6 = 2 (остаток 0). Конец: НОД – это делитель. НОД (30, 18) = 6 18. Алгоритм Евклида - решение#include <fstream>using namespace std; int main(){ ifstream cin("input.txt"); ofstream cout("output.txt"); unsigned long long a, b; cin >> a >> b; do{ if (a >= b) a %= b; else b %= a; } while (a && b); cout << a + b; } 19. Таймер (acmp.ru)Таймер определяет, когда должен быть подан звуковой сигнал. Входные данныеВ первой строке записано текущее время в формате ЧЧ:ММ:СС (с ведущими нулями). При этом оно удовлетворяет ограничениям: ЧЧ - от 00 до 23, ММ и СС - от 00 до 60. Во второй строке записан интервал времени, который должен быть измерен. Интервал записывается в формате Ч:М:С (где Ч, М и С - от 0 до 109, без ведущих нулей). Например, 100:60 на самом деле означает 100 минут 60 секунд, то же самое, что 101:0 или 1:41:0. А 42 обозначает 42 секунды. Выходные данныеВыведите в формате ЧЧ:ММ:СС время, во сколько прозвучит звуковой сигнал. При этом если сигнал прозвучит не в текущие сутки, то дальше должна следовать запись +<кол во> days. Например, если сигнал прозвучит на следующий день – то +1 days. № INPUT.TXT OUTPUT.TXT1 01:01:01 48:0:0 01:01:01+2 days2 01:01:01 58:119 02:01:003 23:59:59 1 00:00:00+1 days 20. Таймер - решение#include <iostream>#define O(x) (x>9 ? "" : "0") << x // макрос для выводаusing namespace std;long long h, m, s, d, time;int main(){ char c; cin >> h >> c >> m >> c >> s; time = h * 3600 + m * 60 + s; m = 0; do{ cin >> s; (m *= 60) += s; } while (cin >> c); time += m; s = time % 60; m = time / 60 %60; h = time / 3600 % 24; d = time / 86400; cout << O(h) << ':' << O(m) << ':' << O(s); if(d) cout << '+' << d << " days";} Slide TitleMake Effective PresentationsUsing Awesome BackgroundsEngage your AudienceCapture Audience Attention Slide TitleProduct AFeature 1Feature 2Feature 3Product BFeature 1Feature 2Feature 3