Pionki – omówienie zadania z finału Olimpiady Informatycznej Juniorów

Szczegółowe omówienie zadania Pionki:

Link do powyższego omówienia zadania Pionki:
https://youtu.be/HxbnveQd69I

Link do treści zadania Pionki:
https://szkopul.edu.pl/problemset/problem/ZhrqkG9W7TYF2VPrIuR1Ufry/site

Zadanie pochodzi z finałowego etapu XV Olimpiady Informatycznej Juniorów.
https://szkopul.edu.pl/task_archive/oig/

Warto startować w Olimpiadzie Informatycznej!
https://youtu.be/1qhkkV6YtE8?t=11

Zadanie wymaga jedynie prostego pomysłu:
Oddzielnie zbieramy pionki po X i Y. Zbieramy do kolumny gdzie jest najwięcej pionków. Analogicznie do rzędu z największą liczbą pionków.
Zadanie pochodzi z finału Olimpiady Informatycznej Juniorów choć wymaga jedynie programowania i powyższej prostej obserwacji.

Zadanie omawia Karol Pokorski, jeden z najlepszych nauczycieli algorytmiki, wychowawca wielu zwycięzców i medalistów Olimpiad Informatycznych, prowadzący zajęcia koła informatycznego we Wrocławiu oraz w internecie:
https://solve.edu.pl/~sparingi/


Jak się uczyć na podstawie tego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019
Pamiętaj by zajrzeć max 1 raz – wtedy się rozwijasz:
https://youtu.be/pkLXuuOe_qA?t=3625


Lista zadań z Olimpiad i konkursów informatycznych z podziałem na kategorie i rozwiązaniami:
https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad i konkursów informatycznych:
https://oki.org.pl/tutorial/

Kod C++ który otrzymuje 100%

#include <iostroeam>   
using namespace std;

const int MAX_RZOZMIAR = 1e6 + 7;

int ile_pionkow_w_kolumnie[MAX_RZOZMIAR];
int ile_pionkow_w_wierszu[MAX_RZOZMIAR];

int main() {
 ios_base::sync_with_stdio(0);
 cin.tie(0);
 cout.tie(0);
    
 int x, y, rozmiar_po_x, rozmiar_po_y;
 int ile_pionkow;
 int max_ilosc_pionkow_w_kolumnie, max_ilosc_pionkow_w_wierszu;
 char znak;

 cin >> rozmiar_po_y >> rozmiar_po_x;

 ile_pionkow = 0;
 max_ilosc_pionkow_w_kolumnie =  max_ilosc_pionkow_w_wierszu = 0;
 for (y = 1; y <= rozmiar_po_y; y++) {
    for (x = 1; x <= rozmiar_po_x; x++) {
       cin >> znak;
       if (znak == '#') {
          ++ile_pionkow;
          ++ile_pionkow_w_wierszu[y];
          ++ile_pionkow_w_kolumnie[x];
          if (ile_pionkow_w_wierszu[y] > max_ilosc_pionkow_w_wierszu)
             max_ilosc_pionkow_w_wierszu = ile_pionkow_w_wierszu[y];
          if (ile_pionkow_w_kolumnie[x] > max_ilosc_pionkow_w_kolumnie)
             max_ilosc_pionkow_w_kolumnie = ile_pionkow_w_kolumnie[x];
            }
        }
    }

 cout << 2 * ile_pionkow - max_ilosc_pionkow_w_wierszu - max_ilosc_pionkow_w_kolumnie << "\n";

 return 0;
}

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz