Swapity Swapity Swap – Omówienie zadania z USACO, Amerykańskiej Olimpiady Informatycznej

Swapity Swapity Swap – Omówienie zadania z USACO, Amerykańskiej Olimpiady Informatycznej

Szczegółowe omówienie zadania Swapity Swapity Swap:

Link do powyższego omówienie zadania Swapity Swapity Swap:
https://youtu.be/nvA92I5nU0c?t=1480
Omówienie kodu zadania Swapity Swapity Swap: https://youtu.be/nvA92I5nU0c?t=4400

Link do treści zadania: http://www.usaco.org/index.php?page=viewproblem2&cpid=1014

Zadanie wymaga jedynie pomysłu – rozpatrzenia cykli.

Zadanie Swapity Swapity Swap 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 Swapity Swapity Swap, 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+10;

int krowy[MAXN];
bool sprawdzone[MAXN];
int wynik[MAXN];
int n, m, k;

void obroc(int l, int r)
{
	int dlugosc = (r - l + 1);
	for (int i = 0; i < dlugosc / 2; ++i) {
		swap(krowy[l + i], krowy[r - i]);
	}
}

int main()
{
	ifstream in("swap.in");
	ofstream out("swap.out");

	in >> n >> m >> k;
	for (int i = 1; i <= n; ++i)
		krowy[i] = i;
	for (int i = 0; i < m; ++i) {
		int l, r;
		in >> l >> r;
		obroc(l, r);
	}

	vector<int> cykl;
	for (int i = 1; i <= n; ++i) {
		if (sprawdzone[i] == false) {
			int aktIndeks = i;
			while (sprawdzone[aktIndeks] == false) {
				cykl.push_back(aktIndeks);
				sprawdzone[aktIndeks] = true;
				aktIndeks = krowy[aktIndeks];
			}

			int dlugoscCyklu = cykl.size();
			for (int j = 0; j < dlugoscCyklu; ++j) {
				int miejsceKrowy = cykl[j];
				int przesuniecie = k % dlugoscCyklu;
				int krowa = cykl[(j + przesuniecie) % dlugoscCyklu];
				wynik[miejsceKrowy] = krowa;
			}
			cykl.clear();
		}
	}

	for (int i = 1; i <= n; ++i) {
		out << wynik[i] << '\n';
	}

	return 0;
}
Kod C++ programu Swapity Swapity Swap, który jest omówiony w powyższym filmie i który otrzymuje 100%

 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz