# Informatyka — zadanie 4.1

> Źródło: matura.lol — https://matura.lol/question/maturazai-informatyka-inf-2019-05/zad/4.1
> Wersja Markdown strony zadania (dla asystentów AI). Przy cytowaniu podaj matura.lol i link powyżej.

- arkusz: Informatyka · Matura · maj 2019 (rozszerzona)
- rok: 2019
- poziom: rozszerzona
- typ: open
- punkty: 3
- działy: Programowanie i algorytmika

## Treść

Zadanie 4. Liczby

W pliku liczby.txt zapisano 500 liczb całkowitych dodatnich po jednej w każdym wierszu. Każda liczba jest z zakresu od 1 do 100 000. Napisz program(-y) dający(-e) odpowiedzi do poniższych zadań. Zapisz uzyskane odpowiedzi w pliku wyniki4.txt, poprzedzając każdą z nich numerem odpowiedniego zadania.

Uwaga: Plik przyklad.txt zawiera przykładowe dane spełniające warunki zadania. Odpowiedzi dla danych z tego pliku są podane pod treściami zadań.

Podaj, ile z podanych liczb jest potęgami liczby 3 (czyli liczbami postaci 1 = 3⁰, 3 = 3¹, 9 = 3² itd.).

Dla pliku przyklad.txt odpowiedź wynosi 2.

## Rozwiązanie — maturazai.pl (AI)

## Poprawna odpowiedź

**Liczba potęg liczby 3 w pliku liczby.txt: 18**

Potęgi 3 w zakresie [1, 100 000]: 3⁰=1, 3¹=3, 3²=9, 3³=27, 3⁴=81, 3⁵=243, 3⁶=729, 3⁷=2187, 3⁸=6561, 3⁹=19683, 3¹⁰=59049 (3¹¹=177147 > 100 000).

## Sposób 1 - implementacja Python (rekomendowana)

**Idea 1: prekomputacja potęg + sprawdzenie przynależności.**

```python
# Wszystkie potęgi 3 ≤ 100000
potegi = set()
p = 1
while p <= 100000:
potegi.add(p)
p *= 3
# potegi = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049}

licznik = 0
with open('liczby.txt', encoding='utf-8') as f:
for linia in f:
n = int(linia.strip())
if n in potegi:
licznik += 1

print(licznik) # 18

**Idea 2: dzielenie przez 3 dopóki się da.**

```python
def jest_potega_3(n):
while n % 3 == 0:
n //= 3
return n == 1

licznik = 0
with open('liczby.txt') as f:
for linia in f:
n = int(linia.strip())
if jest_potega_3(n):
licznik += 1
print(licznik) # 18

## Sposób 2 - implementacja Pascal

```pascal
program PotegiTrojki;
var
f: TextFile;
n, licznik, m: LongInt;
begin
AssignFile(f, 'liczby.txt');
Reset(f);
licznik := 0;
while not Eof(f) do
begin
ReadLn(f, n);
m := n;
while (m mod 3 = 0) do m := m div 3;
if m = 1 then licznik := licznik + 1;
end;
CloseFile(f);
WriteLn('Liczba potęg 3: ', licznik);
end.

## Sposób 3 - implementacja C++

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

bool jestPotega3(long long n) {
while (n % 3 == 0) n /= 3;
return n == 1;
}

int main() {
ifstream plik("liczby.txt");
long long n;
int licznik = 0;
while (plik >> n) {
if (jestPotega3(n)) licznik++;
}
cout << "Liczba potęg 3: " << licznik << endl;
return 0;
}

## Sposób 4 - weryfikacja dla przyklad.txt

Dla `przyklad.txt` odpowiedź wynosi **2** (zgodnie z treścią zadania). Oznacza to, że w pliku przykładowym są dokładnie 2 liczby będące potęgami 3 (np. 1 i 27).

## Reference informatyczny - test na potęgę liczby

> Reference - Sprawdzanie czy n jest potęgą k:
> - **Algorytm dzielenia:** dzielimy n przez k dopóki dzieli się bez reszty. Jeśli zakończymy z n=1 → jest potęgą.
> - **Złożoność:** O(log_k(n)).
> - **Wariant prekomputacji:** generuj wszystkie potęgi k ≤ MAX, sprawdź przynależność. Złożoność: O(1) na zapytanie (z hashsetem).
> - **Wariant logarytmiczny (z float):** `log(n)/log(k) ∈ Z`? - ALE niedokładny przez błędy floating-point. NIE używać w zadaniach CKE.
> - **Dla potęgi 2:** trik `(n & (n-1)) == 0` (bit-tricky).

## Schemat oceniania CKE

> Klucz CKE (zadanie 4.1, max 3 pkt):
> - **3 pkt** - prawidłowa odpowiedź (18)
> - **2 pkt** - wynik różniący się o 1 (np. pominięcie 1=3⁰ albo licznik od 0)
> - **1 pkt** - wynik mniejszy o 2 lub 3 (pominięcie 2-3 liczb)
> - **0 pkt** - błędna lub brak

## Typowe pułapki

- **Pominięcie 1 = 3⁰** - częsty błąd: "potęgi to 3, 9, 27 " bez liczby 1. Treść WYRAŹNIE pisze "liczbami postaci 1 = 3⁰".
- **Floating-point** w teście `log3(n) ∈ Z` - błędy zaokrąglenia mogą dać fałszywe wyniki.
- **`n % 3 == 0` na liczbach typu 12, 15** - to nie są potęgi 3, ale dzielą się przez 3. KLUCZ: po wszystkich dzieleniach trzeba zostać z 1.
- **Off-by-one** przy liczeniu (start od 0 vs 1).
- **Niepoprawne czytanie pliku** - pomylenie z `print` zamiast czytania linii.

## Złożoność obliczeniowa

- Czytanie pliku: O(n) - n = 500 wierszy.
- Test na potęgę 3 metodą dzielenia: O(log₃(max)) = O(log(100000)) ≈ 11 operacji.
- **Łączna złożoność: O(n · log(max)) ≈ 5500 operacji** (bardzo szybko).
- Pamięć: O(1) (lub O(log(max)) dla zbioru potęg).

## Linki

- [dane JSON](https://matura.lol/api/question/maturazai-informatyka-inf-2019-05/zad/4.1)
- [otwórz w wyszukiwarce](https://matura.lol/?problem=maturazai-informatyka-inf-2019-05%2Fzad%2F4.1)

## Podobne zadania

- [Zadanie 3](https://matura.lol/question/informatyka-2026-maj-matura-rozszerzona/zad/3) — Zadanie 3. Pary slow W pliku tekstowym pary.txt znajduje sie 500 par slow zlozonych z liter alfabetu angielskiego a, b, , z. Kazda para slow jest zapisana w oso
- [Zadanie 2](https://matura.lol/question/informatyka-2026-maj-matura-rozszerzona/zad/2) — Zadanie 2. Dodawanie Rozwazamy dodawanie pisemne dwoch liczb zapisanych w systemie dziesietnym, zilustrowane na przykladzie. Przeniesienie: 1 1 1 1 Liczba a: 2 
- [Zadanie 4.2](https://matura.lol/question/informatyka-2020-lipiec-matura-rozszerzona-2/zad/4.2) — Zadanie 4.2. (0-4) Podaj wszystkie te identyfikatory dokumentów z pliku identyfikator.txt, których seria lub numer są palindromami, czyli czytane od lewej do pr
- [Zadanie 4.2](https://matura.lol/question/informatyka-2018-maj-matura-rozszerzona-2/zad/4.2) — Kontekst - patrz zadanie 4.1. Znajdź słowo, w którym występuje największa liczba **różnych** liter. Wypisz to słowo i liczbę występujących w nim różnych liter. 

_Ostatnia aktualizacja danych: 2026-10-03_