• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Problem osmiu hetmanow

Aruba Cloud VPS - 50% taniej przez 3 miesiące!
0 głosów
225 wizyt
pytanie zadane 14 maja 2023 w C i C++ przez polandonion Dyskutant (7,560 p.)

Witam, mialem do napisania taki programik, ktory obsluguje problem n-hetmanow. Sek w tym, ze na szkopule dzialaja mi wszystkie oprocz jednego testu, ze wzgledu na czas. Pomozecie?

Tutaj tresc: https://tinyurl.com/4xva5d9w

A tutaj kodzik:

#include <iostream>
#include <cmath>

using namespace std;

struct Pole {
	int x, y;
};

Pole het[15];
int n, ile = 0;

// ile_akt - ile aktualnie hetmanow znajduje
// sie na szachownicy w aktualnej rekurencji
void symuluj(int ile_akt) {
	for (int i = 0; i < n; i ++) {
		bool ok = 1;
		// ok - czy da sie dostawic hetmana na konkretnym polu,
		// tzn. polu o wspolrzednych: {i, ile_akt}
		for (int j = 0; j < ile_akt; j ++) {
			// sprawdzam, czy hetmany sa w tej samej kolumnie
			if (het[j].x == i)
				ok = 0;
			// i na przekatnej
			else if (abs(het[j].x - i) == abs(het[j].y - ile_akt))
				ok = 0;
		}

		// jezeli ustawilem juz na szachownicy n hetmanow
		if (ok == 1 and ile_akt == n - 1) {
			// zwiekszam ilosc mozliwosci
			ile ++;
			// i wychodze z aktualnej rekurencji
			return;
		}
		else if (ok == 1) {
			het[ile_akt] = {i, ile_akt};
			symuluj(ile_akt + 1);
		}
	}
}

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

	cin >> n;

	symuluj(0);

	cout << ile;
}

 

komentarz 14 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Korzystasz z backtrackingu?
komentarz 17 maja 2023 przez jankustosz1 Nałogowiec (36,720 p.)

@polandonion, Wygląda dobrze, zwięźle i jasno. Zmień tylko inta na long longa bo może być tego 15^15 minus złę kombinacje

komentarz 17 maja 2023 przez polandonion Dyskutant (7,560 p.)
pasjonat_algorytmiki, chyba nie
komentarz 17 maja 2023 przez polandonion Dyskutant (7,560 p.)

@jankustosz1, dodalem long longa i te same rezultaty

komentarz 17 maja 2023 przez jankustosz1 Nałogowiec (36,720 p.)

@polandonion, Korzystasz z backtrackingu, tylko nie wiesz że to się tak nazywa :)

 

Nie wiem gdzie jest błąd, kod wygląda dobrze

1 odpowiedź

0 głosów
odpowiedź 17 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Jeden Ci nie działa ze względu na czas z prostego powodu, jak odpalisz sobie swój program dla N = 14, to będzie się robił pewnie około 20s a max limit czasu na zadanie to 10s.
komentarz 17 maja 2023 przez polandonion Dyskutant (7,560 p.)
a wiesz moze jak to przyspieszyc?

Podobne pytania

0 głosów
1 odpowiedź 1,202 wizyt
pytanie zadane 4 kwietnia 2019 w C i C++ przez Alan Kruszyński Obywatel (1,410 p.)
0 głosów
1 odpowiedź 359 wizyt
pytanie zadane 25 kwietnia 2019 w C i C++ przez Alan Kruszyński Obywatel (1,410 p.)
0 głosów
1 odpowiedź 215 wizyt

93,096 zapytań

142,059 odpowiedzi

321,513 komentarzy

62,441 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj

Wprowadzenie do ITsec, tom 1 Wprowadzenie do ITsec, tom 2

Można już zamawiać dwa tomy książek o ITsec pt. "Wprowadzenie do bezpieczeństwa IT" - mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy aż 15% zniżki! Dziękujemy ekipie Sekuraka za fajny rabat dla naszej Społeczności!

...