Zadanie 64. Obrazki
Każdy obrazek w pliku to 21 wierszy: 20 wierszy po 20 pikseli + bit parzystości wiersza oraz ostatni wiersz z 20 bitami parzystości kolumn. Obrazki oddzielone są pustym wierszem.
Treść zadania
Bit parzystości ciągu zer i jedynek wynosi 0, gdy jedynek jest parzyście wiele, a 1 w przeciwnym razie. Czarno-biały obrazek n × n zapisujemy jako n wierszy po n pikseli (0 — biały, 1 — czarny); na końcu każdego wiersza dopisany jest jego bit parzystości, a pod obrazkiem — wiersz bitów parzystości kolejnych kolumn. Bity parzystości nie należą do obrazka. Plik dane_obrazki.txt zawiera 200 obrazków 20 × 20, oddzielonych pustym wierszem. Odpowiedzi zapisz w pliku wyniki_obrazki.txt, każdą od nowego wiersza, poprzedzoną numerem zadania.
Obrazek jest rewersem, jeśli ma więcej pikseli czarnych niż białych. Podaj, ile obrazków w pliku jest rewersami, oraz największą liczbę czarnych pikseli w jednym obrazku.
obrazki = []
with open("dane_obrazki.txt") as file:
wiersze = file.read().split() # puste wiersze znikają
for i in range(0, len(wiersze), 21):
obrazki.append(wiersze[i:i + 21])
rewersy = 0
najwiecej_czarnych = 0
for obrazek in obrazki:
czarne = 0
for wiersz in obrazek[:20]:
czarne += wiersz[:20].count("1")
if czarne > 400 - czarne:
rewersy += 1
najwiecej_czarnych = max(najwiecej_czarnych, czarne)
print(rewersy, najwiecej_czarnych)#include <algorithm>
#include <fstream>
#include <print>
#include <string>
#include <vector>
int main() {
// wczytujemy słowo po słowie - puste wiersze znikają
std::ifstream plik("dane_obrazki.txt");
std::vector<std::string> wiersze;
std::string s;
while (plik >> s) {
wiersze.push_back(s);
}
std::vector<std::vector<std::string>> obrazki;
for (size_t i = 0; i < wiersze.size(); i += 21) {
obrazki.push_back(std::vector<std::string>(wiersze.begin() + i, wiersze.begin() + i + 21));
}
int rewersy = 0;
int najwiecej_czarnych = 0;
for (const auto& obrazek : obrazki) {
int czarne = 0;
for (int w = 0; w < 20; w++) {
czarne += std::count(obrazek[w].begin(), obrazek[w].begin() + 20, '1');
}
if (czarne > 400 - czarne) {
rewersy += 1;
}
najwiecej_czarnych = std::max(najwiecej_czarnych, czarne);
}
std::println("{} {}", rewersy, najwiecej_czarnych);
}import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.List;
public class Zadanie {
public static void main(String[] args) throws Exception {
// dzielimy cały plik na słowa - puste wiersze znikają
String[] wiersze = Files.readString(Path.of("dane_obrazki.txt")).strip().split("\\s+");
List<String[]> obrazki = new ArrayList<>();
for (int i = 0; i < wiersze.length; i += 21) {
String[] obrazek = new String[21];
System.arraycopy(wiersze, i, obrazek, 0, 21);
obrazki.add(obrazek);
}
int rewersy = 0;
int najwiecejCzarnych = 0;
for (String[] obrazek : obrazki) {
int czarne = 0;
for (int w = 0; w < 20; w++) {
for (int k = 0; k < 20; k++) {
if (obrazek[w].charAt(k) == '1') {
czarne++;
}
}
}
if (czarne > 400 - czarne) {
rewersy += 1;
}
najwiecejCzarnych = Math.max(najwiecejCzarnych, czarne);
}
System.out.println(rewersy + " " + najwiecejCzarnych);
}
}Odpowiedź: 13 rewersów, największa liczba pikseli czarnych: 381
↑Treść zadania
Dane jak w zadaniu 64.1 (200 obrazków 20 × 20 z bitami parzystości w pliku dane_obrazki.txt).
Obrazek n × n jest rekurencyjny, jeśli n jest parzyste, a obrazek składa się z czterech kopii tego samego obrazka o rozmiarze n/2 × n/2 (cztery ćwiartki są identyczne). Podaj liczbę obrazków rekurencyjnych oraz opis pierwszego z nich w pliku — 20 wierszy po 20 pikseli, bez bitów parzystości.
obrazki = []
with open("dane_obrazki.txt") as file:
wiersze = file.read().split()
for i in range(0, len(wiersze), 21):
obrazek = []
for wiersz in wiersze[i:i + 20]:
obrazek.append(wiersz[:20]) # bez bitów parzystości
obrazki.append(obrazek)
def czy_rekurencyjny(obrazek):
for w in range(10):
for k in range(10):
piksel = obrazek[w][k]
if obrazek[w][k + 10] != piksel or obrazek[w + 10][k] != piksel or obrazek[w + 10][k + 10] != piksel:
return False
return True
rekurencyjne = []
for obrazek in obrazki:
if czy_rekurencyjny(obrazek):
rekurencyjne.append(obrazek)
print(len(rekurencyjne))
for wiersz in rekurencyjne[0]:
print(wiersz)#include <fstream>
#include <print>
#include <string>
#include <vector>
using Obrazek = std::vector<std::string>;
bool czy_rekurencyjny(const Obrazek& obrazek) {
for (int w = 0; w < 10; w++) {
for (int k = 0; k < 10; k++) {
char piksel = obrazek[w][k];
if (obrazek[w][k + 10] != piksel || obrazek[w + 10][k] != piksel || obrazek[w + 10][k + 10] != piksel) {
return false;
}
}
}
return true;
}
int main() {
std::ifstream plik("dane_obrazki.txt");
std::vector<std::string> wiersze;
std::string s;
while (plik >> s) {
wiersze.push_back(s);
}
std::vector<Obrazek> obrazki;
for (size_t i = 0; i < wiersze.size(); i += 21) {
Obrazek obrazek;
for (size_t w = i; w < i + 20; w++) {
obrazek.push_back(wiersze[w].substr(0, 20)); // bez bitów parzystości
}
obrazki.push_back(obrazek);
}
std::vector<Obrazek> rekurencyjne;
for (const Obrazek& obrazek : obrazki) {
if (czy_rekurencyjny(obrazek)) {
rekurencyjne.push_back(obrazek);
}
}
std::println("{}", rekurencyjne.size());
for (const std::string& wiersz : rekurencyjne[0]) {
std::println("{}", wiersz);
}
}import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.List;
public class Zadanie {
static boolean czyRekurencyjny(String[] obrazek) {
for (int w = 0; w < 10; w++) {
for (int k = 0; k < 10; k++) {
char piksel = obrazek[w].charAt(k);
if (obrazek[w].charAt(k + 10) != piksel || obrazek[w + 10].charAt(k) != piksel
|| obrazek[w + 10].charAt(k + 10) != piksel) {
return false;
}
}
}
return true;
}
public static void main(String[] args) throws Exception {
String[] wiersze = Files.readString(Path.of("dane_obrazki.txt")).strip().split("\\s+");
List<String[]> obrazki = new ArrayList<>();
for (int i = 0; i < wiersze.length; i += 21) {
String[] obrazek = new String[20];
for (int w = 0; w < 20; w++) {
obrazek[w] = wiersze[i + w].substring(0, 20); // bez bitów parzystości
}
obrazki.add(obrazek);
}
List<String[]> rekurencyjne = new ArrayList<>();
for (String[] obrazek : obrazki) {
if (czyRekurencyjny(obrazek)) {
rekurencyjne.add(obrazek);
}
}
System.out.println(rekurencyjne.size());
for (String wiersz : rekurencyjne.get(0)) {
System.out.println(wiersz);
}
}
}Odpowiedź: 60 obrazków rekurencyjnych; pierwszy z nich to naprzemiennie wiersze 11111111111111111111 i 00000000000000000000
Treść zadania
Dane jak w zadaniu 64.1.
Obrazek jest poprawny, jeśli wszystkie jego bity parzystości (wierszy i kolumn) są poprawne. Jest naprawialny, jeśli nie jest poprawny, ale ma co najwyżej jeden błędny bit parzystości wiersza i co najwyżej jeden błędny bit parzystości kolumny. Pozostałe obrazki są nienaprawialne. Podaj liczbę obrazków poprawnych, naprawialnych i nienaprawialnych oraz największą liczbę błędnych bitów parzystości w jednym obrazku.
obrazki = []
with open("dane_obrazki.txt") as file:
wiersze = file.read().split()
for i in range(0, len(wiersze), 21):
obrazki.append(wiersze[i:i + 21])
def bledne_bity(obrazek):
bledne_wiersze = []
bledne_kolumny = []
for w in range(20):
if obrazek[w][:20].count("1") % 2 != int(obrazek[w][20]):
bledne_wiersze.append(w)
for k in range(20):
jedynki = 0
for w in range(20):
jedynki += int(obrazek[w][k])
if jedynki % 2 != int(obrazek[20][k]):
bledne_kolumny.append(k)
return bledne_wiersze, bledne_kolumny
poprawne = 0
naprawialne = 0
nienaprawialne = 0
najwiecej_bledow = 0
for obrazek in obrazki:
bledne_wiersze, bledne_kolumny = bledne_bity(obrazek)
bledy = len(bledne_wiersze) + len(bledne_kolumny)
najwiecej_bledow = max(najwiecej_bledow, bledy)
if bledy == 0:
poprawne += 1
elif len(bledne_wiersze) <= 1 and len(bledne_kolumny) <= 1:
naprawialne += 1
else:
nienaprawialne += 1
print(poprawne, naprawialne, nienaprawialne, najwiecej_bledow)#include <algorithm>
#include <fstream>
#include <print>
#include <string>
#include <vector>
using Obrazek = std::vector<std::string>;
// numery wierszy i kolumn, których bit parzystości się nie zgadza
void bledne_bity(const Obrazek& obrazek, std::vector<int>& bledne_wiersze, std::vector<int>& bledne_kolumny) {
for (int w = 0; w < 20; w++) {
int jedynki = std::count(obrazek[w].begin(), obrazek[w].begin() + 20, '1');
if (jedynki % 2 != obrazek[w][20] - '0') {
bledne_wiersze.push_back(w);
}
}
for (int k = 0; k < 20; k++) {
int jedynki = 0;
for (int w = 0; w < 20; w++) {
jedynki += obrazek[w][k] - '0';
}
if (jedynki % 2 != obrazek[20][k] - '0') {
bledne_kolumny.push_back(k);
}
}
}
int main() {
std::ifstream plik("dane_obrazki.txt");
std::vector<std::string> wiersze;
std::string s;
while (plik >> s) {
wiersze.push_back(s);
}
std::vector<Obrazek> obrazki;
for (size_t i = 0; i < wiersze.size(); i += 21) {
obrazki.push_back(Obrazek(wiersze.begin() + i, wiersze.begin() + i + 21));
}
int poprawne = 0;
int naprawialne = 0;
int nienaprawialne = 0;
int najwiecej_bledow = 0;
for (const Obrazek& obrazek : obrazki) {
std::vector<int> bledne_wiersze, bledne_kolumny;
bledne_bity(obrazek, bledne_wiersze, bledne_kolumny);
int bledy = bledne_wiersze.size() + bledne_kolumny.size();
najwiecej_bledow = std::max(najwiecej_bledow, bledy);
if (bledy == 0) {
poprawne += 1;
} else if (bledne_wiersze.size() <= 1 && bledne_kolumny.size() <= 1) {
naprawialne += 1;
} else {
nienaprawialne += 1;
}
}
std::println("{} {} {} {}", poprawne, naprawialne, nienaprawialne, najwiecej_bledow);
}import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.List;
public class Zadanie {
// numery wierszy i kolumn, których bit parzystości się nie zgadza
static void bledneBity(String[] obrazek, List<Integer> bledneWiersze, List<Integer> bledneKolumny) {
for (int w = 0; w < 20; w++) {
int jedynki = 0;
for (int k = 0; k < 20; k++) {
jedynki += obrazek[w].charAt(k) - '0';
}
if (jedynki % 2 != obrazek[w].charAt(20) - '0') {
bledneWiersze.add(w);
}
}
for (int k = 0; k < 20; k++) {
int jedynki = 0;
for (int w = 0; w < 20; w++) {
jedynki += obrazek[w].charAt(k) - '0';
}
if (jedynki % 2 != obrazek[20].charAt(k) - '0') {
bledneKolumny.add(k);
}
}
}
public static void main(String[] args) throws Exception {
String[] wiersze = Files.readString(Path.of("dane_obrazki.txt")).strip().split("\\s+");
List<String[]> obrazki = new ArrayList<>();
for (int i = 0; i < wiersze.length; i += 21) {
String[] obrazek = new String[21];
System.arraycopy(wiersze, i, obrazek, 0, 21);
obrazki.add(obrazek);
}
int poprawne = 0;
int naprawialne = 0;
int nienaprawialne = 0;
int najwiecejBledow = 0;
for (String[] obrazek : obrazki) {
List<Integer> bledneWiersze = new ArrayList<>();
List<Integer> bledneKolumny = new ArrayList<>();
bledneBity(obrazek, bledneWiersze, bledneKolumny);
int bledy = bledneWiersze.size() + bledneKolumny.size();
najwiecejBledow = Math.max(najwiecejBledow, bledy);
if (bledy == 0) {
poprawne += 1;
} else if (bledneWiersze.size() <= 1 && bledneKolumny.size() <= 1) {
naprawialne += 1;
} else {
nienaprawialne += 1;
}
}
System.out.println(poprawne + " " + naprawialne + " " + nienaprawialne + " " + najwiecejBledow);
}
}Odpowiedź: poprawne: 171, naprawialne: 14, nienaprawialne: 15, największa liczba błędnych bitów parzystości: 7
↑Treść zadania
Dane jak w zadaniu 64.1; definicje jak w zadaniu 64.3.
Obrazek naprawialny można poprawić, zmieniając jedną wartość: jeśli błędne są bity parzystości i-tego wiersza i j-tej kolumny, zmieniamy j-ty piksel w i-tym wierszu; jeśli błędny jest tylko jeden bit parzystości (wiersza albo kolumny), zmieniamy ten bit. Podaj numery wszystkich obrazków naprawialnych (obrazki numerujemy od 1), a przy każdym numer wiersza i kolumny wartości, którą trzeba zmienić.
obrazki = []
with open("dane_obrazki.txt") as file:
wiersze = file.read().split()
for i in range(0, len(wiersze), 21):
obrazki.append(wiersze[i:i + 21])
def bledne_bity(obrazek):
bledne_wiersze = []
bledne_kolumny = []
for w in range(20):
if obrazek[w][:20].count("1") % 2 != int(obrazek[w][20]):
bledne_wiersze.append(w)
for k in range(20):
jedynki = 0
for w in range(20):
jedynki += int(obrazek[w][k])
if jedynki % 2 != int(obrazek[20][k]):
bledne_kolumny.append(k)
return bledne_wiersze, bledne_kolumny
for numer in range(len(obrazki)):
bledne_wiersze, bledne_kolumny = bledne_bity(obrazki[numer])
if len(bledne_wiersze) + len(bledne_kolumny) == 0:
continue
if len(bledne_wiersze) > 1 or len(bledne_kolumny) > 1:
continue
# wiersz/kolumna 21 oznacza bit parzystości
wiersz = bledne_wiersze[0] + 1 if bledne_wiersze else 21
kolumna = bledne_kolumny[0] + 1 if bledne_kolumny else 21
print(numer + 1, wiersz, kolumna)#include <algorithm>
#include <fstream>
#include <print>
#include <string>
#include <vector>
using Obrazek = std::vector<std::string>;
// numery wierszy i kolumn, których bit parzystości się nie zgadza
void bledne_bity(const Obrazek& obrazek, std::vector<int>& bledne_wiersze, std::vector<int>& bledne_kolumny) {
for (int w = 0; w < 20; w++) {
int jedynki = std::count(obrazek[w].begin(), obrazek[w].begin() + 20, '1');
if (jedynki % 2 != obrazek[w][20] - '0') {
bledne_wiersze.push_back(w);
}
}
for (int k = 0; k < 20; k++) {
int jedynki = 0;
for (int w = 0; w < 20; w++) {
jedynki += obrazek[w][k] - '0';
}
if (jedynki % 2 != obrazek[20][k] - '0') {
bledne_kolumny.push_back(k);
}
}
}
int main() {
std::ifstream plik("dane_obrazki.txt");
std::vector<std::string> wiersze;
std::string s;
while (plik >> s) {
wiersze.push_back(s);
}
std::vector<Obrazek> obrazki;
for (size_t i = 0; i < wiersze.size(); i += 21) {
obrazki.push_back(Obrazek(wiersze.begin() + i, wiersze.begin() + i + 21));
}
for (size_t numer = 0; numer < obrazki.size(); numer++) {
std::vector<int> bledne_wiersze, bledne_kolumny;
bledne_bity(obrazki[numer], bledne_wiersze, bledne_kolumny);
if (bledne_wiersze.size() + bledne_kolumny.size() == 0) {
continue;
}
if (bledne_wiersze.size() > 1 || bledne_kolumny.size() > 1) {
continue;
}
// wiersz/kolumna 21 oznacza bit parzystości
int wiersz = bledne_wiersze.empty() ? 21 : bledne_wiersze[0] + 1;
int kolumna = bledne_kolumny.empty() ? 21 : bledne_kolumny[0] + 1;
std::println("{} {} {}", numer + 1, wiersz, kolumna);
}
}import java.nio.file.Files;
import java.nio.file.Path;
import java.util.ArrayList;
import java.util.List;
public class Zadanie {
// numery wierszy i kolumn, których bit parzystości się nie zgadza
static void bledneBity(String[] obrazek, List<Integer> bledneWiersze, List<Integer> bledneKolumny) {
for (int w = 0; w < 20; w++) {
int jedynki = 0;
for (int k = 0; k < 20; k++) {
jedynki += obrazek[w].charAt(k) - '0';
}
if (jedynki % 2 != obrazek[w].charAt(20) - '0') {
bledneWiersze.add(w);
}
}
for (int k = 0; k < 20; k++) {
int jedynki = 0;
for (int w = 0; w < 20; w++) {
jedynki += obrazek[w].charAt(k) - '0';
}
if (jedynki % 2 != obrazek[20].charAt(k) - '0') {
bledneKolumny.add(k);
}
}
}
public static void main(String[] args) throws Exception {
String[] wiersze = Files.readString(Path.of("dane_obrazki.txt")).strip().split("\\s+");
List<String[]> obrazki = new ArrayList<>();
for (int i = 0; i < wiersze.length; i += 21) {
String[] obrazek = new String[21];
System.arraycopy(wiersze, i, obrazek, 0, 21);
obrazki.add(obrazek);
}
for (int numer = 0; numer < obrazki.size(); numer++) {
List<Integer> bledneWiersze = new ArrayList<>();
List<Integer> bledneKolumny = new ArrayList<>();
bledneBity(obrazki.get(numer), bledneWiersze, bledneKolumny);
if (bledneWiersze.size() + bledneKolumny.size() == 0) {
continue;
}
if (bledneWiersze.size() > 1 || bledneKolumny.size() > 1) {
continue;
}
// wiersz/kolumna 21 oznacza bit parzystości
int wiersz = bledneWiersze.isEmpty() ? 21 : bledneWiersze.get(0) + 1;
int kolumna = bledneKolumny.isEmpty() ? 21 : bledneKolumny.get(0) + 1;
System.out.println((numer + 1) + " " + wiersz + " " + kolumna);
}
}
}Odpowiedź: (numer obrazka, wiersz, kolumna) (14, 1, 15), (19, 4, 20), (26, 21, 13), (29, 2, 8), (33, 15, 21), (115, 21, 14), (116, 21, 13), (129, 21, 14), (131, 10, 7), (143, 7, 15), (154, 7, 7), (161, 21, 17), (162, 21, 16), (187, 21, 18)
↑