Cini mi se da zadatak “slatkisi za sav novac” nije moguce resiti u pythonu na nacin da se dobije 100 bodova, optimizovao sam program jako dugo i nista.Evo ga:
from bisect import bisect
n = int(input())
l = input().split()
k = int(input())
ln = [0]
s = list()
for i in l:
ln.append(ln[-1]+int(i))
for i in range(k):
x, y = map(int, input().split())
f = bisect(ln[x+1:], y+ln)
print(f)
kod je malo pokvaren ovde ali eto
U raw prikazu se vidi
Meni isto ne radi, ne znam u cemu je caka.
Radiš u python-u?
Pokusavam. Cemu ti sluzi bisect? Ako ti ostane novca kad stignes do kraja reda da li se samo zaustavis ili ides ponovo od pocetka?
Zadatak se resava binarnom pretragom po prefiksnim sumama. Prvo se ucita N zatim niz A i onda napravimo jedan niz koji ce predstavljati niz prefiksnih suma niza A. Neka se on zove pre i pre[i]=pre[i-1]+A[i] . Zatim za svaki upit radimo binarnu pretragu tako sto ako je upit tipa S,B gde je S pocetna pozicija a B kolicina novca onda u slucaju kada je pre[mid]-pre[S-1]<=B (gde mid oznacava poziciju binarne pretrage) pretraga se pomera u desno, a u suprotnom pretraga se pomera u levo. Evo kod u C++ (ne znam python dovoljno dobro da napisem ovaj kod u njemu):
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n];
int pre[n+2];
for(int i=1;i<=n;i++)
{
cin>>a[i];
if(i==1)
pre[i]=a[i];
else
pre[i]=pre[i-1]+a[i];
}
pre[0]=0;
int qq;
cin>>qq;
while(qq–)
{
int a,b;
cin>>a>>b;
int low=a+1;
int high=n;
int ans=0;
while(low<=high)
{
int mid=floor((low+high)/2);
if((pre[mid]-pre[a])<=b)
{
low=mid+1;
ans=max(ans,mid-a);
}
else
{
high=mid-1;
}
}
cout<<ans<<endl;
}
}
Da ja napisem program u C++ na ideju ovog on bi 100% radio(jer je python oko 2 puta sporiji), međutim ono ja površno znam C++, a ne kontam što bi se “favorizovao” C++ kad je i python takmičarski jezik.
Bisect je binarno pretraživanje i služi da bi se najbrže moguće pronašao indeks gde bi dati član(u komandi) stojao u datoj listi, tj. evo malog koda pa, ako skontaš skontaš, ako ne imaš na net-u(radi samo u sortiranim listama):
from bisect import bisect
l = sorted([2, 4, 7])
print(bisect(l, 6))
output:
2(jer bi šest u datom sortiranom nizu trebalo biti na 2. mestu da bi on to ostao)
Zdravo svima,
Moguće je zadatak uraditi u Pythonu. Bisect je dobar pravac razmišljanja.
Bacite pogled na zvanično rešenje https://takprog.petlja.org/osnovnaskola
znam bio sam tamo