Problemi 032

Kërkesa

Shefi dhe 2 punonjës të tij janë në lëvizje në terren dhe komunikojnë me radiomarrëse. Radiomarrëset e tyre mund të komunikojnë e shumta deri në një largësi R, por kanë aftësinë të ndërlidhen edhe nëse midis tyre ndodhet një radiomarrëse e tretë me largësi jo më të madhe se R nga secila prej tyre.

Bëni një program që llogarit nëse shefi dhe punonjësit mund të komunikojnë me njëri-tjetrin, nëse i jepen largësia R dhe kordinatat e secilës radiomarrëse.

Referenca: https://www.codechef.com/problems/COMM3

Shembull

$ cat input.txt
3
1
0 1
0 0
1 0
2
0 1
0 0
1 0
2
0 0
0 2
2 1

$ python3 prog.py < input.txt
yes
yes
no

Zgjidhja

import math

def largesia(x1, y1, x2, y2):
    '''
    Gjej largësinë midis pikave (x1, y1) dhe (x2, y2).
    '''
    return math.sqrt((x1 - x2)**2 + (y1 - y2)**2)

for _ in range(int(input())):
    R = int(input())
    x1, y1 = map(int, input().split())
    x2, y2 = map(int, input().split())
    x3, y3 = map(int, input().split())
    d1 = largesia(x1, y1, x2, y2)
    d2 = largesia(x1, y1, x3, y3)
    d3 = largesia(x2, y2, x3, y3)
    k1 = d1 <= R
    k2 = d2 <= R
    k3 = d3 <= R
    if (k1 and k2) or (k1 and k3) or (k2 and k3):
        print('yes')
    else:
        print('no')

Sqarime

Gjejmë largësitë midis radiomarrëseve. Që të mund të komunikojnë të treja, duhet që të paktën dy prej largësive të jenë jo më të mëdhaja se R.

Detyra

Vogëlushja Meli i ka qejf balonat me ngjyra dhe mami i ka blerë për ditëlindje disa balona me ngjyra të ndryshme. Mirëpo Meli do të dëshironte ti kishte të gjitha balonat me të njëjtën ngjyrë, kështu që mori kolorat dhe ju fut punës për ti ngjyrosur.

Bëni një program që gjen sa është numri më i vogël i balonave që duhen ngjyrosur, për ti bërë të gjitha me të njëjtën ngjyrë.

Shembull

$ cat input.txt
3
abc
bb
baabacd

$ python3 prog.py < input.txt
2
0
4

Çdo ngjyrë shënohet me një shkronjë të veçantë. Në rastin e parë mjafton të ngjyrosim balonat b dhe c me ngjyrën a. Në rastin e dytë të gjitha balonat kanë të njëjtën ngjyrë. Kurse në rastin e tretë balonat me ngjyrat b, c dhe d duhet ti ngjyrosim me ngjyrën a.