1. Csokikóstolás
Egy reklámcég új csokoládé-választékot hirdet, és szeretne csokoládémintákat eljuttatni egy körben ülő n (10 ≤ n ≤ 10 000 000) gyermekhez.
A cég alkalmazottai rájönnek, hogy a minták minden gyermek számára történő kiosztása nagyon költséges lenne.
Következésképpen úgy döntenek, hogy a mintákat minden k (0 < k < n) gyermekre osztják szét az n-től,
és megszámolják a gyermekeket k-nként.
(amikor a szám eléri az utolsó gyermeket, akkor az az első gyermekével folytatódik és így tovább).
A számlálás során minden gyermeket figyelembe veszünk, függetlenül attól,
hogy csokoládét kaptak-e vagy sem. A csokiosztás leáll,
amikor egy csokoládét egy olyan gyermeknek kellene adni, aki már megkapta.
Írjon egy függvényt, amely meghatározza azon gyermekek számát, akik nem kapnak csokoládémintát.
A bemeneti paraméterek az n és k természetes számok,
s visszatéríti azon gyermekek számát (nr), akik nem kaptak csokoládét.
1. példa:
Forrás: 2017, BBTE Informatika Felvételi, I/1
2. Egyszerűsítés
Adott két sorozat, a(n) és b(m) (1 ≤ n ≤ 10000 , 1 ≤ m ≤ 10000), amelyek természetes számokból állnak.
Egy részsorozat alatt az egymásutáni elemeket értjük. Azt mondjuk, hogy az a sorozat redukálható b sorozatra,
ha a b elemei felírhatóak az a bizonyos részsorozatainak összegeként.
Írjon egy alprogramot, amely meghatározza, hogy a sorozat redukálható-e b sorozatra.
Ha igen, akkor azonosítsa
a b sorozatban lévő elemet (és ennek az elemnek a k indexét), amelyet a leghosszabb részsorozat összeadásával kapunk.
Az alprogram bemeneti paramétereként megadjuk az a és b sorozatokat, valamint azok hosszát, (n és m),
illetve a kimeneti paraméterekként red, k és nrMax, ahol:
Ha az a nem redukálható b re, akkor k és nrMax = -1.
Ha több ugyanolyan hosszú leghosszabb sorozat van, akkor az elsőnek vesszük az indexét.
1. példa
2. példa