Problemi 077

Kërkesa

Në një varg që përbëhet nga shifrat 0 dhe 1 kontrolloni nëse të gjitha shifrat 1 formojnë një segment të vetëm dhe jo-bosh.

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

Shembull

$ cat input.txt
6
001111110
00110011
000
1111
101010101
101111111111

$ python3 prog.py < input.txt
YES
NO
NO
YES
NO
NO

Zgjidhja 1

Sqarime

Marrim dy indekse i dhe j, njëri që niset nga fillimi dhe tjetri nga fundi, dhe i lëvizim deri sa të gjejmë fillimin dhe fundin e njëshave. Pastaj kontrollojmë nëse midis këtyre ka ndonjë zero.

Zgjidhja 2

Sqarime

Fillimisht gjejmë numrin e njëshave. Pastaj indeksin e njëshit të parë nga fillimi, dhe të njëshit të parë nga fundi. Pastaj kontrollojmë nëse largësia midis këtyre dy indekseve është e barabartë me numrin e njëshave.

Detyra

Në një kompani janë N punonjës, pagat e të cilëve janë \(W_i\) (për i nga 1N). Një ditë pronari vendosi që tua bëjë rrogat të barabarta të gjithëve. Por për të arritur këtë qëllim ai përdor një veprim të tillë: Zgjedh një punonjës, dhe rrit me 1 rrogën e gjithë punonjësve të tjerë (por jo të këtij që ka zgjedhur). Sigurisht që punonjësi i zgjedhur mund të jetë i ndryshëm për secilin veprim. Sa është numri më i vogël i veprimeve të tilla që duhen kryer deri sa të gjithë punonjësit të kenë rroga të barabarta?

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

Shembull

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

$ python3 prog.py < input.txt
3
0

Në rastin e parë, fillimisht zgjidhet punonjësi i tretë, dhe pagat bëhen (2, 3, 3). Pastaj mund të zgjidhet punonjësi i dytë, dhe pagat bëhen (3, 3, 4). Pastaj mund të zgjidhet punonjësi i tretë, dhe pagat bëhen (4, 4, 4). Pra duhen 3 veprime për ti barazuar.

Në rastin e dytë janë tashmë të barabarta, kështu që nuk është nevoja për asnjë veprim.