Strona poświęcona algorytmom

Loteria

Nietypowa Bydgoszcz

W Bydgoszczy jest nietypowa loteria, która składa się z dwóch losowań:

  1. Najpierw losujemy liczbę k
  2. Następnie ze podanego nam zbioru z n liczb losujemy 2 dowolne liczby:
    p1 i p2

Gracz wygrywa nagrodę tylko wtedy, gdy p1 + p2 = k.

Ala ma kota

Można się wycofać

Niestety, nie mamy gwarancji, że po wylosowaniu liczby k, istnieją takie 2 liczby
p1, p2, że p1 + p2 = k.

Ale za to możemy się wycofywać w połowie drogi:

  1. Wylosowanie liczby k kosztuje 1zł.
  2. Wylosowanie liczb p1 i p2 kosztuje kolejną złotówkę

Jednak nie jest obligatoryjne – nie musimy kupować drugiej części loterii.

 

Krzychu spryciarz

Krzysiek pomyślał, że poprosi Ciebie byś napisał program który sprawdzi, czy dla wylosowanej liczby k istnieją 2 liczby p1, p2 które sumują się do k. Tylko wtedy weźmie udział w drugiej części loterii.

 

Wejście

W pierwszej znajduje się 2 liczby oddzielone spacją w następującej kolejności:

1 <= k <=1012                     (liczba k wylosowana przez Krzycha)

2<=n<=108                       (ilość liczb z których Krzysiek będzie losował dwie liczby p1 i p2)

W drugiej linii znajduje się n liczb naturalnych z przedziału 1<=n<=1010, z których Krzysiek będzie losował liczby p1 i p2

 

Wyjście

Jeśli w podanych n liczbach istnieją takie p1 i p2, że p1 + p2 = k wówczas Twój program powinien wypisać:

            Postaw zeta, niech bedzie kareta

 w przeciwnym przypadku program powinien wypisać:

            Kto gra w karty chodzi bosy i obdarty

 

Przykład 1

Wejście

17 4                (k=17, druga część loterii zawiera 4 liczby)

10 15 3 7       (4 liczby z których losujemy p1 i p2)

Wyjście

Postaw zeta, niech będzie kareta

Wyjaśnienie

Istnieją w podanych n liczbach takie p1 i p2, że p1 + p2 = k

Jako p1 możemy wylosować 10, jako p2 możemy wylosować 7, wówczas
p1+p2 = k:

10 + 7 = 17

 

Przykład 2

Wejście

17 4                (k=17, druga część loterii zawiera 4 liczby)

10 15 3 6       (4 liczby z których losujemy p1 i p2)

Wyjście

Kto gra w karty chodzi bosy i obdarty

Wyjaśnienie

NIE istnieją w podanych n liczbach takie p1 i p2, że p1 + p2 = k

 

Przykład 3

Wejście

8 5                  (k=8, druga część loterii zawiera 5 liczb)

1 3 4 4 2        (5 liczby z których losujemy p1 i p2)

Wyjście

Postaw zeta, niech będzie kareta

Wyjaśnienie

Istnieją w podanych n liczbach takie p1 i p2, że p1 + p2 = k

Jako p1 możemy wylosować 4, jako p2 możemy wylosować drugie 4, wówczas
p1+p2 = k:

4 + 4 = 8

 

———–

Testy

http://www.algoorithms.pl//i/Loteria_Testy.zip

———–

Komentarz

Zadanie wzorowane na jednym z pytań jakie amerykański Google daje studentom informatyki przy rozmowie kwalifikacyjnej.

Poniżej oryginalne zadanie jakie Google stawia na interview:

You have an array of numbers and additionally you get value k:

Return whether there exist any two numbers from the array which sum is k.

For example, if array of numbers is

[11, 16, 2, 7]

and

k=18

you shall return true since 11 + 7 = 18

 



Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *