Простые задачи на использование div, mod

Задача 1. Шахматная доска (100 баллов)
Шахматная доска состоит из n × m клеток, покрашенных в черный и белый цвет в «шахматном» порядке. При этом клетка в левом нижнем углу доски покрашена в черный цвет. Определите, сколько всего на доске черных клеток.
Входные данные
Вводятся два числа n и m, записанных в одной строке. Все числа — натуральные, не превосходящие 32 000.
Выходные данные
Вывести одно целое число — количество черных клеток на доске.

Program z1;
var
n, m : integer;
k, s: longint;
begin
read(n,m);
s:=n*m;
if s mod 2 = 0
then k := s div 2
else k := (s div 2)+1;
write(k);
end.

Задача 2. Строки в книге (100 баллов)
В книге на одной странице помещается K строк. Таким образом, на 1-й странице печатаются строки с 1-й по K-ю, на второй — с (K+1)-й по (2∙K)-ю и т.д. Напишите программу, которая по номеру строки в тексте определяет номер страницы, на которой будет напечатана эта строка, и порядковый номер этой строки на странице.
Входные данные
Вводятся два числа: K — количество строк, которое печатается на странице, и N — номер строки (1≤K≤200, 1≤N≤20000).
Выходные данные
Выведите два числа — номер страницы, на которой будет напечатана эта строка, и номер строки на странице.

Задача 3. Абрикосовые числа
Ограничение времени
2 секунды
Ограничение памяти
256Mb
Ввод
стандартный ввод или input.txt
Вывод
стандартный вывод или output.txt
Назовем число абрикосовым, если цифры в десятичной его записи нестрого возрастают (то есть каждая следующая цифра должна быть не меньше, чем предыдущая). Например, числа 123, 4479, 568889, 7, 1111 — абрикосовые, а числа 121, 98765, 10, 42 — нет.
Вам дано число N. Найдите количество чисел от 1 до N, которые являются абрикосовыми.
Формат ввода
В единственной строке задано число N (1 ≤ N ≤ 10⁶).
Формат вывода
Выведите количество абрикосовых чисел, не превосходящих N.

Задача 4.Бублики
Дома Машу ждал неожиданный сюрприз от родителей - ей подарили число N, сделанное из теста! Маша, конечно же, была очень рада такому подарку, но больше, чем числа, она любит бублики. Бубликом Маша считает любое изделие из теста, которое имеет круглую форму и дырку внутри. Первым же делом после получения подарка Маша начала делать из него бублики. Делает она это очень простым образом - откусывая от цифр подаренного числа все лишнее. Более того, из чисел 1, 2, 3, 4, 5 и 7 бубликов сделать нельзя вообще, из цифр 6, 9 и 0 можно сделать 1 бублик, а из цифры 8 - целых два! Помогите Маше определить, сколько бубликов она может сделать из полученного числа.

Входные данные В единственной строке вводится единственное число N (0 <= N <= 1 000 000 000) - подарок Маши.

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

Задача 5. Нечетное количество цифр
Дано целое число N. Найдите количество чисел от 1 до N, запись которых состоит из нечетного количества цифр.
Формат ввода
Первая и единственная строка содержит одно число N (1 ≤ N ≤ 10⁵).
Формат вывода
Выведите количество чисел от 1 до N, запись которых состоит из нечетного количества цифр.

Работа с делителями

1. Сумма делителей
2. Количество делителей
3. Нечетное количество делителей (у чисел, которые являются квадратами других чисел)
4. Занесение делителей числа в массив
5. Другие операции с делителями

Занесение делителей числа в массив
Количество делителей
readln(n);
for i:=1 to n do
if n mod i:=0 then
begin
k:=k+1;
a[k]:=i;
end;

Количество делителей
readln(n);
k:=trunc(sqrt(n));
for i:=1 to k do
if n mod i=0 then
begin
z:=z+1;
end;
if k*k=n then z:=z*2-1 else z:=z*2;
write(z);


1. Прогулка по таблице умножения
Ограничение времени
1 секунда
Ограничение памяти
256Mb
Ввод
стандартный ввод или input.txt
Вывод
стандартный вывод или output.txt

Саша стоит на таблице умножения с бесконечным количеством строк и столбцов.
Квадрат в клетке (i, j) содержит целое число i ⋅ j. Первоначально Саша стоит в (1, 1). За один ход он может перейти от (i, j) к (i + 1, j) или (i, j + 1).
Дано целое число N. Найдите минимальное количество ходов, необходимое для достижения квадрата, содержащего число N.
Формат ввода
Единственная строка содержит число N (1 ≤ N ≤ 10¹²).
Формат вывода
Выведите минимальное количество ходов, необходимое для достижения квадрата, содержащего число N.


2. Король Алекс и закон о замене автомобильных номеров
Ограничение времени
1 секунда
Ограничение памяти
256Mb
Ввод
стандартный ввод или input.txt
Вывод
стандартный вывод или output.txt

Алекс — король Великой Байтландии. Алекс любит издавать законы в Байтландии, порою очень даже странные.
Например, сегодня он издал указ о замене автомобильных номеров в Великой Байтландии. Суть этого закона еще более странная, чем его название.
Каждый автомобильный номер в Великой Байтландии — некоторое натуральное число. Король Алекс считает, что автомобильный номер является красивым, если этот номер имеет нечетное количество делителей. Делители натурального числа a — это все такие натуральные числа b, не превосходящие a, на которые a делится без остатка. Алекс хочет, чтобы все автомобильные номера стали красивыми. Для этого каждый номер, который не является красивым, должен быть заменен наименьшим из красивых номеров, которые больше его.
Вам дан некоторый автомобильный номер X. Определите, какое значение будет у данного номера после применения указа короля Алекса.
Формат ввода
В единственной строке входного файла задано число X (1 ≤ X ≤ 10¹⁸).
Формат вывода
Выведите номер, на который нужно будет заменить X после вступления указа в силу

Program z1;
var n, v, i, l, h, m:int64;
k:real;
begin
read (n);
v:=trunc(sqrt(n));
l:=v;
v:=v * l;
if v=n then
h:=n
else
begin
h:=(l+1)*(l+1);
end;
write (h);
end.


3. Общий делитель
Ограничение времени
1 секунда
Ограничение памяти
256Mb
Ввод
стандартный ввод или input.txt
Вывод
стандартный вывод или output.txt

Даны два числа A и B. Найдите K-е по убыванию число, которое является общим делителем чисел A и B. Гарантируется, что существует хотя бы K чисел, которые делят и A, и B.
Формат ввода
В первой строке записаны три целых числа A, B, K (1 ≤ A, B ≤ 10⁵, K ≥ 1).
Формат вывода
Выведите K-е по убыванию число, которое является общим делителем чисел A и B.


4. Конфеты

Маша очень любит шоколадные конфеты, и на день рождения ей их подарили целую коробку. В коробке оказалось целых N конфет. Как и любой другой житель Байттауна, Маша очень щедрый человек, поэтому первым делом она захотела поделиться с друзьями этими конфетами. Кроме того, делить нужно, конечно же, справедливо: всем, с кем она делится, должно достаться одинаковое количество конфет. Например, если у Маши четыре конфеты, она может разделить их между четырьмя друзьями (по одной конфете каждому), либо между двумя друзьями (по две конфеты каждому), либо одному другу отдать все четыре конфеты.
Помогите Маше определить, сколькими способами можно разделить ее конфеты.
Входные данные
Единственная строка входного файла содержит число N(1<N<10 ) — число конфет в коробке Маши.
Решения, работающие при N < 10б, получат не менее 70 баллов.
Решения, работающие при N < 109, получат не менее 90 баллов.
Выходные данные
Единственная строка выходного файла должна содержать одно число — число способов разделить конфеты.

Операции с целыми числами

1. Нахождение простых чисел
2. Нахождение взаимно простых чисел
3. Нахождение НОД
4. Нахождение НОК

Операции в массиве
1. Есть ли заданные числа или последовательности
2. Максимальная длина заданной последовательности
3. Полиндром
4. Сортировка (если есть i+1, то цикл до n-1)
5. Быстрая сортировка целых чисел.


Пузырьковая сортировка
for j:=1 to N-1 do
for i:=1 to N-j do
if a[i] > a[i+1] then
swap(a[i],a[i+1]);

Сортировка заменой
for i:=1 to N do
begin
max:=a[i]; k:=i;
for j:=i to N do
if a[j] > max then begin max:=a[j]; k:=j; end;
swap(a[i],a[k]);
end;

Быстрая сортировка целых чисел
max:=20000;
for i:=1 to N do
begin
b[a[i]]:=b[a[i]]+1;
end;

k:=1;
for i:=1 to max do
for j:=1 to b[i] do
begin
a[k]:=i;k:=k+1;
end;

Нахождение максимального элемента и его номера
for j:=i to N do
if a[j] > max then begin max:=a[j]; k:=j; end;


4.Лестницы
У Маши в подъезде лестница устроена странным образом. Она представляет собой длинную последовательность из N ступенек, каждая из которых имеет высоту Ai. Причем почему-то сначала может идти более высокая ступенька, потом - более низкая, а за ней - опять более высокая! Маша считает набор подряд идущих ступенек правильным, если их высоты расположены по возрастанию. Помогите Маше определить длину самого длинного правильного набора.
Входные данные В первой строке вводится единственное число N (1 <= N <= 20 000) - количество ступенек. Во второй строке вводится N чисел, разделенных пробелом - высоты ступенек Ai (0 <= Ai <= 20 000).
Выходные данные Выведите единственное число - длину самого длинного правильного набора.
program z1;
var n,k,z,i:integer;
a:array[1..20000] of integer;
begin
readln(n);
for i:=1 to n do
read(a[i]);
k:=1;
for i:=1 to n-1 do
if a[i+1]>a[i] then k:=k+1 else begin if k>z then z:=k; k:=1; end;
if k>=z then writeln(k) else writeln(z);
end.

6. Гипер-Лото
Маша и Петя участвуют в знаменитой на всю Байтландию командной игре - “Гипер-Лото”. Правила игры простые. Участникам дают мешок с N числами. Далее, пока в мешке есть хотя бы два числа, участники делают следующую операцию - они достают из мешка такую пару чисел, что разница между ними максимально возможная, и добавляют эту разницу к своему количеству очков, после чего числа выкидываются и в мешок не возвращаются.
Например, у участников есть числа 7, 3, 4, 2 и 2. На первом шаге они возьмут числа 2 и 7, потому что разница между ними равна 5. После чего выкинут эти числа, в мешке осталось 3, 4 и 2. Участники берут 2 и 4 - разница равна 2. После этого в мешке осталось только одно число - игра заканчивается. Команда набрала 5+2=7 очков.
Ваша задача - по заданному набору чисел в мешке определить, какое число очков наберет команда.
Входные данные
В первой строке вводится единственное число N (1 <= N <= 200 000) - количество чисел.
Во второй строке вводится N чисел, разделенных пробелом - значения чисел Ai (0 <= Ai <= 100 000).
Выходные данные
Выведите единственное число - количество очков, которые наберет команда.

7. Король Алекс и закон о лучниках Великой Байтландии
Ограничение времени
1 секунда
Ограничение памяти
256Mb
Ввод
стандартный ввод или input.txt
Вывод
стандартный вывод или output.txt
Алекс — король Великой Байтландии. Алекс любит издавать законы в Байтландии, порою очень даже странные.
Например, сегодня он издал указ о лучниках Великой Байтландии (как и в любом королевстве, в Байтландии есть свои лучники). Этим указом король Алекс обязует всех лучников в королевстве пройти тест и показать свой уровень владения луком.
Для этих целей Алекс заказал в соседнем королевстве некоторое количество мишеней. У каждой мишени есть собственный номер, выражающийся некоторым натуральным числом. Совершенно случайно оказалось, что номера мишеней, которые заказал Алекс, имеют номера 1, 2, 3, …, n-1, n.
Оценивание некоторого лучника происходит следующим образом. Сперва все n мишеней выставляются в ряд перед лучником. Затем лучник производит два выстрела по мишенем и тем самым попадает по двум из n мишеней (возможно, дважды по одной и той же). После этого Алекс выбирает два некоторых числа l и r. Количество очков, которое набрал лучник, вычисляется как количество мишеней с номерами l, l+1, l+2, …, r-1, r, в которые лучник не попал.
Вам заданы значения n, l, r. Вычислите, сколько очков получит лучник, который сделал выстрелы по мишеням a и b?

Формат ввода
В единственной строке ввода заданы числа n, l, r, a, b (1 ≤ n ≤ 10⁹, 1 ≤ l ≤ r ≤ n, 1 ≤ a, b ≤ n).
Формат вывода
Выведите количество очков, которое получит лучник.

Program z1;
var n, l, a, b, r, h: longint;
begin
read (n,l,r,a,b);
h:=(r-l)+1;
if (a=0) or (b=0) then
h:=h-1;
if (a<=r) and (a>=l) then
h:=h-1;
if (b<=r) and (b>=l) then
h:=h-1;
write (h);
end.

8 Тринидад Итобагович и порядок
Ограничение времени
1 секунда
Ограничение памяти
256Mb
Ввод
стандартный ввод или input.txt
Вывод
стандартный вывод или output.txt
Тринидад Итобагович — преподаватель, ответственный за класс из N учеников. Все ученики пронумерованы различными числами от 1 до N.
Сегодня все учащиеся заходили в класс в разные моменты времени. Согласно записям Тринидада Итобаговича, в классе было A_i учеников после того как ученик с номером i-й зашел в класс. Используя эти записи, восстановите порядок, в котором ученики заходили в класс.
Формат ввода
В первой строке записано число N (1 ≤ N ≤ 10⁵) — количество учеников. Во второй строке через пробел записаны N различных целых чисел A_i (1 ≤ A_i ≤ N).
Формат вывода
Выведите N чисел через пробел — порядок, в котором ученики заходили в класс.

Program z1;
var a:array[1..100000] of longint;
b:array[1..100000] of longint;
n, i: longint;
begin
readln (n);
for i:=1 to n do
read (a[i]);
for i:=1 to n do
begin
b[a[i]]:=i;
end;
for i:=1 to n do
write (b[i],' ');
end.

Операции со строками и символами

1. Ввод, вывод
2. Полиндром
3. Замена букв
4. Подсчет букв
5. Накапливание строки

Исходные данные

Операция

Результат

s1:='Мото'; s2:='роллер'

s3:=s1+s2;

s3=’Мотороллер’

s5:='Мотороллер';

k:=Pos('рол',s5);

k=5

s3:='Мотороллер';

l:=Length(s3);

l=10

s3:='астроном';

s4:=Copy(s3,3,4);

s4= ‘трон’

s5:='Коробочка';

Delete(s5,4,2);

s5=’Корочка’

s6:='Рука'; s7:='баш';

Insert(s7,s6,3);

s6=’Рубашка’

x:=2.73284;

Str(x:4:2,s8);

s8=’2.73′

s8='2.73';

Val(s8,x,Osh);

x=2.73

1. Накопление строки (100 баллов)
Вводится символ С и строка S.
Исходное состояние новой строки P - символ C.
Далее новая строка P достраивается по правилу: Если очередной символ строки S меньше первого символа (С) строки P, то он добавляется в начало строки P иначе – в конец строки P.
Входные данные:
Первая строка ввода содержит один символ С.
Вторая строка содержит строковую величину S с длиной ≤ 255.
Выходные данные:
Вывод должен содержать одну строковую величину P.




Пояснение: в строковых величинах буквы можно сравнивать между собой, как и цифры. Большей считается буква, стоящая в алфавите дальше, т.е. буква В >(больше) буквы А.

program z1;
var s,p :string; c:char;
i, n: integer;
begin
readln(c);
readln(s);
n:=length(s);
p:=c;
for i := 1 to n do
if s[i]<c
then p:=s[i]+p
else p:=p+s[i];
writeln (p);

End.

2. Палиндромы
Ограничение времени
1 секунда
Ограничение памяти
256Mb
Ввод
стандартный ввод или input.txt
Вывод
стандартный вывод или output.txt
Саша любит палиндромы. Палиндром — это слово из латинских букв, которое читается одинаково как слева направо, так и справа налево. Непалиндромные слова для Саши неприемлемы. За одну монету Саша может изменить любой символ слова на любую букву алфавита по своему выбору.
Дано слово S. Найдите минимальное количество монет, необходимых для того, чтобы сделать S палиндромом.
Формат ввода
Первая строка содержит число n (1 ≤ n ≤ 10⁵) — длину слова.
Следующая строка содержит слово S длины n, состоящее только из маленьких латинских букв.
Формат вывода
Выведите минимальное количество монет, необходимых для того, чтобы сделать S палиндромом.


3. Палиндромов много не бывает!
Ограничение времени
1 секунда
Ограничение памяти
256Mb
Ввод
стандартный ввод или input.txt
Вывод
стандартный вывод или output.txt
В один прекрасный день философ Владислав понял, что он хочет делать мир лучше!
Так как первым, что увидел Владислав, выйдя из своего дома была строка s, то он решил сделать лучше и её. Как известно, строки-палиндромы лучше, чем обычные строки (хотя бы потому что это любимый вид строк всех философов). Строка называется палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, строки «abaaba», «radar» и «q» — палиндромы, а строки «hello» и «world» — нет.
Теперь Владислава интересует q вопросов, i-й из которых звучит как «А станет ли строка палиндромом, если в ней поменять местами символы на позициях xi и yi?» Если Владислав станет сам искать ответы на все свои вопросы, то он больше не сможет никому помочь, помогите Владиславу и найдите ответы на все его вопросы.
Формат ввода
В первой строке входных данных содержится одна строка s(2≤∣∣s∣∣≤106) — строка, найденная Владиславом.
Во второй строке содержится одно число q(1≤q≤106) — количество вопросов.
В каждой из следующих q строк содержится по два числа xi, yi (1≤xi,yi≤|s|, xi≠yi) — описание i-го вопроса.
Формат вывода
Выведите q строк, i-я строка должна содержать «Yes», если для i-го вопроса ответ положительный, и «No» в противном случае.

Что знать

1. функции sqrt, round, trunc, downto, exit, break, readln, writeln
2. Типы данных
a. Byte – 1 байт
b. Integer - 2 байта
c. Longint - 4 байта
d. Int64 – 8 байт
e. Real - 6 байт
f. Double – 8 байт
g. Char -1 байт
h. String, ansistring – 1 байт одна буква
3. Размер типов данных
a. Byte – от 0 до 255
b. Integer - -32768 – 32767
c. Longint - - 2 147 483 648 - 2 147 483 647
d. Int64 - -9223372036854775808...9223372036854775807
e. Real - 2.9 * 10E-39 .. 1.7 * 10E38
f. Double - 5 * 10E-324 .. 1.7 * 10E308
4. Нечетное количество делителей у чисел, которые являются квадратами других чисел. У всех остальных чисел количество делителей четное.
5. При подсчете количества делителей и при выполнении операций с делителями находим делители перебирая варианты до корня числа округленного до целого.
6. Читать задачу и прогонять на примере не менее пяти раз