Matura 2024 — maj, poziom rozszerzony (formuła 2023)
Treść zadania
Plansza ma n wierszy (numerowanych od góry 1..n) i m kolumn (numerowanych od lewej 1..m); każde pole jest białe albo czarne. Opisuje ją tablica A[1..n][1..m], w której A[i][j] = 1 oznacza pole białe, a 0 — czarne. Lewy górny i prawy dolny róg są zawsze białe. Algorytm korzysta z pomocniczej tablicy logicznej P[1..n][1..m] i zwraca PRAWDA albo FAŁSZ:
P[1][1] ← PRAWDA
dla i = 1, 2, ..., n wykonuj
dla j = 1, 2, ..., m wykonuj
jeżeli A[i][j] = 0
P[i][j] ← FAŁSZ
w przeciwnym przypadku
jeżeli i = 1 oraz j ≠ 1: P[i][j] ← P[i][j−1]
jeżeli i ≠ 1 oraz j = 1: P[i][j] ← P[i−1][j]
jeżeli i ≠ 1 oraz j ≠ 1: P[i][j] ← P[i][j−1] lub P[i−1][j]
podaj wynik P[n][m]- 1.1 — Podaj wynik algorytmu dla trzech plansz przedstawionych na rysunkach w arkuszu: a) 3 × 3, b) 5 wierszy × 3 kolumny, c) 5 × 5.
- 1.2 — Podaj przykład planszy (z białymi narożnikami: lewym górnym i prawym dolnym): a) 5 × 5 z co najwyżej 2 czarnymi polami, dla której wynikiem jest FAŁSZ; b) 4 × 4 z co najmniej 9 czarnymi polami, dla której wynikiem jest PRAWDA.
- 1.3 — Dla kwadratowej planszy n × n podaj największą możliwą liczbę czarnych pól, przy której algorytm zwraca PRAWDA.
def algorytm(A):
n = len(A)
m = len(A[0])
P = [[False] * m for _ in range(n)]
P[0][0] = True
for i in range(n):
for j in range(m):
if A[i][j] == 0:
P[i][j] = False
elif i == 0 and j != 0:
P[i][j] = P[i][j - 1]
elif i != 0 and j == 0:
P[i][j] = P[i - 1][j]
elif i != 0 and j != 0:
P[i][j] = P[i][j - 1] or P[i - 1][j]
return P[n - 1][m - 1]
# 1.1 (1 - pole białe, 0 - pole czarne)
a = [[1, 1, 1],
[0, 1, 0],
[1, 1, 1]]
b = [[1, 1, 1],
[0, 0, 1],
[1, 1, 1],
[1, 0, 0],
[1, 1, 1]]
c = [[1, 0, 0, 0, 0],
[1, 1, 0, 0, 1],
[0, 1, 0, 0, 1],
[0, 1, 1, 1, 0],
[0, 1, 0, 1, 1]]
for plansza in [a, b, c]:
print(algorytm(plansza))
# 1.2 - sprawdzenie przykładowych plansz
a2 = [[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 1, 1, 1, 0],
[1, 1, 1, 0, 1]]
b2 = [[1, 0, 0, 0],
[1, 0, 0, 0],
[1, 0, 0, 0],
[1, 1, 1, 1]]
print(algorytm(a2), algorytm(b2))
# 1.3 - sprawdzenie wzoru (n-1)^2 dla małych plansz (przegląd wszystkich plansz)
for n in range(2, 5):
najwiecej = 0
for maska in range(2 ** (n * n)):
A = [[0 if maska >> (i * n + j) & 1 else 1 for j in range(n)] for i in range(n)]
if A[0][0] == 1 and A[n - 1][n - 1] == 1 and algorytm(A):
czarne = sum(row.count(0) for row in A)
najwiecej = max(najwiecej, czarne)
print(n, najwiecej, (n - 1) ** 2)#include <algorithm>
#include <print>
#include <vector>
using Plansza = std::vector<std::vector<int>>;
bool algorytm(const Plansza& A) {
int n = A.size();
int m = A[0].size();
std::vector<std::vector<bool>> P(n, std::vector<bool>(m, false));
P[0][0] = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (A[i][j] == 0) {
P[i][j] = false;
} else if (i == 0 && j != 0) {
P[i][j] = P[i][j - 1];
} else if (i != 0 && j == 0) {
P[i][j] = P[i - 1][j];
} else if (i != 0 && j != 0) {
P[i][j] = P[i][j - 1] || P[i - 1][j];
}
}
}
return P[n - 1][m - 1];
}
// wypisuje wartość logiczną tak jak Python
const char* napis(bool w) {
return w ? "True" : "False";
}
int main() {
// 1.1 (1 - pole białe, 0 - pole czarne)
Plansza a = {{1, 1, 1},
{0, 1, 0},
{1, 1, 1}};
Plansza b = {{1, 1, 1},
{0, 0, 1},
{1, 1, 1},
{1, 0, 0},
{1, 1, 1}};
Plansza c = {{1, 0, 0, 0, 0},
{1, 1, 0, 0, 1},
{0, 1, 0, 0, 1},
{0, 1, 1, 1, 0},
{0, 1, 0, 1, 1}};
for (const Plansza& plansza : {a, b, c}) {
std::println("{}", napis(algorytm(plansza)));
}
// 1.2 - sprawdzenie przykładowych plansz
Plansza a2 = {{1, 1, 1, 1, 1},
{1, 1, 1, 1, 1},
{1, 1, 1, 1, 1},
{1, 1, 1, 1, 0},
{1, 1, 1, 0, 1}};
Plansza b2 = {{1, 0, 0, 0},
{1, 0, 0, 0},
{1, 0, 0, 0},
{1, 1, 1, 1}};
std::println("{} {}", napis(algorytm(a2)), napis(algorytm(b2)));
// 1.3 - sprawdzenie wzoru (n-1)^2 dla małych plansz (przegląd wszystkich plansz)
for (int n = 2; n < 5; n++) {
int najwiecej = 0;
for (int maska = 0; maska < (1 << (n * n)); maska++) {
Plansza A(n, std::vector<int>(n));
int czarne = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
A[i][j] = (maska >> (i * n + j) & 1) ? 0 : 1;
if (A[i][j] == 0) {
czarne++;
}
}
}
if (A[0][0] == 1 && A[n - 1][n - 1] == 1 && algorytm(A)) {
najwiecej = std::max(najwiecej, czarne);
}
}
std::println("{} {} {}", n, najwiecej, (n - 1) * (n - 1));
}
}public class Zadanie {
static boolean algorytm(int[][] A) {
int n = A.length;
int m = A[0].length;
boolean[][] P = new boolean[n][m];
P[0][0] = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (A[i][j] == 0) {
P[i][j] = false;
} else if (i == 0 && j != 0) {
P[i][j] = P[i][j - 1];
} else if (i != 0 && j == 0) {
P[i][j] = P[i - 1][j];
} else if (i != 0 && j != 0) {
P[i][j] = P[i][j - 1] || P[i - 1][j];
}
}
}
return P[n - 1][m - 1];
}
// wypisuje wartość logiczną tak jak Python
static String napis(boolean w) {
return w ? "True" : "False";
}
public static void main(String[] args) throws Exception {
// 1.1 (1 - pole białe, 0 - pole czarne)
int[][] a = {{1, 1, 1},
{0, 1, 0},
{1, 1, 1}};
int[][] b = {{1, 1, 1},
{0, 0, 1},
{1, 1, 1},
{1, 0, 0},
{1, 1, 1}};
int[][] c = {{1, 0, 0, 0, 0},
{1, 1, 0, 0, 1},
{0, 1, 0, 0, 1},
{0, 1, 1, 1, 0},
{0, 1, 0, 1, 1}};
for (int[][] plansza : new int[][][]{a, b, c}) {
System.out.println(napis(algorytm(plansza)));
}
// 1.2 - sprawdzenie przykładowych plansz
int[][] a2 = {{1, 1, 1, 1, 1},
{1, 1, 1, 1, 1},
{1, 1, 1, 1, 1},
{1, 1, 1, 1, 0},
{1, 1, 1, 0, 1}};
int[][] b2 = {{1, 0, 0, 0},
{1, 0, 0, 0},
{1, 0, 0, 0},
{1, 1, 1, 1}};
System.out.println(napis(algorytm(a2)) + " " + napis(algorytm(b2)));
// 1.3 - sprawdzenie wzoru (n-1)^2 dla małych plansz (przegląd wszystkich plansz)
for (int n = 2; n < 5; n++) {
int najwiecej = 0;
for (int maska = 0; maska < (1 << (n * n)); maska++) {
int[][] A = new int[n][n];
int czarne = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
A[i][j] = ((maska >> (i * n + j)) & 1) == 1 ? 0 : 1;
if (A[i][j] == 0) {
czarne++;
}
}
}
if (A[0][0] == 1 && A[n - 1][n - 1] == 1 && algorytm(A)) {
najwiecej = Math.max(najwiecej, czarne);
}
}
System.out.println(n + " " + najwiecej + " " + (n - 1) * (n - 1));
}
}
}Odpowiedź: 1.1: a) PRAWDA, b) FAŁSZ, c) PRAWDA. 1.2: algorytm zwraca PRAWDA wtedy i tylko wtedy, gdy istnieje ścieżka po białych polach z lewego górnego do prawego dolnego rogu, poruszając się tylko w prawo lub w dół; a) np. plansza 5 × 5 z czarnymi polami (4, 5) i (5, 4) — FAŁSZ; b) np. plansza 4 × 4, w której białe są tylko pierwsza kolumna i ostatni wiersz (9 pól czarnych) — PRAWDA. 1.3: (n − 1)² (ścieżka z rogu do rogu ma zawsze 2n − 1 białych pól, więc czarnych może być n² − (2n − 1)).
↑Treść zadania
Algorytm dla nieujemnej liczby całkowitej n oblicza liczbę c (mod i div to reszta i iloraz z dzielenia całkowitego):
b ← 1
c ← 0
dopóki n > 0 wykonuj
a ← n mod 10
n ← n div 10
jeżeli a mod 2 = 0
c ← c + b * (a div 2)
w przeciwnym razie
c ← c + b
b ← b * 10- 2.1 — Uzupełnij tabelę: dla n = 542102 oraz n = 87654321012345678 podaj wartość c po zakończeniu algorytmu i liczbę wykonań instrukcji c ← c + b (przykład: dla n = 33658 jest c = 11314 i 3 wykonania).
- 2.2 — Podaj wartość c dla osiemnastocyfrowej liczby n, której pierwsze sześć cyfr to 3, kolejne sześć to 6, a ostatnie sześć to 9.
def algorytm(n):
b = 1
c = 0
wykonania = 0
while n > 0:
a = n % 10
n = n // 10
if a % 2 == 0:
c = c + b * (a // 2)
else:
c = c + b
wykonania += 1
b = b * 10
return c, wykonania
# 2.1
for n in [33658, 542102, 87654321012345678]:
print(n, *algorytm(n))
# 2.2
n = int("3" * 6 + "6" * 6 + "9" * 6)
print(algorytm(n)[0])#include <print>
#include <string>
#include <utility>
// zwraca parę (c, liczba wykonań gałęzi "else")
std::pair<long long, int> algorytm(long long n) {
long long b = 1;
long long c = 0;
int wykonania = 0;
while (n > 0) {
long long a = n % 10;
n = n / 10;
if (a % 2 == 0) {
c = c + b * (a / 2);
} else {
c = c + b;
wykonania += 1;
}
b = b * 10;
}
return {c, wykonania};
}
int main() {
// 2.1 (liczby do 10^17 - potrzebny long long)
for (long long n : {33658LL, 542102LL, 87654321012345678LL}) {
auto [c, wykonania] = algorytm(n);
std::println("{} {} {}", n, c, wykonania);
}
// 2.2
long long n = std::stoll(std::string(6, '3') + std::string(6, '6') + std::string(6, '9'));
std::println("{}", algorytm(n).first);
}public class Zadanie {
// zwraca tablicę {c, liczba wykonań gałęzi "else"}
static long[] algorytm(long n) {
long b = 1;
long c = 0;
long wykonania = 0;
while (n > 0) {
long a = n % 10;
n = n / 10;
if (a % 2 == 0) {
c = c + b * (a / 2);
} else {
c = c + b;
wykonania += 1;
}
b = b * 10;
}
return new long[]{c, wykonania};
}
public static void main(String[] args) throws Exception {
// 2.1 (liczby do 10^17 - potrzebny long)
for (long n : new long[]{33658L, 542102L, 87654321012345678L}) {
long[] wynik = algorytm(n);
System.out.println(n + " " + wynik[0] + " " + wynik[1]);
}
// 2.2
long n = Long.parseLong("3".repeat(6) + "6".repeat(6) + "9".repeat(6));
System.out.println(algorytm(n)[0]);
}
}Odpowiedź: 2.1: 33658 → 11314, 3 wykonania; 542102 → 121101, 2 wykonania; 87654321012345678 → 41312111011121314, 8 wykonań. 2.2: c = 111111333333111111.
↑Treść zadania
Nieparzystym skrótem dodatniej liczby całkowitej n jest liczba m powstała przez usunięcie z zapisu dziesiętnego n wszystkich cyfr parzystych. Jeśli n ma same cyfry parzyste, skrót nie istnieje. Przykłady: skrót 294762 to 97, skrót 39101 to 3911, skrót 224 nie istnieje.
Napisz (w pseudokodzie lub wybranym języku) funkcję, która dla dodatniej liczby całkowitej n, mającej nieparzysty skrót, wyznacza ten skrót m. Algorytm może operować wyłącznie na liczbach całkowitych i używać tylko podstawowych operacji arytmetycznych (w tym div i mod), porównań, instrukcji sterujących i własnych funkcji — bez funkcji wbudowanych.
def skrot(n):
m = 0
p = 1
while n > 0:
cyfra = n % 10
if cyfra % 2 != 0:
m = m + cyfra * p
p = p * 10
n = n // 10
return m
for n in [294762, 39101]:
print(n, skrot(n))#include <print>
int skrot(int n) {
int m = 0;
int p = 1;
while (n > 0) {
int cyfra = n % 10;
if (cyfra % 2 != 0) {
m = m + cyfra * p;
p = p * 10;
}
n = n / 10;
}
return m;
}
int main() {
for (int n : {294762, 39101}) {
std::println("{} {}", n, skrot(n));
}
}public class Zadanie {
static int skrot(int n) {
int m = 0;
int p = 1;
while (n > 0) {
int cyfra = n % 10;
if (cyfra % 2 != 0) {
m = m + cyfra * p;
p = p * 10;
}
n = n / 10;
}
return m;
}
public static void main(String[] args) throws Exception {
for (int n : new int[]{294762, 39101}) {
System.out.println(n + " " + skrot(n));
}
}
}Odpowiedź: funkcja skrot (np. skrot(294762) = 97, skrot(39101) = 3911).
Treść zadania
Plik skrot.txt zawiera 200 dodatnich liczb całkowitych mniejszych od 30 000, po jednej w wierszu; dla co najmniej jednej z nich nieparzysty skrót (zob. 3.1) nie istnieje.
Napisz program, który poda, dla ilu liczb z pliku nieparzysty skrót nie istnieje, oraz największą z tych liczb. Odpowiedź zapisz w pliku wyniki3_2.txt. Dla pliku skrot_przyklad.txt są dwie takie liczby (266 i 2428), największa to 2428.
def skrot(n):
m = 0
p = 1
while n > 0:
cyfra = n % 10
if cyfra % 2 != 0:
m = m + cyfra * p
p = p * 10
n = n // 10
return m
with open("skrot.txt") as file:
liczby = [int(wiersz) for wiersz in file]
bez_skrotu = [n for n in liczby if skrot(n) == 0]
print(len(bez_skrotu))
print(max(bez_skrotu))#include <algorithm>
#include <fstream>
#include <print>
#include <vector>
int skrot(int n) {
int m = 0;
int p = 1;
while (n > 0) {
int cyfra = n % 10;
if (cyfra % 2 != 0) {
m = m + cyfra * p;
p = p * 10;
}
n = n / 10;
}
return m;
}
int main() {
std::ifstream plik("skrot.txt");
std::vector<int> liczby;
int x;
while (plik >> x) {
liczby.push_back(x);
}
std::vector<int> bez_skrotu;
for (int n : liczby) {
if (skrot(n) == 0) {
bez_skrotu.push_back(n);
}
}
std::println("{}", bez_skrotu.size());
std::println("{}", std::ranges::max(bez_skrotu));
}import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Zadanie {
static int skrot(int n) {
int m = 0;
int p = 1;
while (n > 0) {
int cyfra = n % 10;
if (cyfra % 2 != 0) {
m = m + cyfra * p;
p = p * 10;
}
n = n / 10;
}
return m;
}
public static void main(String[] args) throws Exception {
List<Integer> bezSkrotu = new ArrayList<>();
for (String wiersz : Files.readAllLines(Path.of("skrot.txt"))) {
int n = Integer.parseInt(wiersz.trim());
if (skrot(n) == 0) {
bezSkrotu.add(n);
}
}
System.out.println(bezSkrotu.size());
System.out.println(Collections.max(bezSkrotu));
}
}Odpowiedź: 18 liczb, największa z nich: 28422.
↑Treść zadania
Plik skrot2.txt zawiera 200 dodatnich liczb całkowitych mniejszych od 30 000, po jednej w wierszu; każda ma nieparzysty skrót (zob. 3.1).
Napisz program, który wypisze (po jednej w wierszu) te liczby z pliku, dla których największy wspólny dzielnik liczby i jej nieparzystego skrótu jest równy 7. Wynik zapisz w pliku wyniki3_3.txt. Do testów służy plik skrot2_przyklad.txt.
from math import gcd
def skrot(n):
m = 0
p = 1
while n > 0:
cyfra = n % 10
if cyfra % 2 != 0:
m = m + cyfra * p
p = p * 10
n = n // 10
return m
with open("skrot2.txt") as file:
for wiersz in file:
n = int(wiersz)
if gcd(n, skrot(n)) == 7:
print(n)#include <fstream>
#include <numeric>
#include <print>
int skrot(int n) {
int m = 0;
int p = 1;
while (n > 0) {
int cyfra = n % 10;
if (cyfra % 2 != 0) {
m = m + cyfra * p;
p = p * 10;
}
n = n / 10;
}
return m;
}
int main() {
std::ifstream plik("skrot2.txt");
int n;
while (plik >> n) {
if (std::gcd(n, skrot(n)) == 7) {
std::println("{}", n);
}
}
}import java.nio.file.Files;
import java.nio.file.Path;
public class Zadanie {
static int skrot(int n) {
int m = 0;
int p = 1;
while (n > 0) {
int cyfra = n % 10;
if (cyfra % 2 != 0) {
m = m + cyfra * p;
p = p * 10;
}
n = n / 10;
}
return m;
}
static int gcd(int a, int b) {
while (b != 0) {
int t = a % b;
a = b;
b = t;
}
return a;
}
public static void main(String[] args) throws Exception {
for (String wiersz : Files.readAllLines(Path.of("skrot2.txt"))) {
int n = Integer.parseInt(wiersz.trim());
if (gcd(n, skrot(n)) == 7) {
System.out.println(n);
}
}
}
}Odpowiedź: 784, 14196, 2247, 24087, 3871, 10192.
↑Treść zadania
Plik liczby.txt ma dwa wiersze: w pierwszym jest 3000 liczb pierwszych z przedziału [2, 2000], w drugim — 20 liczb całkowitych z przedziału [2, 1 000 000 000]; liczby oddzielone są spacjami. Odpowiedzi zapisz w pliku wyniki4.txt, poprzedzając każdą numerem zadania. Plik liczby_przyklad.txt (200 liczb 2, 3, 5, 7, 31 w pierwszym wierszu i 20 liczb w drugim) służy do testów.
- 4.1 — Podaj, ile liczb z pierwszego wiersza jest dzielnikiem co najmniej jednej liczby z drugiego wiersza (dla pliku przykładowego: 199).
- 4.2 — Podaj liczbę, która po uporządkowaniu liczb z pierwszego wiersza jest sto pierwsza, licząc od największej (np. wśród 2, 4, 2, 3, 3, 4 druga od największej to 4; dla pliku przykładowego: 5).
- 4.3 — Wypisz te liczby z drugiego wiersza, które da się przedstawić jako iloczyn wyłącznie liczb z pierwszego wiersza, przy czym każdy czynnik może wystąpić w iloczynie co najwyżej tyle razy, ile razy występuje w pierwszym wierszu (dla pliku przykładowego: 10 12 14 15 18 20 21 25 27 28; np. 16 = 2·2·2·2 odpada, bo 2 występuje tylko dwa razy).
- 4.4 — W ciągu liczb z pierwszego wiersza znajdź spójny fragment o co najmniej 50 elementach i największej średniej arytmetycznej (przy remisie — pierwszy w pliku). Podaj tę średnią, liczbę elementów fragmentu i jego pierwszy element (dla pliku przykładowego:
5,52 50 5).
with open("liczby.txt") as file:
pierwsze = [int(x) for x in file.readline().split()]
liczby = [int(x) for x in file.readline().split()]
# 4.1
ile = 0
for p in pierwsze:
for x in liczby:
if x % p == 0:
ile += 1
break
print("4.1", ile)
# 4.2
posortowane = sorted(pierwsze, reverse=True)
print("4.2", posortowane[100])
# 4.3
wystapienia = {}
for p in pierwsze:
wystapienia[p] = wystapienia.get(p, 0) + 1
wynik = []
for x in liczby:
reszta = x
dobra = True
for p in wystapienia:
ile_razy = 0
while reszta % p == 0:
reszta //= p
ile_razy += 1
if ile_razy > wystapienia[p]:
dobra = False
if dobra and reszta == 1:
wynik.append(x)
print("4.3", *wynik)
# 4.4
n = len(pierwsze)
prefiks = [0] * (n + 1)
for i in range(n):
prefiks[i + 1] = prefiks[i] + pierwsze[i]
najl_suma, najl_dl, najl_start = 0, 1, -1
for start in range(n):
for koniec in range(start + 50, n + 1):
suma = prefiks[koniec] - prefiks[start]
dl = koniec - start
# suma / dl > najl_suma / najl_dl, bez ułamków
if najl_start == -1 or suma * najl_dl > najl_suma * dl:
najl_suma, najl_dl, najl_start = suma, dl, start
print("4.4", najl_suma / najl_dl, najl_dl, pierwsze[najl_start])#include <algorithm>
#include <fstream>
#include <functional>
#include <map>
#include <print>
#include <sstream>
#include <string>
#include <vector>
std::vector<long long> wczytaj_wiersz(std::ifstream& plik) {
std::string linia;
std::getline(plik, linia);
std::istringstream strumien(linia);
std::vector<long long> wynik;
long long x;
while (strumien >> x) {
wynik.push_back(x);
}
return wynik;
}
int main() {
std::ifstream plik("liczby.txt");
std::vector<long long> pierwsze = wczytaj_wiersz(plik);
std::vector<long long> liczby = wczytaj_wiersz(plik);
// 4.1
int ile = 0;
for (long long p : pierwsze) {
for (long long x : liczby) {
if (x % p == 0) {
ile += 1;
break;
}
}
}
std::println("4.1 {}", ile);
// 4.2
std::vector<long long> posortowane = pierwsze;
std::ranges::sort(posortowane, std::greater<>());
std::println("4.2 {}", posortowane[100]);
// 4.3
std::map<long long, int> wystapienia;
for (long long p : pierwsze) {
wystapienia[p] += 1;
}
std::vector<long long> wynik;
for (long long x : liczby) {
long long reszta = x;
bool dobra = true;
for (auto [p, ile_dozwolonych] : wystapienia) {
int ile_razy = 0;
while (reszta % p == 0) {
reszta /= p;
ile_razy += 1;
}
if (ile_razy > ile_dozwolonych) {
dobra = false;
}
}
if (dobra && reszta == 1) {
wynik.push_back(x);
}
}
std::print("4.3");
for (long long x : wynik) {
std::print(" {}", x);
}
std::println();
// 4.4
int n = pierwsze.size();
std::vector<long long> prefiks(n + 1, 0);
for (int i = 0; i < n; i++) {
prefiks[i + 1] = prefiks[i] + pierwsze[i];
}
long long najl_suma = 0, najl_dl = 1;
int najl_start = -1;
for (int start = 0; start < n; start++) {
for (int koniec = start + 50; koniec <= n; koniec++) {
long long suma = prefiks[koniec] - prefiks[start];
long long dl = koniec - start;
// suma / dl > najl_suma / najl_dl, bez ułamków
if (najl_start == -1 || suma * najl_dl > najl_suma * dl) {
najl_suma = suma;
najl_dl = dl;
najl_start = start;
}
}
}
std::println("4.4 {} {} {}", (double)najl_suma / najl_dl, najl_dl, pierwsze[najl_start]);
}import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
public class Zadanie {
static List<Long> naLiczby(String linia) {
List<Long> wynik = new ArrayList<>();
for (String s : linia.trim().split("\\s+")) {
wynik.add(Long.parseLong(s));
}
return wynik;
}
public static void main(String[] args) throws Exception {
List<String> linie = Files.readAllLines(Path.of("liczby.txt"));
List<Long> pierwsze = naLiczby(linie.get(0));
List<Long> liczby = naLiczby(linie.get(1));
// 4.1
int ile = 0;
for (long p : pierwsze) {
for (long x : liczby) {
if (x % p == 0) {
ile += 1;
break;
}
}
}
System.out.println("4.1 " + ile);
// 4.2
List<Long> posortowane = new ArrayList<>(pierwsze);
posortowane.sort(Comparator.reverseOrder());
System.out.println("4.2 " + posortowane.get(100));
// 4.3
Map<Long, Integer> wystapienia = new LinkedHashMap<>();
for (long p : pierwsze) {
wystapienia.put(p, wystapienia.getOrDefault(p, 0) + 1);
}
StringBuilder wynik = new StringBuilder("4.3");
for (long x : liczby) {
long reszta = x;
boolean dobra = true;
for (var wpis : wystapienia.entrySet()) {
long p = wpis.getKey();
int ileRazy = 0;
while (reszta % p == 0) {
reszta /= p;
ileRazy += 1;
}
if (ileRazy > wpis.getValue()) {
dobra = false;
}
}
if (dobra && reszta == 1) {
wynik.append(" ").append(x);
}
}
System.out.println(wynik);
// 4.4
int n = pierwsze.size();
long[] prefiks = new long[n + 1];
for (int i = 0; i < n; i++) {
prefiks[i + 1] = prefiks[i] + pierwsze.get(i);
}
long najlSuma = 0, najlDl = 1;
int najlStart = -1;
for (int start = 0; start < n; start++) {
for (int koniec = start + 50; koniec <= n; koniec++) {
long suma = prefiks[koniec] - prefiks[start];
long dl = koniec - start;
// suma / dl > najlSuma / najlDl, bez ułamków
if (najlStart == -1 || suma * najlDl > najlSuma * dl) {
najlSuma = suma;
najlDl = dl;
najlStart = start;
}
}
}
System.out.println("4.4 " + (double) najlSuma / najlDl + " " + najlDl + " " + pierwsze.get(najlStart));
}
}Odpowiedź: 4.1: 212. 4.2: 1933. 4.3: 547839600, 2954285, 573219169, 573549984, 212444924. 4.4: średnia 1200,704918… (≈ 1200,70), 61 elementów, pierwszy element 1847.
↑