{"id":"informatyka-2019-maj-matura-rozszerzona/zad/4.3","paper_id":"informatyka-2019-maj-matura-rozszerzona","number":"4.3","points":5,"ptype":"open","subject":"informatyka","category":"matura","year":2019,"month":"maj","level":"rozszerzona","text":"Kontekst - patrz zadanie 4.1.\n\nUwaga: Możesz skorzystać z zależności NWD(a, b, c) = NWD(NWD(a, b), c).\n\nPrzykład:\nDla liczb 3, 7, 4, 6, 10, 2, 5 odpowiedzią jest 4 (pierwsza liczba ciągu), 4 (długość ciągu) i 2 (największy wspólny dzielnik), natomiast dla liczb 5, 70, 28, 42, 98, 1 odpowiedzią jest 70 (pierwsza liczba ciągu), 4 (długość ciągu) i 14 (największy wspólny dzielnik).\n\nOdpowiedź dla pliku przyklad.txt: pierwsza liczba ciągu 90, długość 5, największy wspólny dzielnik 10.\n\nW pliku liczby.txt znajdź najdłuższy ciąg liczb występujących kolejno po sobie i taki, że największy wspólny dzielnik ich wszystkich jest większy od 1 (innymi słowy: istnieje taka liczba całkowita większa od 1, która jest dzielnikiem każdej z tych liczb).\n\nJako odpowiedź podaj wartość pierwszej liczby w takim ciągu, długość ciągu oraz największą liczbę całkowitą, która jest dzielnikiem każdej liczby w tym ciągu. W pliku z danymi jest tylko jeden taki ciąg o największej długości.","answer":null,"answer_text":null,"solution":"## Poprawna odpowiedź\n\n**Najdłuższy ciąg z NWD > 1 w pliku liczby.txt:**\n- **Pierwsza liczba ciągu: 31968**\n- **Długość ciągu: 150**\n- **Największy wspólny dzielnik: 74**\n\n## Sposób 1 - implementacja Python\n\n**Idea:** przeglądamy ciąg od lewej. Utrzymujemy bieżący NWD i długość. Gdy NWD spadnie do 1 - kończymy ciąg, sprawdzamy czy jest najdłuższy, i zaczynamy nowy ciąg od bieżącej liczby. Wykorzystujemy własność: **NWD(a, b, c) = NWD(NWD(a, b), c)**.\n\n```python\nfrom math import gcd\n\nwith open('liczby.txt', encoding='utf-8') as f:\nliczby = [int(linia) for linia in f]\n\nnajdluzszy_start_idx = 0\nnajdluzsza_dlugosc = 1\nnajdluzszy_nwd = liczby[0]\n\nbiezacy_start = 0\nbiezacy_nwd = liczby[0]\n\nfor i in range(1, len(liczby)):\nnowy_nwd = gcd(biezacy_nwd, liczby[i])\nif nowy_nwd > 1:\nbiezacy_nwd = nowy_nwd\ndlugosc = i - biezacy_start + 1\nif dlugosc > najdluzsza_dlugosc:\nnajdluzsza_dlugosc = dlugosc\nnajdluzszy_start_idx = biezacy_start\nnajdluzszy_nwd = biezacy_nwd\nelse:\n# nowy ciąg startuje od liczby[i]\nbiezacy_start = i\nbiezacy_nwd = liczby[i]\n\nprint(f'pierwsza liczba: {liczby[najdluzszy_start_idx]}')\nprint(f'długość: {najdluzsza_dlugosc}')\nprint(f'dzielnik: {najdluzszy_nwd}')\n# pierwsza liczba: 31968\n# długość: 150\n# dzielnik: 74\n\n**Algorytm NWD (Euklides):**\n```python\ndef nwd(a, b):\nwhile b > 0:\na, b = b, a % b\nreturn a\n\n## Sposób 2 - implementacja Pascal\n\n```pascal\nprogram NajdluzszyCiagNWD;\nvar\nf: TextFile;\nliczby: array[1 500] of LongInt;\ni, n: Integer;\nbiezacyStart, biezacyNWD, najStart, najDl, najNWD, nowyNWD, dl: LongInt;\n\nfunction NWD(a, b: LongInt): LongInt;\nvar t: LongInt;\nbegin\nwhile b > 0 do begin t := b; b := a mod b; a := t; end;\nNWD := a;\nend;\n\nbegin\nAssignFile(f, 'liczby.txt');\nReset(f);\nn := 0;\nwhile not Eof(f) do begin Inc(n); ReadLn(f, liczby[n]); end;\nCloseFile(f);\n\nbiezacyStart := 1; biezacyNWD := liczby[1];\nnajStart := 1; najDl := 1; najNWD := liczby[1];\n\nfor i := 2 to n do\nbegin\nnowyNWD := NWD(biezacyNWD, liczby[i]);\nif nowyNWD > 1 then\nbegin\nbiezacyNWD := nowyNWD;\ndl := i - biezacyStart + 1;\nif dl > najDl then\nbegin\nnajDl := dl; najStart := biezacyStart; najNWD := biezacyNWD;\nend;\nend\nelse\nbegin\nbiezacyStart := i; biezacyNWD := liczby[i];\nend;\nend;\n\nWriteLn('pierwsza: ', liczby[najStart]);\nWriteLn('długość: ', najDl);\nWriteLn('dzielnik: ', najNWD);\nend.\n\n## Sposób 3 - implementacja C++\n\n```cpp\n#include \n#include \n#include \nusing namespace std;\n\nlong long nwd(long long a, long long b) {\nwhile (b > 0) { long long t = b; b = a % b; a = t; }\nreturn a;\n}\n\nint main() {\nifstream plik(\"liczby.txt\");\nvector liczby;\nlong long x;\nwhile (plik >> x) liczby.push_back(x);\n\nlong long biezacyNWD = liczby[0], najNWD = liczby[0];\nint biezacyStart = 0, najStart = 0, najDl = 1;\n\nfor (int i = 1; i < (int)liczby.size(); i++) {\nlong long nowy = nwd(biezacyNWD, liczby[i]);\nif (nowy > 1) {\nbiezacyNWD = nowy;\nint dl = i - biezacyStart + 1;\nif (dl > najDl) {\nnajDl = dl;\nnajStart = biezacyStart;\nnajNWD = biezacyNWD;\n}\n} else {\nbiezacyStart = i;\nbiezacyNWD = liczby[i];\n}\n}\n\ncout << \"pierwsza: \" << liczby[najStart] << endl;\ncout << \"długość: \" << najDl << endl;\ncout << \"dzielnik: \" << najNWD << endl;\nreturn 0;\n}\n\n## Weryfikacja na przykładzie\n\nDla `przyklad.txt`: pierwsza 90, długość 5, dzielnik 10. Oznacza, że istnieje ciąg 5 kolejnych liczb (zaczynający się od 90), których wszystkie wartości są wielokrotnościami 10.\n\nDla przykładu z treści: `3, 7, 4, 6, 10, 2, 5`:\n- 3,7 - gcd=1 (koniec ciągu 3 samodzielnie). Start nowego od 7. Ale gcd(7,4)=1 → start od 4.\n- 4,6 → gcd=2. 4,6,10 → gcd=2. 4,6,10,2 → gcd=2. 4,6,10,2,5 → gcd=1. → Ciąg: 4,6,10,2, długość 4, gcd=2 ✓.\n\n## Reference informatyczny - NWD (GCD)\n\n> Reference - Algorytm Euklidesa:\n> ```\n> NWD(a, b):\n> dopóki b > 0\n> a, b = b, a mod b\n> zwróć a\n> ```\n> Złożoność: O(log min(a, b)).\n>\n> Reference - Własności NWD:\n> - NWD(a, b) = NWD(b, a mod b).\n> - NWD(a, 0) = a.\n> - NWD(a, b, c) = NWD(NWD(a, b), c).\n> - NWD(a, b) ≥ 1 zawsze.\n> - NWD(a, b) > 1 ⟺ a i b mają wspólny dzielnik > 1.\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 4.3, max 5 pkt):\n> - **1 pkt** - pierwsza liczba w ciągu (31968)\n> - **2 pkt** - długość ciągu (150); 1 pkt jeśli różni się o 1 (np. liczenie od 0)\n> - **2 pkt** - wspólny dzielnik (74)\n> - **4 pkt** - za wariant (56536, 149, 74) - wynik z błędem off-by-one\n> - **0 pkt** - błędna albo brak\n\n## Typowe pułapki\n\n- **Resetowanie NWD po nowym elemencie ZAMIAST liczenia od zera** - gdy NWD spadnie do 1, musisz zacząć NOWY ciąg od bieżącej liczby (NIE od następnej).\n- **Aktualizacja długości tylko gdy NWD > 1** - wybór maksymalnej długości musi działać dla najdłuższego ciągu z NWD > 1, NIE każdego okna.\n- **Off-by-one przy długości** - długość = i - start + 1 (gdy indeksowanie od 0).\n- **Pierwsza liczba = `liczby[start]`** - pamiętaj, że pytanie pyta o WARTOŚĆ pierwszej liczby, nie jej indeks.\n- **Złe NWD dla pierwszego ciągu jednoelementowego** - start jako liczba pojedyncza ma NWD = sama ta liczba.\n\n## Złożoność obliczeniowa\n\n- Czytanie pliku: O(n), n = 500.\n- Główna pętla: O(n) iteracji, w każdej NWD: O(log(max)) ≈ 17 operacji dla wartości do 100 000.\n- **Łącznie: O(n · log(max))** ≈ 8500 operacji.\n- Pamięć: O(n) na tablicę liczb (lub O(1) gdy czytamy streaming).","image":null,"solution_image":null,"topics":null,"page_from":null,"source":"maturazai","answer_source":null,"answer_text_source":null,"solution_source":"maturazai","text_source":"maturazai","source_label":"Informatyka · Matura · maj 2019 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Kontekst - patrz zadanie 4.1.

\n

Uwaga: Możesz skorzystać z zależności NWD(a, b, c) = NWD(NWD(a, b), c).

\n

Przykład:
Dla liczb 3, 7, 4, 6, 10, 2, 5 odpowiedzią jest 4 (pierwsza liczba ciągu), 4 (długość ciągu) i 2 (największy wspólny dzielnik), natomiast dla liczb 5, 70, 28, 42, 98, 1 odpowiedzią jest 70 (pierwsza liczba ciągu), 4 (długość ciągu) i 14 (największy wspólny dzielnik).

\n

Odpowiedź dla pliku przyklad.txt: pierwsza liczba ciągu 90, długość 5, największy wspólny dzielnik 10.

\n

W pliku liczby.txt znajdź najdłuższy ciąg liczb występujących kolejno po sobie i taki, że największy wspólny dzielnik ich wszystkich jest większy od 1 (innymi słowy: istnieje taka liczba całkowita większa od 1, która jest dzielnikiem każdej z tych liczb).

\n

Jako odpowiedź podaj wartość pierwszej liczby w takim ciągu, długość ciągu oraz największą liczbę całkowitą, która jest dzielnikiem każdej liczby w tym ciągu. W pliku z danymi jest tylko jeden taki ciąg o największej długości.

","solutions":[{"source":"maturazai","label":"maturazai.pl (AI)","kind":"text","html":"

Poprawna odpowiedź

\n

Najdłuższy ciąg z NWD > 1 w pliku liczby.txt:

\n
  • Pierwsza liczba ciągu: 31968
  • Długość ciągu: 150
  • Największy wspólny dzielnik: 74
\n

Sposób 1 - implementacja Python

\n

Idea: przeglądamy ciąg od lewej. Utrzymujemy bieżący NWD i długość. Gdy NWD spadnie do 1 - kończymy ciąg, sprawdzamy czy jest najdłuższy, i zaczynamy nowy ciąg od bieżącej liczby. Wykorzystujemy własność: NWD(a, b, c) = NWD(NWD(a, b), c).

\n

```python
from math import gcd

\n

with open('liczby.txt', encoding='utf-8') as f:
liczby = [int(linia) for linia in f]

\n

najdluzszy_start_idx = 0
najdluzsza_dlugosc = 1
najdluzszy_nwd = liczby[0]

\n

biezacy_start = 0
biezacy_nwd = liczby[0]

\n

for i in range(1, len(liczby)):
nowy_nwd = gcd(biezacy_nwd, liczby[i])
if nowy_nwd > 1:
biezacy_nwd = nowy_nwd
dlugosc = i - biezacy_start + 1
if dlugosc > najdluzsza_dlugosc:
najdluzsza_dlugosc = dlugosc
najdluzszy_start_idx = biezacy_start
najdluzszy_nwd = biezacy_nwd
else:

\n

nowy ciąg startuje od liczby[i]

\n

biezacy_start = i
biezacy_nwd = liczby[i]

\n

print(f'pierwsza liczba: {liczby[najdluzszy_start_idx]}')
print(f'długość: {najdluzsza_dlugosc}')
print(f'dzielnik: {najdluzszy_nwd}')

\n

pierwsza liczba: 31968

\n

długość: 150

\n

dzielnik: 74

\n

Algorytm NWD (Euklides):
```python
def nwd(a, b):
while b > 0:
a, b = b, a % b
return a

\n

Sposób 2 - implementacja Pascal

\n

```pascal
program NajdluzszyCiagNWD;
var
f: TextFile;
liczby: array[1 500] of LongInt;
i, n: Integer;
biezacyStart, biezacyNWD, najStart, najDl, najNWD, nowyNWD, dl: LongInt;

\n

function NWD(a, b: LongInt): LongInt;
var t: LongInt;
begin
while b > 0 do begin t := b; b := a mod b; a := t; end;
NWD := a;
end;

\n

begin
AssignFile(f, 'liczby.txt');
Reset(f);
n := 0;
while not Eof(f) do begin Inc(n); ReadLn(f, liczby[n]); end;
CloseFile(f);

\n

biezacyStart := 1; biezacyNWD := liczby[1];
najStart := 1; najDl := 1; najNWD := liczby[1];

\n

for i := 2 to n do
begin
nowyNWD := NWD(biezacyNWD, liczby[i]);
if nowyNWD > 1 then
begin
biezacyNWD := nowyNWD;
dl := i - biezacyStart + 1;
if dl > najDl then
begin
najDl := dl; najStart := biezacyStart; najNWD := biezacyNWD;
end;
end
else
begin
biezacyStart := i; biezacyNWD := liczby[i];
end;
end;

\n

WriteLn('pierwsza: ', liczby[najStart]);
WriteLn('długość: ', najDl);
WriteLn('dzielnik: ', najNWD);
end.

\n

Sposób 3 - implementacja C++

\n

```cpp
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

\n

long long nwd(long long a, long long b) {
while (b > 0) { long long t = b; b = a % b; a = t; }
return a;
}

\n

int main() {
ifstream plik("liczby.txt");
vector<long long> liczby;
long long x;
while (plik >> x) liczby.push_back(x);

\n

long long biezacyNWD = liczby[0], najNWD = liczby[0];
int biezacyStart = 0, najStart = 0, najDl = 1;

\n

for (int i = 1; i < (int)liczby.size(); i++) {
long long nowy = nwd(biezacyNWD, liczby[i]);
if (nowy > 1) {
biezacyNWD = nowy;
int dl = i - biezacyStart + 1;
if (dl > najDl) {
najDl = dl;
najStart = biezacyStart;
najNWD = biezacyNWD;
}
} else {
biezacyStart = i;
biezacyNWD = liczby[i];
}
}

\n

cout << "pierwsza: " << liczby[najStart] << endl;
cout << "długość: " << najDl << endl;
cout << "dzielnik: " << najNWD << endl;
return 0;
}

\n

Weryfikacja na przykładzie

\n

Dla przyklad.txt: pierwsza 90, długość 5, dzielnik 10. Oznacza, że istnieje ciąg 5 kolejnych liczb (zaczynający się od 90), których wszystkie wartości są wielokrotnościami 10.

\n

Dla przykładu z treści: 3, 7, 4, 6, 10, 2, 5:

\n
  • 3,7 - gcd=1 (koniec ciągu 3 samodzielnie). Start nowego od 7. Ale gcd(7,4)=1 → start od 4.
  • 4,6 → gcd=2. 4,6,10 → gcd=2. 4,6,10,2 → gcd=2. 4,6,10,2,5 → gcd=1. → Ciąg: 4,6,10,2, długość 4, gcd=2 ✓.
\n

Reference informatyczny - NWD (GCD)

\n
Reference - Algorytm Euklidesa:
```
NWD(a, b):
dopóki b > 0
a, b = b, a mod b
zwróć a
```
Złożoność: O(log min(a, b)).

Reference - Własności NWD:
- NWD(a, b) = NWD(b, a mod b).
- NWD(a, 0) = a.
- NWD(a, b, c) = NWD(NWD(a, b), c).
- NWD(a, b) ≥ 1 zawsze.
- NWD(a, b) > 1 ⟺ a i b mają wspólny dzielnik > 1.
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 4.3, max 5 pkt):
- 1 pkt - pierwsza liczba w ciągu (31968)
- 2 pkt - długość ciągu (150); 1 pkt jeśli różni się o 1 (np. liczenie od 0)
- 2 pkt - wspólny dzielnik (74)
- 4 pkt - za wariant (56536, 149, 74) - wynik z błędem off-by-one
- 0 pkt - błędna albo brak
\n

Typowe pułapki

\n
  • Resetowanie NWD po nowym elemencie ZAMIAST liczenia od zera - gdy NWD spadnie do 1, musisz zacząć NOWY ciąg od bieżącej liczby (NIE od następnej).
  • Aktualizacja długości tylko gdy NWD > 1 - wybór maksymalnej długości musi działać dla najdłuższego ciągu z NWD > 1, NIE każdego okna.
  • Off-by-one przy długości - długość = i - start + 1 (gdy indeksowanie od 0).
  • Pierwsza liczba = liczby[start] - pamiętaj, że pytanie pyta o WARTOŚĆ pierwszej liczby, nie jej indeks.
  • Złe NWD dla pierwszego ciągu jednoelementowego - start jako liczba pojedyncza ma NWD = sama ta liczba.
\n

Złożoność obliczeniowa

\n
  • Czytanie pliku: O(n), n = 500.
  • Główna pętla: O(n) iteracji, w każdej NWD: O(log(max)) ≈ 17 operacji dla wartości do 100 000.
  • Łącznie: O(n · log(max)) ≈ 8500 operacji.
  • Pamięć: O(n) na tablicę liczb (lub O(1) gdy czytamy streaming).
"}]}