Problemi 012

Kërkesa

Nqs kemi N monedha dhe i vendosim në formë trekëndëshi, në mënyrë të tillë që:

  • në rreshtin e parë vendosim 1 monedhë
  • në rreshtin e dytë vendosim 2 monedha
  • në rreshtin e tretë vendosim 3 monedha
  • e kështu me radhë (siç tregohet në figurë)

Sa është lartësia e trekëndëshit më të madh që mund të formohet?

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

Shembull

$ cat input.txt
3
3
5
7

$ python3 prog.py < input.txt
2
2
3
  • Testi 1: Nuk mund të formojmë një trekëndësh me lartësi >2, sepse kjo kërkon të paktën 6 monedha.
  • Testi 2: Nuk mund të formojmë një trekëndësh me lartësi >2, sepse kjo kërkon të paktën 6 monedha.
  • Testi 3: Nuk mund të formojmë një trekëndësh me lartësi >3, sepse kjo kërkon të paktën 10 monedha.

Zgjidhja 1

Sqarime

Fillimisht shënojmë me 0 lartësinë e trekëndëshit dhe sasinë e monedhave që duhet për ta ndërtuar. Pastaj fillojmë ta rrisim lartësinë me nga 1, duke llogaritur edhe sasinë e monedhave që na duhen për ta ndërtuar. Këtë punë e bëjmë deri sa sasia e monedhave mos ta kalojë numrin n që na është dhënë.

Zgjidhja 2

Fillojmë ta rrisim lartësinë me nga 1, duke llogaritur edhe sasinë e monedhave që na duhen. Këtë punë e bëjmë deri sa sasia e duhur e monedhave ta kalojë numrin n që na është dhënë. Atere lartësia e mundshme e trekëndëshit është vlera e l-së që sapo kaluam (ku sasia e dhënë e monedhave ishte e mjaftueshme për ta ndërtuar).

Detyra

Shkruani një program që llogarit shumën e shifrave të një numri të dhënë.

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

Shembull

$ cat input.txt
3
12345
31203
2123

$ python3 prog.py < input.txt
15
9
8