From a52f462140e3a38fb0f08d5ea74bdafe039bb428 Mon Sep 17 00:00:00 2001 From: Franciszek Malinka Date: Wed, 17 Mar 2021 15:44:51 +0100 Subject: Zmiana struktury folderu pstwo, dodane jakies listy --- Semestr 4/aisd/Lista 1/lista1.pdf | Bin 0 -> 103432 bytes Semestr 4/aisd/Lista 2/Lista 2.pdf | Bin 0 -> 2301798 bytes Semestr 4/aisd/Lista 2/lista2.pdf | Bin 0 -> 128638 bytes .../Notatka 5 - divide and conquer cd.pdf" | Bin 0 -> 146884 bytes .../Notatka 6 - Programowanie Dynamiczne.pdf" | Bin 0 -> 213697 bytes Semestr 4/aisd/themis/AISDDEBIUT21.cpp | 24 +++++++++ Semestr 4/aisd/themis/AISDPOTEGOWANIE.cpp | 29 +++++++++++ Semestr 4/aisd/themis/BELLMAN.cpp | 55 +++++++++++++++++++ Semestr 4/aisd/themis/FIB.cpp | 58 +++++++++++++++++++++ 9 files changed, 166 insertions(+) create mode 100644 Semestr 4/aisd/Lista 1/lista1.pdf create mode 100644 Semestr 4/aisd/Lista 2/Lista 2.pdf create mode 100644 Semestr 4/aisd/Lista 2/lista2.pdf create mode 100644 "Semestr 4/aisd/Wyk\305\202ady/Notatka 5 - divide and conquer cd.pdf" create mode 100644 "Semestr 4/aisd/Wyk\305\202ady/Notatka 6 - Programowanie Dynamiczne.pdf" create mode 100644 Semestr 4/aisd/themis/AISDDEBIUT21.cpp create mode 100644 Semestr 4/aisd/themis/AISDPOTEGOWANIE.cpp create mode 100644 Semestr 4/aisd/themis/BELLMAN.cpp create mode 100644 Semestr 4/aisd/themis/FIB.cpp (limited to 'Semestr 4/aisd') diff --git a/Semestr 4/aisd/Lista 1/lista1.pdf b/Semestr 4/aisd/Lista 1/lista1.pdf new file mode 100644 index 0000000..a7dc065 Binary files /dev/null and b/Semestr 4/aisd/Lista 1/lista1.pdf differ diff --git a/Semestr 4/aisd/Lista 2/Lista 2.pdf b/Semestr 4/aisd/Lista 2/Lista 2.pdf new file mode 100644 index 0000000..ccf83b7 Binary files /dev/null and b/Semestr 4/aisd/Lista 2/Lista 2.pdf differ diff --git a/Semestr 4/aisd/Lista 2/lista2.pdf b/Semestr 4/aisd/Lista 2/lista2.pdf new file mode 100644 index 0000000..2d8937f Binary files /dev/null and b/Semestr 4/aisd/Lista 2/lista2.pdf differ diff --git "a/Semestr 4/aisd/Wyk\305\202ady/Notatka 5 - divide and conquer cd.pdf" "b/Semestr 4/aisd/Wyk\305\202ady/Notatka 5 - divide and conquer cd.pdf" new file mode 100644 index 0000000..48fc8e4 Binary files /dev/null and "b/Semestr 4/aisd/Wyk\305\202ady/Notatka 5 - divide and conquer cd.pdf" differ diff --git "a/Semestr 4/aisd/Wyk\305\202ady/Notatka 6 - Programowanie Dynamiczne.pdf" "b/Semestr 4/aisd/Wyk\305\202ady/Notatka 6 - Programowanie Dynamiczne.pdf" new file mode 100644 index 0000000..d8b61ce Binary files /dev/null and "b/Semestr 4/aisd/Wyk\305\202ady/Notatka 6 - Programowanie Dynamiczne.pdf" differ diff --git a/Semestr 4/aisd/themis/AISDDEBIUT21.cpp b/Semestr 4/aisd/themis/AISDDEBIUT21.cpp new file mode 100644 index 0000000..3666d69 --- /dev/null +++ b/Semestr 4/aisd/themis/AISDDEBIUT21.cpp @@ -0,0 +1,24 @@ +/* + * Autor: Franciszek Malinka + * Numer indeksu: 316093 + * Prowadzący: WJA + */ + +#include +using namespace std; + +int main() +{ + ios_base::sync_with_stdio(false); + cin.tie(); + int a, b; + cin >> a >> b; + for (int i = a; i <= b; i++) + { + if (i % 2021 == 0) + { + cout << i << " "; + } + } + cout << "\n"; +} \ No newline at end of file diff --git a/Semestr 4/aisd/themis/AISDPOTEGOWANIE.cpp b/Semestr 4/aisd/themis/AISDPOTEGOWANIE.cpp new file mode 100644 index 0000000..c1b76fe --- /dev/null +++ b/Semestr 4/aisd/themis/AISDPOTEGOWANIE.cpp @@ -0,0 +1,29 @@ +#include +using namespace std; + +int fast_pow(int a, int b, int m) +{ + if (b == 0) + { + return 1; + } + long long p = fast_pow(a, b / 2, m); + p = (p * p) % m; + if (b % 2 == 0) + return (int)p; + return (p * (long long)a) % m; +} + +int main() +{ + ios_base::sync_with_stdio(false); + cin.tie(); + int t; + cin >> t; + while (t--) + { + int a, b, m; + cin >> a >> b >> m; + cout << fast_pow(a, b, m) << "\n"; + } +} \ No newline at end of file diff --git a/Semestr 4/aisd/themis/BELLMAN.cpp b/Semestr 4/aisd/themis/BELLMAN.cpp new file mode 100644 index 0000000..5a65096 --- /dev/null +++ b/Semestr 4/aisd/themis/BELLMAN.cpp @@ -0,0 +1,55 @@ +#include +using namespace std; + +const int N = 503; +int dist[N]; +vector>> edges; +int main() +{ + ios_base::sync_with_stdio(false); + cin.tie(); + int n, m, s; + cin >> n >> m >> s; + for (int i = 0; i <= n; i++) + { + dist[i] = 2e9; + } + dist[s] = 0; + for (int i = 0; i < m; i++) + { + int u, v, w; + cin >> u >> v >> w; + edges.push_back({w, {u, v}}); + // edges.push_back({w, {v, u}}); + } + + for (int i = 0; i < n + 1; i++) + { + for (auto e : edges) + { + int w = e.first; + int u = e.second.first; + int v = e.second.second; + if (dist[v] > dist[u] + w) + { + dist[v] = dist[u] + w; + } + } + } + for (auto e : edges) + { + int w = e.first; + int u = e.second.first; + int v = e.second.second; + if (dist[v] > dist[u] + w) + { + cout << "NIE\n"; + return 0; + } + } + for (int i = 0; i < n; i++) + { + if (i != s && dist[i] < 1e9) + cout << i << " " << dist[i] << "\n"; + } +} \ No newline at end of file diff --git a/Semestr 4/aisd/themis/FIB.cpp b/Semestr 4/aisd/themis/FIB.cpp new file mode 100644 index 0000000..dd38c5c --- /dev/null +++ b/Semestr 4/aisd/themis/FIB.cpp @@ -0,0 +1,58 @@ +#include +using namespace std; +typedef long long ll; + +class matrix +{ +public: + ll a, b, c, d; + static ll m; + + matrix(ll _a = 0, ll _b = 0, ll _c = 0, ll _d = 0) : a(_a), b(_b), c(_c), d(_d) {} + + matrix operator*(const matrix &M) const + { + matrix res; + res.a = (a * M.a + b * M.c) % m; + res.b = (a * M.b + b * M.d) % m; + res.c = (c * M.a + d * M.c) % m; + res.d = (c * M.b + d * M.d) % m; + return res; + } +}; + +ll matrix::m = 1; + +matrix fast_pow(matrix M, int w) +{ + matrix res(1, 0, 0, 1); + while (w) + { + if (w % 2 == 1) + res = res * M; + M = M * M; + w >>= 1; + } + return res; +} + +void solve() +{ + int n, m; + cin >> n >> m; + matrix M(0, 1, 1, 1); + matrix::m = m; + cout << fast_pow(M, n + 1).a << "\n"; +} + +int main() +{ + ios_base::sync_with_stdio(false); + cin.tie(); + int t; + cin >> t; + while (t--) + { + solve(); + } +} \ No newline at end of file -- cgit v1.2.3