Informatika feladatmegoldó verseny Kiss Elemér Szakkollégium 2013. február 19. Dr. Kovács Lehel István
Állás
Összesítő
Új feladat 5. forduló
4. Feladat • A prímszámok generálása ősi matematikai feladat. • Írjunk minél gyorsabb algoritmust, amely 350 000 000-ig legenerálja a prímszámokat!
Be / Ki • BE: • 350 000 000 • KI: • Állomány prímszámokkal • Generálási idő
Határidő • 2013. március 17. 24 óra • Beküldeni (név, szak, évfolyam, kód): •
[email protected]
Megoldások
Feladatok • 1. feladat – Gyors darabolás
• 2. feladat – Szomszédok
• 3. feladat – Huszárok
I.
1. feladat • Adjunk minél gyorsabb algoritmust (C, C++ programot) a következő feladat megoldására:
• Az nyer, akinek a programja a leggyorsabb (mérjük a futási időt)!
Feladat • Adott egy A hosszúságú rúd. • Hányféleképpen vághatjuk fel A1, A2, ..., An hosszúságú darabokra a rudat, úgy hogy mindegyik darabból legfennebb egyet használunk.
Példa • • • • • • • • • •
A = 33 A1 = 1 A2 = 4 A3 = 7 A4 = 8 A5 = 9 A6 = 10 A7 = 14 A8 = 15 A9 = 18
Megoldás • Backtracking • Valami jobb...
A matematikai modell • SDE – Speciális Diofantoszi Egyenlet:
• a1x1 + a2x2 + … + anxn = a • ahol: – xi ∈ {0, 1}
Az egyenlet megoldása • Aritmetikai módszer • Geometriai módszer • Algoritmus – Backtracking – Linearizálás – Maszkolással
Backtracking procedure back(i: integer; len: integer; eq: TIntArray; var bin: TIntArray; res: integer; var sol: TSolution; var solnr: integer); begin if i = len-1 then begin if Sum(len, eq, bin) = res then Solution(len, bin, sol, solnr) end else begin bin[i+1] := 0; back(i+1, len, eq, bin, res, sol, solnr); bin[i+1] := 1; back(i+1, len, eq, bin, res, sol, solnr); end; end;
Linearizálás • n a feladat rendje • n-hosszúságú bináris regiszter:
0
0
0
0
0
…
0
0
1
2
3
4
…
n–1
∑
1
1
1
1
1
…
1
0
1
2
3
4
…
n–1
Maszkolás • Ugyanaz, csak egy regiszterben megvalósítható eltolás <<, >> operátorok segítségével.
II.
2. feladat • Adott n és m, valamint k (1<=k<=8). A következő elvek betartásával rendezzük be egy nxm-es mátrixba a 2, 4, 8, 16, ..., 2k számokat úgy, hogy a mátrix elemeinek összege maximális legyen: • - a 2-ot bárhova beírhatjuk • - a 4-nek kell hogy legyen legalább egy 2-es szomszédja • - a 8-nak kell hogy legyen legalább egy 2-es és egy 4-es szomszédja • - a 16-nak kell hogy legyen legalább egy 2-es, egy 4-es, egy 8-as szomszédja • - ... • - 2k-nak kell hogy legyen legalább egy 2-es, egy 4-es, egy 8-as, ..., egy 2k-1-es szomszédja
Be / Ki • Be: –n –m –k
• Ki: – mátrix – összeg
Szomszéd
X X X
X o X
X X X
Például • n=3 • m=3 • k=3
8 4 8 8 2 8 8 4 8
III.
3.1. Feladat • Egy 8×8-as sakktáblára elhelyezünk egy huszárt. A huszár „lóugrásban” lép, azaz vagy vízszintes irányban lép egyet és függőlegesen kettőt, vagy pedig fordítva. • Készíts programot, amely egy adott pozícióra elhelyezett huszár esetén megadja, hogy a huszár mely pozíciókra minimum hány lépésben juthat el! •
(Forrás: NEMES TIHAMÉR SZÁMÍTÁSTECHNIKA VERSENY 2009)
Be / Ki • A BE.IN szöveges állomány első sorában a tesztesetek száma található, majd mindegyik teszteset egyetlen sorában a huszár sorindexe (1≤SOR≤8) és oszlopindexe (1≤OSZLOP≤8) van, egy szóközzel elválasztva. • A képernyőre mindegyik tesztesetre 8 sort kell írni, mindegyikben 8 szám legyen egy-egy szóközzel elválasztva! Az i-edik sor j-edik oszlopában az a lépésszám legyen, ahány lépésben az adott mező elérhető a kiinduló mezőről! A teszteseteket egy üres sorral kell elválasztani.
Példa Be: 1 32
Ki: 1 2 2 3 3 0 2 3 1 2 2 3 3 2 4 3
1 2 3 2 1 2 3 4
4 1 2 1 4 3 2 3
3 2 3 2 3 2 3 4
2 3 2 3 2 3 4 3
3 4 3 4 3 4 3 4
4 3 4 3 4 3 4 5
Adatok • • • •
#include
#include #include using namespace std;
• • • • • •
struct node { int x; int y; node(int xx, int yy){x = xx; y = yy;}; };
• • •
int hx, hy; int cache[10][10]; int inq[10][10];
• •
const int dx[] = { 2, 2, 1, 1, -2, -2, -1, -1}; const int dy[] = { 1, -1, 2, -2, 1, -1, 2, -2};
Főprogram • int main() • { • freopen("sakk.be","r",stdin); • freopen("sakk.ki","w",stdout); • memset(cache, -1, sizeof(cache)); • memset(inq, 0, sizeof(inq)); • read(); • solve(hx, hy); • print(); • return 0; • }
read • void read() • { • scanf("%d%d", &hx, &hy); • } • inline int good(int x, int y) • { • if (x > 0 && x < 9 && y > 0 && y < 9) return 1; • return 0; • }
print • void print() • { • int i, j; • for (i = 1; i < 9; ++i) • { • for (j = 1; j < 9; ++j) • printf("%d ", cache[i][j]); • printf("\n"); • } • }
solve • void solve(int hx, int hy) • { • queue<node> q; • q.push(node(hx,hy)); • cache[hx][hy] = 0; • while (!q.empty()) • { • int x = q.front().x; • int y = q.front().y; • q.pop(); • inq[x][y] = 0; • int k, newx, newy;
solve • • • • • • • • • • • • • • • •
for (k = 0; k < 8; ++k) { newx = x + dx[k]; newy = y + dy[k]; if (!good(newx, newy)) continue; if (cache[newx][newy] == -1 || (cache[newx][newy] > cache[x][y] + 1)) { cache[newx][newy] = cache[x][y] + 1; if (!inq[newx][newy]) { inq[newx][newy] = 1; q.push(node(newx,newy)); } } } } }
3.2. Feladat • Egy 8×8-as sakktáblára elhelyezünk egy huszárt, amellyel két játékos felváltva lép. • Aki nem tud olyan mezőre lépni, ahol még nem járt a huszár, az veszít. • Kinek van nyerő stratégiája? • Szimuláljuk le a játékot!
Be / Ki • BE: • A huszár kezdeti pozíciója. • A kezdő fél (ember / szamítógép, ember 1 / ember 2) • KI: • A kétszemélyes játék lejátszása
