Основи програмирања

БРТСИ1300 / ОЕ1-ОП

View on GitHub

Основи програмирања: колоквијум 2024.

Задатак A

Млади програмер Перица једног сунчаног дана је наишао на пећину. Перица као знатижељни дечак кренуо је у истрагу те пећине. Када је ушао открио је да се ту налази тачно N сталактита, који су индексирани од 1 до N редом. Познато је да се $i-ти$ сталактит налази на висини Hi у односу на земљу. Последњи пут када је Перица мерио своју висину, она је износила тачно $L$.


Перица је ушао у пећину и ходао док није наишао на сталактит који не може да заобиђе. Прецизније, он може да прође поред сталактита уколико се најнижи део сталактита налази изнад њега.


Ваш задатак је да помогнете Перици и да одредите редни број, односно индекс сталактита где би се он зауставио. Уколико Перица може да прође кроз целу пећину, онда је потребно исписати -1.


Опис улаза

У првом реду стандардног улаза, налазе се два природна броја $N$ и $L$, који представљају број сталактита и Перичину висину, респективно. У другом и последњем реду стандардног улаза се налазе $N$ природних бројева, где $i-ти$ број представља $H_i$ - висину $i-тог$ сталактита.


Опис излаза

У првој и јединој линији стандардног излаза исписати редни број, односно индекс траженог сталактита, или −1 уколико он не постоји.

Решење
N, L = map(int,input().split())
H = list(map(int,input().split()))

if min(H) > L:
    print(-1)

for i in range(N):
    if H[i] <= L:
        print(i+1)
        break

Текстуално објашњење
Прво се извршава провера случаја да Перица може проћи кроз читаву пећину; поменути случај је могућ уколико је најдужи сталактит (чији је крај најнижи гледајући од земље) виши од Перице. Уколико није тако, проласком кроз низ висина сталактита се тражи први који Перица не може заобићи, и потом се као излаз програма штампа његов индекс увећан за један (пошто су у задатку сталактити индексирани од $1$ до $N$ редом, а познато је да у пајтону индексирање креће од $0$).

Задатак B

Учитељица Милена, наша вољена познаница, неретко има обичај да примерено понашање и залагање награди слаткишима. Обично подели слаткише насумично, па потом примети да неки ђаци имају мање слаткиша од осталих.


Како би сви Миленини ђаци били задовољни, она потом неким ђацима подели додатан број слаткиша, тако да на крају сви ђаци добију од ње једнак број слаткиша.


Ваш задатак је одредити најмањи број додатних слаткиша које Милена мора поделити ђацима, ако знате број ђака у учионици, као и број слаткиша који је до сада поделила сваком од ђака.


Опис улаза


У првом реду стандардног улаза налази се природан број $n$ ($1 \le n \le 100$), који представља укупан број ђака.


У другом и последњем реду стандардног улаза налази се $n$ природних бројева ($s_1, s_2, … , s_n$), где $s_i$ представља број слаткиша који је добио $i-ти$ ђак.


Опис излаза


У првом и једином реду стандардног излаза исписати најмањи могући број слаткиша које учитељица Милена мора додатно поделити, како би сви ученици имали једнак број слаткиша.


Решење
n = int(input())
s = list(map(int,input().split()))
sum_s = sum(s)
M = max(s)

print(M * n - sum_s)
Текстуално објашњење
Из поставке су дата 2 предуслова за додатну поделу слаткиша: * Потребно је да након додале сви ђаци имају исти број слаткиша. * Милену занима најмањи потребан број да испуни први услов. Поменути услови су испуњени уколико након друге доделе сви ђаци имају онолико слаткиша колико је након прве доделе имао ђак са највише слаткиша. Другим речима, након друге доделе, укупан број подељених слаткиша ће бити једнак производу броја ђака и највећем броју слаткиша које је добио један од ђака у првој додели. Укупан број слаткиша подељених у првој итерацији одговара суми чланова низа $s$. Разлика броја слаткиша након прве и након друге доделе управо јесте решење задатка.

Задатак C

Ваш задатак је да имплементирате алгоритам за рачунање контролне цифре помоћу Лунове формуле. Лунова формула (или Лунов алгоритам) је такође позната као мод 10 алгоритам, а име је добила по свом креатору, научнику под називом Ханс Петар Лун. Поменута формула је једноставан начин валидације идентификационих бројева на основу вредности контролне цифре.


Израчунавање контролне цифре применом Лунове формуле се извршава на следећи начин:

kontrolna_cifra = (10 - (s \mod 10)) \mod 10 .


Опис улаза


У првом реду стандардног улаза налази се број $N$, који означава број различитих случајева унутар тест примера.


У наредних $N$ редова стандардног улаза, налази се по $1$ идентификациони број $ID_i$ за који је потребно одредити контролну цифру применом Лунове формуле.


Опис излаза


Потребно је у $N$ редова стандардног излаза исписати израчунате контролне цифре на основу прослеђених идентификационих бројева.


Решење
def luhn(n):
    r = [int(ch) for ch in str(n)][::-1]
    checksum = sum(r[1::2]) + sum(sum(divmod(d * 2, 10)) for d in r[0::2])
    luhn_digit = (10 - (checksum % 10)) % 10
    return luhn_digit

N = int(input())
for _ in range(N):
    n = int(input())
    print(luhn(n))

Текстуално објашњење
У суштини, неопходно је само пратити формуле из поставке задатка. Ради лакшег рада са индексима може се изокренути унети низ са цифрама (опционо). Рачунање суме је подразумевало 2 подскупа цифара, од којих се за први креће од последње цифре (прве ако је низ изокренут), узима свака друга, множе се са 2, а потом сабирају. Неопходно је било водити рачуна о томе да резултати поменутог множења могу изаћи из опсега, односно резултовати двоцифреним бројевима, које је потом потребно раставити на појединачне цифре и сабрати. Функција [divmod](https://www.w3schools.com/python/ref_func_divmod.asp) се бави поменутим растављањем, односно прави поворку састојану од резултата дељења са 10 (значи враћа цео део и остатак као 2 члана поворке). За други подскуп цифара је било неопходно извршити класично сабирање, а потом и две поменуте суме сабрати заједно. Коначно, контролна цифра се рачуна применом формуле из поставке, где се mod оператор мења одговарајућим оператором у пајтону, односно /%.

Задатак D

Плесни клуб Fiesta из Крагујевца добио је појачање у виду новог кореографа Које. Која је до скоро бивствовао у Берлину, и одатле са собом доноси нову сензацију - Танц Шафл!


Поменута кореографија је релативно једноставна, а изгледа овако:


Плесачима је кореографија на први поглед деловала збуњујуће и бесмислено, но одлучили су да се опробају и дају новом кореографу шансу. Међутим, наишли су на проблем током вежбања: Да би кореографију навежбали, потребно је поновити исти сет корака више пута. Када би извршили поменути Шафл три пута, нису могли засигурно да се сете почетног распореда од ког су кренули.


Помозите плесачима и кореографу Који да адекватно навежбају Танц Шафл. Потребно је да одредите иницијални распоред плесача, уколико вам је познат број плесача који учествују у изведби, образац по којем се премештају плесачи, као и њихов коначан распоред, након три итерације премештања.


Опис улаза


У првом реду стандардног улаза налази се природан број $N$.


У другом реду стандардног улаза налази се $N$ природних бројева, и то $a_1, a_2, … , a_N$, а који се односе на образац Шафл-а.


У последњем реду стандардног улаза налази се $N$ природних бројева, и то распоред плесача по позицијама након три итерације Шафл-а. Сваки од $N$ природних бројева представља идентификациони број плесача.


Опис излаза


Потребно је у $N$ редова стандардног излаза исписати по један идентификациони број плесача, пратећи њихов иницијални распоред.


Решење
N = int(input())
A = list(map(int,input().split()))
order = list(map(int,input().split()))
original_order = [0 for i in range(N)]

for _ in range(3):
    for i in range(N):
        original_order[i] = order[A[i]-1]
    order = original_order[::]


for i in range(N):
    print(order[i])

Текстуално објашњење
Задатак је решен применом *шафл*-а уназад. Односно, употребљена је правилност описана *шафл*-ом, која казује да *i-ти* члан иде на $A_i-ту$ позицију. Поменут инверзни *шафл* је примењен три пута како би се дошло до оригиналног распореда.

Задатак E

Учитељица Милена, наша вољена познаница, добила је нову генерацију ђака. Претходне сезоне је имала иновативну идеју за изучавање енглеске абецеде; ове сезоне планира да анимира децу док их учи бројању!


Конкретно, идеја јој је следећа:


Примера ради, бројање до $24$ би изгледало овако:

1, 2, Бум!, 4, Трас!, Бум!, 7, 8, Бум!, Трас!, 11, Бум!, 13, 14, Бум-Трас!, 16, 17, Бум!, 19, Трас!, Бум!, 22, 23, Бум!.


Учитељица Милена има задатак и за Вас! Она Вас пита до ког броја су избројали њени ђаци ако су изговорили $N$ бројева наглас.


Опис улаза


У првом и једином реду стандардног улаза налази се број $N$.


Опис излаза


У првом и једином реду стандардног излаза потребно је исписати $N$-ти број који су изговорили њени ђаци.


Решење
br = 0
k = 0
n = int(input())
while True:
    if k%3 != 0 and k%5 != 0:
        br += 1
    if br == n:
        break
    k+=1

print(k)
Текстуално објашњење
Најједноставније, а у овом случају и довољно ефикасно решење, јесте исцрпно набрајање бројева, уз проверу њихове дељивости са 3 и 5. Када се изброји $n$ бројева који нису дељиви ни са 3 ни са 5 (самим тим ни са 15), извршено је k итерација, где k одговара решењу задатка. Охрабрују се студенти да покушају имплементирати ефикасније решење.