Mutating DNA – Międzynarodowa Olimpiada Informatyczna – IOI – Omówienie zadania

Mutating DNA – Międzynarodowa Olimpiada Informatyczna – IOI – Omówienie zadania

Szczegółowe omówienie zadania Mutating DNA:

Link do powyższego omówienie zadania Mutating DNA: https://youtu.be/sed5wUYVHd0?t=1050
Omówienie kodu zadania Mutating DNA: https://youtu.be/sed5wUYVHd0?t=4800

Link do treści zadania Mutating DNA: https://mirror.ioi2021.sg/statement/dna-ISC.pdf
Wrzucanie rozwiązań zadania Mutating DNA: https://loj.ac/p/3526

Zadanie Mutating DNA jest zadaniem na pomysł i wykorzystanie sum prefiksowych.

Zadanie Mutating DNA  z IOI – International Olympiad in Informatics. Międzynarodowa Olimpiada Informatyczna, to najbardziej prestiżowe zawody informatyczna i algorytmiczne na świecie.
Posiada w swoim CV takiego zadania to wielka motywacja, wartość i potwierdzenie własnych umiejętności. Warto myśleć, kodować, walczyć z tym zadaniem.


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 przygotowujące do Olimpiady Informatycznej: https://oki.org.pl/harmonogram-zajec/

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


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


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

const int MAXN = 100*1000 + 7;

int slowo1[MAXN];
int slowo2[MAXN];
int pref[MAXN][3][3];

void init(string a, string b)
{
	int n = a.size();

	// zamiana znakow na liczby
	for (int i = 0; i < n; ++i) {
		if (a[i] == 'A')
			slowo1[i + 1] = 0;
		if (a[i] == 'T')
			slowo1[i + 1] = 1;
		if (a[i] == 'C')
			slowo1[i + 1] = 2;

		if (b[i] == 'A')
			slowo2[i + 1] = 0;
		if (b[i] == 'T')
			slowo2[i + 1] = 1;
		if (b[i] == 'C')
			slowo2[i + 1] = 2;
	}

	// liczenie sum prefiksowych
	for (int i = 1; i <= n; ++i) {

		for (int c1 = 0; c1 < 3; ++c1) {
			for (int c2 = 0; c2 < 3; ++c2) {

				// jezeli mamy c1 w slowo1 oraz c2 w slowo2
				if ((slowo1[i] == c1) && (slowo2[i] == c2))
					pref[i][c1][c2] = pref[i - 1][c1][c2] + 1;
				else
					pref[i][c1][c2] = pref[i - 1][c1][c2] + 0;
			}
		}

	}
}

int get_distance(int x, int y)
{
	x = x + 1;
	y = y + 1;

	int AT = pref[y][0][1] - pref[x - 1][0][1];
	int TA = pref[y][1][0] - pref[x - 1][1][0];

	int TC = pref[y][1][2] - pref[x - 1][1][2];
	int CT = pref[y][2][1] - pref[x - 1][2][1];

	int CA = pref[y][2][0] - pref[x - 1][2][0];
	int AC = pref[y][0][2] - pref[x - 1][0][2];

	// jezeli mamy tyle samo A, T, C w obu podslowach
	if ((AT + AC == TA + CA) && (TA + TC == AT + CT)) {
		int wynik = min(AT, TA) + min(TC, CT) + min(CA, AC);
		wynik += 2 * abs(AT - TA);
		return wynik;
	}
	else {
		return -1;
	}
}

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

// 	int n, q;
// 	cin >> n >> q;

// 	string a, b;
// 	cin >> a;
// 	cin >> b;

// 	init(a, b);

// 	for (int i = 1; i <= q; ++i) {
// 		int x, y;
// 		cin >> x >> y;
// 		cout << get_distance(x, y) << '\n';
// 	}

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

 


Analogiczny kod w języku Python programu Mutating DNA:

MAXN = 100*1000 + 7
pref = [[[0, 0, 0], [0, 0, 0], [0, 0, 0]] for i in range(MAXN)]

def init(a, b):
	slowo1 = [0 for i in range(MAXN)]
	slowo2 = [0 for i in range(MAXN)]

	n = len(a)

	# zamiana znakow na liczby
	for i in range(n):
		if (a[i] == 'A'):
			slowo1[i + 1] = 0
		if (a[i] == 'T'):
			slowo1[i + 1] = 1
		if (a[i] == 'C'):
			slowo1[i + 1] = 2

		if (b[i] == 'A'):
			slowo2[i + 1] = 0
		if (b[i] == 'T'):
			slowo2[i + 1] = 1
		if (b[i] == 'C'):
			slowo2[i + 1] = 2


	# liczenie sum prefiksowych
	for i in range(1, n+1):
		for c1 in range(0, 3):
			for c2 in range(0, 3):

				# jezeli mamy c1 w slowo1 oraz c2 w slowo2
				if ((slowo1[i] == c1) and (slowo2[i] == c2)):
					pref[i][c1][c2] = pref[i - 1][c1][c2] + 1
				else:
					pref[i][c1][c2] = pref[i - 1][c1][c2] + 0



def get_distance(x, y):
	x = x + 1
	y = y + 1

	AT = pref[y][0][1] - pref[x - 1][0][1]
	TA = pref[y][1][0] - pref[x - 1][1][0]

	TC = pref[y][1][2] - pref[x - 1][1][2]
	CT = pref[y][2][1] - pref[x - 1][2][1]

	CA = pref[y][2][0] - pref[x - 1][2][0]
	AC = pref[y][0][2] - pref[x - 1][0][2]

	# jezeli mamy tyle samo A, T, C w obu podslowach
	if ((AT + AC == TA + CA) and (TA + TC == AT + CT)):
		wynik = min(AT, TA) + min(TC, CT) + min(CA, AC)
		wynik += 2 * abs(AT - TA)
		return wynik
	else:
		return -1

if __name__ == '__main__':
	_ = input()

	n, q = input().split()

	a = input()
	b = input()

	init(a, b)

	print("7abbcd01962faf1b2655df14ab1e12")
	print("OK")

	for i in range(int(q)):
		x, y = input().split()
		print(get_distance(int(x), int(y)))

 

Nie dodano jeszcze komentarza, rozpocznij dyskusję pierwszy.

Dodaj komentarz