PMitura

Omezené hanojské veže

Na vstupu dostanete zadané přirozené číslo N. Uvažujme klasickou úlohu Hanojských věží (viz. taky přednáška nebo wikipedie), kde máte tři věže, n kotoučů s různými poloměry, které jsou na záčátku uložené na první věži od největšího (dolu) po nejmenší (nahoře) a máte je přenést na druhou věž ve stejném pořadí, přičemž:

• můžete přenášet pouze jeden kotouč najednou
• smíte pouze přemístit kotouč z vrcholu jedné věže na vrchol druhé
• nemůžete položit větší kotouč na menší

Vašim úkolem je napsat program, který vypíše postupnost přenosů kotoučů pro omezenou variantu téhle úlohy. Mějme věže označené jako A, B, C, kotouče jsou iniciálně navlečeny na věži A a chcete je přemístit na věž B s využitím věže C jako odkladiště. V omezené variantě nesmíte přemísťovat kotouče přímo z věže A na věž B, nebo z věže B přímo na věž A.

PMitura

Řazení řetězců (1b)

Na vstupu dostanete přirozené číslo n a za ním n řetězců. Každý řetězec bude uvedený na samostatné řádce a bude obsahovat jenom malé a velké písmena latinské abecedy.

Vaší úlohou je vypsat dané řetězce vzestupně, v lexikografickém pořadí. Bereme, že velká písmena jsou v pořadí za jejich malými protějšky a pokud je jeden řetězec předponou druhého, tak ten první je menší.

Příklad vstupu:

9

PMitura

Násobení matic (1b)

Na vstupu dostanete zadaný rozměr n < 100 a dvě čtvercové matice, zadané jako dvě n-tice řádků s celočíselnými prvky oddělenými mezerami.

Vaším úkolem je vypsat matici, která je výsledkem maticového násobení daných dvou matic. Použijte dynamickou alokaci a nevyužívejte víc paměti, než je potřeba k uložení obou matic, výsledku a konstantního množství pomocných proměnných. Veškerou využitou paměť po sobě na konci programu uvolněte.

Příklad vstupu:

3

PMitura

Slévání polí (1b)

Na vstupu dostanete dvě přirozené čísla 1 <= n, m <= 100 000, na dalším řádku pak seznam n čísel oddělených mezerou a seřazených vzestupně, a na třetím řádku seznam m čísel oddělených mezerou a seřazených vzestupně.

Vašim úkolem je sloučit seznamy na obou řádcích do jednoho seřazeného pole o délce n+m, které vypíšete na standardní výstup.

• 0,5 bodu bude uděleno za jakékoliv správné řešení.
• 0,5 bodu navíc získáte, pokud vaše řešení bude pracovat v asymptoticky lineárním čase v závislosti od hodnoty n+m (to znamená, že můžete v nejhorším případě vykonat maximálně k*(n+m) operací, kde k je konstanta).

PMitura

[1] EREW / CREW / CRCW (priority, arbitrary, common) [4b]
[2] typy schedulingu [4b]
[3] definujte hranovy rez a bisekcnu sirku [4b]
[4] preco je tento kod mergesortu pomaly? [8b]
[5] synchronizacia pristupu [8b]
[6] paralelna binarna scitacka / PPS [10b]
[7] Cannon [12b]

PMitura

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

typedef unsigned long long u64;
vector<u64> gen(u64 x, u64 k) {
    u64 bound = 1ULL << x, p = 0;
    for (u64 i = 0; i < k; i++)
        p |= 1ULL << i;
    vector<u64> result;
    // courtesy of http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation

PMitura

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

typedef unsigned long long u64;
vector<u64> gen(u64 x, u64 k) {
    u64 bound = 1ULL << x;
    vector<u64> result;
    for (u64 i = 0; i < bound; i++) {
        if (__builtin_popcountll(i) == k) {
            result.push_back(i);

PMitura

int N;
struct Edge { int from, to, residue; };
vector<Edge> edges;
vector<int> graph[N]; // graph[node] = indexes of outgoing edges

void add_edge(int from, int to, int capacity) {
    graph[from].push_back(edges.size());
    edges.push_back(Edge{from, to, capacity});

    graph[to].push_back(edges.size());

PMitura

8.000, 0.002, 0.000, 0.000, 0.001, 0.001, 0.000, 0.000, 0.000, 0.402, 0.000, 
7.000, 0.002, 0.007, 0.000, 0.001, 0.001, 0.001, 0.000, 0.700, 0.000, 0.003, 
5.000, 0.000, 0.001, 0.000, 0.001, 0.004, 0.441, 0.001, 0.000, 0.001, 0.001, 
0.000, 0.755, 0.000, 0.000, 0.000, 0.000, 0.000, 0.000, 0.001, 0.003, 0.000, 
0.000, 0.698, 0.000, 0.000, 0.000, 0.000, 0.000, 0.000, 0.001, 0.006, 0.000, 
5.000, 0.000, 0.002, 0.000, 0.001, 0.004, 0.604, 0.001, 0.001, 0.001, 0.001, 
0.000, 0.703, 0.000, 0.000, 0.000, 0.000, 0.000, 0.000, 0.000, 0.005, 0.000, 
5.000, 0.000, 0.001, 0.000, 0.001, 0.003, 0.334, 0.002, 0.000, 0.004, 0.000, 
0.000, 0.732, 0.001, 0.000, 0.000, 0.000, 0.000, 0.000, 0.001, 0.003, 0.000, 
8.000, 0.001, 0.000, 0.000, 0.001, 0.001, 0.001, 0.000, 0.000, 0.520, 0.000, 

PMitura

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

int SIZE = 1e8;

int main() {
    srand(time(NULL));

    int * aligned = new int[SIZE],