Podsumowanie OKI#20

Podsumowanie OKI#20

OKI 20 – pokonaliśmy problem z rozmowy kwalifikacyjnej Facebooka!
https://tiny.pl/t6nm6

Jędrzej – laureat poprzednich Olimpiad – podzielił się swoim doświadczeniem, co robić by uzyskać dobry wynik w Olimpiadzie:
https://tiny.pl/t6ng9

Powiedzieliśmy sobie też jak się uczyć!
Jak wykorzystać zadania z platformy OKI, które są omówione, dla których mamy kod:
https://youtu.be/ufvS-VfPDLs?t=6515
Zadania z Olimpijksiego Koła Informatycznego które mają pełne omówienie i kod:

Omówienia zadań

———————-
Podstawą naszych zajęć było zadanie Depesza:
https://youtu.be/ufvS-VfPDLs?t=1190
które rozwiązaliśmy korzystając z PROGRAMOWANIA DYNAMICZNEGO:
https://youtu.be/ufvS-VfPDLs?t=1472
a które jest problemem z rozmowy kwalifikacyjnej Facebook-a:
https://tiny.pl/t6nm6

Programowanie dynamiczne przypomnieliśmy sobie w naszym początkowym quizie:
https://youtu.be/ufvS-VfPDLs?t=326

———————-
Jędrzej – laureat poprzednich Olimpiad:
https://youtu.be/ufvS-VfPDLs?t=4737
omówił zadanie Photoshoot z Amerykańskiej Olimpiady Informatycznej, z Pracy Domowej:
https://youtu.be/ufvS-VfPDLs?t=4828
Mieliśmy również krótki wywiad z Jędrzejem – czym się zajmuje, czy wiedza z Olimpiad mu się przydaje, jak przygotowywać się do Olimpiady:
https://youtu.be/ufvS-VfPDLs?t=6279

———-
Powiedzieliśmy sobie na ile sposobów można wybrać 2 klocki z 4:
https://youtu.be/ufvS-VfPDLs?t=7044
I że to jest gigantyczny problem dla komputerów:
https://youtu.be/ufvS-VfPDLs?t=7292
który to problem znowu potrzebuje naszej inteligencji:
https://youtu.be/ufvS-VfPDLs?t=7359

———————-
Sukces to… ciężka praca!
https://youtu.be/ufvS-VfPDLs?t=6640
Robimy to co… kochamy:
https://youtu.be/ufvS-VfPDLs?t=6651

Za tydzień USACO…
https://tiny.pl/t6ntd
Daniel Olkowski

——————–
Omówienie zadania Depesza:
https://youtu.be/ufvS-VfPDLs?t=1190
Link do zadania Depesza:
https://szkopul.edu.pl/problemset/problem/depesza/site

Kod C++ programu Depesza, który otrzymuje 100%

#include <bits/stdc++.h>
using namespace std;

const int MAX_DLUGOSC = 2e6+7;
const int MODULO_WAR = 1e9+7;

string wiadomosc;
int ile_mozliwosci[MAX_DLUGOSC];

bool Czy_2_OstatnieTworzaLitere(int i) {
if (wiadomosc[i-1] == ‘1’)
return true;
if ( (wiadomosc[i-1] == ‘2’) && (wiadomosc[i] <= ‘6’) )
return true;
return false;
}

bool Czy_1_OstatniaTworzyLitere(int i) {
if (wiadomosc[i] == ‘0’)
return false;
return true;
}

int main() {
int akt_wynik;
int i;

cin >> wiadomosc;

wiadomosc = ” ” + wiadomosc;

ile_mozliwosci[0] = 0;
ile_mozliwosci[1] = 1;
for (i=2; i<wiadomosc.length(); ++i) {
akt_wynik = 0;
if ( Czy_2_OstatnieTworzaLitere(i) == true ) {
akt_wynik = ile_mozliwosci[i-2];
}
if ( Czy_1_OstatniaTworzyLitere(i) == true ) {
akt_wynik += ile_mozliwosci[i-1];
akt_wynik %= MODULO_WAR;
}
if (akt_wynik == 0) {
cout << “0\n”;
return 0;
}
ile_mozliwosci[i] = akt_wynik;
}
cout << ile_mozliwosci[ (wiadomosc.length()-1 ] << “\n”;

return 0;
}

——————–
Omówienie zadania Photoshoot z Amerykańskiej Olimpiady Informatycznej USACO:
https://youtu.be/ufvS-VfPDLs?t=4828


Link do zadania:
http://usaco.org/index.php?page=viewproblem2&cpid=988

Zadanie wymaga jedynie pomysłu i świetnie przygotowuje do Olimpiady Informatycznej Juniorów-

Zadanie omawia Jędrzej, laureat poprzednich edycji Olimpiady Informatycznej:https://youtu.be/ufvS-VfPDLs?t=4737który w filmie dzieli się również swoim doświadczeniem:https://youtu.be/ufvS-VfPDLs?t=6279
——-
Poniżej kod wzorcowy do zadania użyty przez Jędrzeja

#include<bits/stdc++.h>
using namespace std;

const int N=1010;
int TablicaSum[N];
int TablicaWynikow[N];
int TablicaWystapien[N];

int Sprawdz(int n){
int aktu;
for(int i=1; i<=n; i++) TablicaWystapien[i]=0;
TablicaWystapien[ TablicaWynikow[1] ]=1;
for(int i=2; i<=n; i++){
TablicaWynikow[i]=TablicaSum[i-1]-TablicaWynikow[i-1];
aktu=TablicaWynikow[i];
if( TablicaWystapien[ aktu ]==1 || aktu>n || aktu<1) return 0;
TablicaWystapien[ aktu ]=1;
}
return 1;
}

int main (){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
freopen(“photo.in”, “r”, stdin);
freopen(“photo.out”, “w”, stdout);
int n;
cin>>n;
for(int i=1; i<n; i++) cin>>TablicaSum[i];
for(int i=1; i<=n; i++){
TablicaWynikow[1]=i;
if( Sprawdz(n) ) break;
}
for(int i=1; i<n; i++)
cout << TablicaWynikow[i] << ” “;
cout << TablicaWynikow[n];
cout << “\n”;
return 0;
}

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz