{"id":"informatyka-2018-maj-matura-rozszerzona/zad/4.3","paper_id":"informatyka-2018-maj-matura-rozszerzona","number":"4.3","points":4,"ptype":"open","subject":"informatyka","category":"matura","year":2018,"month":"maj","level":"rozszerzona","text":"Kontekst - patrz zadanie 4.1.\n\nNa przykład CGECF jest takim słowem, ale ABEZA nie jest (odległość A - Z wynosi 25).\n\nW tym zadaniu rozważmy odległość liter w alfabecie - np. litery A i B są od siebie oddalone o 1, A i E o 4, F i D o 2, a każda litera od siebie samej jest oddalona o 0. Wypisz wszystkie słowa, w których każde dwie litery oddalone są od siebie w alfabecie co najwyżej o 10. Słowa wypisz w kolejności występowania w pliku sygnaly.txt, po jednym w wierszu.\n\nDla danych z pliku przyklad.txt wynikiem jest 15 słów: AAAAAAAAAI, AAAAAAAAAE, AAAAAAAAAC, AAAAAAAAAH, AAAAAAAAAC, AAAAAAAAAI, AAAAAAAAAA, BB, AAAAAAAAAA, AAAAAAAAAA, AAAAAAAAAB, AAAAAAAAAE, AAAAAAAAAD, AAAAAAAAAI, AAAAAAAAAE.","answer":null,"answer_text":null,"solution":"## Poprawna odpowiedź\n\n**Lista słów** (przykładowe pierwsze z sygnaly.txt):\nQQMLKKQNOHPKKPJOLHIPJKLKQIIHQHPNKNQPHNKLKQNIMLQPNLPMHNNIPNJJONQOHHKKQOIHOHHJMOJPMNIPIKION, OO, FH, AE, (cała lista to słowa spełniające warunek max odległość 10 między KAŻDYMI dwiema literami).\n\n## Sposób 1 - kluczowa interpretacja zadania\n\n**UWAGA - kluczowy detal:** warunek dotyczy **KAŻDEJ PARY liter w słowie**, nie tylko sąsiadów!\n\nDla słowa s, warunek: dla każdego i, j: `|s[i] - s[j]| ≤ 10`.\n\nTo równoważne: `max(s) - min(s) ≤ 10` (różnica między największą a najmniejszą literą).\n\n**Przykład:** `ABEZA`:\n- min = A, max = Z, różnica = 25. **NIE spełnia** warunku (25 > 10).\n- Mimo że sąsiednie litery są blisko siebie (np. A-B, B-E, E-Z=21, Z-A=25), to KAŻDE dwie litery muszą się różnić ≤ 10.\n\n**Przykład:** `CGECF`:\n- min = C, max = G, różnica = 4. **Spełnia** (4 ≤ 10).\n\n## Sposób 2 - implementacja Python\n\n```python\nwyniki = []\nwith open('sygnaly.txt', encoding='utf-8') as f:\nfor linia in f:\ns = linia.strip()\nif not s:\ncontinue\n# Warunek: max(s) - min(s) <= 10\nif ord(max(s)) - ord(min(s)) <= 10:\nwyniki.append(s)\n\nwith open('wyniki4.txt', 'a', encoding='utf-8') as f:\nf.write(\"4.3\\n\")\nfor s in wyniki:\nf.write(s + '\\n')\n\nprint(f\"Liczba słów: {len(wyniki)}\")\nprint(\"Pierwsze 5:\")\nfor s in wyniki[:5]:\nprint(s)\n\n## Sposób 3 - C++\n\n```cpp\n#include \n#include \n#include \n#include \nusing namespace std;\n\nbool sprawdz(const string& s) {\nif (s.empty()) return false;\nchar min_c = *min_element(s.begin(), s.end());\nchar max_c = *max_element(s.begin(), s.end());\nreturn (max_c - min_c) <= 10;\n}\n\nint main() {\nifstream fin(\"sygnaly.txt\");\nofstream fout(\"wyniki4.txt\", ios::app);\nfout << \"4.3\\n\";\nstring s;\nwhile (fin >> s) {\nif (sprawdz(s)) fout << s << \"\\n\";\n}\nreturn 0;\n}\n\n## Sposób 4 - Pascal\n\n```pascal\nprogram Wega43;\nvar fin, fout: TextFile; s: String;\ni: Integer; minC, maxC: Char;\nbegin\nAssignFile(fin, 'sygnaly.txt'); Reset(fin);\nAssignFile(fout, 'wyniki4.txt'); Append(fout);\nWriteln(fout, '4.3');\nwhile not Eof(fin) do begin\nReadln(fin, s);\nif Length(s) = 0 then Continue;\nminC := s[1]; maxC := s[1];\nfor i := 2 to Length(s) do begin\nif s[i] < minC then minC := s[i];\nif s[i] > maxC then maxC := s[i];\nend;\nif (Ord(maxC) - Ord(minC)) <= 10 then Writeln(fout, s);\nend;\nCloseFile(fin); CloseFile(fout);\nend.\n\n## Reference informatyczny - odległość alfabetyczna\n\n> Reference - Min/max w stringu:\n> - **Python**: `min(s)`, `max(s)` - leksykograficznie (alfabetycznie).\n> - **C++**: `min_element(s.begin(), s.end())`, `max_element( )`.\n> - **Pascal**: pętla z porównaniem.\n>\n> Reference - Równoważność warunków:\n> - \"Każde dwie litery oddalone ≤ 10\" ≡ \"max(s) - min(s) ≤ 10\".\n> - DOWÓD: jeśli max - min ≤ 10, to dla dowolnej pary (a, b): |a-b| ≤ max-min ≤ 10. I odwrotnie - jeśli max-min > 10, to para (min, max) łamie warunek.\n>\n> Reference - Klucz CKE - pułapka z 2 pkt:\n> - **Jeśli porównujemy tylko SĄSIEDNIE litery** (s[i] vs s[i+1]), wynik to 207 słów. To częsta pomyłka.\n> - Poprawny wynik (max - min) daje 15 słów dla przyklad.txt.\n\n## Schemat oceniania CKE\n\n> Klucz CKE (zadanie 4.3, max 4 pkt):\n> - **4 pkt** - poprawna lista (warunek dla WSZYSTKICH par)\n> - **2 pkt** - lista z porównania tylko SĄSIADUJĄCYCH liter (207 słów dla sygnaly.txt)\n> - **0 pkt** - błędna lub brak\n>\n> **Uwaga: NIE PRZYZNAJE SIĘ 3 ani 1 PUNKTU.**\n\n## Typowe pułapki\n\n- **Porównywanie tylko sąsiadów** - KLASYCZNA pułapka. \"Każde dwie\" = WSZYSTKIE PARY, nie tylko sąsiednie.\n- **Wzór `max - min ≤ 10`** - eleganckie i poprawne; alternatywa to podwójna pętla po wszystkich parach (O(L²)).\n- **Pomylenie odległości** - A i B oddalone o 1 (nie 2), A i E o 4 (nie 5). Bez offset.\n- **Wartość bezwzględna** - `|a-b|`, bo odległość nie ma znaku.\n- **`ord('A')`** - kod ASCII A to 65. Dla A do Z: 65-90. Różnica między 'Z' a 'A' = 25.\n- **Pominięcie pustego słowa** - sprawdź `if not s` lub `if Length(s) = 0`.\n\n## Złożoność obliczeniowa\n\n- Dla każdego słowa: O(L) (znajdowanie min/max).\n- Dla 1000 słów × max 100 znaków: **O(N · L)** = O(100 000) operacji.\n- Alternatywa naiwna O(L²) per słowo = O(N · L²) = 10⁷ operacji. Mniej elegancko, ale wciąż mieści się w czasie.","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 2018 (rozszerzona)","subject_label":"Informatyka","category_label":"Matura","text_html":"

Kontekst - patrz zadanie 4.1.

\n

Na przykład CGECF jest takim słowem, ale ABEZA nie jest (odległość A - Z wynosi 25).

\n

W tym zadaniu rozważmy odległość liter w alfabecie - np. litery A i B są od siebie oddalone o 1, A i E o 4, F i D o 2, a każda litera od siebie samej jest oddalona o 0. Wypisz wszystkie słowa, w których każde dwie litery oddalone są od siebie w alfabecie co najwyżej o 10. Słowa wypisz w kolejności występowania w pliku sygnaly.txt, po jednym w wierszu.

\n

Dla danych z pliku przyklad.txt wynikiem jest 15 słów: AAAAAAAAAI, AAAAAAAAAE, AAAAAAAAAC, AAAAAAAAAH, AAAAAAAAAC, AAAAAAAAAI, AAAAAAAAAA, BB, AAAAAAAAAA, AAAAAAAAAA, AAAAAAAAAB, AAAAAAAAAE, AAAAAAAAAD, AAAAAAAAAI, AAAAAAAAAE.

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

Poprawna odpowiedź

\n

Lista słów (przykładowe pierwsze z sygnaly.txt):
QQMLKKQNOHPKKPJOLHIPJKLKQIIHQHPNKNQPHNKLKQNIMLQPNLPMHNNIPNJJONQOHHKKQOIHOHHJMOJPMNIPIKION, OO, FH, AE, (cała lista to słowa spełniające warunek max odległość 10 między KAŻDYMI dwiema literami).

\n

Sposób 1 - kluczowa interpretacja zadania

\n

UWAGA - kluczowy detal: warunek dotyczy KAŻDEJ PARY liter w słowie, nie tylko sąsiadów!

\n

Dla słowa s, warunek: dla każdego i, j: |s[i] - s[j]| ≤ 10.

\n

To równoważne: max(s) - min(s) ≤ 10 (różnica między największą a najmniejszą literą).

\n

Przykład: ABEZA:

\n
  • min = A, max = Z, różnica = 25. NIE spełnia warunku (25 > 10).
  • Mimo że sąsiednie litery są blisko siebie (np. A-B, B-E, E-Z=21, Z-A=25), to KAŻDE dwie litery muszą się różnić ≤ 10.
\n

Przykład: CGECF:

\n
  • min = C, max = G, różnica = 4. Spełnia (4 ≤ 10).
\n

Sposób 2 - implementacja Python

\n

```python
wyniki = []
with open('sygnaly.txt', encoding='utf-8') as f:
for linia in f:
s = linia.strip()
if not s:
continue

\n

Warunek: max(s) - min(s) <= 10

\n

if ord(max(s)) - ord(min(s)) <= 10:
wyniki.append(s)

\n

with open('wyniki4.txt', 'a', encoding='utf-8') as f:
f.write("4.3\\n")
for s in wyniki:
f.write(s + '\\n')

\n

print(f"Liczba słów: {len(wyniki)}")
print("Pierwsze 5:")
for s in wyniki[:5]:
print(s)

\n

Sposób 3 - C++

\n

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

\n

bool sprawdz(const string& s) {
if (s.empty()) return false;
char min_c = *min_element(s.begin(), s.end());
char max_c = *max_element(s.begin(), s.end());
return (max_c - min_c) <= 10;
}

\n

int main() {
ifstream fin("sygnaly.txt");
ofstream fout("wyniki4.txt", ios::app);
fout << "4.3\\n";
string s;
while (fin >> s) {
if (sprawdz(s)) fout << s << "\\n";
}
return 0;
}

\n

Sposób 4 - Pascal

\n

```pascal
program Wega43;
var fin, fout: TextFile; s: String;
i: Integer; minC, maxC: Char;
begin
AssignFile(fin, 'sygnaly.txt'); Reset(fin);
AssignFile(fout, 'wyniki4.txt'); Append(fout);
Writeln(fout, '4.3');
while not Eof(fin) do begin
Readln(fin, s);
if Length(s) = 0 then Continue;
minC := s[1]; maxC := s[1];
for i := 2 to Length(s) do begin
if s[i] < minC then minC := s[i];
if s[i] > maxC then maxC := s[i];
end;
if (Ord(maxC) - Ord(minC)) <= 10 then Writeln(fout, s);
end;
CloseFile(fin); CloseFile(fout);
end.

\n

Reference informatyczny - odległość alfabetyczna

\n
Reference - Min/max w stringu:
- Python: min(s), max(s) - leksykograficznie (alfabetycznie).
- C++: min_element(s.begin(), s.end()), max_element( ).
- Pascal: pętla z porównaniem.

Reference - Równoważność warunków:
- "Każde dwie litery oddalone ≤ 10" ≡ "max(s) - min(s) ≤ 10".
- DOWÓD: jeśli max - min ≤ 10, to dla dowolnej pary (a, b): |a-b| ≤ max-min ≤ 10. I odwrotnie - jeśli max-min > 10, to para (min, max) łamie warunek.

Reference - Klucz CKE - pułapka z 2 pkt:
- Jeśli porównujemy tylko SĄSIEDNIE litery (s[i] vs s[i+1]), wynik to 207 słów. To częsta pomyłka.
- Poprawny wynik (max - min) daje 15 słów dla przyklad.txt.
\n

Schemat oceniania CKE

\n
Klucz CKE (zadanie 4.3, max 4 pkt):
- 4 pkt - poprawna lista (warunek dla WSZYSTKICH par)
- 2 pkt - lista z porównania tylko SĄSIADUJĄCYCH liter (207 słów dla sygnaly.txt)
- 0 pkt - błędna lub brak

Uwaga: NIE PRZYZNAJE SIĘ 3 ani 1 PUNKTU.
\n

Typowe pułapki

\n
  • Porównywanie tylko sąsiadów - KLASYCZNA pułapka. "Każde dwie" = WSZYSTKIE PARY, nie tylko sąsiednie.
  • Wzór max - min ≤ 10 - eleganckie i poprawne; alternatywa to podwójna pętla po wszystkich parach (O(L²)).
  • Pomylenie odległości - A i B oddalone o 1 (nie 2), A i E o 4 (nie 5). Bez offset.
  • Wartość bezwzględna - |a-b|, bo odległość nie ma znaku.
  • ord('A') - kod ASCII A to 65. Dla A do Z: 65-90. Różnica między 'Z' a 'A' = 25.
  • Pominięcie pustego słowa - sprawdź if not s lub if Length(s) = 0.
\n

Złożoność obliczeniowa

\n
  • Dla każdego słowa: O(L) (znajdowanie min/max).
  • Dla 1000 słów × max 100 znaków: O(N · L) = O(100 000) operacji.
  • Alternatywa naiwna O(L²) per słowo = O(N · L²) = 10⁷ operacji. Mniej elegancko, ale wciąż mieści się w czasie.
"}]}