Riyanın doğum günü sorusu

Python
1

Sorumuz şu:

Problem

Madhav Riya’nın Doğum Günü Partisine gitti. O bir inek, bu yüzden hangi hediye hoşuna gideceği konusunda hiçbir fikri yoktu. Bu yüzden bir dizi tamsayıyı yanına aldı. Dizi belirli bir düzene uyuyordu. Dizinin ilk elemanı 1’di. Dizinin ikinci elemanı 6 idi.
Dizinin diğer elemanları, kendisinden önce gelen ve sonrasındaki sayının aritmetik ortalamasının iki eksiği olarak belirleniyordu. Açıkça görüleceği gibi, Riya bu fikrin aptalca olduğunu düşündü ve bu yüzden Madhav’ı cezalandırmak istedi. Madhav’ın bu utanç verici durumdan kaçmasına yardım et.

Girdi

Girdi, T, Test Durumlarının sayısı ile başlar.
Sonraki T satırda tamsayı N bulunur.

Çıktı

Her test durumu için, dizinin N’inci bir tamsayısını çıktı olarak verin. Cevap çok büyük olabileceğinden, sonucu 10 üzeri 9 + 7’e göre modulo alarak çıktı verin.

Kısıtlamalar:

1 ≤ T ≤ 105
1 ≤ N ≤ 1018

Örnek Giriş
2
1
3
Örnek Çıktı
1
15

Kısacası özetlersek [1,6,15,28…] diye giden bir serinin N-1 inci elemanını veren sonuçlar olacak.

Örnek girdide 2 tane isteneceği söyleniyor, sonraki girdiler N. eleman 1 için 1, 3 için 15 değerini döndürüyor.

Sorunun orjinal linki: Riya's Birthday Party | Practice Problems

2

Buna ilk başta aşağıdaki kodu yazdım mevzuyu anlamak için.

dizi = [1,6]
N = []
T = int(input())
for _ in range(T):
    N.append(int(input()))

ma = max(N)
for i in range(2,ma):
    dizi.append(2*dizi[i-1]-dizi[i-2]+4)

for i in N:
    print(dizi[i-1])

Program doğru sonuçları döndürüyor fakat zaman hızı ve bellek testlerinden geçemedi.

3

Daha sonra şöyle hızlanır belki diye düşünüp bu kodu yazdım.

def bul(eleman):
    if eleman == 1:
        return 1
    tp=0
    for n in range(0,eleman-1):
        tp += n       

    return 1+5*(eleman-1)+4*(tp)

T = int(input())
for _ in range(T):
    print(bul(int(input())))

Ama bu da zaman ve bellek sorununa takıldı.

4

Biraz daha kafa yorup şu hale indirdim programı

T = int(input())
for s in range(T):
    N = int(input())
    to = 1
    for i in range(N-1):
        to = to +5+ i*4
    print(to)

Program gitgide kısaldı ama bu da üstüne çıktı malesef zaman , bellek limitlerini.

Paylaşayım dedim belki ilginizi çeker ilginç çözümler gelir.

5

Ben de farklı bir çözüm ürettim ama kriterleri denemedim açıkçası.

def generate_list(length: int) -> list:
    generated_list = [1,6]
    
    next_element = lambda previous_element, mean_element: (mean_element + 2) * 2 - previous_element
    
    for i in range(0, length - 2):
       generated_list.append(next_element(generated_list[i],generated_list[i + 1]))
       
    return generated_list[:length]
1 Beğeni
6

Merhabalar,

Normalde, recursion veya döngü ile yapılabilir.

Alternatif bir algoritma da benden olsun:

def f(n: int):
    return 4 * n + 1 + f(n - 1) if n else 1


for i in range(10):
    print(f(i))

Çıktı:

1
6
15
28
45
66
91
120
153
190

Ama, bunu O(1) zaman karmaşıklığı ile yapmak için matematiksel bir formül elde etmek gerekiyor. Biraz üzerinde çalıştım ve sonunda f(x) = 2x2 + 3x + 1 formülünü elde ettim. Bu formülü bir Python fonksiyonuna çevirirsek O(1) hızında bir fonksiyonumuz olur.

def g(n: int):
    return 2 * n ** 2 + 3 * n + 1

f ve g fonksiyonlarını aynı anda çalıştırıp, sonuçları karşılaştıralım:

for i in range(10):
    print(f(i), g(i))

Çıktı:

1 1
6 6
15 15
28 28
45 45
66 66
91 91
120 120
153 153
190 190
1 Beğeni
7

İlki için runtime error verdi (sanırım rekürsif belirli bir yerden sonra arıza çıkarıyor)

ikincisi için wrong answer cevabı geldi. Dizinin belirli bir kısmını kontrol ettim doğru ama ileride bozuluyor olabilir.

8

Özür dilerim hatayı 10^9+7 modulasından veriyormuş.

def g(n: int):
    return 2 * n ** 2 + 3 * n + 1

T = int(input())
for s in range(T):
    print(g(int(input())-1)%(10**9+7))

Şu şekilde düzeltince hata kalktı ayrıca bellek ve zaman limitlerini de karşıladı. Tebrik ederim.

1 Beğeni