Matura 2023 — maj, poziom rozszerzony (formuła 2015)
ARKUSZ CZ. IARKUSZ CZ. IIDANEODPOWIEDZI
Treść zadania
Dla ciągu A liczb całkowitych dodatnich tworzymy jego opis B: każdy maksymalny fragment A będący p-krotnym powtórzeniem liczby x zastępujemy parą liczb p, x. Np. opisem (1, 1, 3, 2, 2, 2, 1) jest (2, 1, 1, 3, 3, 2, 1, 1), a opisem (2, 2, 2, 2, 5, 3, 3) — (4, 2, 1, 5, 2, 3).
- 1.1 — Uzupełnij tabelę: dla ciągów (3, 3, 3, 2, 2, 1, 1, 1, 6) i (2, 2, 2, 2, 2, 2) podaj opis i jego długość (liczbę elementów B); dla opisu (4, 1, 1, 4) odtwórz ciąg A.
- 1.2 — Zapisz algorytm, który dla tablicy A[1..n] liczb całkowitych dodatnich obliczy długość jej opisu (liczbę elementów ciągu B). Wolno używać tylko podstawowych operacji arytmetycznych, porównań, odwołań do pojedynczych elementów tablicy i instrukcji sterujących — bez funkcji wbudowanych.
def opis(A):
B = []
i = 0
while i < len(A):
p = 1
while i + p < len(A) and A[i + p] == A[i]:
p += 1
B += [p, A[i]]
i += p
return B
# 1.2 - długość opisu: każda zmiana wartości rozpoczyna nowy fragment (2 liczby)
def dlugosc_opisu(A, n):
w = 2
for i in range(n - 1):
if A[i] != A[i + 1]:
w += 2
return w
# 1.1
for A in [[3, 3, 3, 2, 2, 1, 1, 1, 6], [2, 2, 2, 2, 2, 2]]:
print(A, opis(A), dlugosc_opisu(A, len(A)))
B = [4, 1, 1, 4] # odtworzenie ciągu A z opisu
A = []
for i in range(0, len(B), 2):
A += [B[i + 1]] * B[i]
print(A, B, len(B))#include <print>
#include <vector>
std::vector<int> opis(const std::vector<int>& A) {
std::vector<int> B;
int n = A.size();
int i = 0;
while (i < n) {
int p = 1;
while (i + p < n && A[i + p] == A[i]) p++;
B.push_back(p);
B.push_back(A[i]);
i += p;
}
return B;
}
// 1.2 - długość opisu: każda zmiana wartości rozpoczyna nowy fragment (2 liczby)
int dlugosc_opisu(const std::vector<int>& A, int n) {
int w = 2;
for (int i = 0; i < n - 1; i++)
if (A[i] != A[i + 1]) w += 2;
return w;
}
int main() {
// 1.1
std::vector<std::vector<int>> ciagi = {{3, 3, 3, 2, 2, 1, 1, 1, 6}, {2, 2, 2, 2, 2, 2}};
for (auto& A : ciagi) std::println("{} {} {}", A, opis(A), dlugosc_opisu(A, A.size()));
std::vector<int> B = {4, 1, 1, 4}; // odtworzenie ciągu A z opisu
std::vector<int> A;
for (size_t i = 0; i < B.size(); i += 2)
for (int k = 0; k < B[i]; k++) A.push_back(B[i + 1]);
std::println("{} {} {}", A, B, B.size());
}import java.util.*;
public class Zadanie {
static List<Integer> opis(List<Integer> A) {
var B = new ArrayList<Integer>();
int n = A.size();
int i = 0;
while (i < n) {
int p = 1;
while (i + p < n && A.get(i + p).equals(A.get(i))) p++;
B.add(p);
B.add(A.get(i));
i += p;
}
return B;
}
// 1.2 - długość opisu: każda zmiana wartości rozpoczyna nowy fragment (2 liczby)
static int dlugoscOpisu(List<Integer> A, int n) {
int w = 2;
for (int i = 0; i < n - 1; i++)
if (!A.get(i).equals(A.get(i + 1))) w += 2;
return w;
}
public static void main(String[] args) throws Exception {
// 1.1
List<List<Integer>> ciagi = List.of(List.of(3, 3, 3, 2, 2, 1, 1, 1, 6), List.of(2, 2, 2, 2, 2, 2));
for (var A : ciagi) System.out.println(A + " " + opis(A) + " " + dlugoscOpisu(A, A.size()));
List<Integer> B = List.of(4, 1, 1, 4); // odtworzenie ciągu A z opisu
var A = new ArrayList<Integer>();
for (int i = 0; i < B.size(); i += 2)
for (int k = 0; k < B.get(i); k++) A.add(B.get(i + 1));
System.out.println(A + " " + B + " " + B.size());
}
}Odpowiedź: 1.1: (3, 3, 3, 2, 2, 1, 1, 1, 6) → (3, 3, 2, 2, 3, 1, 1, 6), długość 8; (2, 2, 2, 2, 2, 2) → (6, 2), długość 2; ciąg A = (1, 1, 1, 1, 4), długość 4. 1.2: funkcja dlugosc_opisu.
Treść zadania
Dana jest tablica A[1..n] liczb całkowitych dodatnich i rekurencyjna funkcja f(p, q), gdzie 1 ≤ p ≤ q ≤ n:
f(p, q):
jeżeli p < q
k ← (q - p + 1) div 2
dla i = 1, 2, ..., k
zamień(A[p + i - 1], A[q - k + i])
f(p, p + k - 1)
f(q - k + 1, q)- 2.1 — Podaj zawartość tablicy A po wywołaniu f(1, n) dla: n = 3, A = [2, 3, 4]; n = 4, A = [1, 2, 3, 4]; n = 10, A = [1, 2, ..., 10].
- 2.2 — Podaj, ile razy wykona się operacja zamień() po wywołaniu f(1, n) dla n = 8, 16 i 256 (dla n = 4 jest to 4). Liczba ta zależy tylko od n.
zamiany = 0
def f(p, q):
global zamiany
if p < q:
k = (q - p + 1) // 2
for i in range(1, k + 1):
A[p + i - 1], A[q - k + i] = A[q - k + i], A[p + i - 1]
zamiany += 1
f(p, p + k - 1)
f(q - k + 1, q)
# 2.1 (tablica indeksowana od 1, A[0] nieużywane)
for A in [[0, 2, 3, 4], [0, 1, 2, 3, 4], [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]]:
f(1, len(A) - 1)
print(A[1:])
# 2.2
for n in [4, 8, 16, 256]:
A = [0] * (n + 1)
zamiany = 0
f(1, n)
print(n, zamiany)#include <print>
#include <utility>
#include <vector>
std::vector<int> A; // tablica indeksowana od 1, A[0] nieużywane
int zamiany = 0;
void f(int p, int q) {
if (p < q) {
int k = (q - p + 1) / 2;
for (int i = 1; i <= k; i++) {
std::swap(A[p + i - 1], A[q - k + i]);
zamiany++;
}
f(p, p + k - 1);
f(q - k + 1, q);
}
}
int main() {
// 2.1
std::vector<std::vector<int>> tablice = {{0, 2, 3, 4}, {0, 1, 2, 3, 4}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}};
for (auto& tab : tablice) {
A = tab;
f(1, A.size() - 1);
std::println("{}", std::vector<int>(A.begin() + 1, A.end()));
}
// 2.2
for (int n : {4, 8, 16, 256}) {
A.assign(n + 1, 0);
zamiany = 0;
f(1, n);
std::println("{} {}", n, zamiany);
}
}import java.util.*;
public class Zadanie {
static int[] A; // tablica indeksowana od 1, A[0] nieużywane
static int zamiany = 0;
static void f(int p, int q) {
if (p < q) {
int k = (q - p + 1) / 2;
for (int i = 1; i <= k; i++) {
int t = A[p + i - 1];
A[p + i - 1] = A[q - k + i];
A[q - k + i] = t;
zamiany++;
}
f(p, p + k - 1);
f(q - k + 1, q);
}
}
public static void main(String[] args) throws Exception {
// 2.1
int[][] tablice = {{0, 2, 3, 4}, {0, 1, 2, 3, 4}, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}};
for (var tab : tablice) {
A = tab.clone();
f(1, A.length - 1);
System.out.println(Arrays.toString(Arrays.copyOfRange(A, 1, A.length)));
}
// 2.2
for (int n : new int[] {4, 8, 16, 256}) {
A = new int[n + 1];
zamiany = 0;
f(1, n);
System.out.println(n + " " + zamiany);
}
}
}Odpowiedź: 2.1: [4, 3, 2]; [4, 3, 2, 1]; [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]. 2.2: n = 8 → 12, n = 16 → 32, liczba zamian 1024 dla n = 256.
↑Treść zadania
Plik slowa.txt zawiera 50 słów (długości do 1000) złożonych z małych liter alfabetu angielskiego (dane przykładowe: przyklad.txt).
WK-słowo to słowo, w którym litery w i k występują tyle samo razy (także po 0 razy, np. „matura”). Zapisz w pliku wyniki4_1.txt wszystkie WK-słowa z pliku, każde w osobnym wierszu, w kolejności z pliku.
with open("slowa.txt") as file:
slowa = [linia.strip() for linia in file if linia.strip()]
with open("wyniki4_1.txt", "w") as wynik:
for slowo in slowa:
if slowo.count("w") == slowo.count("k"):
print(slowo, file=wynik)#include <algorithm>
#include <fstream>
#include <string>
#include <vector>
int main() {
std::vector<std::string> slowa;
std::ifstream plik("slowa.txt");
std::string linia;
while (plik >> linia) slowa.push_back(linia);
std::ofstream wynik("wyniki4_1.txt");
for (auto& slowo : slowa)
if (std::count(slowo.begin(), slowo.end(), 'w') == std::count(slowo.begin(), slowo.end(), 'k'))
wynik << slowo << "\n";
}import java.io.*;
import java.nio.file.*;
public class Zadanie {
public static void main(String[] args) throws Exception {
try (var wynik = new PrintWriter("wyniki4_1.txt")) {
for (var linia : Files.readAllLines(Path.of("slowa.txt"))) {
String slowo = linia.strip();
if (slowo.isEmpty()) continue;
long w = slowo.chars().filter(c -> c == 'w').count();
long k = slowo.chars().filter(c -> c == 'k').count();
if (w == k) wynik.println(slowo);
}
}
}
}Odpowiedź: dsasahdadelebsdsidihdiahsaihd, abba, echwakacjeachwakacje, weweakaddcjjreewakacjerk, … (19 słów, ostatnie: awszystkoprzepasanejakbywstega)
↑Treść zadania
Dane jak w zadaniu 4.1 (50 słów w slowa.txt).
Dla każdego słowa oblicz, ile słów wakacje można ułożyć z jego liter (każdej litery wolno użyć najwyżej raz). Np. dla wwwaaaaakkcccjjee wynik to 2, dla awkcjcje — 0. Zapisz w jednym wierszu pliku wyniki4_2.txt 50 liczb oddzielonych spacjami (i-ta liczba dotyczy i-tego słowa).
with open("slowa.txt") as file:
slowa = [linia.strip() for linia in file if linia.strip()]
wzor = "wakacje"
wyniki = []
for slowo in slowa:
ile = len(slowo)
for litera in set(wzor):
ile = min(ile, slowo.count(litera) // wzor.count(litera)) # "a" potrzebne 2 razy
wyniki.append(ile)
with open("wyniki4_2.txt", "w") as wynik:
print(*wyniki, file=wynik)#include <algorithm>
#include <fstream>
#include <string>
#include <vector>
int main() {
std::vector<std::string> slowa;
std::ifstream plik("slowa.txt");
std::string linia;
while (plik >> linia) slowa.push_back(linia);
std::string wzor = "wakacje";
std::vector<int> wyniki;
for (auto& slowo : slowa) {
int ile = slowo.size();
for (char litera : wzor) {
int w_slowie = std::count(slowo.begin(), slowo.end(), litera);
int we_wzorze = std::count(wzor.begin(), wzor.end(), litera); // "a" potrzebne 2 razy
ile = std::min(ile, w_slowie / we_wzorze);
}
wyniki.push_back(ile);
}
std::ofstream wynik("wyniki4_2.txt");
for (size_t i = 0; i < wyniki.size(); i++) wynik << (i > 0 ? " " : "") << wyniki[i];
wynik << "\n";
}import java.io.*;
import java.nio.file.*;
import java.util.*;
public class Zadanie {
static int ile(String s, char c) {
return (int) s.chars().filter(z -> z == c).count();
}
public static void main(String[] args) throws Exception {
String wzor = "wakacje";
var wyniki = new ArrayList<String>();
for (var linia : Files.readAllLines(Path.of("slowa.txt"))) {
String slowo = linia.strip();
if (slowo.isEmpty()) continue;
int ile = slowo.length();
for (char litera : wzor.toCharArray())
ile = Math.min(ile, ile(slowo, litera) / ile(wzor, litera)); // "a" potrzebne 2 razy
wyniki.add(String.valueOf(ile));
}
try (var wynik = new PrintWriter("wyniki4_2.txt")) {
wynik.println(String.join(" ", wyniki));
}
}
}Odpowiedź: 0 0 2 2 2 3 2 17 2 6 78 1 19 4 4 91 0 14 4 2 23 1 19 5 6 137 1 21 2 5 88 0 13 3 14 124 2 21 4 8 123 0 0 1 1 1 0 2 2 3
↑Treść zadania
Dane jak w zadaniu 4.1 (50 słów w slowa.txt).
Wakacyjne słowo to słowo wakacje sklejone ze sobą dowolnie wiele razy (także 0 razy — słowo puste). Dla każdego słowa oblicz najmniejszą liczbę liter, które trzeba z niego wykreślić (bez zmiany kolejności pozostałych), aby otrzymać wakacyjne słowo. Np. wakaaaacjee → 4, waktfaczdjeaewasakvgacrje → 11, awkcjcje → 8. Zapisz w jednym wierszu pliku wyniki4_3.txt 50 wyników oddzielonych spacjami.
with open("slowa.txt") as file:
slowa = [linia.strip() for linia in file if linia.strip()]
wzor = "wakacje"
wyniki = []
for slowo in slowa:
j = 0 # która litera słowa "wakacje" jest teraz szukana
pelne = 0 # liczba ułożonych pełnych słów "wakacje"
for litera in slowo:
if litera == wzor[j]:
j += 1
if j == len(wzor):
pelne += 1
j = 0
wyniki.append(len(slowo) - len(wzor) * pelne)
with open("wyniki4_3.txt", "w") as wynik:
print(*wyniki, file=wynik)#include <fstream>
#include <string>
#include <vector>
int main() {
std::vector<std::string> slowa;
std::ifstream plik("slowa.txt");
std::string linia;
while (plik >> linia) slowa.push_back(linia);
std::string wzor = "wakacje";
std::vector<int> wyniki;
for (auto& slowo : slowa) {
size_t j = 0; // która litera słowa "wakacje" jest teraz szukana
int pelne = 0; // liczba ułożonych pełnych słów "wakacje"
for (char litera : slowo) {
if (litera == wzor[j]) {
j++;
if (j == wzor.size()) {
pelne++;
j = 0;
}
}
}
wyniki.push_back(slowo.size() - wzor.size() * pelne);
}
std::ofstream wynik("wyniki4_3.txt");
for (size_t i = 0; i < wyniki.size(); i++) wynik << (i > 0 ? " " : "") << wyniki[i];
wynik << "\n";
}import java.io.*;
import java.nio.file.*;
import java.util.*;
public class Zadanie {
public static void main(String[] args) throws Exception {
String wzor = "wakacje";
var wyniki = new ArrayList<String>();
for (var linia : Files.readAllLines(Path.of("slowa.txt"))) {
String slowo = linia.strip();
if (slowo.isEmpty()) continue;
int j = 0; // która litera słowa "wakacje" jest teraz szukana
int pelne = 0; // liczba ułożonych pełnych słów "wakacje"
for (char litera : slowo.toCharArray()) {
if (litera == wzor.charAt(j)) {
j++;
if (j == wzor.length()) {
pelne++;
j = 0;
}
}
}
wyniki.add(String.valueOf(slowo.length() - wzor.length() * pelne));
}
try (var wynik = new PrintWriter("wyniki4_3.txt")) {
wynik.println(String.join(" ", wyniki));
}
}
}Odpowiedź: 29 4 6 6 10 17 100 965 33 65 545 100 965 12 79 419 100 972 12 93 951 100 965 5 65 48 100 958 33 65 426 100 965 19 2 146 100 951 12 44 160 9 4 55 0 76 30 24 44 15
↑