e-olymp 1327. Ладьи на шахматной доске

Задача

Ещё в детстве маленького Гарика заинтересовал вопрос: а сколькими способами на шахматной доске размером [latex]n \times n[/latex] можно расставить [latex] n [/latex] ладей так, чтобы они не били друг друга. Он очень долго решал эту задачку для каждого варианта, а когда решил — бросил шахматы.

А как быстро Вы управитесь с этой задачкой?

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

Размер шахматной доски — натуральное число, не превышающее [latex] 1000 [/latex].

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

Выведите ответ, найденный Гариком.

Тесты

Входные данные Выходные данные
2 2
10 3628800
500 122013682599111006870123878542304692625357434280319284219241
358838584537315388199760549644750220328186301361647714820358
416337872207817720048078520515932928547790757193933060377296
085908627042917454788242491272634430567017327076946106280231
045264421887878946575477714986349436778103764427403382736539
747138647787849543848959553753799042324106127132698432774571
554630997720278101456108118837370953101635632443298702956389
662891165897476957208792692887128178007026517450776841071962
439039432253642260523494585012991857150124870696156814162535
905669342381300885624924689156412677565448188650659384795177
536089400574523894033579847636394490531306232374906644504882
466507594673586207463792518420045936969298102226397195259719
094521782333175693458150855233282076282002340262690789834245
171200620771464097945611612762914595123722991334016955236385
094288559201872743379517301458635757082835578015873543276888
868012039988238470215146760544540766353598417443048012893831
389688163948746965881750450692636533817505547812864000000000
000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000
999 402387260077093773543702433923003985719374864210714632543799
910429938512398629020592044208486969404800479988610197196058
631666872994808558901323829669944590997424504087073759918823
627727188732519779505950995276120874975462497043601418278094
646496291056393887437886487337119181045825783647849977012476
632889835955735432513185323958463075557409114262417474349347
553428646576611667797396668820291207379143853719588249808126
867838374559731746136085379534524221586593201928090878297308
431392844403281231558611036976801357304216168747609675871348
312025478589320767169132448426236131412508780208000261683151
027341827977704784635868170164365024153691398281264810213092
761244896359928705114964975419909342221566832572080821333186
116811553615836546984046708975602900950537616475847728421889
679646244945160765353408198901385442487984959953319101723355
556602139450399736280750137837615307127761926849034352625200
015888535147331611702103968175921510907788019393178114194545
257223865541461062892187960223838971476088506276862967146674
697562911234082439208160153780889893964518263243671616762179
168909779911903754031274622289988005195444414282012187361745
992642956581746628302955570299024324153181617210465832036786
906117260158783520751516284225540265170483304226143974286933
061690897968482590125458327168226458066526769958652682272807
075781391858178889652208164348344825993266043367660176999612
831860788386150279465955131156552036093988180612138558600301
435694527224206344631797460594682573103790084024432438465657
245014402821885252470935190620929023136493273497565513958720
559654228749774011413346962715422845862377387538230483865688
976461927383814900140767310446640259899490222221765904339901
886018566526485061799702356193897017860040811889729918311021
171229845901641921068884387121855646124960798722908519296819
372388642614839657382291123125024186649353143970137428531926
649875337218940694281434118520158014123344828015051399694290
153483077644569099073152433278288269864602789864321139083506
217095002597389863554277196742822248757586765752344220207573
630569498825087968928162753848863396909959826280956121450994
871701244516461260379029309120889086942028510640182154399457
156805941872748998094254742173582401063677404595741785160829
230135358081840096996372524230560855903700624271243416909004
153690105933983835777939410970027753472000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000

Программный код

Алгоритм решения

Алгоритм решения данной задачи заключается в том, что нужно вычислить [latex]n! = 1\times 2\times 3\times \cdots\times n [/latex] , используя длинную арифметику ( умножение длинного числа на короткое ).
Иллюстрация для восьми ладей:

В коде № 1 разбиваем вектор на ячейки по три цифры. Но, некоторые ячейки могут иметь менее чем три цифры. С учетом того, что перенос может состоять не из трех цифр, следует выводить результат так: cout << setw(3) << setfill('0') << res[i];.
В коде № 2 разбиваем строку посимвольно.

Детали реализации

  • Безусловно, для использования векторов и строк нам понадобятся соответствующие  библиотеки: #include и #include .
  • Для вывода данных в коде № 1 стоит подключить библиотеку #include .

Ссылки :
Задача на e-olymp
Код № 1 на ideone
Код № 2 на ideone
Засчитанное решение № 1
Засчитанное решение № 2

e-olymp 1442. Одномерная Кликомания

Задача

«Одномерная Кликомания» — это логическая компьютерная игра. Для нее используется полоска размеров $1 \times N$, разбитая на $N$ квадратов $1 \times 1.$ Каждый из квадратов окрашен в красный или желтый цвет.
За один ход игрок может выбрать любой из квадратов и щелкнуть по нему мышкой. В результате компьютер выделяет на полоске группу максимальной длины, состоящую из стоящих подряд квадратов одинакового цвета и содержащую выделенный квадрат, и удаляет все квадраты из этой группы. При этом все квадраты, находящиеся правее удаленной группы (если они существуют), сдвигаются влево так, чтобы пристыковаться к квадратам, находящимся левее удаленной группы (если они существуют) и сохранить целостность полоски:
prb1442-r

Игрок может удалять группы квадратов любой длины, в том числе, состоящие из одного квадрата. Игра продолжается до тех пор, пока все квадраты не удалены.
В начале игры количество баллов у игрока равно нулю. После каждого его хода количество баллов пересчитывается. Если игрок очередным ходом удалил группу из $L$ квадратов, то вычисляется число  $X = A \cdot L + B$, где $A$ и $B$ — некоторые целочисленные константы. Если число $X$ неотрицательное, то количество баллов игрока увеличивается на $X$, иначе оно уменьшается на $-X$.
Цель игрока — набрать по окочанию игры как можно больше баллов. Напишите программу, оптимально играющую в «Одномерную Кликоманию». Программа должна получать на входе цвета всех квадратов исходной полоски, а также целые числа $A$ и $B$, и возвращать максимальное количество баллов, которое может набрать игрок по окончанию игры.

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

В первой строке задана строка, состоящая из символов $’R’/’Y’$, перечисляющих слева направо цвета всех квадратов исходной полоски. Символ $’R’$ соответствует квадрату красного цвета, а символ $’Y’$ — квадрату желтого цвета.
Во второй и третьей строках соответственно целые числа $A(1 \leq A \leq 1000)$ и $B(-100 \leq B \leq 100)$, задающие константы в формуле начисления очков за каждый сделанный ход.

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

Целое число, равное максимальному количеству очков, которое может набрать игрок по окончанию игры.

Тесты

Входные данные Выходные данные
1 YYYYYYY
73
14
525
2 RYRYRYR
100
-100
300
3 YYYRRR
1
-100
-194
4 YRYYRRRYYYYY
12
34
314

Код программы

Решение

По условию задачи необходимо определить максимальное количество очков которое можно получить в игре. Число $a$ всегда положительное и умножается на количество квадратов удалённых за один ход. В конце игры будут удалены все квадраты, а значит этот вклад в общий счёт игры равен $a \cdot n$, где $n$ — количество квадратиков в игре. Число $b$ может быть как положительным так и отрицательным. В первом случае, нам выгодно, что бы игрок совершил максимальное число ходов, то есть ровно столько, сколько содержится последовательностей из квадратиков одного цвета. Если $b$ меньше нуля, то счёт будет наибольший, если игрок сделает наименьшее количество ходов, а именно избавиться от чередования цветов и за один ход удалит все квадраты, это количество последовательностей пополам, плюс один.
Считаем необходимые данные и выводим ответ в зависимости от положительности $b$.

Ссылки

e-olymp 555. Ближайшие точки

Задача 

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

Готовясь к контрольной работе, Антон столкнулся со следующей задачей: На числовой прямой задано $n$ точек. Необходимо найти среди них две ближайшие. Расстояние между двумя точками числовой прямой $x$ и $y$ равно $|x-y|$.

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

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

Первая строка содержит количество точек $n$ $\left(2\leq n \leq 10^{5}\right)$. Вторая строка содержит $n$ различных целых чисел $x_{i}$- координаты заданных точек числовой прямой. Числа в строке разделены пробелом. Значение любой координаты  $x_{i}$ не превосходит $10^{9}$
по абсолютной величине.

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

В первой строке вывести минимальное расстояние между двумя заданными точками. Во второй строке вывести номера точек, которым соответствует найденное расстояние. Точки нумеруются натуральными числами от $1$ до $n$ в том же порядке, в котором они заданы во входе. Если ответов несколько, выведите любой из них.

Тесты

Входные данные Выходные данные
5
10 3 6 2 5
1
2 4
6
10 3 6 1 5 11
1
3 5
9
14545690 4343 -6 10 500 1100 -1 2 10
0
4 9
2
1 5
4
2 1
2
-1000000000 1000000000
2000000000
2 1
9
1 5 9 15 3 100 -1 4 10
1
8 5
10
0 1 5 10 20 100 120 250 -100 55
1
2 1

Решение

Объяснение

В начале создаётся ассоциативный контейнер, где каждой точке на прямой ставится в соответствие её номер. Попутно выполняется проверка, не было ли до этого точки с такой же координатой (тогда расстояние между ними равно $0$, соответственно). Затем, поскольку  map автоматически выполняет сортировку, сравниваем разность координат рядом стоящих элементов с текущим минимальным расстоянием, и, при необходимости, обновляем значение расстояния и индексы точек, для которых это расстояние верно.

Замечание

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

e-olymp

ideone

e-olymp 1228. Добавить все

Условие

Условие задачи отражает Вашу задачу: необходимо просто сложить числа. Но это будет унизительно если Вас попросят просто написать такую программу на языке C/C++ для заданного множества чисел. Давайте внесем в задачу оттенок изобретательности.

Введем понятие стоимости для операции сложения. Стоимость сложения двух чисел положим равным их сумме. Например, сложить числа $1$ и $10$ стоит $11$. Стоимость сложения $1,$ $2$ равна $3$. Складывать числа можно разными способами:

  • $1 + 2 = 3 \left(стоимость = 3\right), 3 + 3 = 6 \left(стоимость = 6\right), Всего = 9 $
  • $1 + 3 = 4 \left(стоимость = 4\right), 2 + 4 = 6 \left(стоимость = 6\right), Всего = 10 $
  • $2 + 3 = 5 \left(стоимость = 5\right), 1 + 5 = 6 \left(стоимость = 6\right), Всего = 11 $

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

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

Начинаются целым числом $n (2 \leqslant n \leqslant 100000)$, за которым следуют $n$ целых неотрицательных чисел (все числа меньше $100000$).

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

Вывести наименьшую стоимость сложения всех чисел.

Тесты

Ввод Вывод
$4$
$10$ $12$ $13$ $11$
$92$
$5$
$100$ $11$ $8$ $30$ $12$
$272$
$4$
$2$ $2$ $2$ $2$
$16$
$6$
$1$ $2$ $3$ $4$ $5$ $6$
$51$

Код

Решение

Стоимость сложения всех чисел будет минимальной, если на каждом следующем шаге мы будем складывать два наименьшие числа из множества $A$, состоящего из данного ряда чисел и уже вычисленных «частичных сумм». Таким образом, каждый шаг цикла поиска минимальной стоимости сложения будет состоять из нахождения двух минимальных чисел из множества, удаления этих чисел из множества $A$ и добавления в него результата их суммирования. В специальную переменную $min\_sum$ будем также каждый раз добавлять результат этого суммирования. Таким образом, количество элементов во множестве будет с каждым шагом уменьшаться на одно, и в конце, когда в нем останется единственный элемент, переменная $min\_sum$ будет содержать искомую стоимость сложения всех чисел.

Реализовать такой код достаточно просто, если реализовать множество $A$ в виде очереди с приоритетом. Так как в задаче нужны минимальные элементы множества, а очередь располагает элементы в порядке их увеличения, то будем хранить в ней не сами элементы множества $A$, а противоположные им числа.

Ссылки

Условие на e-olymp.com
Код на ideone.com

e-olymp 1226. Обмен иностранцами

Задача

Ваша неприбыльная организация координирует программу по обмену студентами. И ей нужна Ваша помощь.

Программа обмена работает следующим образом. Каждый из участников дает информацию о месте своем проживания и месте, куда бы он хотел переехать. Программа считается успешной, если каждый студент найдет для обмена подходящего партнера. Другими словами, если некоторый студент желает переехать из $A$ в $B$, то обязательно должен быть другой студент, который хочет переехать из $B$ в $A$. Это простая задача, если участников программы всего $10$. Но что делать если их будет $100001$?

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

Первая строка содержит количество тестов $t$. Первая строка каждого теста содержит количество студентов $n$ $(1 ≤ n ≤ 100001)$, за которыми следуют $n$ строк, описывающие данные по обмену. Каждая из этих строк содержит информацию об одном студенте — два целых числа, разделенные пробелом, соответствующих текущему месту проживания студента и месту, куда он желает переехать. Места описываются неотрицательными целыми числами, не большими $10^9$. Ни у одного из кандидатов место проживания и место желаемого переезда не совпадают.

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

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

Тесты

Входные данные Выходные данные
2
2
1 2
2 1
2
31 13
13 31
YES
YES
1
4
17 3
28 15
15 28
3 17
YES
1
4
17 3
28 15
15 28
3 18
NO
3
2
1 2
3 4
2
47 7
7 47
2
12 34
12 34
NO
YES
NO

Код программы

Решение задачи

После задания переменной $n$ (количества студентов) очищаем мультимножество $M$. Для каждой пары $(a, b)$ нашего мультимножества проверяем, есть ли в нем пара $(b, a)$:
1. Если есть, то удаляем пару $(b, a)$.
2. Если нет, то вставляем $(a, b)$.
Если в конце мультимножество $M$ пустое, то у каждой пары $(a, b)$ существует соответствующая ей пара $(b, a)$, следовательно обмен студентами может быть произведен успешно.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

e-olymp 333. Детская железная дорога-2

Задача

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

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

Сколько всего разных слов может быть в таком необычном «английском» словаре Витэка?

Тесты

Входные данные
Выходные данные
ALPHABET 35
AAAA 4
UNIVERSITY

54
ABABABABC

24

Код на C++

Код на Java

Решение

Казалось бы, задачу можно решить простым циклом. Ведь в 6-буквенном слове: 6 однобуквенных слов, 5 двубуквенных и т.д. Однако очевидной становится проблема повторения,причем не только повторений букв, но и повторений подстрок, что изрядно усложняет наше решение. Создадим вектор, состоящий из строк, куда мы будем добавлять все подстроки строки из входного потока. Отсортируем полученный вектор. Это нужно для того чтобы одинаковые элементы шли рядом с друг другом. Тогда мы можем использовать функцию unique(), которая удалит из вектора все повторяющиеся элементы, кроме одного. Для того, чтобы провести resize() вектора нам понадобится итератор, который мы приравняем к функции unique(). После resize() останется только вывести размер вектора и прибавить к нему единицу, так как само слово не является подстрокой.

Ссылки

1.Код на С++

2.Код на Java

3.Условие на e-olymp

A272. Количество осадков

Задача

Даны действительные числа [latex]a_{1}, a_{2}, …, a_{n}[/latex] – количество осадков (в миллиметрах), выпавших в Москве в течение [latex]n[/latex] лет. Вычислить среднее количество осадков [latex]average[/latex] и отклонение от среднего для каждого года [latex]d_{1}, d_{2}, …, d_{n}[/latex].

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

Последовательность действительных чисел.

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

Среднее количество осадков [latex]average[/latex].
Последовательность действительных чисел [latex]d_{1}, d_{2}, …, d_{n}[/latex] — отклонение от среднего.

Тесты

 №  Входные данные  Выходные данные
 1  0 0 0 0 0 0 1 0 0 0  0.1
0.1 0.1 0.1 0.1 0.1 0.1 0.9 0.1 0.1 0.1
 2  1.23 2.34 3.45 4.56 5.67  3.45
2.22 1.11 0 1.11 2.22
 3  234.109 4655.15 43.629 14.109  1236.75
1002.64 3418.4 1193.12 1222.64
 4  5 5 5 5 5 5  5
0 0 0 0 0 0

Код программы

Решение

В цикле считываем числа из входного потока и прибавляем их к переменной [latex]average[/latex] (изначально [latex]average=0[/latex]), а также помещаем их в вектор [latex]v[/latex]. Далее делим [latex]average[/latex] на количество элементов в векторе, таким образом получим среднее количество осадков. Затем при помощи цикла поочередно будем выводить отклонение от среднего количества осадков для каждого года. Отклонением от среднего будет абсолютная величина разности соответствующего элемента вектора [latex]v[/latex] и среднего значения [latex]average[/latex].

Ссылки

А273. Центр тяжести системы

Задача. Задача из сборника задач по программированию С.А.Абрамова за 2000 год.
Система из 25 материальных точек в пространстве задана с помощью последовательности действительных чисел [latex]x_{1}, y_{1}, z_{1}, p_{1}, x_{2}, y_{2}, z_{2}, p_{2},\ldots,x_{25}, y_{25}, z_{25}, p_{25}[/latex], где [latex]x_{i}, y_{i}, z_{i}[/latex] — координаты [latex]i[/latex]-ой точки, а [latex]p_{i}[/latex] — ее вес ([latex]i=1,2,\ldots,25[/latex]). Получить координаты центра тяжести системы, а также расстояние от центра тяжести до всех точек системы.

Входные данные:
[latex]x, y, z, p[/latex] — координаты и вес точки.

Выходные данные:
[latex]sum(x,y,z)[/latex] — координаты центра тяжести системы, [latex]l[/latex] — расстояние от центра тяжести до одной из точек.

Тесты:

Входные данные Выходные данные
[latex]x[/latex] [latex]y[/latex] [latex]z[/latex] [latex]p[/latex] [latex]sum[/latex]
[latex](x[/latex]
[latex]y[/latex]
[latex]z)[/latex]
[latex]l[/latex]
2 2 1 2
3 1 2 1
2.33333 1.66667 1.33333 0.57735
1.1547
7 10 5 20
1 0 3 1
43 50 6 3
0 9 0 200
4 8 15 66
1.84138 9.23448 3.83103 5.34452
9.3099
57.9704
4.25705
11.4424

Код программы на С++

Код программы на Java

Решение
В цикле «[latex]while[/latex]» читаем числа из входного потока и запоминаем координаты точек в векторе [latex]а[/latex], к переменной [latex]sum[/latex] прибавляем эти координаты, умноженные на [latex]p[/latex].
Потом подсчитываем координаты центра тяжести системы и выводим эти координаты.
В цикле «[latex]for[/latex]» берем из вектора координаты одной из точек системы, считаем расстояние от центра тяжести до одной из точек системы и выводим это расстояние.

Ссылки
Код в ideone.com (C++)
Код в ideone.com (Java)
Условие задачи (с.117)

А282(а)

Задача

Даны действительные числа [latex]a_1,a_2, …,a_{2n}[/latex]. Получить:
[latex]a_1,a_{n+1},a_2,a_{n+2}, …,a_n,a_{2n}[/latex]

Тесты

Ввод
Вывод
1 2 3 4 5 6 7 8 9 10 1 6 2 7 3 8 4 9 5 10
8 25 3 7 8 3 25 7
5.5 6.025 2.387 1.0986 7.762 3.5958

5.5 1.0986 6.025 7.762 2.387 3.5958

Хороший код

Решение

Считываем действительные числа в первый вектор и узнаем [latex]n[/latex]. Затем поочередно вписываем элементы и элементы с измененным индексом в другой вектор, пока счетчик не будет равен [latex]n[/latex] и выводим полученный вектор, он и будет ответом.

Лучший код на C++

Лучший код на Java

 

Решение

В первом способе мы задавали два вектора, чем естественно увеличивали занимаемую память. C помощью функции insert() мы можем вставлять элементы в вектор, не используя дополнительных средств. Однако мы сталкиваемся с тем, что функция по определению вставляет в вектор константу из-за чего наш цикл не будет правильно работать. Чтобы изменять параметр вводимого элемента, заводим отдельный счетчик. Теперь каждый [latex]2*i+1[/latex]-ый шаг мы вставляем [latex]n+b+i[/latex]-ый элемент вектора. Проведем resize() вектора чтобы убрать лишние элементы и получим готовый результат.

Ссылки

  1. Хорошее решение на C++
  2. Лучшее решение на C++
  3. Лучшее решение на Java
  4. Условие в задачнике Абрамова(стр.120)

A274. Среднее арифметическое всех членов последовательности, кроме одного

Задача из сборника задач по программированию Абрамова С.А. 2000г.
Даны действительные числа [latex]a_{ 1 }[/latex],…,[latex]a_{ 20 }[/latex]. Получить числа [latex]b_{ 1 }[/latex],…,[latex]b_{ 20 }[/latex], где [latex]b_{ i }[/latex] – среднее арифметическое всех членов последовательности [latex]a_{ 1 }[/latex],…,[latex]a_{ 20 }[/latex], кроме [latex]a_{ i }[/latex] ([latex]i[/latex] = 1,2,…,20).

Обобщим задачу для последовательности длины [latex]n[/latex]
Даны действительные числа [latex]a_{ 1 }[/latex],…,[latex]a_{ n }[/latex]. Получить числа [latex]b_{ 1 }[/latex],…,[latex]b_{ n }[/latex], где [latex]b_{ i }[/latex] – среднее арифметическое всех членов последовательности [latex]a_{ 1 }[/latex],…,[latex]a_{ n }[/latex], кроме [latex]a_{ i }[/latex] ([latex]i[/latex] = 1,2,…,[latex]n[/latex]).

Входные данные:
Последовательность действительных чисел.

Выходные данные:
[latex]n[/latex] чисел, [latex]i[/latex]-ое из которых является средним арифметическим всех членов последовательности, кроме [latex]i[/latex]-го ([latex]i[/latex] = 1,2,…,[latex]n[/latex]).

Тесты

Входные данные Выходные данные
1 4 The sequence must consist of at least two elements.
2 1 0 1 The arithmetic average of all elements of this series except the element №i is:
for i = 1: 0.5
for i = 2: 1
for i = 3: 0.5
3 10.1 2.4 11.3 0.8 The arithmetic average of all elements of this series except the element №i is:
for i = 1: 4.8(3)
for i = 2: 7.4
for i = 3: 4.4(3)
for i = 4: 7.9(3)
4 2.5 -1.5 4 -9 1.22 The arithmetic average of all elements of this series except the element №i is:
for i = 1: -1.32
for i = 2: -0.32
for i = 3: -1.695
for i = 4: 1.555
for i = 5: -1

Код на C++

Код на Java

Решение
Для начала, в первом цикле мы читаем числа из входного потока, помещаем их в вектор a и прибавляем к переменной sum, предназначенной для хранения суммы всех чисел последовательности. Последовательность должна состоять как минимум из двух элементов. Чтобы получить среднее арифметическое всех её членов, кроме [latex]i[/latex]-го, достаточно отнять [latex]i[/latex]-й элемент вектора a от значения переменной sum и разделить результат на количество членов такой неполной последовательности, а оно будет на единицу меньше размера вектора a. Таким образом заполняется вектор b, в котором хранятся элементы последовательности [latex]b_{ 1 }[/latex],…,[latex]b_{ n }[/latex], после чего требуемая последовательность выводится.

Код на ideone.com (C++)
Код на ideone.com (Java)
Условие задачи (с.118)

Монстр

Задача 787A с сайта codeforces.com.

Задача

Монстр гонится за Риком и Морти на другой планете. Они настолько напуганы, что иногда кричат. Точнее, Рик кричит в моменты времени b, b + a, b + 2a, b + 3a, …, а Морти кричит в моменты времени d, d + c, d + 2c, d + 3c, ….

Монстр поймает их, если в какой-то момент времени они закричат одновременно. Так что он хочет знать, когда он поймает их (первый момент времени, когда они закричат одновременно) или они никогда не закричат одновременно.

Ввод

Первая строка входных данных содержит два целых числа a и b (1 ≤ a, b ≤ 100).

Вторая строка входных данных содержит два целых числа c и d (1 ≤ c, d ≤ 100).

Вывод

Выведите первый момент времени, когда Рик и Морти закричат одновременно, или  - 1, если они никогда не закричат одновременно.

Тесты

Ввод
Вывод
20 2
9 19
82
2 1
16 12
-1

Код

Решение

В этих моментах времени, заданных прогрессиями, изменяется только коэффициент при и c. Создадим для них 2 цикла. Так как равных моментов времени может быть много, а нам нужен только первый, создаем вектор и ,когда моменты равны, добавляем в него этот момент. Затем, уже вне цикла, проверяем пустой ли вектор, и в таком случаем выводим -1, так как моменты на данном промежутке не были равны ни разу. Если же вектор непустой, выходим первый элемент вектора. Он и будет искомым первым одновременным криком.

А282в

Задача

Даны действительные числа [latex]a_{1}, a_{2}, \cdots, a_{2n}.[/latex] Получить [latex]a_{1}+a_{2n}, a_{2}+ a_{2n-1}, \cdots, a_{n}+a_{n+1}.[/latex]

Тесты

Входные данные Выходные данные
 2 4 6 2 2 9 7 5 7 11 15 4
1 2 2 1 1 4
139 64 15 20 10 5 6 1 140 70 20 30
 111111 22222 33333 11 25 4 111115 22247 33344
15 7 6 9 24 13
2 2 4
138 56 78 3 141 134

Код программы

Решение задачи

Считаем все числа [latex]a_{1}, \cdots, a_{2n}[/latex] в ранее объявленный вектор, пока есть, что считывать. Поскольку мы используем класс vector и цикл  while (cin >> b)  и метод push_back(), в числе [latex]n[/latex] нет необходимости, а во входых данных присутствуют только сами числа [latex]a_{1}, \cdots, a_{2n}[/latex]. Далее, чтобы узнать количество элементов в векторе, будем использовать метод size(). Остается только выводить в цикле сумму двух текущих чисел, начиная с краев вектора и сдвигаясь в каждом витке на элемент ближе к центру вектора, пока не дойдем до центра.

Ссылки

Задача взята из задачника С. Абрамова;
Ссылка на код на ideone.com.

A271

Задача.
Даны действительные числа [latex]a_{1},\ldots,a_{k}[/latex]. Получить [latex]\sqrt{\frac{\sum\limits_{i=1}^{k}(a_{i}-\tilde{a})^{2}}{k-1}},[/latex] где [latex]\tilde{a}=\frac{1}{k}\sum\limits_{i=1}^{k}a_{i}.[/latex]

Тесты

input [latex]\tilde{a}[/latex] [latex]\sqrt{\frac{\sum\limits_{i=1}^{k}(a_{i}-\tilde{a})^{2}}{k-1}}[/latex] Комментарий
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 8  

4.4712

 

Пройдено
2 8 3 4 5 6 7 9 11 15 17 12 19 7 5 1 7 9 19 14 9  

6.35834659

Пройдено
3 3 3 3 3 0 0 0 5 5 5 15 15 15 15 6 5.8554 Пройдено

Решение

  1. Заполняем вектор действительными числами
  2. Считаем их сумму (с помощью цикла прибавляем каждый элемент вектора).
  3. Находим значение [latex]\tilde{a}[/latex].
  4. Находим сумму под корнем второй формулы через цикл (аналогично п.2)
  5. Производим необходимые арифметические операции для нахождения значения второй формулы.
  6. Вывод значений.
    Ссылка на код

A285

Задача

Даны действительные числа [latex]{ a }_{ 1 }[/latex]…[latex]{ a }_{ n }[/latex] .  Если в результате замены отрицательных членов последовательности [latex]{ a }_{ 1 }[/latex]…[latex]{ a }_{ n }[/latex] их квадратами члены будут образовывать неубывающую последовательность, то получить сумму членов исходной последовательности ; в противном случае получить их произведение.

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

Последовательность

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

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

Тесты

 

Последовательность Результат
1 1 2 3 4 10
2 1 2 -3 4 -24
3 1 -2 5 6 7 8 25
4 -1 -1 -2 -3 -4 -5 -16

Код

Решение

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

Код на ideone.

A298

Условие взято со сборника задач С.Абрамова и др.

Задача

Даны целые числа [latex]a_1,\ldots,a_n[/latex],[latex]b_1,\ldots,b_n[/latex]. Преобразовать последовательность [latex]b_1,\ldots,b_n[/latex] по правилу: если [latex] a_i \leq 0[/latex], то [latex]b_i[/latex] увеличить в 10 раз, иначе [latex]b_i[/latex] заменить нулем [latex](i=1,\ldots,n[/latex]). Данные принимать до конца входного потока.

Тесты:

Входные данные Выходные данные
1 -1 0 12 4 5 0 1 2 3 4 5 6 -1 0 12 4 5 0 10 20 0 0 0 60
2 0 2147483647 0 21474836470
3 1 2 3 4 5 6 7 8 0 0 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 90 100

Решение:

Описание решения:

При решении данной задачи был использован тип данных [latex]long long[/latex], так как было необходимо охватить как можно больший диапазон значений. Заданные последовательности чисел будем хранить в одном векторе [latex]a[/latex], где последним элементов первой последовательности будем элемент под номером [latex]a.size()/2-1[/latex]. Отсюда, в цикле будем просматривать каждый элемент первой последовательности. Если данный элемент не положителен, то увеличим в 10 раз соответствующий элемент второй последовательности, иначе, присвоим ему значение нуля. Номер в векторе соответствующего элемента из второй последовательности можно найти по формуле [latex]a.size()/2+i[/latex], где [latex]i[/latex] — это номер элемента из первой последовательности. После прохода по всей первой последовательности, выведем весь вектор на экран.

Код можно запустить и опробовать здесь.

А291а

Задача: А291а

Условие:

Даны действительные числа [latex]a_{1},\ldots,a_{30}.[/latex] Получить [latex]\max (a_{1}+ a_{30},a_{2}+a_{29},\ldots,a_{15}+a_{n}).[/latex]

Тесты:

Входные данные Выходные данные
1 2 3 5 4 8
2 2 3 7 5 4 14
3 4.5 1.1 3 9.25 0.75 10.35
4 -4.5 -2 0 -7.1 5 0.5

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

Решение:

После считывания входного потока данных в вектор [latex]real[/latex] вещественных чисел, вычисляем размер вектора [latex]sum[/latex], равный половине количества элементов входного потока с округлением вверх. В случае нечетного количества элементов, последним элементом вектора [latex]sum[/latex] будет центральный элемент вектора [latex]real[/latex] увеличенный в два раза. Далее, после сортировки полученного вектора по убыванию, выводим первый элемент вектора.

Ссылки:

Задачник по программированию С. Абрамова.

Код программы на ideone.com.

A280

Условие: Пусть [latex] x_{i},y_{i} [/latex]   ( i=1,2, . . .)  и определены, как в задаче 167. Получить [latex] x_{1},\ldots ,x_{25},y_{1},\ldots y_{25}. [/latex]

Задача А167: Пусть [latex] x_{1}=y_{1}=1;[/latex] [latex] x_{2}=y_{2}=2;[/latex] [latex]x_{i}=\dfrac{y_{i-1}-y_{i-2}}{i};[/latex] [latex] y_{i}=\dfrac{x_{i-1}^{2}+x_{i-2}+y_{i-1}}{i!};[/latex] [latex]i=3,4,\ldots[/latex]

 

Ссылка на код в ideone

A276

Условие: Построить последовательность целых чисел [latex]a_{1},\ldots ,a_{30},[/latex] где [latex]a_{1}=1,a_{2}=1;a_{i}=a_{i/2}+a_{i-2}\left( i=3,\ldots ,30\right) .[/latex]

Ссылка на код в ideone

A305

Задача A305

Условие задачи

Даны действительные числа [latex]a_{1},\dots,a_{n}[/latex]. Оставить без изменения последовательность [latex]a_{1},\dots,a_{n}[/latex], если она упорядочена по неубыванию или по невозрастанию; в противном случае удалить из последовательности те члены, порядковые номера которых кратны четырём, сохранив прежним порядок оставленных членов.

Тестирование

Входные данные Выходные данные
1. 5
-1 2 3 4 5
-1 2 3 4 5
2. 6
6 0 2 3 4 6.7
0 2 3 6.7
3. 10
1 2 5 7 -10 3 1 3 2 1
2 5 7 3 1 3 1
4. 5
1 5 6 7.5 0
5 6 7.5
5. 3
-23 46 -80
46 -80

Реализация

Алгоритм решения

Считываем все действительные числа до конца входного потока и записываем их в вектор v1. Проверяем, упорядочена ли последовательность по возрастанию или по убыванию. Если да, выводим на экран исходную последовательность без изменений с помощью функции copy() и итератора вывода ostream_iterator, который записывает элементы последовательно в выходной поток. Если же последовательность не упорядочена ни по убыванию, ни по возрастанию, удаляем из неё элементы, порядковые номера которых кратны четырём. Важно сохранить прежним порядок оставленных членов.
Работаем следующим образом:
1. Создаём вектор v_2.
2. Уменьшаем размер контейнера с помощью функции resize(): v2.resize(size_of_the_sequence - temp). Инициализируем переменную  size_of_the_sequence значением ноль.
3. Если порядковый номер элемента неупорядоченной последовательности кратен четырём, то увеличиваем количество элементов на единицу с каждой итерацией. Иначе, присваиваем вектору v_2 значение вектора v_1: v2[i - size_of_the_sequence] = v1[i].
4. Уменьшаем размер контейнера v_1. Присваиваем вектору v_1 значение вектора v_2.
5. С помощью функции shrink_to_fit() уменьшаем количество используемой памяти вектора v_1.
6. Извлекаем все элементы из вектора v_2 с помощью функции clear().

Для запроса на выполнение следует перейти по ссылке.

A288

Задача A288

Условие задачи

Даны целые числа [latex]a_{1}[/latex], …, [latex]a_{n}[/latex], каждое из которых отлично от нуля. Если в последовательности отрицательные и положительные члены чередуются (+, –, +, –,  или –, +, –, +, … ), то ответом должна служить сама исходная последовательность. Иначе получить все отрицательные члены последовательности, сохранив порядок их следования.

Код программы

Тесты

 

Входные данные Выходные данные
5 5 3 1 2 7 8 100000
-9 -5 -1 -3 -7 -4198 -852 -9 -5 -1 -3 -7 -4198 -852
5 -3 1 81 3 -7 1 -5 6 -3 -7 -5
-1 2 -8 995 -3 777 -42 -1 2 -8 995 -3 777 -42

Решение

Для решение данной задачи я воспользовался следующим алгоритмом. Заводим два целочисленных вектора, булеву переменную, которую мы будем проверять при печати и целочисленную переменную, которая будет являться первым элементом последовательности, а также начальным значением переменной [latex]tester[/latex], с которой будет сравниваться следующий элемент, а после этого его значение мы снова положим в [latex]tester[/latex].  В ходе цикла мы положительные числа кладем в один вектор, а отрицательные в оба. И в зависимости от того чередовались ли знаки или нет (значение переменной [latex]alternate[/latex]), мы печатаем нужный вектор.