Matura 2022 — maj, poziom rozszerzony (formuła 2015)
ARKUSZ CZ. IARKUSZ CZ. IIDANEODPOWIEDZI
Treść zadania (n-permutacja): n-permutacją nazywamy n-elementowy ciąg liczb całkowitych zawierający każdą z liczb 1, 2, …, n dokładnie raz, np. (4,2,1,3) jest 4-permutacją, a (1,3,1,2) czy (2,3,4,5) nie są. W ciągu, który nie jest n-permutacją, można podmienić niektóre elementy, aby nią był – np. w (1,3,1) wystarczy zmienić jedną jedynkę na 2.
- 1.1 — Dla podanych ciągów wpisz najmniejszą liczbę elementów do podmiany (0, jeśli ciąg już jest n-permutacją): n=4 (1,4,2,5); n=5 (2,2,2,2,2); n=4 (4,2,3,1); n=6 (5,4,1,5,6,8); n=6 (8,4,9,6,5,7). Przykład: n=3 (1,3,1) → 1.
- 1.2 — Zapisz algorytm, który dla tablicy
A[1..n]dodatnich liczb całkowitych obliczy minimalną liczbękelementów do podmiany, aby powstała n-permutacja. Wolno używać tylko instrukcji sterujących, podstawowych operatorów arytmetycznych (w tymdiv,mod), logicznych, porównań, odwołań do elementów tablicy i przypisań – bez funkcji wbudowanych.
def do_podmiany(A):
n = len(A)
wystapienia = [0] * (n + 1) # wystapienia[x] - ile razy liczba x (1..n) jest w A
k = 0
for x in A:
if 1 <= x <= n:
wystapienia[x] += 1
else:
k += 1 # liczba spoza [1, n] na pewno do podmiany
for x in range(1, n + 1):
if wystapienia[x] > 1:
k += wystapienia[x] - 1 # wszystkie powtórzenia poza jednym
return k
for A in [[1, 3, 1], [1, 4, 2, 5], [2, 2, 2, 2, 2], [4, 2, 3, 1], [5, 4, 1, 5, 6, 8], [8, 4, 9, 6, 5, 7]]:
print(A, do_podmiany(A))#include <print>
#include <vector>
int do_podmiany(const std::vector<int>& A) {
int n = A.size();
std::vector<int> wystapienia(n + 1, 0); // wystapienia[x] - ile razy liczba x (1..n) jest w A
int k = 0;
for (int x : A) {
if (1 <= x && x <= n)
wystapienia[x]++;
else
k++; // liczba spoza [1, n] na pewno do podmiany
}
for (int x = 1; x <= n; x++)
if (wystapienia[x] > 1) k += wystapienia[x] - 1; // wszystkie powtórzenia poza jednym
return k;
}
int main() {
std::vector<std::vector<int>> tablice = {{1, 3, 1}, {1, 4, 2, 5}, {2, 2, 2, 2, 2},
{4, 2, 3, 1}, {5, 4, 1, 5, 6, 8}, {8, 4, 9, 6, 5, 7}};
for (auto& A : tablice) std::println("{} {}", A, do_podmiany(A));
}import java.util.*;
public class Zadanie {
static int doPodmiany(int[] A) {
int n = A.length;
int[] wystapienia = new int[n + 1]; // wystapienia[x] - ile razy liczba x (1..n) jest w A
int k = 0;
for (int x : A) {
if (1 <= x && x <= n)
wystapienia[x]++;
else
k++; // liczba spoza [1, n] na pewno do podmiany
}
for (int x = 1; x <= n; x++)
if (wystapienia[x] > 1) k += wystapienia[x] - 1; // wszystkie powtórzenia poza jednym
return k;
}
public static void main(String[] args) throws Exception {
int[][] tablice = {{1, 3, 1}, {1, 4, 2, 5}, {2, 2, 2, 2, 2},
{4, 2, 3, 1}, {5, 4, 1, 5, 6, 8}, {8, 4, 9, 6, 5, 7}};
for (var A : tablice) System.out.println(Arrays.toString(A) + " " + doPodmiany(A));
}
}Odpowiedź: 1.1: (1,3,1) → 1, (1,4,2,5) → 1, (2,2,2,2,2) → 4, (4,2,3,1) → 0, (5,4,1,5,6,8) → 2, (8,4,9,6,5,7) → 3. 1.2: do podmiany są liczby spoza [1, n] oraz wszystkie powtórzenia (poza jednym wystąpieniem) liczb z [1, n] — funkcja do_podmiany.
Treść zadania
Dla słowa s długości n złożonego z liter a i b wykonujemy algorytm, którego wynikiem jest k:
A[0] ← 0
dla i = 1..n: jeżeli s[i] = 'a' to A[i] ← A[i-1] + 1, w p.p. A[i] ← A[i-1]
B[n+1] ← 0
dla j = n..1: jeżeli s[j] = 'b' to B[j] ← B[j+1] + 1, w p.p. B[j] ← B[j+1]
k ← 1
dla i = 0..n: jeżeli A[i] + B[i+1] > k to k ← A[i] + B[i+1]- 2.1 — Podaj wynik k dla słów
aababb(n=6) ibaabbaaab(n=9). Przykłady:aabab→ 4,ab→ 2,aaa→ 3. - 2.2 — Podaj przykłady dziesięcioliterowych słów, dla których k = 10 oraz k = 5.
- 2.3 — Zapis aᵐ (bᵐ) oznacza literę a (b) powtórzoną m razy. Podaj wynik k dla słowa a³⁰⁰b⁵⁵⁰a³⁰⁰b⁷a²⁸⁰b¹¹⁰.
def algorytm(s):
n = len(s)
s = " " + s # indeksowanie od 1 jak w treści
A = [0] * (n + 2)
for i in range(1, n + 1):
if s[i] == "a":
A[i] = A[i - 1] + 1
else:
A[i] = A[i - 1]
B = [0] * (n + 2)
for j in range(n, 0, -1):
if s[j] == "b":
B[j] = B[j + 1] + 1
else:
B[j] = B[j + 1]
k = 1
for i in range(0, n + 1):
if A[i] + B[i + 1] > k:
k = A[i] + B[i + 1]
return k
# 2.1
for s in ["aabab", "ab", "aaa", "aababb", "baabbaaab"]:
print(s, algorytm(s))
# 2.2 - k = najdłuższy podciąg postaci a...ab...b; szukamy przykładów
print("aaaaabbbbb", algorytm("aaaaabbbbb"))
print("bbbbbaaaaa", algorytm("bbbbbaaaaa"))
# 2.3
print(algorytm("a" * 300 + "b" * 550 + "a" * 300 + "b" * 7 + "a" * 280 + "b" * 110))#include <print>
#include <string>
#include <vector>
int algorytm(std::string s) {
int n = s.size();
s = " " + s; // indeksowanie od 1 jak w treści
std::vector<int> A(n + 2, 0);
for (int i = 1; i <= n; i++) {
if (s[i] == 'a')
A[i] = A[i - 1] + 1;
else
A[i] = A[i - 1];
}
std::vector<int> B(n + 2, 0);
for (int j = n; j >= 1; j--) {
if (s[j] == 'b')
B[j] = B[j + 1] + 1;
else
B[j] = B[j + 1];
}
int k = 1;
for (int i = 0; i <= n; i++)
if (A[i] + B[i + 1] > k) k = A[i] + B[i + 1];
return k;
}
int main() {
// 2.1
for (std::string s : {"aabab", "ab", "aaa", "aababb", "baabbaaab"})
std::println("{} {}", s, algorytm(s));
// 2.2 - k = najdłuższy podciąg postaci a...ab...b; szukamy przykładów
std::println("aaaaabbbbb {}", algorytm("aaaaabbbbb"));
std::println("bbbbbaaaaa {}", algorytm("bbbbbaaaaa"));
// 2.3
std::string s = std::string(300, 'a') + std::string(550, 'b') + std::string(300, 'a') +
std::string(7, 'b') + std::string(280, 'a') + std::string(110, 'b');
std::println("{}", algorytm(s));
}public class Zadanie {
static int algorytm(String s) {
int n = s.length();
s = " " + s; // indeksowanie od 1 jak w treści
int[] A = new int[n + 2];
for (int i = 1; i <= n; i++) {
if (s.charAt(i) == 'a')
A[i] = A[i - 1] + 1;
else
A[i] = A[i - 1];
}
int[] B = new int[n + 2];
for (int j = n; j >= 1; j--) {
if (s.charAt(j) == 'b')
B[j] = B[j + 1] + 1;
else
B[j] = B[j + 1];
}
int k = 1;
for (int i = 0; i <= n; i++)
if (A[i] + B[i + 1] > k) k = A[i] + B[i + 1];
return k;
}
public static void main(String[] args) throws Exception {
// 2.1
for (String s : new String[] {"aabab", "ab", "aaa", "aababb", "baabbaaab"})
System.out.println(s + " " + algorytm(s));
// 2.2 - k = najdłuższy podciąg postaci a...ab...b; szukamy przykładów
System.out.println("aaaaabbbbb " + algorytm("aaaaabbbbb"));
System.out.println("bbbbbaaaaa " + algorytm("bbbbbaaaaa"));
// 2.3
String s = "a".repeat(300) + "b".repeat(550) + "a".repeat(300) + "b".repeat(7) + "a".repeat(280) + "b".repeat(110);
System.out.println(algorytm(s));
}
}Odpowiedź: 2.1: aababb → 5, baabbaaab → 6. 2.2: k = 10 np. aaaaabbbbb (wszystkie a przed wszystkimi b), k = 5 np. bbbbbaaaaa. 2.3: k = 990
↑Treść zadania (Liczby): Plik
liczby.txtzawiera 200 różnych liczb całkowitych z zakresu [10, 100000], każda w osobnym wierszu. Odpowiedzi zapisz wwyniki4.txt, poprzedzając je numerem zadania (do testów:przyklad.txt).
- 4.1 — Podaj, ile liczb ma taką samą pierwszą i ostatnią cyfrę, oraz pierwszą taką liczbę w pliku. Dla pliku przykładowego:
26 626.- 4.2 — Znajdź liczbę o największej liczbie czynników pierwszych (licząc z powtórzeniami) i podaj ją wraz z tą liczbą czynników, a także liczbę o największej liczbie różnych czynników pierwszych wraz z ich liczbą. Np. 420 = 2·2·3·5·7 ma 5 czynników, w tym 4 różne. Dla pliku przykładowego:
144 6 210 4.- 4.3 — Trójka (x, y, z) jest dobra, gdy x dzieli y, y dzieli z i liczby są różne; analogicznie dobra piątka (u, w, x, y, z) – każda kolejna liczba jest podzielna przez poprzednią, wszystkie różne. Liczby mogą stać w pliku w dowolnych miejscach. a) Podaj liczbę dobrych trójek i zapisz je wszystkie do pliku
trojki.txt(każdą w osobnym wierszu); b) podaj liczbę dobrych piątek. Dla pliku przykładowego: a) 10, b) 1 (np. trójka13 26 52).
liczby = []
with open("liczby.txt") as file:
for line in file:
liczby.append(int(line))
# 4.1
ile = 0
pierwsza = 0
for x in liczby:
napis = str(x)
if napis[0] == napis[-1]:
if ile == 0:
pierwsza = x
ile += 1
print("4.1", ile, pierwsza)
# 4.2
def czynniki(x):
wszystkie = 0
rozne = 0
d = 2
while d * d <= x:
if x % d == 0:
rozne += 1
while x % d == 0:
x //= d
wszystkie += 1
d += 1
if x > 1:
wszystkie += 1
rozne += 1
return wszystkie, rozne
max_wsz, liczba_wsz = 0, 0
max_roz, liczba_roz = 0, 0
for x in liczby:
wszystkie, rozne = czynniki(x)
if wszystkie > max_wsz:
max_wsz, liczba_wsz = wszystkie, x
if rozne > max_roz:
max_roz, liczba_roz = rozne, x
print("4.2", liczba_wsz, max_wsz, liczba_roz, max_roz)
# 4.3 - liczby w pliku są różne, więc wystarczy x | y, y | z i x != y != z
trojki = 0
with open("trojki.txt", "w") as wyjscie:
for x in liczby:
for y in liczby:
if y != x and y % x == 0:
for z in liczby:
if z != y and z % y == 0:
trojki += 1
print(x, y, z, file=wyjscie)
# dobre piątki - liczymy rekurencyjnie łańcuchy podzielności długości 5
def lancuchy(ostatnia, dlugosc):
if dlugosc == 5:
return 1
wynik = 0
for nastepna in liczby:
if nastepna != ostatnia and nastepna % ostatnia == 0:
wynik += lancuchy(nastepna, dlugosc + 1)
return wynik
piatki = 0
for u in liczby:
piatki += lancuchy(u, 1)
print("4.3", trojki, piatki)#include <fstream>
#include <print>
#include <string>
#include <utility>
#include <vector>
std::vector<long long> liczby;
// 4.2 - zwraca (liczba wszystkich czynników pierwszych, liczba różnych czynników)
std::pair<int, int> czynniki(long long x) {
int wszystkie = 0;
int rozne = 0;
for (long long d = 2; d * d <= x; d++) {
if (x % d == 0) {
rozne++;
while (x % d == 0) {
x /= d;
wszystkie++;
}
}
}
if (x > 1) {
wszystkie++;
rozne++;
}
return {wszystkie, rozne};
}
// dobre piątki - liczymy rekurencyjnie łańcuchy podzielności długości 5
long long lancuchy(long long ostatnia, int dlugosc) {
if (dlugosc == 5) return 1;
long long wynik = 0;
for (long long nastepna : liczby)
if (nastepna != ostatnia && nastepna % ostatnia == 0) wynik += lancuchy(nastepna, dlugosc + 1);
return wynik;
}
int main() {
std::ifstream plik("liczby.txt");
long long a;
while (plik >> a) liczby.push_back(a);
// 4.1
int ile = 0;
long long pierwsza = 0;
for (long long x : liczby) {
std::string napis = std::to_string(x);
if (napis.front() == napis.back()) {
if (ile == 0) pierwsza = x;
ile++;
}
}
std::println("4.1 {} {}", ile, pierwsza);
// 4.2
int max_wsz = 0, max_roz = 0;
long long liczba_wsz = 0, liczba_roz = 0;
for (long long x : liczby) {
auto [wszystkie, rozne] = czynniki(x);
if (wszystkie > max_wsz) {
max_wsz = wszystkie;
liczba_wsz = x;
}
if (rozne > max_roz) {
max_roz = rozne;
liczba_roz = x;
}
}
std::println("4.2 {} {} {} {}", liczba_wsz, max_wsz, liczba_roz, max_roz);
// 4.3 - liczby w pliku są różne, więc wystarczy x | y, y | z i x != y != z
int trojki = 0;
std::ofstream wyjscie("trojki.txt");
for (long long x : liczby)
for (long long y : liczby)
if (y != x && y % x == 0)
for (long long z : liczby)
if (z != y && z % y == 0) {
trojki++;
wyjscie << x << " " << y << " " << z << "\n";
}
long long piatki = 0;
for (long long u : liczby) piatki += lancuchy(u, 1);
std::println("4.3 {} {}", trojki, piatki);
}import java.io.*;
import java.nio.file.*;
import java.util.*;
public class Zadanie {
static List<Long> liczby = new ArrayList<>();
// 4.2 - zwraca {liczba wszystkich czynników pierwszych, liczba różnych czynników}
static int[] czynniki(long x) {
int wszystkie = 0;
int rozne = 0;
for (long d = 2; d * d <= x; d++) {
if (x % d == 0) {
rozne++;
while (x % d == 0) {
x /= d;
wszystkie++;
}
}
}
if (x > 1) {
wszystkie++;
rozne++;
}
return new int[] {wszystkie, rozne};
}
// dobre piątki - liczymy rekurencyjnie łańcuchy podzielności długości 5
static long lancuchy(long ostatnia, int dlugosc) {
if (dlugosc == 5) return 1;
long wynik = 0;
for (long nastepna : liczby)
if (nastepna != ostatnia && nastepna % ostatnia == 0) wynik += lancuchy(nastepna, dlugosc + 1);
return wynik;
}
public static void main(String[] args) throws Exception {
for (var linia : Files.readAllLines(Path.of("liczby.txt")))
if (!linia.isBlank()) liczby.add(Long.parseLong(linia.trim()));
// 4.1
int ile = 0;
long pierwsza = 0;
for (long x : liczby) {
String napis = Long.toString(x);
if (napis.charAt(0) == napis.charAt(napis.length() - 1)) {
if (ile == 0) pierwsza = x;
ile++;
}
}
System.out.println("4.1 " + ile + " " + pierwsza);
// 4.2
int maxWsz = 0, maxRoz = 0;
long liczbaWsz = 0, liczbaRoz = 0;
for (long x : liczby) {
int[] wr = czynniki(x);
if (wr[0] > maxWsz) {
maxWsz = wr[0];
liczbaWsz = x;
}
if (wr[1] > maxRoz) {
maxRoz = wr[1];
liczbaRoz = x;
}
}
System.out.println("4.2 " + liczbaWsz + " " + maxWsz + " " + liczbaRoz + " " + maxRoz);
// 4.3 - liczby w pliku są różne, więc wystarczy x | y, y | z i x != y != z
int trojki = 0;
try (var wyjscie = new PrintWriter("trojki.txt")) {
for (long x : liczby)
for (long y : liczby)
if (y != x && y % x == 0)
for (long z : liczby)
if (z != y && z % y == 0) {
trojki++;
wyjscie.println(x + " " + y + " " + z);
}
}
long piatki = 0;
for (long u : liczby) piatki += lancuchy(u, 1);
System.out.println("4.3 " + trojki + " " + piatki);
}
}Odpowiedź: 4.1: 18 93639; 4.2: 99792 10 (także 20992 i 56064 mają 10 czynników), 62790 6; 4.3: a) 27 dobrych trójek (np. 955 8595 42975, 232 13688 27376, 13594 27188 81564, …), b) 2 dobre piątki
↑