Przykładowe rozwiązania zadań z kolokwium

Palindromiczne liczby pierwsze

Zadanie

Zadaniem programu jest testowanie pierwszości zadanej liczby i liczby powstałej z odwrócenia kolejności cyfr w zapisie dziesiętnym.

Wejście

Pierwsza linia wejścia zawiera liczbę N oznaczającej ilość testowanych liczb (1 <= N <= 1000). Następnie następuje ciąg N dodatnich liczb całkowitych, każda z nich jest nie większa niż 30000.

Wyjście

Dla każdej testowanej liczby należy wypisać jedną liczbę, będącą sumą liczb odpowiadających poniższym możliwościom:

  • 1 – podana liczba jest pierwsza;
  • 2 – liczba powstała przez odwrócenie cyfr jest pierwsza;
  • 4 – podana liczba jest palindromem, tzn. po odwróceniu cyfr w zapisie dziesiętnym jest tą samą liczbą.

Uwaga: liczby jednocyfrowe są palindromami.

Np. dla liczby 13 wypisujemy 3 (= 1+2), bo jest liczbą pierwszą i po odwróceniu cyfr dostajemy liczbę pierwszą (31), jednak 13 nie jest palindromem.

Przykład

Wejście

6
42
19
91
13
121
11

Wyjście

0
1
2
3
4
7
#include <cstdlib>
#include <string>
#include <iostream>
#include <cmath>

using namespace std;

bool isPrime(int n) {
    int g = sqrt(n);
    for(int i = 2; i <= g; ++i) {
        if(n % i == 0)
            return false;
    }
    return true;
}

void test() {
    string word;
    cin >> word;
    string palindrome(word.rbegin(), word.rend());
    int odp = 0;
    int n   = atoi(word.c_str());
    int m   = atoi(palindrome.c_str());
    if(isPrime(n))
        odp += 1;
    if(isPrime(m))
        odp += 2;
    if(n == m)
        odp += 4;
    cout << odp << endl;
}

int main() {
    int n;
    cin >> n;
    while(n--)
        test();
    return 0;
}

Tasowanie przez odwracanie

Zadanie

Zadaniem jest przetestowanie następującej metody tasowania kart. W zadanym ciągu kart (dla wygody oznaczonych liczbami), dla podanych dwóch pozycji należy odwrócić porządek kart znajdujących sie pomiędzy tymi pozycjami (z tymi pozycjami włącznie). Czynność tę powtarzamy określoną liczbę razy i zwracamy otrzymany na końcu ciąg kart.

Wejście

Pierwsza linijka wejścia to ilość kart N (1 <= N <= 100). W następnej linijce znajduje się N dodatnich liczb całkowitych pooddzielanych spacjami, które oznaczają początkowe ustawienie kart (liczby te niekoniecznie są różne). Liczby oznaczające karty są nie większe niż 1000.

Trzecia linjka zawiera liczbę M (1 <= M <= 1000) operacji odwracania.

Następne M linijek zawiera po dwie dwie dodatnie liczby całkowite I oraz J oddzielone spacją (1 <= I <= J <= N). Dla każdej takiej pary liczb – pozycji – należy odwrócić kolejność liczb w ciągu między zadanymi pozycjami. Uwaga: Pozycje numerujemy od jedynki.

Wyjście

Należy wypisać w jednej linijce ciąg otrzymany z zadanego po przeprowadzeniu kolejno wszystkich wskazanych operacji odwracania.

Przykład 1

Wejście

4
4 3 2 1
1
2 4

Wyjście

4 1 2 3

Przykład 2

Wejście

5
1 2 3 4 5
2
3 5
1 3

Wyjście

5 2 1 4 3
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void test(vector<int>& cards) {
    int begin, end;
    cin >> begin;
    cin >> end;
    --begin;
    end;
    reverse(cards.begin()+begin, cards.begin()+end);
}

int main() {
    int n;
    vector<int> cards;
    cin >> n;
    while (n--) {
        int tmp;
        cin >> tmp;
        cards.push_back(tmp);
    }
    int t;
    cin >> t;
    while(t--) {
        test(cards);
    }
    for(vector<int>::iterator it = cards.begin();
            it!= cards.end();
            ++it) {
        cout << *it << " ";
    }
    return 0;
}

Konkurs

Zadanie

W konkursie SMS uczestnicy wysyłają liczby. Wygrywa ta osoba, która przesłała najmniejszą liczbę, której nie przesłał nikt inny. Zadaniem programu jest wybrać wygrywającą liczbę mając podane liczby wysłane przez uczestników.

Wejście

W pierwszej linijce wejścia znajduje się liczba N graczy biorących udział w konkursie (1 <= N <= 1000). W następej linijce znajduje sie N liczb pooddzielanych spacjami – liczby wysłane przez uczestników. Każda z tych liczb jest dodatnią liczb całkowitą nie większą od 30000.

Wyjście

Na wyjściu należy wypisać wygrywającą liczbę, lub w przypadku jej braku (wszystkie liczby się powtarzają) liczbę zero.

Przykład

Wejście

5
1 1 2 1 3

Wyjście

2
#include <map>
#include <algorithm>
#include <iostream>

using namespace std;

int main() {
    map<int, int> m;
    int vote;
    cin >> vote;
    while(vote--) {
        int n;
        cin >> n;
        ++m[n];
    }
    map<int, int>::iterator it;
    for(it = m.begin(); it != m.end(); ++it) {
        if(it->second == 1)
            break;
    }
    if(it == m.end())
        cout << 0 << endl;
    else
        cout << it->first << endl;
    return 0;
}

Czynniki pierwsze

Zadanie

Zadaniem programu jest wypisać dzielniki pierwsze zadanych liczb w kolejności malejącej.

Opis wejścia

Pierwsza linijka wejścia zawiera liczbę N liczb do przetestowania (1 <= N <= 1000). W N następnych linjkach podane są liczby do przetestowania (każda liczba jest liczbą całowitą większą od 1 i nie większą niż 30000).

Opis wyjścia

Wyjście dla każdej testowanej liczby należy wypisać tę liczbę poprzedzoną dwukropkiem i ciągiem wszystkich czynników pierwszych w kolejności malejącej (czynniki pierwsze wystęþują tyle ray ile testowana liczba się przez daną liczbę pierwszą dzieli).

Przykład

Wejśćie

2
35
250

Wyjście

35: 7 5
250: 5 5 5 2
#include <cstdlib>
#include <string>
#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

vector<int> factor(int n) {
    vector<int> factors;
    int f = 2;
    while(n > 1) {
        if(n % f == 0) {
            factors.push_back(f);
            n /= f;
        } else {
            ++f;
        }
    }
    return factors;
}

void test() {
    int n;
    cin >> n;
    vector<int> factors = factor(n);
    cout << n << ": ";
    for(vector<int>::reverse_iterator it = factors.rbegin();
            it != factors.rend();
            ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

int main() {
    int n;
    cin >> n;
    while(n--)
        test();
    return 0;
}

Tasowanie

Zadanie

Zadaniem jest zasymulowanie tasowania kart. W zadanym ciągu kart (dla wygody oznaczonych liczbami) należy poprzestawiać karty zgodnie z podaną kolejnością. Czynność tę powtarzamy określoną liczbę razy i zwracamy otrzymany na końcu ciąg kart.

Wejście

Pierwsza linijka wejścia to ilość kart N (1 <= N <= 100). W następnej linijce znajduje się N dodatnich liczb całkowitych pooddzielanych spacjami, które oznaczają początkowe ustawienie kart (liczby te niekoniecznie są różne). Liczby oznaczające karty są nie większe niż 1000.

Trzecia linjka zawiera liczbę M (1 <= M <= 1000) operacji przestawiania.

Następne M linijek zawiera po N liczb pooddzielanych spacjami, są to dokładnie wszystkie liczby naturalne z przedziału [1, N] w pewnej kolejności. Pierwsza z tych liczb określa pozycją na którą powinna powędrować pierwsza karta w dotychczasowym ciągu. Druga liczba, na którą pozycję powinna powędrować karta druga itd.

Wyjście

Należy wypisać w jednej linijce ciąg otrzymany z zadanego po przeprowadzeniu kolejno wszystkich wskazanych operacji przestawiania, oddzielając elementy ciągu spacjami.

Przykład 1

Wejście

3
4 5 7
1
3 1 2

Wyjście

5 7 4

Przykład 2

Wejście

4
3 1 4 2
2
4 3 2 1
2 1 4 3

Wyjście

4 2 3 1
#include <iostream>
#include <vector>
using namespace std;

void test(vector<int>& cards) {
    vector<int> tmp(cards.size());
    for(int i = 0; i < cards.size(); ++i) {
        int position;
        cin >> position;
        tmp[position-1] = cards[i];
    }
    swap(cards, tmp);
}

int main() {
    int n;
    vector<int> cards;
    cin >> n;
    while (n--) {
        int tmp;
        cin >> tmp;
        cards.push_back(tmp);
    }
    int t;
    cin >> t;
    while(t--) {
        test(cards);
    }
    for(vector<int>::iterator it = cards.begin();
            it!= cards.end();
            ++it) {
        cout << *it << " ";
    }
    return 0;
}

Głosowanie folwarczne

Zadanie

„Wszystkie zwierzęta są równe. Ale niektóre są równiejsze od innych.”

W folwarcznej demokracji różne zwierzęta mają różną wagę głosów, w zależności od swojej pozycji wsród równych sobie. Mając listę głosów i ich wag wskaż zwycięzcę wyborów – numer kandydata, który zdobył najwięcej głosów (w przypadku remisu między kandydatami, zwycięzcą zostaje kandydat z wyższym numerem).

Wejście

W pierwszej linijce wejścia znajduje się liczba N głosujących zwierząt (1 <= N <= 1000). W następnych N linijkach znajdują się pary liczb pooddzielane spacjami. Każda z tych liczb jest dodatnią liczbą całkowitą. Pierwsza liczba w każdej parze jest nie większa od 100 i oznacza numer kandydata na którego oddano głos, a druga liczba to waga tego głosu i jest nie większa niż 1000.

Wyjście

Na wyjściu należy wypisać numer kandydata, który wygrał wybory.

Przykład

Wejście

5
1 1
1 1
1 1
1 1
2 4

Wyjście

2
#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

bool compareSecond(const pair<int, int>& left,
                   const pair<int, int>& right) {
    return left.second < right.second;
}

int main() {
    int n;
    cin >> n;
    map<int, int> votes;
    while(n--) {
        int vote, voteWeight;
        cin >> vote >> voteWeight;
        votes[vote] += voteWeight;
    }
    cout << max_element(votes.rbegin(),
                        votes.rend(),
                        compareSecond)->first << endl;
    return 0;
}