Ukázková úloha

Bankovní pomocník

Maxipes Fíks provozoval investiční banku pro místní lesní obyvatele. Měl ji skvěle zorganizovanou: banka obsahovala N schránek očíslovaných 1 až N, ve kterých měl po řadě uloženy peníze v množství S₁, S₂,...,S_N korun. A protože byl též pořádkumilovný, množství peněz uložených v schránkách se zvětšovalo s číslem schránky. Jinými slovy, pro dvě čísla schránek i < j platilo S_i ≤ S_j. Jednou přišel do banky bobr a žádal půjčku K korun na stavbu nové hráze. Interní předpisy banky přikazují, že peníze se musí vydávat přesně ze dvou různých schránek, a navíc se schránky musí kompletně vyprázdnit. Fíks tedy potřebuje co nejrychleji zjistit, jestli mezi schránkami existují dvě, které obsahují dohromady přesně K korun. Navrhněte algoritmus a napište program, který Fíksovi co nejrychleji poradí, které schránky otevřít.

Ke stažení

Kompletní zadání Vzorové řešení

Implementace

Níže se nachází ukázková implementace v jazycích C, C++, Java a Pascal, ovšem je pouze na tobě, ve kterém z jazyků se rozhodneš úlohu implementovat.

Implementace v jazyce C

#include <stdio.h>
#define MAX 10000

int S[ MAX ];
int N, K;

int main ( void ) {
    scanf( "%d %d", &N, &K );
    int i, j;

    for ( i = 0; i < N; i++ )
        scanf( "%d", S + i );

    i = 0;
    j = N - 1;
    while ( i < j ) {
        int s = S[ i ] + S[ j ];
        if ( s == K ) {
            printf( "Reseni je %d a %d.\n", i+1, j+1 );
            return 0;
        }
        if ( s < K )
            i++;
        else
            j--;
    }

    printf("Reseni neexistuje.\n");
    return 0;
}

Implementace v jazyce C++

#include <iostream>
using namespace std;
#define MAX 10000

int S[ MAX ];
int N, K;

int main ( void ) {
    cin >> N >> K;
    int i, j;

    for ( i = 0; i < N; i++ )
        cin >> S[i];

    i = 0;
    j = N - 1;
    while ( i < j ) {
        int sum = S[ i ] + S[ j ];
        if ( sum == K ) {
            cout << "Reseni je " << ( i + 1 ) << " a " << ( j + 1 ) << "." << endl;
            return 0;
        }
        if (sum < K)
            i++;
        else
            j--;
    }

    cout << "Reseni neexistuje." << endl;
    return 0;
}

Implementace v jazyce Java

import java.util.Scanner;

public class Ukazka {

    static final int MAX = 10000;

    public static void main ( String [] args ) {
        Scanner sc = new Scanner( System.in );

        int [] S = new int [ MAX ];
        int N = sc.nextInt();
        int K = sc.nextInt();
        int i, j;

        for ( i = 0; i < N; i++ )
            S[ i ] = sc.nextInt();

        i = 0;
        j = N - 1;
        while ( i < j ) {
            int sum = S[ i ] + S[ j ];
            if ( sum == K ) {
                System.out.println( "Reseni je " + ( i + 1 ) + " a " + ( j + 1 ) + "." );
                System.exit(0);
            }
            if ( sum < K )
                i++;
            else
                j--;
        }

        System.out.println( "Reseni neexistuje." );
    }
}

Implementace v jazyce Pascal

program Ukazka;
const MAX = 10000;

var S : array[ 0 .. MAX ] of longint;
    N, K, i, j, sum : longint;

begin
    read( N );
    read( K );
    for i := 0 to N - 1 do
        read( S[ i ] );

    i := 0;
    j := N - 1;

    while i < j do
    begin
        sum := S[ i ] + S[ j ];
        if sum = K then
        begin
            writeln( 'Reseni je ', ( i + 1 ), ' a ', ( j + 1 ), '.' );
            Exit;
        end;

        if sum < K then
            i := i + 1
        else
            j := j - 1;
    end;

    writeln( 'Reseni neexistuje.' );
end.