Aug 2007
21 / 26
Feb 2015
Dec 2019
arekbulski
Feb '15

Crucian, format w Wysadzanie grafu jest w oczywisty sposób niezgodny ze specyfikacją. W przykładzie masz dodatkowe puste linie o których nie ma mowy w tekście. Nie możesz zakładać że wszyscy używają cin'a. Proszę powiedz mi jak mam wczytać dane.

[bbone=python,2384]
import sys
f = sys.stdin
notestow = int(f.readline())
for t in range(notestow):
n,m = map(int, f.readline().split())
V = range(1,n+1)
E = dict()

for _ in range(m):
    a,b = map(int, f.readline().split())

[/bbone]

Crucian_sof
Feb '15

Arek, po liczbie zestawów danych nie było pustej linii, a między zestawami danych były. Wgrywam właśnie Skończyłem wgrywać nowe testy, które zawierają pustą linię i między zestawami danych i po liczbie zestawów danych. Zmieniłem test przykładowy, żeby było widać gdzie są puste linie.

4 years later
arekbulski
Dec '19

Odnośnie właściwego zadania (TRT - krowie zadanie). Dostaję WA mimo że kod outputuje 43 na przykładzie z zadania. Czy mogę prosić o podpowiedź?

N = int(input())
ns = list()
for i in range(N):
    ns.append(int(input()))
    
age = 1
i,j = 0,N-1
total = 0
while i <= j:
    if ns[i] > ns[j]:
        total += age*ns[j]
        j -= 1
    else:
        total += age*ns[i]
        i += 1
    age += 1
print(total)
arekbulski
Dec '19

Right. Comments were useful:

Instead of thinking it in terms of pure DP its better to approach the problem with recursion(TOPDOWN) with memoization… AC

6 | 6 1 1 1 5 5 . Ans = 70 <- Greedy approach fails
5 | 1 3 1 5 2 . Ans = 43 <- Greedy approach works

narbej
Dec '19

And this 2 comments:

The Financier:

Tornike Mandzulashvili, isn’t. Try 6 98 98 98 98 1 99 , correct is 1865

What is the optimal logik ? I solved using bruteforce with caching. But it’s too slow

Tornike Mandzulashvili:

if c[l]<=c[r] then take c[l]*a and l++; else choose c[r]*a and r–; this is o(n) solution . isnt it right???