شایان ضیایی
با سلام
برای سوال “رشته در کوئرا” سه کد زیر رو نوشتم ولی هر کدوم اشکالاتی دارن و نتونستم امتیاز کامل رو بگیرم، کسی از دوستان میتونه راهنمایی کنه؟ ممنون
روش 1 : پیاده سازی سوال
num = int(input()) s1 = "1" for i in range(2,num+1): s1 = s1+str(i)+s1 print(sum([int(item) for item in (s1)]) % 1000000007)
روش 2: با توجه به این الگو
n*pow(2,0) , pow(2,1)*(n-1) , (n-2)*pow(2,2), …….
num = int(input())
Sum ,j = 0 , 0
for i in range(num,0,-1):
Sum +=i * pow(2,j,1000000007)
#print("i:",i,"j:",j,"pow:",pow(2,j,1000000007))
j += 1
#print("i:",i"j:",j,"pow:",pow(2,j,1000000007))
print(Sum%1000000007)
روش 3 : بازگشتی
num = int(input()) s1 = "1" for i in range(2,num+1): s1 = s1+str(i)+s1 print(sum([int(item) for item in (s1)]) % 1000000007)
سلام
وقتتون بخیر
ممنون از اینکه راه‌حل‌هاتون رو با ما به اشتراک گذاشتید!
مشکل روش اول و سوم (که فکر کنم فرقی هم ندارن) اینه که خود رشته s_n رو می‌سازه. می‌توانید با استقرای ریاضی ثابت کنید طول رشته s_n دقیقا برابر 2 بتوان n منهای یک است. پس ساختن این رشته برای مقدارهای بزرگ زمان‌بر (حتی حافظه‌بر!) هست.
ولی توی روش گفته شده رد سوال فقط مجموع ارقام s_{n-1} رو در ۲ ضرب می‌کنیم اینطوری حداکثر O(n) عملیات انجام می‌دیم. (به طور خلاصه به جای ذخیره خود رشته، مجموع ارقام رشته رو به پیمانه ذخیره می‌کنیم.)
اما مشکل راه حل دوم که مشکل اساسی هست اینه که باید مجموع ارقام رو ذخیره کنید. (و این توی سوال بلد شده) یعنی اگر مثلا عدد ۱۳ رو داریم باید جمع ارقامش که ۴ هست رو اضافه کنید نه خود ۱۳. پس میتونید در نظر بگیرید که عدد i چند بار اومده و به‌جای ضرب کردن خود i، جمع ارقام i رو ضرب کنید.
فکر کنم با این تغییر مشکل برنامه شما برطرف خواهد شد. اگر بازهم موردی توی حرفام درست نبود و یا سوالی بود، خوشحال می‌شیم که با ما در میان بگذارید!
توجه کنید اگر توان‌های base به پیمانه mod در روش درهم‌سازی را پیش‌پردازش کنید و در یک آرایه ذخیره کنید؛ برابری دو زیر رشته را می‌توانید از مرتبه O(1) بررسی کنید، پس برای جستوجوی دودویی O(log(n)) نیاز دارید و چون برای هر کدام از n شیفت این کار را انجام می‌دهیم در کل مرتبه زمانی از O(nlog(n)) خواهد بود.
سلام
من سوال 3 (نامه‌ها در کوئرا) را با این کد حل کردم امتیاز 91 گرفتم و برای چنتا تست اخر ارور time limit میگیرم به نظرتون مشکل از کندی زبان پایتون هستش یا این کد هنوز میتونه بهینه تر باشه ؟
first_input = input() n = int(first_input.split()[0]) m = int(first_input.split()[1]) secend_input = input() l = list(map(int, secend_input.split())) # def main(n, m, l): # first main func # while m: # if n/2 < l.count(m): # return 'NO' # m -= 1 # return 'YES' def main(n, m, l): # secend main func ( more optimal ) most_frequent = max(set(l), key = l.count) most_frequent_count = l.count(most_frequent) if most_frequent_count > n/2: return 'NO' return 'YES' print(main(n, m, l))
