Ciasta – Finał Olimpiady Informatycznej Gimnazjalistów – Omówienie zadania

Ciasta – Finał Olimpiady Informatycznej Gimnazjalistów – Omówienie zadania

Szczegółowe omówienie zadania Ciasta:

Link do powyższego omówienia zadania Ciasta:
https://youtu.be/Rz17jmhgoMM?t=1031

Omówienie kodu zadania Ciasta:
https://youtu.be/Rz17jmhgoMM?t=2748

Link do treści zadania Ciasta oraz możliwości umieszczania rozwiązań:
https://szkopul.edu.pl/problemset/problem/ciasta/site/


Rozwiązanie zadania Ciasta wymaga znajomości:
1.
Znajdowania liczb pierwszych na przedziale – Sito Eratostenesa
https://youtu.be/Rz17jmhgoMM?t=2371
Wytłumaczenie Sita Eratostenesa – quiz:
https://youtu.be/Rz17jmhgoMM?t=6176
2.
Własności liczb pierwszych – zauważenia, że maksymalna liczba ciast składa się z liczb pierwszych lub ich potęg:
https://youtu.be/Rz17jmhgoMM?t=3446
3.
Operacji na resztach -> modulo
https://youtu.be/Rz17jmhgoMM?t=3137


Zadanie Ciasta pochodzi z finału 11 Olimpiady Informatycznej Gimnazjalistów z zawodów drużynowych.

Zadanie Omawia Tomek Kwiatkowski – finalista Olimpiady Informatycznej:
https://youtu.be/2ZL03PfmQiI?t=2175


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


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


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

const int MAXN = 1000*1000 + 7;
const int MOD = 1e9 + 33;

bool zlozona[MAXN];

// Sito Eratostenesa
void Sito(int n)
{
	for (int i = 2; i * i <= n; i++) {
		// jezeli wykreslona wczesniej, nic nie wykreslamy
		// idziemy do kolejnego i
		if (zlozona[i])
			continue;

		// wykreslamy wielokrotnosci i
		for (int j = i*i; j <= n; j += i)
			zlozona[j] = true;
	}
}

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

	int n; // liczba ciast
	cin >> n;

	Sito(n);

	int wynik = 1;
	for (int akt = 2; akt <= n; akt++) {
		if (zlozona[akt])
			continue;
		// tutaj akt jest pierwsze

		// liczymy ile jest liczb postaci akt^k <= n
		int ile = 0;
		long long iloczyn = 1;
		while (iloczyn * akt <= n) {
			iloczyn *= akt;
			ile++;
		}

		wynik = ((long long)wynik * ile) % MOD;
	}

	cout << wynik << '\n';
	return 0;
}
Kod C++ programu Ciasta, który jest omówiony w powyższym filmie i który otrzymuje 100%

 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz