Задача 1. Козак Вус подарував вам набiр з n цифр (тобто чисел вiд 0 до 9 включно). I хоче дiзнатися у вас: яку максимальну кiлькiсть чисел з них можна скласти так, щоб кожне з них дiлилося на 3 та кожна цифра з набору була використана не бiльше 1 разу. Щоб скласти число, вам потрiбно вибрати будь-які цифри з набору, вибрати їхнiй порядок та скласти число з цих цифр. Звернiть увагу, що ви не зобов’язанi використати всi цифри. Ви ж не можете вiдмовити Вусу? :)
Маленька пiдказка вiд Математичної Сови:
Остача (залишок) вiд дiлення x на число 3 дорiвнює остачi вiд дiлення суми цифр числа x на число 3.
Число a є кратним числу b (тобто a дiлиться на b) лише, якщо остача вiд дiлення числа a на число b дорiвнює 0.
Технічні умови Програма Newnumbers читає з пристрою стандартного введення у першому рядку мiстить одне цiле число n (1 ⩽ n⩽5 · 105) — кiлькiсть цифр. У другому рядку записано n цiлих чисел, кожне з яких має значення вiд 0 до 9 включно. Програма виводить на пристрій стандартного виведення одне ціле число — максимальну кількість чисел кратних 3, що можна скласти з цього набору.
Приклади
Введення
|
Виведення
|
1
0 |
1
|
14
8 8 4 8 1 1 0 0 2 1 9 3 4 1 |
8
|
Зауваження до прикладів
У першому прикладі ми можемо скласти лише одне число 0.
У другому прикладі з цього набору ми можемо скласти максимум 8 чисел. Один iз можливих способів — це скласти такі числа: 0, 0, 48, 9, 3, 21, 81, 84. Невикористаними у нас залишаться цифри 1, 1.
Задача 2. Дано набiр з n цифр вiд 0 до 9 включно. Потрібно дiзнатися, яку максимальну кiлькiсть чисел з них можна скласти так, щоб кожне з них дiлилося на 3 та кожна цифра з набору була використана не бiльше 1 разу. Щоб скласти число, вам потрiбно вибрати будь-які цифри з набору, вибрати їх порядок та скласти число з цих цифр. Звернiть увагу, що ви не зобов’язані використати всi цифри.
Математична підказка:
· Остача (залишок) вiд дiлення x на число 3 дорiвнює остачi вiд дiлення суми цифр числа x на число 3.
· Число a є кратним числу b (тобто a дiлиться на b) лише, якщо остача вiд дiлення числа a на число b дорiвнює 0.
Технічні умови. Програма читає з пристрою стандартного введення у першому рядку одне цiле число n (1 ⩽ n⩽5 · 105) — кiлькiсть цифр. У другому рядку записано n цiлих чисел, кожне з яких має значення вiд 0 до 9 включно. Програма виводить на пристрій стандартного виведення одне цiле число — максимальну кiлькiсть чисел кратних 3, що можна скласти з цього набору.
Приклади
Введення
|
Виведення
|
1
0 |
1
|
14
8 8 4 8 1 1 0 0 2 1 9 3 4 1 |
8
|
Зауваження до прикладів
У першому прикладi ми можемо скласти лише одне число 0.
У другому прикладi з цього набору ми можемо скласти максимум 8 чисел. Один iз можливих способiв — це скласти наступнi числа: 0, 0, 48, 9, 3, 21, 81, 84. Невикористаними у нас залишаться цифри 1, 1.
Математична модель до завдання:
Максимальна кількість чисел обчислюється за формулою
n =p(0=mod3)+min(k(1=mod3); m(2=mod3))+(1/3)*(max(k(1=mod3); m(2=mod3) -min(k(1=mod3); m(2=mod3))
де p(0=mod3) - це кількість цифр, що кратні 3.;
k(1=mod3) -це кількість цифр, що мають вигляд 3х+1;
m(2=mod3)) - це кількість цифр, що мають вигляд 3х+2;
Кодування алгоритму на СІ++
#include <iostream>
#include <cmath>
using namespace std;
int main(){
long long kol, tsifra, ost;
cin >> kol;
long long n = 0, L = 0, m = 0;
for (long long i = 0; i < kol; i++){
cin >> tsifra;
ost = tsifra % 3;
if (ost == 0)
n = n + 1;
else if (ost == 1)
L = L + 1;
else
m = m + 1;
}
long long rez = n + min(L, m) + (max(L, m) - min(L,m))/3;
cout << rez;
}
Кодування алгоритму на мові Рython
var k,l,o,m,n,i,min,max,rez:longint;
begin
readln(n);
k:=0; l:=0; m:=0;
for i:=1 to n do
begin
read(o);
o:=(o mod 3);
case o of
0:k:=k+1;
1:l:=l+1;
2:m:=m+1;
end;
end;
if l>m then begin max:=l; min:=m; end
else begin max:=m; min:=l; end;
rez:=k+min+((max-min) div 3);
write(rez);
endA.
Кодування алгоритму на мові Pascal
var k,l,o,m,n,i,min,max,rez:longint;
begin
readln(n);
k:=0; l:=0; m:=0;
for i:=1 to n do
begin
read(o);
o:=(o mod 3);
case o of
0:k:=k+1;
1:l:=l+1;
2:m:=m+1;
end;
end;
if l>m then begin max:=l; min:=m; end
else begin max:=m; min:=l; end;
rez:=k+min+((max-min) div 3);
write(rez);
end.
Кодування на мові Pascal генератора перевірочних тестів(текстових файлів з даними) до алгоритму:
var f:text;
n,p,i,k,l,m,min,max,a,o,rez,c:longint;
pp:boolean;
begin
read(n);
read(p);
assign(f,'figures.test.20');
rewrite(f);
writeln(f,n);
for i:=1 to n do
begin
pp:=true;
case p of
1:begin while pp do begin a:=random(10); c:=(a mod 3); if c=0 then pp:=false; end; end;
2:begin while pp do begin a:=random(10); c:=(a mod 3); if c=1 then pp:=false; end; end;
3:begin while pp do begin a:=random(10); c:=(a mod 3); if c=2 then pp:=false; end; end;
4:begin while pp do begin a:=random(10); c:=(a mod 3); if ((c=0) or (c=1)) then pp:=false; end; end;
5:begin while pp do begin a:=random(10); c:=(a mod 3); if ((c=0) or (c=2)) then pp:=false; end; end;
6:begin while pp do begin a:=random(10); c:=(a mod 3); if ((c=2) or (c=1)) then pp:=false; end; end;
7:a:=random(10);
end;
write(f,a,' ');
o:=(a mod 3);
case o of
0:k:=k+1;
1:l:=l+1;
2:m:=m+1;
end;
if l>m then begin max:=l; min:=m; end else begin max:=m; min:=l; end;
end;
rez:=k+min+((max-min) div 3);
writeln(f,'');
write(f,rez);
close(f);
write(rez);
end.
Тести для перевірки алгоритму:
Тест 1.
Ввід 4
5 5 8 8
Вивід 1
Тест 2.
Ввід 8
5 5 7 8 8 5 8 4
Вивід 3
Тест 3.
Ввід 16
5 5 7 8 6 8 5 8 4 6 6 3 4 2 8 0
Вивід 9
Тест 4.
Ввід 32
5 5 7 8 8 5 8 4 4 2 8 2 4 7 8 5 4 5 8 8 7 1 8 8 4 7 8 4 5 7 1 7
Вивід 15
Онлайн-опитування.
Алгоритми вибору мовою програмування Pascal
Загальна форма запису:
case <селектор (логічний вираз, математичний вираз, змінна)> of
значення1 : оператор;
значення2 : оператор;
. . . . . . . . . .
значенняN : оператор
else
оператор;
end;
В
операторі може бути кілька дій, тобто використовуватися begin, end, а може бути
порожній оператор. Значень може бути кілька.
Завдання
1.
З клавіатури
вводиться цифра. Вивести письмову назву цієї цифри.
Розв’язання.
Кодування
мовою програмування Pascal:
program Z1;
var
a : integer;
begin
write('введіть цифру: ');
readln(a);
case a
of
0 : writeln ('ви
ввели нуль.');
1 : writeln ('ви
ввели одиницю.');
2 : writeln ('ви
ввели двійку.');
3 : writeln ('ви
ввели трійку.');
4 : writeln ('ви
ввели четвірку.');
5 : writeln ('ви
ввели пятірку.');
6 : writeln ('ви
ввели шістку.');
7 : writeln ('ви
ввели сімку.');
8 : writeln ('ви
ввели вісімку.');
9 : writeln ('ви
ввели цифру девять.')
else writeln('ви
ввели не цифру.');
end;
end.
Задача
2.
Складіть
програму, яка імітує своєрідний калькулятор, де 1-сума двох чисел, 2-різницю
двох чисел, 3-твір двох чисел, 4-ціла частина від ділення, 5-залишок від
ділення, 6 - квадратний корінь числа, інакше введений невідомий номер операції .
Розв’язання.
Кодування
мовою програмування Pascal:
program Z2;
var
a, b: real;
i, c, d: integer;
begin
writeln('Калькулятор.');
writeln('1 - сума двох чисел;');
writeln('2 - різниця двох чисел;');
writeln('3 - добуток двох чисел;');
writeln('4 - ціла частина від ділення;');
writeln('5 - остача від ділення;');
writeln('6 - квадратний корінь числа.');
write('Введіть цифру: ');
readln(i);
case i of
1:
begin
write('Введіть
три довільні числа: ');
read(a, b, c);
writeln(1*a+1*b+1*c);
end;
2:
begin
write(' Введіть
два довільні числа: ');
read(a, b);
writeln(1*a - 1*b);
end;
3:
begin
write(' Введіть
два довільні числа: ');
read(a, b);
writeln(1*a * b);
end;
4:
begin
write(' Введіть
два довільні числа: ');
read(c, d);
writeln(c
div d);
end;
5:
begin
write(' Введіть
два довільні числа: ');
read(c, d);
writeln(c
mod d);
end;
6:
begin
write('Введіть
число: ');
read(c);
writeln(sqrt(c):4:5);
end;
else writeln('Помилка.');
end;
end.
l
Немає коментарів:
Дописати коментар