GCD on Blackboard – Omówienie zadania – Algorytm Euklidesa

GCD on Blackboard – Omówienie zadania – Algorytm Euklidesa

Szczegółowe omówienie zadania GCD on Blackboard:

Link do powyższego omówienia zadania GCD on Blackboard: https://youtu.be/evtnTwRKtkE?t=986
Złożoność rozwiązania / kroki rozwiązania: https://youtu.be/evtnTwRKtkE?t=4331
Omówienie kodu zadania GCD on Blackboard: https://youtu.be/evtnTwRKtkE?t=4557

Link do treści zadania GCD on Blackboard:
https://atcoder.jp/contests/abc125/tasks/abc125_c

Zadanie GCD on Blackboard wymaga obliczania NWD – Największego Wspólnego Dzielnika: https://youtu.be/evtnTwRKtkE?t=725
Jak liczyć NWD – Klasyczny algorytm Euklidesa: https://youtu.be/evtnTwRKtkE?t=1330
Klasyczny algorytm Euklidesa jest wolny! https://youtu.be/evtnTwRKtkE?t=1928
Szybki algorytm Euklidesa – długie wyjaśnienie: https://youtu.be/evtnTwRKtkE?t=1929
Szybki algorytm Euklidesa – krótkie wyjaśnienie: https://youtu.be/evtnTwRKtkE?t=2405
Złożoność szybkiego algorytmu Euklidesa: https://youtu.be/evtnTwRKtkE?t=2598
Kod szybkiego algorytmu Euklidesa: https://youtu.be/evtnTwRKtkE?t=4581
Warto poćwiczyć NWD: https://youtu.be/evtnTwRKtkE?t=5521

Jak policzyć NWD wielu liczb? https://youtu.be/evtnTwRKtkE?t=2915
Czy złożoność O(2n) jest różna od O(n)? https://youtu.be/evtnTwRKtkE?t=4947
Zadanie z AtCoder! https://youtu.be/evtnTwRKtkE?t=5829


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/
Zajęcia: : https://oki.org.pl/harmonogram-zajec/

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


Kod C++ programu "GCD on Blackboard", który jest omówiony w powyższym filmie i który otrzymuje 100%


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

const int MAXN = 1e5 + 7;

int tab[MAXN];
int prefNWD[MAXN];
int sufNWD[MAXN];

int NWD(int a, int b)
{
	while (b != 0) {
		int tmp = b;
		b = a % b;
		a = tmp;
	}
	return a;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i)
		cin >> tab[i];

	for (int i = 1; i <= n; ++i)
		prefNWD[i] = NWD(prefNWD[i - 1], tab[i]);

	for (int i = n; i >= 1; --i)
		sufNWD[i] = NWD(sufNWD[i + 1], tab[i]);

	int wynik = 0;
	for (int i = 1; i <= n; ++i) {
		wynik = max(NWD(prefNWD[i - 1], sufNWD[i + 1]), wynik);
	}
	cout << wynik << '\n';
	return 0;
}
Kod C++ programu "GCD on Blackboard", który jest omówiony w powyższym filmie i który otrzymuje 100%

 


Kod Python programu GCD on Blackboard, który otrzymuje 100%:

def NWD(a, b):
	while (b != 0):
		tmp = b
		b = a % b
		a = tmp
	return a

n = int(input())
tab = list(map(int, input().split()))

prefNWD = [0] * (n + 2)
for i in range(1, n+1):
	prefNWD[i] = NWD(prefNWD[i - 1], tab[i - 1])

sufNWD = [0] * (n + 2)
for i in range(n, 0, -1):
	sufNWD[i] = NWD(sufNWD[i + 1], tab[i - 1])

wynik = 0
for i in range(1, n+1):
	wynik = max(NWD(prefNWD[i - 1], sufNWD[i + 1]), wynik)
print(wynik)

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz