Szczegółowe omówienie zadania Breed Counting:

Link do powyższego omówienie zadania Breed Counting: https://youtu.be/_gLUezRAW0s?t=823
Omówienie kodu zadania Breed Counting: https://youtu.be/_gLUezRAW0s?t=3899
Link do treści zadania Breed Counting: http://www.usaco.org/index.php?page=viewproblem2&cpid=572

Zadanie Breed Counting jest ćwiczeniowym zadaniem na sumy prefiksowe – możliwość policzenia sumy liczb na dowolnym przedziale przy pomocy jednej operacji odejmowania (czas stały).

Zadanie Breed Counting  pochodzi z dywizji Silver Amerykańskiej Olimpiady Informatycznej USACO – odpowiednika naszej Olimpiady Informatycznej Juniorów: https://youtu.be/KI7un-HU_Hk?t=49
Daje piękny wpis do CV: https://youtu.be/P2sLFZBjOmM?t=7223
Dlaczego warto brać udział w Amerykańskiej Olimpiady Informatycznej USACO? https://youtu.be/K7fZfJ8nN6A?t=6848
Co to jest USACO? https://youtu.be/nvA92I5nU0c?t=1414

–
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 rozwiązaniami: https://oki.org.pl/lista-zadan-materialy.php
Samouczek – przygotowanie do Olimpiad: https://oki.org.pl/tutorial/

Bezpłatne zajęcia OKI: https://oki.org.pl/harmonogram-zajec/

Informacje o zajęciach: https://oki.org.pl/newsletter.php

Warto startować w Olimpiadzie Informatycznej!
https://youtu.be/K7fZfJ8nN6A?t=109

–
Kod C++ programu Breed Counting, który jest omówiony w powyższym filmie i który otrzymuje 100%

–

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100*1000 + 7;
int krowy1[MAXN];
int krowy2[MAXN];
int krowy3[MAXN];
int pref1[MAXN]; // sumy prefiksowe dla krow o id = 1
int pref2[MAXN]; // sumy prefiksowe dla krow o id = 2
int pref3[MAXN]; // sumy prefiksowe dla krow o id = 3
int main()
{
ifstream in("bcount.in");
ofstream out("bcount.out");
int n, q;
in >> n >> q;
for (int i = 1; i <= n; ++i) {
int idKrowy;
in >> idKrowy;
if (idKrowy == 1)
krowy1[i] = 1;
if (idKrowy == 2)
krowy2[i] = 1;
if (idKrowy == 3)
krowy3[i] = 1;
}
// obliczamy sumy prefiksowe dla kazdego id
for (int i = 1; i <= n; ++i) {
pref1[i] = pref1[i - 1] + krowy1[i];
pref2[i] = pref2[i - 1] + krowy2[i];
pref3[i] = pref3[i - 1] + krowy3[i];
}
// odpowiadamy na zapytania, kazde w czasie stalym
for (int i = 1; i <= q; ++i) {
int l, r;
in >> l >> r;
int ileKrowId1 = pref1[r] - pref1[l - 1];
int ileKrowId2 = pref2[r] - pref2[l - 1];
int ileKrowId3 = pref3[r] - pref3[l - 1];
out << ileKrowId1 << ' ' << ileKrowId2 << ' ' << ileKrowId3 << '\n';
}
return 0;
}

–
Kod Python programu Breed Counting, który otrzymuje 100%

MAXN = 100*1000 + 7
krowy1 = [0 for i in range(MAXN)]
krowy2 = [0 for i in range(MAXN)]
krowy3 = [0 for i in range(MAXN)]
pref1 = [0 for i in range(MAXN)] # sumy prefiksowe dla krow o id = 1
pref2 = [0 for i in range(MAXN)] # sumy prefiksowe dla krow o id = 2
pref3 = [0 for i in range(MAXN)] # sumy prefiksowe dla krow o id = 3
inFile = open("bcount.in", 'r')
outFile = open("bcount.out", "w")
n, q = inFile.readline().split()
n = int(n)
q = int(q)
for i in range(1, n+1):
idKrowy = int(inFile.readline())
if idKrowy == 1:
krowy1[i] = 1
if idKrowy == 2:
krowy2[i] = 1
if idKrowy == 3:
krowy3[i] = 1
# obliczamy sumy prefiksowe dla kazdego id
for i in range(1, n+1):
pref1[i] = pref1[i - 1] + krowy1[i]
pref2[i] = pref2[i - 1] + krowy2[i]
pref3[i] = pref3[i - 1] + krowy3[i]
# odpowiadamy na zapytania, kazde w czasie stalym
for i in range(1, q+1):
l, r = inFile.readline().split()
l = int(l)
r = int(r)
ileKrowId1 = pref1[r] - pref1[l - 1]
ileKrowId2 = pref2[r] - pref2[l - 1]
ileKrowId3 = pref3[r] - pref3[l - 1]
outFile.write(str(ileKrowId1) + ' ' + str(ileKrowId2) + ' ' + str(ileKrowId3) + '\n')