Задаци: Минимум и максимум два броја¶
Алгоритми и програми у програмском језику C: Минимум и максимум два броја.
Куглице¶
Прочитај текст задатка.
Претпоставимо да је број црвених и плавих куглица у првој и другој кутији \(c_1\), \(p_1\) тј. \(c_2\), \(p_2\). Прва могућност је да се све црвене куглице из прве кутије пребаце у другу, а да све плаве куглице из друге кутије пребаце у прву, чиме се добија \(c_1+p_2\) премештања. Друга могућност је да се све плаве куглице из прве кутије пребаце у другу, а да све црвене куглице из друге кутије пребаце у прву, чиме се добија \(p_1+c_2\) премештања. Решење се добија одређивањем мањег од ова два броја тј. њиховог минимума.
Минимум је могуће одредити а могуће га је имплементирати и коришћењем гранања, на
пример, коришћењем наредбе if-else.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int c1, p1, c2, p2;
scanf("%d%d%d%d", &c1, &p1, &c2, &p2);
int iz1u2 = c1 + p2, iz2u1 = c2 + p1, min;
if (iz1u2 < iz2u1)
min = iz1u2;
else
min = iz2u1;
printf("%d", min);
return 0;
}
Гранање којим се одређује минимум могуће је имплементирати и коришћењем условног израза.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int c1, p1, c2, p2;
scanf("%d%d%d%d", &c1, &p1, &c2, &p2);
int iz1u2 = c1 + p2, iz2u1 = c2 + p1;
int min = iz1u2 < iz2u1 ? iz1u2 : iz2u1;
printf("%d", min);
return 0;
}
Проја¶
Прочитај текст задатка.
Да би се од постојећих намирница направила највећа могућа количина хлеба потребно је задовољити све услове рецепта који захтева да кукурузно брашно чини два дела смеше а пшенично један. Укупна количина брашна је збирна количина та три дела а потребна количина воде коју треба одредити је пола укупне количине брашна.
Дакле, ако са \(M\) означимо количину једног дела смеше, количина пшеничног брашна је \(M\), кукурузног брашна је \(2M\), укупна количина брашна је \(M+2\cdot M=3\cdot M\), а воде је \(\frac{3\cdot M}{2}\). Ако је расположива количина пшеничног брашна \(P_b\), а кукурузног \(K_b\), потребно је наћи највећу вредност \(M\) такву да важи \(M\leq P_b\) и \(2\cdot M\leq K_b\), тј. \(M\leq\frac{K_b}{2}\). Пошто је \(M\) мање или једнако од вредности \(P_b\) и \(\frac{K_b}{2}\), оно је мање или једнако од мање од те две вредности тј. од \(\min{(P_b,\frac{K_b}{2})}\) и то је уједно највећа могућа вредност за \(M\). Када се одреди вредност \(M=\min{(P_b,\frac{K_b}{2})}\), израчунава се и исписује количина воде \(\frac{3\cdot M}{2}\).
Минимум два броја је могуће одредити гранањем помоћу наредбе гранања if-else.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
double kb, pb, m;
scanf("%lf%lf", &kb, &pb);
if (pb <= kb / 2.0)
m = pb;
else
m = kb / 2.0;
double v = 3.0 * m / 2.0;
printf("%.2lf", v);
return 0;
}
Минимум два броја је могуће одредити и гранањем помоћу условног израза.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
double kb, pb;
scanf("%lf%lf", &kb, &pb);
double m = pb <= kb / 2.0 ? pb : kb / 2.0;
double v = 3.0 * m / 2.0;
printf("%.2lf", v);
return 0;
}
Генерално, највеће \(x\) које задовољава систем неједначина \(x\leq a_1, \ \ldots, \ x\leq a_n\) je \(x=\min{(a_1,\ldots,a_n)}\). Дуално, најмање \(x\) које задовољава систем неједначина \(x\geq a_1, \ \ldots, \ x\geq a_n\) je \(x=\max{(a_1,\ldots, a_n)}\).
Скупови спортиста¶
Прочитај текст задатка.
На основу принципа укључивања-искључивања важи да је \(|K\cup F|=|K|+|F|-|K\cap F|\), где \(|K\cup F|\) означава број елемената уније скупа кошаркаша и фудбалера, \(|K|\) означава број кошаркаша и једнак је датом броју \(k\), \(|F|\) број фудбалера и једнак је датом броју \(f\), а \(|K\cap F|\) означава број оних који играју и фудбал и кошарку. Пошто су и фудбалери и кошаркаши ученици одељења у коме има \(n\) ученика важи да је \(|K\cup F|\leq n\). Зато је \(|K|+|F|-|K\cap F|\leq n\), тј. \(|K\cap F|\geq k+f-n\). Са друге стране, важи да је \(|K\cap F|\geq 0\). Зато је \(|K\cap F|\geq\max{(k+f-n, 0)}\).
Докажимо да се ова доња граница увек може достићи, тј. да је најмања вредност броја ученика који су добри у оба спорта управо \(\max{(k+f-n,0)}\). Заиста, ако је \(k+f\leq n\) могуће је да се фудбалери и кошаркаши не преклапају. Са друге стране, ако је \(k+f>n\) тада је могуће да њих \(k+f-n\) тренирају оба спорта, да \(n-f\) игра само кошарку, а \(n-k\) игра само фудбал (сви ови бројеви су ненегативни, па је могуће направити баш овакав распоред).
Са друге стране важи да је \(K\cap F\subseteq K,K\cap F\subseteq F\), па је \(|K\cap F|\leq |K|=k,|K\cap F|\leq |F|=f\), тј. \(|K\cap F|\leq\min{(k,f)}\).
Та вредност се може постићи ако је \(K\subseteq F\) или је \(F\subseteq K\) тј. ако сви они који тренирају онај спорт којег тренира мање ђака, уједно тренирају и онај други спорт.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int n, k, f;
scanf("%d%d%d", &n, &k, &f);
int max = k + f - n > 0 ? k + f - n : 0;
int min = k < f ? k : f;
printf("%d\n%d", max, min);
return 0;
}
Домине¶
Прочитај текст задатка.
Сваку од две домине је потребно окренути тако да већа цифра на тој домини буде испред мање (ако су цифре једнаке, свеједно је како се домина окреће). Редослед две домине се одређује тако да број записан на првој домини буде већи од броја записаног на другој.
Прву цифру сваке од две домине одређујемо као максимум две цифре на тој домини, а другу као њихов минимум. Два двоцифрена броја можемо упоредити и лексикографски: прва домина иде испред друге ако је њена прва цифра већа од прве цифре друге домине или су те цифре једнаке, а друга цифра прве домине је већа од друге цифре друге домине.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int d11, d12, d21, d22;
scanf("%d%d%d%d", &d11, &d12, &d21, &d22);
int m11 = d11 > d12 ? d11 : d12;
int m12 = d11 < d12 ? d11 : d12;
int m21 = d21 > d22 ? d21 : d22;
int m22 = d21 < d22 ? d21 : d22;
if (m11 > m21 || m11 == m21 && m12 > m22)
printf("%d %d %d %d", m11, m12, m21, m22);
else
printf("%d %d %d %d", m21, m22, m11, m12);
return 0;
}
Једно могуће решење је и да експлицитно формирамо двоцифрене бројеве множењем прве цифре са 10 и додавањем друге, да их затим упоредимо и да тражени четвороцифрени број добијемо множењем већег двоцифреног са 100 и додавањем мањег (ово решење је исправно јер смо сигурни да се не јавља цифра 0). Када је број формиран, цифре можемо да издвојимо коришћењем целобројног дељења са 10.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int d11, d12, d21, d22;
scanf("%d%d%d%d", &d11, &d12, &d21, &d22);
int d1 = d11 > d12 ? 10 * d11 + d12 : 10 * d12 + d11;
int d2 = d21 > d22 ? 10 * d21 + d22 : 10 * d22 + d21;
int d = d1 > d2 ? 100 * d1 + d2 : 100 * d2 + d1;
printf("%d %d %d %d", (d / 1000) % 10, (d / 100) % 10, (d / 10) % 10, (d / 1) % 10);
return 0;
}
Интервали¶
Прочитај текст задатка.
Почетак покривача два интервала је мањи од два лева краја та два интервала (тј. \(a_{pokrivac}=\min{(a_1,a_2)}\)), а крај покривача је већи од два десна краја (тј. \(b_{pokrivac}=\max{(b_1,b_2)}\)). Напоменимо и да покривач увек постоји (пробај да објасниш зашто). Почетак евентуалног пресека је већи од два лева краја (тј. \(a_{presek}=\max{(a_1,a_2)}\)), а крај евентуалног пресека је мањи од два десна краја (тј. \(b_{presek}=\min{(b_1,b_2)}\)). Пресек постоји ако и само ако је \(b_{presek}>a_{presek}\). На крају, дужину уније можемо једноставно одредити тако што од збира дужина једног и другог интервала одузме дужина пресека (дужину интервала рачунамо као разлику између његовог десног и левог краја).
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
double a1, b1, a2, b2;
scanf("%lf%lf%lf%lf", &a1, &b1, &a2, &b2);
double ap = a1 < a2 ? a1 : a2;
double bp = b1 > b2 ? b1 : b2;
printf("%.2lf %.2lf\n", ap, bp);
double ad = a1 > a2 ? a1 : a2;
double bl = b1 < b2 ? b1 : b2;
double dp;
if (bl >= ad)
{
printf("%.2lf %.2lf\n", ad, bl);
dp = bl - ad;
}
else
{
printf("presek ne postoji\n");
dp = 0.0;
}
double du = (b1 - a1) + (b2 - a2) - dp;
printf("%.2lf", du);
return 0;
}
Позитиван део интервала¶
Прочитај текст задатка.
Један начин да одредимо дужину дела интервала \([a,b]\) који лежи на позитивном делу праве је да применимо технику проналажења пресека два интервала, при чему је први интервал \([a,b]\), а други је \([0,+\infty)\). Пресек одређујемо тако што одредимо већи од два почетка (то је број \(\max{(a,0)}\)) и леви од два краја (пошто је један крај \(+\infty\) то је број \(b\)), и затим ако је крај десно од почетка та два броја одузмемо, док је у супротном резултат нула.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int a, b;
scanf("%d%d", &a, &b);
int p = b - (0 > a ? 0 : a) > 0 ? b - (0 > a ? 0 : a) : 0;
printf("%d", p);
return 0;
}
Још један начин је да одредимо десни и леви крај пресека и да их одузмемо. Десни крај је већи од бројева \(b\) и 0, док је леви крај већи од бројева \(a\) и \(0\). Зато је тражена дужина једнака \(\max{(b,0)}-\max{(a,0)}\).
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int a, b;
scanf("%d%d", &a, &b);
int p = (0 > b ? 0 : b) - (0 > a ? 0 : a);
printf("%d", p);
return 0;
}
Задатак се може решити и тако што се примени угнежђено (хијерархијско) гранање. Ако је \(b\leq 0\), тада цео интервал лежи лево од координатног почетка и дужина његовог позитивног дела је 0. У супротном, ако је \(a\geq 0\) тада цео интервал лежи десно од координатног почетка и дужина позитивног дела је \(b-a\), а у супротном, ако је \(a<0\) тада је позитивни део интервала интервал \([0,b]\) чија је дужина \(b\).
Предложено решење задатка (3)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int a, b, p;
scanf("%d%d", &a, &b);
if (b <= 0)
p = 0;
else if (a >= 0)
p = b - a;
else
p = b - 0;
printf("%d", p);
return 0;
}
Део правоугаоника у првом квадранту¶
Прочитај текст задатка.
Ако одредимо доње лево и горње десно теме (што можемо урадити применом минимума и максимума), тада површину можемо израчунати анализом разних случајева. Прво, ако се горње десно теме налази ван првог квадранта, тада је површина једнака нули. У супротном анализирамо положај доњег левог темена и у зависности од квадранта коме оно припада одређујемо површину.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int x1, y1, x2, y2, p;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int xl = x1 < x2 ? x1 : x2;
int xd = x1 > x2 ? x1 : x2;
int yd = y1 < y2 ? y1 : y2;
int yg = y1 > y2 ? y1 : y2;
if (xd <= 0 || yg <= 0)
p = 0;
else if (xl <= 0 && yd <= 0)
p = xd * yg;
else if (xl > 0 && yd <= 0)
p = (xd - xl) * yg;
else if (xl <= 0 && yd > 0)
p = xd * (yg - yd);
else
p = (xd - xl) * (yg - yd);
printf("%d", p);
return 0;
}
Задатак можемо решити и тако што одредимо дужину дела горње странице правоугаоника и дужину дела десне странице правоугаоника који припадају првом квадранту (површина дела правоугаоника у првом квадранту је онда производ те две дужине). То се своди на проналажење дела дужи на \(x\)-оси тј. \(y\)-оси који припадају позитивном делу те осе.
Пошто не знамо у ком редоследу су задате координате \(x_1\) и \(x_2\) нити у ком редоследу су задате координате \(y_1\) и \(y_2\), пре одређивања дужине позитивног дела сваког од њих врши се одређивање мањег и већег од њих (ако су \(a\) и \(b\) бројеви који представљају крајње тачке неког интервала, онда се помоћу \(l=\min{(a,b)}\) и \(d=\max{(a,b)}\) могу одредити леви и десни крај тог интервала).
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int ax = ((x1 > x2 ? x1 : x2) > 0 ? (x1 > x2 ? x1 : x2) : 0) -
((x1 < x2 ? x1 : x2) > 0 ? (x1 < x2 ? x1 : x2) : 0);
int by = ((y1 > y2 ? y1 : y2) > 0 ? (y1 > y2 ? y1 : y2) : 0) -
((y1 < y2 ? y1 : y2) > 0 ? (y1 < y2 ? y1 : y2) : 0);
printf("%d", ax * by);
return 0;
}
Још један начин је да одредимо леви и десни крај дужи (применом минимума и максимума) и да позитивни део дужи одредимо анализом случајева (ако је десни крај негативан дужина тог дела је нула, ако је позитиван, а леви је негативан, онда је једнака вредности тог десног краја, а у супротном је једнака разлици између десног и левог краја).
Предложено решење задатка (3)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int x1, y1, x2, y2, x, y;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int xl = x1 < x2 ? x1 : x2;
int xd = x1 > x2 ? x1 : x2;
if (0 <= xl)
x = xd - xl;
else if (0 <= xd)
x = xd;
else
x = 0;
int yl = y1 < y2 ? y1 : y2;
int yd = y1 > y2 ? y1 : y2;
if (0 <= yl)
y = yd - yl;
else if (0 <= yd)
y = yd;
else
y = 0;
printf("%d", x * y);
return 0;
}
Темена правоугаоника¶
Прочитај текст задатка.
Координата x леве ивице се може одредити као мања од две x-координате датих темена, док се координата x десне ивице може одредити као већа од њих. Слично, координата y горње ивице се може одредити као мања од две y-координате, док се координата y доње ивице може одредити као већа од њих. Координате горњег левог темена се добијају комбиновањем x-координате леве ивице и y-координате горње ивице, док се координате доњег десног темена добијају комбиновањем x-координате десне ивице и y-координате доње ивице.
Предложено решење задатка (1)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int xl = x1 < x2 ? x1 : x2;
int xd = x1 > x2 ? x1 : x2;
int yg = y1 < y2 ? y1 : y2;
int yd = y1 > y2 ? y1 : y2;
printf("%d %d\n%d %d", xl, yg, xd, yd);
return 0;
}
Један начин да се дође до решења је да се координате \(x_1\) и \(x_2\) уреде по величини, тј. да се размене ако је \(x_1>x_2\). Размену вредности две променљиве вршимо тако што користимо трећу, привремену. Након уређивања (кажемо и сортирања) знамо да \(x_1\) представља координату леве, а \(x_2\) десне ивице, док \(y_1\) представља координату горње, а \(y_2\) доње ивице.
Предложено решење задатка (2)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
if (x1 > x2)
{
int tmp = x1;
x1 = x2;
x2 = tmp;
}
if (y1 > y2)
{
int tmp = y1;
y1 = y2;
y2 = tmp;
}
printf("%d %d\n%d %d", x1, y1, x2, y2);
return 0;
}
H2SO4¶
Прочитај текст задатка.
Претпоставимо да је дат број атома водоника \(h\), сумпора \(s\) и кисеоника \(o\). Ако претпоставимо да је могуће направити \(x\) молекула \(H_2SO_4\), тада мора да важи да је \(2x\leq h\), \(x\leq s\) и \(4x\leq o\). Дакле, потребно је пронаћи највећи цео број \(x\) тако да важи \(x\leq h/2\), \(x\leq s\) и \(x\leq o/4\). Знамо да је \(x\leq\left\lfloor{\frac{h}{2}}\right\rfloor\), \(x\leq s\) и \(x\leq\left\lfloor{\frac{o}{4}}\right\rfloor\) па можемо закључити да је \(x=\min{(h\div 2, \ s, \ o\div 4)}\).
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
int main(void)
{
int h, s, o;
scanf("%d%d%d", &h, &s, &o);
int m = h / 2;
if (s < m)
m = s;
if (o / 4 < m)
m = o / 4;
printf("%d", m);
return 0;
}
Краљево растојање¶
Прочитај текст задатка.
Нека су \((x_1,y_1)\) координате полазног поља, а \((x_2,y_2)\) координате долазног поља. Растојање по првој координати једнако је \(|x_2-x_1|\), а по другој координати једнако је \(|y_1-y_2|\). Да би краљ стигао на жељено поље, оба ова растојања морају бити смањена на нулу. У сваком кораку (било хоризонталном, било вертикалном, било дијагоналном) свака од координата се може променити највише за један (у дијагоналном потезу истовремено се мењају обе координате, али свака за по један). Зато се у сваком од потеза хоризонтално и вертикално растојање могу смањити за један. У почетку краљ може ићи дијагонално истовремено смањујући оба растојања за по један, све док једно од растојања не постане једнако нули (док не стигне у врсту или колону у којој се налази циљно поље). Након тога може се кретати хоризонтално тј. вертикално до циља.
Дакле, број потеза потребан да се стигне до циљаног поља је једнак већем од
растојања по координатама \(x\) и \(y\) тј. једнако је вредности
\(\max{(|x_2-x_1|,|y_2-y_1|)}\). Максимум два броја се може израчунати гранањем.
Апсолутну вредност је могуће израчунати коришћењем функције abs која је за
целе бројеве декларисана у заглављу stdlib.h.
Предложено решење задатка
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int x1, y1, x2, y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
int n = abs(x1 - x2) > abs(y1 - y2) ? abs(x1 - x2) : abs(y1 - y2);
printf("%d", n);
return 0;
}