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

Программа реализует диалог с пользователем в виде пар чисел X(отображает программа) и Y (вводит пользователь). Пользователь вводит

       1 – если его число меньше X

       2 – если его число больше X

       3 – если его число равно X

После того, как число отгадано, программа выводит в новой строке одно число Z–количество попыток, за которые это было сделано.

Решение

#include <iostream>

using namespace std;

int main(){

int x1 = 1, x2 = 100, x, y, count = 0;

do{

   x = (x1+x2)/2;

   count++;

   cout << "Ваше число " << x

     << "?\n1 Меньше\n2 Больше\n3 Равно\n";

   cin >> y;

   if(y==1) x2 = x;

   else x1 = x;

} while (y!=3 && x1!=x2);

cout << "Попыток: " << count;

}

Задача №62. Таймер (acmp.ru)

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

Источник задачи: Московская олимпиада по информатике 2002/2003 г.

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

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

В первой строке входного файла INPUT.TXT записано текущее время в формате ЧЧ:ММ:СС (с ведущими нулями). При этом оно удовлетворяет ограничениям: ЧЧ - от 00 до 23, ММ и СС - от 00 до 60.

Во второй строке записан интервал времени, который должен быть измерен. Интервал записывается в формате Ч:М:С (где Ч, М и С - от 0 до 10⁹, без ведущих нулей). Дополнительно если Ч=0 (или Ч=0 и М=0), то они могут быть опущены. Например, 100:60 на самом деле означает 100 минут 60 секунд, то же самое, что 101:0 или 1:41:0. А 42 обозначает 42 секунды. 100:100:100 - 100 часов, 100 минут, 100 секунд, то же самое, что 101:41:40.

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

В выходной файл OUTPUT.TXT выведите в формате ЧЧ:ММ:СС время, во сколько прозвучит звуковой сигнал. При этом если сигнал прозвучит не в текущие сутки, то дальше должна следовать запись +<кол во> days. Например, если сигнал прозвучит на следующий день – то +1 days.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	01:01:01 48:0:0	01:01:01+2 days
2	01:01:01 58:119	02:01:00
3	23:59:59 1	00:00:00+1 days

Решение

Для разделения вводимых чисел воспользуемся переменной cтипа char (односимвольный тип данных – подробнее см. гл. «Задачи с символами и строками»)

#include <fstream>

#define O(x) (x>9 ? "" : "0")<<x     // макрос для вывода в формате 00

using namespace std;

long long h, m, s, d, time;

int main(){

ifstream cin("input.txt");

ofstream cout("output.txt");

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";

}

Избавляемся от циклов

Компилировать нужно компилятором, а оптимизировать головой.

Крис Касперски

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

Задача №63. Замечательные числа

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

Назовем целое число N замечательным, если для него справедливо равенство:

       N² = (N – 1)² + M²,

где М – целое число. Даны два целых числа А и В. Найти количество замечательныхчисел из диапазона [A,B] включительно. Например, в диапазоне [1,10] таких чисел два, а именно числа 1 и 5.

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

Два целых числа А и В (1 ≤ A ≤ B ≤ 10⁹), разделенных пробелом.

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

Единственная строка - количество замечательных чисел из заданного диапазона.

Пример

Ввод	Вывод
1 10	2

Решение

Первое интуитивное решение задачи состоит в переборе возможных пар N и M для каждого числа диапазона [A;B]. Для больших значений B программа получит превышение лимита времени и не сможет пройти тесты. Попробуем оптимизировать перебор.

После несложных преобразований исходного равенства получим

       2×N – 1= M²

В левой части этого равенства находится нечетное число, следовательно, М тоже нечетное и принадлежит отрезку от 1 до квадратного корня из числа 2×N–1. Так как максимальное значение N равно В, то правая граница отрезка, содержащего М, равна квадратному корню из числа 2*1000000000-1. Эта величина меньше 50000.

#include <iostream>

using namespace std;

int main() {

int a, b, cnt = 0, n;

cin >> a >> b;

for(int m = 1; m*m <= 2e9; m += 2){

   n = (m*m + 1)/2;

   if (a<=n && n<=b) cnt++;

}

cout << cnt;

}

Второй лучший способ состоит в том, чтобы вообще избавиться от перебора. Найдем наименьшее нечетное m₁, такое что

и наибольшее нечетное m₂, такое что

Очевидно, нечетных чисел от m₁ до m₂ всего

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int a, b, cnt = 0, n;

cin >> a >> b;

a = sqrt(2*a - 1);

if (a%2 == 0) a++;

b = sqrt(2*b - 1);

if (b%2 == 0) b--;

cnt = (b-a)/2 + 1;

cout << cnt;

}

Задача №64. Рассадка гостей

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

Требуется написать программу, которая по заданным числам N и M определит, сколько существует способов рассадки, чтобы сидящие на соседних местах гости находились на равном расстоянии друг от друга.

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

Входной поток содержит два целых числа n и m (0 ≤ m , n ≤ 1000).

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

Вывести одно целое число — искомое число способов.

Пример

№	Ввод	Вывод
1	8  4	7

Пояснение к примеру

Если обозначить сидящего гостя за 1, а свободное место за 0, то возможны следующие выборы кресел 11110000, 01111000, 00111100, 00011110, 00001111, 10101010, 01010101.

Решение

Зафиксируем расстояние между гостями после рассадки. Пусть оно равно d,

Гости с зафиксированным расстоянием образуют систему – отрезок длины m+(m-1)*d, который можно “двигать” по отрезку длины n.

Таким образом имеется n – d*(m – 1) – m + 1 способов рассадить гостей. Суммируя по всем d, получаем ответ.

n

d

d

Код выглядит так:

#include <iostream>

int main() {

int n, m, s = 0;

std::cin >> n >> m;

if (!m) s = 1;

else

   if (m==1) s = n;

   else

       for(int d = 1; d <= (n-1)/(m-1); d++)

           s += n - (m-1)*d;

std::cout << s;

}

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

#include<iostream>

int main() {

int n, m, s = 0;

std::cin >> n >> m;

if (!m) s = 1;

else

   if (m==1) s = n;

   else {

       int k = (n-1)/(m-1); //количество членов прогрессии

       int d = 1 - m; //шаг прогрессии

       s = (2*(n–m+1) + (k-1)*d)*k/2;

   }

std::cout << s;

}

Задача №65. Замок (acmp.ru)

Замок состоит из K уровней. Каждый уровень - это правильный N-угольник, угол которого совпадает с углом предыдущего. На сторонах первого уровня находится по две комнаты (в углах), на сторонах каждого следующего - на одну больше. Сколько в замке комнат?

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

Два целых числа N и K (3 ≤ N ≤ 10⁶; 1 ≤ K ≤ 10⁶).

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

Выведите целое число - количество комнат в замке.

Пример

INPUT.TXT	OUTPUT.TXT
6  3	28

Решение

Рассмотрим «уровни» N-угольников. Начальным уровнем является комната, от которой они начинают достраиваться. Сторона каждого следующего N-угольника содержит ровно на 1 комнату больше, чем сторона предыдущего. При этом каждый из N-угольников содержит такое же количество угловых вершин, что и предыдущий. Оно равно N-1. Отсюда выводим формулу

Полученное решение выглядит достаточно простым.

#include <iostream>

unsigned long long n, k, r = 0, s, i;

int main(){

std::cin >> n >> k;

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

   r += i;

s = 1 + (n-1)*k + (n-2)*r;

std::cout <<s;

}

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

#include <iostream>

unsigned long long n, k;

int main(){

std::cin >> n >> k;

std::cout << 1 + k*(n-1) + k*(k-1)*(n-2)/2;

}

Задача №66. Бинарные числа (acmp.ru)

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

Говорят, что плохой программист – это тот, кто считает, что в одном килобайте 1000 байт, а хороший программист – это тот, кто полагает, что в одном километре 1024 метра.

Многим эта шутка понятна, так как все знают, что в процессах, связанных с информатикой и компьютерной техникой, фигурирует множество значений, выражаемых степенью двойки, то есть чисел вида 2^K, где K – некоторое неотрицательное целое число. Назовем такие числа бинарными. Это такие числа как 2, 4, 8, 16, 32 и т.д. Действительно, когда речь идет о размере памяти или о разрешении экрана монитора, то мы часто наталкиваемся на бинарные числа. Все это связано с принципом хранения информации в памяти ЭВМ.

Задано целое число N. Требуется определить, является ли оно бинарным.

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

Единственное целое число N, не превосходящее 10000 по абсолютной величине.

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

Выведите YES, если заданное число является бинарным, и NO в противном случае.

Примеры

№	Ввод	Вывод
1	1024	YES
2	23	NO

Решение

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

В нашем случае aи bдолжны быть целыми.

#include <iostream>

#include <cmath>     //функция log2

using namespace std;

int main() {

int a;

double b;

cin >> a;

a = b = log2(a);

cout << (b==a ? "YES" : "NO");

}

Задача №67. Садовник (e-olymp)

Садовник посадил за день N деревьев и должен был вылить под каждое деревцо по ведру воды. Так как в день посадки шёл дождь, садовник начал поливку деревьев не в день посадки, а начиная с какого-то K-го дня.

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

Рис. 16. Иллюстрация "Исполнитель садовник" (Ступеньки к информатике)

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

Количество деревьев N. 0 < N ≤ 1000000

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

Искомое количество дней.

Пример

Ввод	Вывод
3	2
1000000	606531

Решение

Рассмотрим первое решение с помощью циклов

#include <iostream>

int main() {

int n, k, days = 0;

double waterPerTree = 0;

std::cin >> n;

while(waterPerTree <= 0.5)

waterPerTree += (double) 1 / (n - days++);

k = n - days +1;

std::cout << k;

}

Здесь days – количество дней, когда садовник поливал деревья, waterPerTree– объем воды, потраченной на дерево. Несмотря на то, что решение достаточно быстрое и проходит все тесты, его можно ускорить, заменив циклический алгоритм линейным. Воспользуемся для этого свойствами гармонических рядов. Для нахождения их частичных сумм можно применить приближенную формулу Эйлера.

где n – количество членов ряда, а γ»0,577 215 – постоянная Эйлера

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

#include <iostream>

#include <cmath>

int main() {

double n;

std::cin >> n;

std::cout << round(exp(log(n) + 0.41 / n - 0.5));

}

Задача №68. Кубы 888

Все натуральные числа, кубы которых, заканчиваются на 888, образуют возрастающую последовательность

                   a1 = 192

                   …

                   a4 = 942

                   …

По номеру элемента последовательности найти его значение

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

Одно число N из диапазона 1< N ≤ 1000000.

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

Одно число – значение a_N элемента последовательности с номером N.

Решение

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

#include <iostream>

using namespace std;

int main(){

int n, i = 1;

cin >> n;

while (n){

   i++;

   if(i * i * i % 1000 == 888) n--;

}

cout << i;

return 0;

}

Однако это решение неправильное. Точнее, частично правильное.

Несмотря на кажущуюся простоту, алгоритм очень долгий и дающий заведомо неправильные ответы для i>1290 (k=6) из-за переполнения при возведении в куб

Однако эта программа является вспомогательной и полезна при определении закономерности:

       a1=192; a2=442; a3=692; a4=942; a5=1192…

Легко увидеть, что полученные числа образуют арифметическую прогрессию с шагом 250 и первым членом 192. Если Вы – любознательный скептик, то легко методом математической индукции доказать, что если x³заканчивается на 888, то (250+x)³ также закончится на 888.

Сама программа приобретает вид

#include <iostream>

int main(){

int n;

std::cin >> n;

std::cout << 192 + 250*(n-1);

return 0;

}

ВАЖНО: Написав для задачи неправильное решение, не спешите от него избавляться. Постарайтесь «выжать» из него всё возможное. Чем больше данных Вы получите даже от неверных идей, тем эффективнее Вы будете расходовать на олимпиаде (и не только!!!) свой самый ценный ресурс – время.

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