Matura 2026 — maj, poziom rozszerzony (formuła 2023)
Treść zadania
Dla dodatnich liczb całkowitych m, n funkcja A jest zdefiniowana rekurencyjnie:
- A(m, n) = m, gdy n = 1;
- A(m, n) = A(2·m, n/2), gdy n > 1 i n jest parzyste;
- A(m, n) = 2·A(m, (n − 1)/2) + m, gdy n > 1 i n jest nieparzyste.
Przykład: obliczenie A(3, 9) wymaga trzech wywołań rekurencyjnych A(3, 4), A(6, 2), A(12, 1), bo A(3, 9) = 2·A(3, 4) + 3 = 2·A(6, 2) + 3 = 2·A(12, 1) + 3 = 27.
Uzupełnij tabelę: dla par (m, n) = (2⁵, 2⁵) oraz (10, 15) podaj liczbę wywołań rekurencyjnych funkcji A i wypisz te wywołania z argumentami, a dla (1, 2¹⁰⁰ + 1) podaj tylko liczbę wywołań rekurencyjnych.
def A(m, n, wywolania):
# wywolania - lista, do której dopisujemy argumenty kolejnych wywołań rekurencyjnych
if n == 1:
return m
if n % 2 == 0:
wywolania.append((2 * m, n // 2))
return A(2 * m, n // 2, wywolania)
wywolania.append((m, (n - 1) // 2))
return 2 * A(m, (n - 1) // 2, wywolania) + m
for m, n in [(3, 9), (2 ** 5, 2 ** 5), (10, 15), (1, 2 ** 100 + 1)]:
wywolania = []
A(m, n, wywolania)
print(m, n, len(wywolania), wywolania if len(wywolania) < 10 else "")#include <print>
#include <string>
#include <utility>
#include <vector>
// n = 2^100 + 1 nie mieści się w long long - używamy 128-bitowego typu GCC (__int128)
using Liczba = __int128;
std::string na_napis(Liczba x) {
if (x == 0) {
return "0";
}
std::string s = "";
while (x > 0) {
s = char('0' + int(x % 10)) + s;
x /= 10;
}
return s;
}
// wywolania - lista, do której dopisujemy argumenty kolejnych wywołań rekurencyjnych
Liczba A(Liczba m, Liczba n, std::vector<std::pair<Liczba, Liczba>>& wywolania) {
if (n == 1) {
return m;
}
if (n % 2 == 0) {
wywolania.push_back({2 * m, n / 2});
return A(2 * m, n / 2, wywolania);
}
wywolania.push_back({m, (n - 1) / 2});
return 2 * A(m, (n - 1) / 2, wywolania) + m;
}
int main() {
Liczba jeden = 1;
std::vector<std::pair<Liczba, Liczba>> dane = {{3, 9}, {32, 32}, {10, 15}, {1, (jeden << 100) + 1}};
for (auto [m, n] : dane) {
std::vector<std::pair<Liczba, Liczba>> wywolania;
A(m, n, wywolania);
// lista par wypisana jak w Pythonie: [(3, 4), (6, 2)]
std::string lista = "";
if (wywolania.size() < 10) {
lista = "[";
for (size_t i = 0; i < wywolania.size(); i++) {
if (i > 0) {
lista += ", ";
}
lista += "(" + na_napis(wywolania[i].first) + ", " + na_napis(wywolania[i].second) + ")";
}
lista += "]";
}
std::println("{} {} {} {}", na_napis(m), na_napis(n), wywolania.size(), lista);
}
}import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
public class Zadanie {
static final BigInteger DWA = BigInteger.TWO;
// wywolania - lista, do której dopisujemy argumenty kolejnych wywołań rekurencyjnych
// (n = 2^100 + 1 nie mieści się w long - używamy BigInteger)
static BigInteger A(BigInteger m, BigInteger n, List<String> wywolania) {
if (n.equals(BigInteger.ONE)) {
return m;
}
if (n.mod(DWA).signum() == 0) {
wywolania.add("(" + m.multiply(DWA) + ", " + n.divide(DWA) + ")");
return A(m.multiply(DWA), n.divide(DWA), wywolania);
}
BigInteger polowa = n.subtract(BigInteger.ONE).divide(DWA);
wywolania.add("(" + m + ", " + polowa + ")");
return A(m, polowa, wywolania).multiply(DWA).add(m);
}
public static void main(String[] args) throws Exception {
BigInteger[][] dane = {
{BigInteger.valueOf(3), BigInteger.valueOf(9)},
{BigInteger.valueOf(32), BigInteger.valueOf(32)},
{BigInteger.valueOf(10), BigInteger.valueOf(15)},
{BigInteger.ONE, DWA.pow(100).add(BigInteger.ONE)}
};
for (BigInteger[] para : dane) {
List<String> wywolania = new ArrayList<>();
A(para[0], para[1], wywolania);
// lista wypisana jak w Pythonie: [(3, 4), (6, 2)]
String lista = wywolania.size() < 10 ? "[" + String.join(", ", wywolania) + "]" : "";
System.out.println(para[0] + " " + para[1] + " " + wywolania.size() + " " + lista);
}
}
}Odpowiedź: (2⁵, 2⁵): 5 wywołań — A(2⁶, 2⁴), A(2⁷, 2³), A(2⁸, 2²), A(2⁹, 2¹), A(2¹⁰, 2⁰); (10, 15): 3 wywołania — A(10, 7), A(10, 3), A(10, 1); (1, 2¹⁰⁰ + 1): 100 wywołań.
↑Treść zadania
Funkcja A(m, n) jest zdefiniowana w zadaniu 1.1.
Podaj wartości A(1, 777) oraz A(2·10⁶, 256·10⁶). Wynik można zapisać z użyciem mnożenia i potęgowania.
def A(m, n):
if n == 1:
return m
if n % 2 == 0:
return A(2 * m, n // 2)
return 2 * A(m, (n - 1) // 2) + m
# funkcja A liczy iloczyn m * n
print(A(1, 777))
print(A(2 * 10 ** 6, 256 * 10 ** 6))#include <print>
long long A(long long m, long long n) {
if (n == 1) {
return m;
}
if (n % 2 == 0) {
return A(2 * m, n / 2);
}
return 2 * A(m, (n - 1) / 2) + m;
}
int main() {
// funkcja A liczy iloczyn m * n (wynik 512 * 10^12 wymaga long long)
std::println("{}", A(1, 777));
std::println("{}", A(2'000'000, 256'000'000));
}public class Zadanie {
static long A(long m, long n) {
if (n == 1) {
return m;
}
if (n % 2 == 0) {
return A(2 * m, n / 2);
}
return 2 * A(m, (n - 1) / 2) + m;
}
public static void main(String[] args) throws Exception {
// funkcja A liczy iloczyn m * n (wynik 512 * 10^12 wymaga long)
System.out.println(A(1, 777));
System.out.println(A(2_000_000L, 256_000_000L));
}
}Odpowiedź: A(1, 777) = 777, A(2·10⁶, 256·10⁶) = 512·10¹² = 512 000 000 000 000 (funkcja oblicza m·n).
↑Treść zadania
Funkcja A(m, n) jest zdefiniowana w zadaniu 1.1; pierwszy argument nie ma tu znaczenia.
Dla n = 8, n = 2ᵏ oraz n = 2ᵏ − 1 podaj liczbę wywołań rekurencyjnych funkcji A oraz wyrażenie opisujące drugi argument w i-tym wywołaniu rekurencyjnym (dla i od 1 do liczby wywołań). Przykład dla n = 8: drugi argument w i-tym wywołaniu to 8/2ⁱ, czyli 2³⁻ⁱ.
def drugie_argumenty(n):
# wartości drugiego argumentu w kolejnych wywołaniach rekurencyjnych
wynik = []
while n > 1:
if n % 2 == 0:
n = n // 2
else:
n = (n - 1) // 2
wynik.append(n)
return wynik
print(8, drugie_argumenty(8))
for k in range(3, 7):
print("n = 2^%d:" % k, drugie_argumenty(2 ** k))
print("n = 2^%d - 1:" % k, drugie_argumenty(2 ** k - 1))#include <print>
#include <vector>
std::vector<int> drugie_argumenty(int n) {
// wartości drugiego argumentu w kolejnych wywołaniach rekurencyjnych
std::vector<int> wynik;
while (n > 1) {
if (n % 2 == 0) {
n = n / 2;
} else {
n = (n - 1) / 2;
}
wynik.push_back(n);
}
return wynik;
}
int main() {
// wektor wypisuje się jak lista w Pythonie: [4, 2, 1]
std::println("{} {}", 8, drugie_argumenty(8));
for (int k = 3; k < 7; k++) {
std::println("n = 2^{}: {}", k, drugie_argumenty(1 << k));
std::println("n = 2^{} - 1: {}", k, drugie_argumenty((1 << k) - 1));
}
}import java.util.ArrayList;
import java.util.List;
public class Zadanie {
static List<Integer> drugieArgumenty(int n) {
// wartości drugiego argumentu w kolejnych wywołaniach rekurencyjnych
List<Integer> wynik = new ArrayList<>();
while (n > 1) {
if (n % 2 == 0) {
n = n / 2;
} else {
n = (n - 1) / 2;
}
wynik.add(n);
}
return wynik;
}
public static void main(String[] args) throws Exception {
// lista wypisuje się jak w Pythonie: [4, 2, 1]
System.out.println(8 + " " + drugieArgumenty(8));
for (int k = 3; k < 7; k++) {
System.out.println("n = 2^" + k + ": " + drugieArgumenty(1 << k));
System.out.println("n = 2^" + k + " - 1: " + drugieArgumenty((1 << k) - 1));
}
}
}Odpowiedź: n = 8: 3 wywołania, i-te ma drugi argument 8/2ⁱ = 2³⁻ⁱ; n = 2ᵏ: k wywołań, drugi argument 2ᵏ⁻ⁱ; n = 2ᵏ − 1: k − 1 wywołań, drugi argument 2ᵏ⁻ⁱ − 1.
↑Treść zadania
Rozważamy dodawanie pisemne dwóch liczb w systemie dziesiętnym i liczymy przeniesienia, np. przy dodawaniu 27732 + 72619 = 100351 występują 4 przeniesienia.
- 2.1 — Podaj liczbę przeniesień przy dodawaniu par: 37932 + 12528 (przykład w tabeli: 3), 88765 + 11111 oraz 456789 + 222222.
- 2.2 — Zapisz (w pseudokodzie lub wybranym języku) algorytm, który dla dwóch dodatnich liczb całkowitych a i b o tej samej liczbie cyfr oblicza liczbę p przeniesień w trakcie ich dodawania pisemnego (dla 27732 i 72619 wynik to 4).
def przeniesienia(a, b):
# a i b mają tyle samo cyfr; operujemy tylko na liczbach całkowitych
w_pamieci = 0
p = 0
while a > 0:
suma = a % 10 + b % 10 + w_pamieci
if suma >= 10:
w_pamieci = 1
p += 1
else:
w_pamieci = 0
a = a // 10
b = b // 10
return p
print(przeniesienia(27732, 72619)) # przykład z treści: 4
for a, b in [(37932, 12528), (88765, 11111), (456789, 222222)]:
print(a, b, przeniesienia(a, b))#include <print>
#include <utility>
#include <vector>
int przeniesienia(int a, int b) {
// a i b mają tyle samo cyfr; operujemy tylko na liczbach całkowitych
int w_pamieci = 0;
int p = 0;
while (a > 0) {
int suma = a % 10 + b % 10 + w_pamieci;
if (suma >= 10) {
w_pamieci = 1;
p += 1;
} else {
w_pamieci = 0;
}
a = a / 10;
b = b / 10;
}
return p;
}
int main() {
std::println("{}", przeniesienia(27732, 72619)); // przykład z treści: 4
std::vector<std::pair<int, int>> pary = {{37932, 12528}, {88765, 11111}, {456789, 222222}};
for (auto [a, b] : pary) {
std::println("{} {} {}", a, b, przeniesienia(a, b));
}
}public class Zadanie {
static int przeniesienia(int a, int b) {
// a i b mają tyle samo cyfr; operujemy tylko na liczbach całkowitych
int wPamieci = 0;
int p = 0;
while (a > 0) {
int suma = a % 10 + b % 10 + wPamieci;
if (suma >= 10) {
wPamieci = 1;
p += 1;
} else {
wPamieci = 0;
}
a = a / 10;
b = b / 10;
}
return p;
}
public static void main(String[] args) throws Exception {
System.out.println(przeniesienia(27732, 72619)); // przykład z treści: 4
int[][] pary = {{37932, 12528}, {88765, 11111}, {456789, 222222}};
for (int[] p : pary) {
System.out.println(p[0] + " " + p[1] + " " + przeniesienia(p[0], p[1]));
}
}
}Odpowiedź: 2.1: 37932 + 12528 → 3, 88765 + 11111 → 0, 456789 + 222222 → 3. 2.2: funkcja przeniesienia powyżej.
Treść zadania
Plik pary.txt zawiera 500 wierszy; w każdym jest para słów z małych liter alfabetu angielskiego, oddzielonych pojedynczą spacją, każde o długości co najwyżej 50 (np. bcba babb, abaa ccc). Odpowiedzi zapisz w pliku wyniki3.txt, poprzedzając każdą numerem zadania. Plik pary_przyklad.txt (500 par) służy do testów.
Niech f(s) oznacza sumę kodów ASCII liter słowa s. Podaj parę słów s1, s2 z jednego wiersza, dla której |f(s1) − f(s2)| jest największe, oraz tę wartość (jest jedna taka para). Przykład: f(oko) = 329, f(pies) = 433, różnica 104; dla pliku przykładowego: eddcd eededcddceeecededcc 1403.
def f(slowo):
return sum(ord(znak) for znak in slowo)
najwieksza = -1
with open("pary.txt") as file:
for linia in file:
s1, s2 = linia.split()
roznica = abs(f(s1) - f(s2))
if roznica > najwieksza:
najwieksza = roznica
para = (s1, s2)
print(para[0], para[1], najwieksza)#include <cstdlib>
#include <fstream>
#include <print>
#include <string>
int f(const std::string& slowo) {
int suma = 0;
for (char znak : slowo) {
suma += znak; // kod ASCII litery
}
return suma;
}
int main() {
int najwieksza = -1;
std::string para1, para2;
std::ifstream plik("pary.txt");
std::string s1, s2;
while (plik >> s1 >> s2) {
int roznica = std::abs(f(s1) - f(s2));
if (roznica > najwieksza) {
najwieksza = roznica;
para1 = s1;
para2 = s2;
}
}
std::println("{} {} {}", para1, para2, najwieksza);
}import java.nio.file.Files;
import java.nio.file.Path;
public class Zadanie {
static int f(String slowo) {
int suma = 0;
for (char znak : slowo.toCharArray()) {
suma += znak; // kod ASCII litery
}
return suma;
}
public static void main(String[] args) throws Exception {
int najwieksza = -1;
String[] para = null;
for (String linia : Files.readAllLines(Path.of("pary.txt"))) {
String[] s = linia.trim().split("\\s+");
int roznica = Math.abs(f(s[0]) - f(s[1]));
if (roznica > najwieksza) {
najwieksza = roznica;
para = s;
}
}
System.out.println(para[0] + " " + para[1] + " " + najwieksza);
}
}Odpowiedź: gpeeazeugmvsbzwsrxfplqdbakoxxe lhpbmoirdm 2206
↑Treść zadania
Dane jak w zadaniu 3.1 (500 par słów w pliku pary.txt).
Wspólna liczba wystąpień litery x w słowach s1, s2 to W(x, s1, s2) = min(d(x, s1), d(x, s2)), gdzie d(x, s) to liczba wystąpień x w s. Podaj parę słów z jednego wiersza, dla której suma W po wszystkich literach jest największa, oraz tę sumę (jest jedna taka para). Przykład: dla adabbcdde i aadabbbccdc suma wynosi 2 + 2 + 1 + 2 = 7; dla pliku przykładowego: ccccdcedddddecde ccdcdddecc 10.
najwieksza = -1
with open("pary.txt") as file:
for linia in file:
s1, s2 = linia.split()
suma = 0
for litera in "abcdefghijklmnopqrstuvwxyz":
suma += min(s1.count(litera), s2.count(litera))
if suma > najwieksza:
najwieksza = suma
para = (s1, s2)
print(para[0], para[1], najwieksza)#include <algorithm>
#include <fstream>
#include <print>
#include <string>
int main() {
int najwieksza = -1;
std::string para1, para2;
std::ifstream plik("pary.txt");
std::string s1, s2;
while (plik >> s1 >> s2) {
int suma = 0;
for (char litera = 'a'; litera <= 'z'; litera++) {
suma += std::min(std::ranges::count(s1, litera), std::ranges::count(s2, litera));
}
if (suma > najwieksza) {
najwieksza = suma;
para1 = s1;
para2 = s2;
}
}
std::println("{} {} {}", para1, para2, najwieksza);
}import java.nio.file.Files;
import java.nio.file.Path;
public class Zadanie {
static int ile(String s, char litera) {
int wynik = 0;
for (char c : s.toCharArray()) {
if (c == litera) {
wynik++;
}
}
return wynik;
}
public static void main(String[] args) throws Exception {
int najwieksza = -1;
String[] para = null;
for (String linia : Files.readAllLines(Path.of("pary.txt"))) {
String[] s = linia.trim().split("\\s+");
int suma = 0;
for (char litera = 'a'; litera <= 'z'; litera++) {
suma += Math.min(ile(s[0], litera), ile(s[1], litera));
}
if (suma > najwieksza) {
najwieksza = suma;
para = s;
}
}
System.out.println(para[0] + " " + para[1] + " " + najwieksza);
}
}Odpowiedź: aacbcccaacacbcabac cccccaaaacaccbabcba 18
↑Treść zadania
Dane jak w zadaniu 3.1.
Prefiksosufiks pary słów s1, s2 to słowo, które jest początkiem s1 i końcem s2 albo początkiem s2 i końcem s1. Wypisz wszystkie pary z pliku, których najdłuższy prefiksosufiks ma co najmniej 5 liter, a przy każdej podaj długość tego najdłuższego prefiksosufiksu. Przykład: dla aabbbca caacaab najdłuższy prefiksosufiks to aab (3 litery) — para nie spełnia warunku; dla abbaabaa baabaabba jest to baabaa (6) — spełnia; dla pliku przykładowego: ececdddeed dddeedd 6.
def najdluzszy_prefiksosufiks(s1, s2):
for dlugosc in range(min(len(s1), len(s2)), 0, -1):
if s1[:dlugosc] == s2[-dlugosc:] or s2[:dlugosc] == s1[-dlugosc:]:
return dlugosc
return 0
with open("pary.txt") as file:
for linia in file:
s1, s2 = linia.split()
dlugosc = najdluzszy_prefiksosufiks(s1, s2)
if dlugosc >= 5:
print(s1, s2, dlugosc)#include <algorithm>
#include <fstream>
#include <print>
#include <string>
int najdluzszy_prefiksosufiks(const std::string& s1, const std::string& s2) {
for (int dlugosc = std::min(s1.size(), s2.size()); dlugosc > 0; dlugosc--) {
// prefiks jednego słowa równy sufiksowi drugiego
if (s1.substr(0, dlugosc) == s2.substr(s2.size() - dlugosc)
|| s2.substr(0, dlugosc) == s1.substr(s1.size() - dlugosc)) {
return dlugosc;
}
}
return 0;
}
int main() {
std::ifstream plik("pary.txt");
std::string s1, s2;
while (plik >> s1 >> s2) {
int dlugosc = najdluzszy_prefiksosufiks(s1, s2);
if (dlugosc >= 5) {
std::println("{} {} {}", s1, s2, dlugosc);
}
}
}import java.nio.file.Files;
import java.nio.file.Path;
public class Zadanie {
static int najdluzszyPrefiksosufiks(String s1, String s2) {
for (int dlugosc = Math.min(s1.length(), s2.length()); dlugosc > 0; dlugosc--) {
// prefiks jednego słowa równy sufiksowi drugiego
if (s2.endsWith(s1.substring(0, dlugosc)) || s1.endsWith(s2.substring(0, dlugosc))) {
return dlugosc;
}
}
return 0;
}
public static void main(String[] args) throws Exception {
for (String linia : Files.readAllLines(Path.of("pary.txt"))) {
String[] s = linia.trim().split("\\s+");
int dlugosc = najdluzszyPrefiksosufiks(s[0], s[1]);
if (dlugosc >= 5) {
System.out.println(s[0] + " " + s[1] + " " + dlugosc);
}
}
}
}Odpowiedź:
bbbbaabbababbaaaa baaaaabaaabbbabab 5
aababbbababbbbbbaab bbbbaabbababababa 7
aaaababaaaabbbb aabbbbbabbbaaaa 6
bbbbabaaabbbabb aaababaabbbbbbba 5
ccccabacbba acbbabcbcbcbaa 5
caabbccabccc cabccccabbaac 6
abaacabcccccabbbc abbbcbbbbbcabaca 5Treść zadania
W korporacji pracuje n osób o numerach 1..n. Pracownik 1 jest prezesem i nie ma przełożonego; każdy inny ma dokładnie jednego bezpośredniego przełożonego o mniejszym numerze. Przełożonymi pracownika są jego bezpośredni przełożony i wszyscy przełożeni tamtego; podwładni są zdefiniowani odwrotnie. W przykładowej hierarchii (rysunek w arkuszu) bezpośrednimi przełożonymi pracowników 2–8 są kolejno 1, 2, 1, 2, 2, 3, 4.
Dla każdego pracownika z przykładowej hierarchii podaj liczbę jego bezpośrednich podwładnych oraz liczbę wszystkich podwładnych.
# przykładowa hierarchia z Rysunku 1. (zapis jak w pliku: przełożony pracownika i)
szef = [0, 1, 2, 1, 2, 2, 3, 4]
n = len(szef)
bezposredni = [0] * (n + 1)
wszyscy = [0] * (n + 1)
for i in range(2, n + 1):
bezposredni[szef[i - 1]] += 1
p = szef[i - 1]
while p != 0: # każdy przełożony pracownika i ma go wśród podwładnych
wszyscy[p] += 1
p = szef[p - 1]
for i in range(1, n + 1):
print(i, bezposredni[i], wszyscy[i])#include <print>
#include <vector>
int main() {
// przykładowa hierarchia z Rysunku 1. (zapis jak w pliku: przełożony pracownika i)
std::vector<int> szef = {0, 1, 2, 1, 2, 2, 3, 4};
int n = szef.size();
std::vector<int> bezposredni(n + 1, 0);
std::vector<int> wszyscy(n + 1, 0);
for (int i = 2; i <= n; i++) {
bezposredni[szef[i - 1]] += 1;
int p = szef[i - 1];
while (p != 0) { // każdy przełożony pracownika i ma go wśród podwładnych
wszyscy[p] += 1;
p = szef[p - 1];
}
}
for (int i = 1; i <= n; i++) {
std::println("{} {} {}", i, bezposredni[i], wszyscy[i]);
}
}public class Zadanie {
public static void main(String[] args) throws Exception {
// przykładowa hierarchia z Rysunku 1. (zapis jak w pliku: przełożony pracownika i)
int[] szef = {0, 1, 2, 1, 2, 2, 3, 4};
int n = szef.length;
int[] bezposredni = new int[n + 1];
int[] wszyscy = new int[n + 1];
for (int i = 2; i <= n; i++) {
bezposredni[szef[i - 1]] += 1;
int p = szef[i - 1];
while (p != 0) { // każdy przełożony pracownika i ma go wśród podwładnych
wszyscy[p] += 1;
p = szef[p - 1];
}
}
for (int i = 1; i <= n; i++) {
System.out.println(i + " " + bezposredni[i] + " " + wszyscy[i]);
}
}
}Odpowiedź: 1: 2 i 7; 2: 3 i 4; 3: 1 i 1; 4: 1 i 1; 5, 6, 7, 8: 0 i 0.
↑Treść zadania
Plik korpo.txt zawiera n = 50 000 liczb, po jednej w wierszu, opisujących strukturę korporacji z zadania 4.1: w pierwszym wierszu jest 0 (prezes nie ma przełożonego), a w i-tym wierszu (2 ≤ i ≤ 50 000) — numer bezpośredniego przełożonego pracownika i (dla przykładowej hierarchii: 0 1 2 1 2 2 3 4). Odpowiedzi zapisz w pliku wyniki4.txt, poprzedzając każdą numerem zadania. W pliku testowym korpo_przyklad.txt przełożonym pracowników 2 i 3 jest 1, a wszystkich pozostałych — 3.
- 4.2 — Podaj, ilu pracowników nie jest przełożonym nikogo (dla pliku przykładowego: 49 998).
- 4.3 — Podaj numer pracownika mającego najwięcej bezpośrednich podwładnych oraz ich liczbę (dla pliku przykładowego:
3 49997). - 4.4 — Podaj największą liczbę przełożonych, jaką ma jeden pracownik, oraz liczbę pracowników mających tylu przełożonych (dla pliku przykładowego:
2 49997).
szef = [0] # szef[i] - bezpośredni przełożony pracownika i (indeks 0 nieużywany)
with open("korpo.txt") as file:
for linia in file:
szef.append(int(linia))
n = len(szef) - 1
# 4.2
podwladni = [0] * (n + 1)
for i in range(2, n + 1):
podwladni[szef[i]] += 1
print("4.2", podwladni[1:].count(0))
# 4.3
numer = 1
for i in range(2, n + 1):
if podwladni[i] > podwladni[numer]:
numer = i
print("4.3", numer, podwladni[numer])
# 4.4 - liczba przełożonych = głębokość pracownika w drzewie
glebokosc = [-1] * (n + 1)
glebokosc[1] = 0
for i in range(2, n + 1):
sciezka = []
p = i
while glebokosc[p] == -1:
sciezka.append(p)
p = szef[p]
for q in reversed(sciezka):
glebokosc[q] = glebokosc[szef[q]] + 1
najwiecej = max(glebokosc)
print("4.4", najwiecej, glebokosc.count(najwiecej))#include <algorithm>
#include <fstream>
#include <print>
#include <vector>
int main() {
std::vector<int> szef = {0}; // szef[i] - bezpośredni przełożony pracownika i (indeks 0 nieużywany)
std::ifstream plik("korpo.txt");
int x;
while (plik >> x) {
szef.push_back(x);
}
int n = szef.size() - 1;
// 4.2
std::vector<int> podwladni(n + 1, 0);
for (int i = 2; i <= n; i++) {
podwladni[szef[i]] += 1;
}
std::println("4.2 {}", std::count(podwladni.begin() + 1, podwladni.end(), 0));
// 4.3
int numer = 1;
for (int i = 2; i <= n; i++) {
if (podwladni[i] > podwladni[numer]) {
numer = i;
}
}
std::println("4.3 {} {}", numer, podwladni[numer]);
// 4.4 - liczba przełożonych = głębokość pracownika w drzewie
std::vector<int> glebokosc(n + 1, -1);
glebokosc[1] = 0;
for (int i = 2; i <= n; i++) {
std::vector<int> sciezka;
int p = i;
while (glebokosc[p] == -1) {
sciezka.push_back(p);
p = szef[p];
}
for (int j = sciezka.size() - 1; j >= 0; j--) {
int q = sciezka[j];
glebokosc[q] = glebokosc[szef[q]] + 1;
}
}
int najwiecej = std::ranges::max(glebokosc);
std::println("4.4 {} {}", najwiecej, std::ranges::count(glebokosc, najwiecej));
}import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Zadanie {
public static void main(String[] args) throws Exception {
List<Integer> szef = new ArrayList<>(); // szef[i] - bezpośredni przełożony pracownika i (indeks 0 nieużywany)
szef.add(0);
for (String linia : Files.readAllLines(Path.of("korpo.txt"))) {
if (!linia.isBlank()) {
szef.add(Integer.parseInt(linia.trim()));
}
}
int n = szef.size() - 1;
// 4.2
int[] podwladni = new int[n + 1];
for (int i = 2; i <= n; i++) {
podwladni[szef.get(i)] += 1;
}
int bezPodwladnych = 0;
for (int i = 1; i <= n; i++) {
if (podwladni[i] == 0) {
bezPodwladnych++;
}
}
System.out.println("4.2 " + bezPodwladnych);
// 4.3
int numer = 1;
for (int i = 2; i <= n; i++) {
if (podwladni[i] > podwladni[numer]) {
numer = i;
}
}
System.out.println("4.3 " + numer + " " + podwladni[numer]);
// 4.4 - liczba przełożonych = głębokość pracownika w drzewie
int[] glebokosc = new int[n + 1];
Arrays.fill(glebokosc, -1);
glebokosc[1] = 0;
for (int i = 2; i <= n; i++) {
List<Integer> sciezka = new ArrayList<>();
int p = i;
while (glebokosc[p] == -1) {
sciezka.add(p);
p = szef.get(p);
}
for (int j = sciezka.size() - 1; j >= 0; j--) {
int q = sciezka.get(j);
glebokosc[q] = glebokosc[szef.get(q)] + 1;
}
}
int najwiecej = -1;
for (int g : glebokosc) {
najwiecej = Math.max(najwiecej, g);
}
int ile = 0;
for (int g : glebokosc) {
if (g == najwiecej) {
ile++;
}
}
System.out.println("4.4 " + najwiecej + " " + ile);
}
}Odpowiedź: 4.2: 25113; 4.3: 2 19 (pracownik 2 ma 19 bezpośrednich podwładnych); 4.4: 22 2 (najwięcej przełożonych: 22, mają ich 2 osoby).
↑Treść zadania
Uzupełnij brakujące liczby tak, aby obie równości były prawdziwe: 1440₅ + …₅ = 427₁₀ = …₃ − 110002₃ (pierwsza luka w systemie piątkowym, druga w trójkowym).
def na_system(liczba, podstawa):
cyfry = ""
while liczba > 0:
cyfry = str(liczba % podstawa) + cyfry
liczba //= podstawa
return cyfry
# 1440(5) + x(5) = 427(10) = y(3) - 110002(3)
x = 427 - int("1440", 5)
y = 427 + int("110002", 3)
print(na_system(x, 5), na_system(y, 3))#include <print>
#include <string>
std::string na_system(int liczba, int podstawa) {
std::string cyfry = "";
while (liczba > 0) {
cyfry = std::to_string(liczba % podstawa) + cyfry;
liczba /= podstawa;
}
return cyfry;
}
int main() {
// 1440(5) + x(5) = 427(10) = y(3) - 110002(3)
// std::stoi(napis, nullptr, podstawa) działa jak int(napis, podstawa) w Pythonie
int x = 427 - std::stoi("1440", nullptr, 5);
int y = 427 + std::stoi("110002", nullptr, 3);
std::println("{} {}", na_system(x, 5), na_system(y, 3));
}public class Zadanie {
static String naSystem(int liczba, int podstawa) {
String cyfry = "";
while (liczba > 0) {
cyfry = (liczba % podstawa) + cyfry;
liczba /= podstawa;
}
return cyfry;
}
public static void main(String[] args) throws Exception {
// 1440(5) + x(5) = 427(10) = y(3) - 110002(3)
// Integer.parseInt(napis, podstawa) działa jak int(napis, podstawa) w Pythonie
int x = 427 - Integer.parseInt("1440", 5);
int y = 427 + Integer.parseInt("110002", 3);
System.out.println(naSystem(x, 5) + " " + naSystem(y, 3));
}
}Odpowiedź: (1440)₅ + (1212)₅ = (427)₁₀ = (1000220)₃ − (110002)₃
↑