შეკითხვები 2010-2011 წლის შეჯიბრებების შესახებ აქ დავდოთ :)

mainteresebs 2010 wlis finalis D amocanashi uketesei idea: me maqvs aseti :dinamiurad vitvli ramdennairad miva (1,1) wertilidan pirvel aucileblad gamaval wertilze ,shemdeg am wertilidan shemdeg aucileblad gamaval wertilze ramdennairad miva imas vitvli da ase shemdeg gavagrdzeleb sanam bolo aucileblad gamaval wertilze ar miva da roca miva mashin vitvli am wertilidan bolo wertilze (n,m) ze ramdennairad miva. ufro kargad rom gaigot ai ase vaketeb:
n=5 m=5
k=2 k(1)=2,2 k(2)=3,4
1 1 0 0 0
1 2 2 2 0
0 2 4 6 6
0 0 0 6 12
0 0 0 6 18 am ideit ki droshi mechreba :(

ეგ ამოხსნა სწორ პასუხს კი მიიღებს მაგრამ 100000x100000 მასივი მეხსიერებაში არ ჩაეტევა (მასივების შემცირება შეიძლება მაგრამ მაინც დროში ჩავარდება).

უკეთესი ამოხსნისთვის უნდა ეცადო რომ ერთი ადგილიდან მეორეში მიმავალი გზების რაოდენობა ფორმულის გამოყენებით დათვალო და ბოლოს ეგ რიცხვები გადაამრავლო.

dinamiur daprogramebas pormula aaqvs?

გაინტერესებს რამდენი გზით შეგიძლია მიხვიდე წერტილიდან წერტილამდე.
ეს იგივეა რაც ეს ამოცანა - რამდენი გზით შეიძლება მიხვიდე -დან წერტილში?

არც ისე რთულად მტკიცდება, რომ -დან -ში მისასვლელი გზების რაოდენობა არის

va es ar vicodi :)

@varlevani:
მაგისთვის 0 იდან n+m მდე ყველა რიცხვის ფაქტორიალი ხო უნდა გქონდეს დათვლილი, და:
Ans = Fact[x+y] / (Fact[x] * Fact[y]);
პასუხში უზუსტობას არ მოგვცემს,იმიტომ რომ მასივში ფაქტორიალები კი არა
1000000009 ზე გაყოფისას მიღებული ნაშთები გვიწერია,და ჩემი აზრით ნაშთების გამრავლებით და გაყოფით სწორ პასუხს ვერ მივიღებთ.
ჩემ ამოხსნაში ალბათ ეგ მაქ შეცდომა და ხო არ იცი ეგ პრობლემა თავიან როგორ ავიცილო?

@gskhirtladze03

რა თქმა უნდა, როცა ნაშთებს ინახავ, გაყოფის ოპერაცია არასწორ პასუხს გვაძლევს. ნაშთებზე შესაძლებელია უპრობლემოდ ჩავატაროთ დანარჩენი (მიმატება, გამოკლება, გამრავლება, ახარისხება) ოპერაციები. გაყოფის დროს შემდეგნაირად ვიქცევით.

ვთქვათ გვინდა ვიპოვოთ (P მარტივია. 1000000009-ც მარტივია) ვიქცევით შემდეგნაირად.

ფერმას მცირე თეორემის თანახმად , ამიტომ
ე.ი. გაყოფის ოპერაცია ჩავანაცვლეთ გამრავლების და ახარისხების ოპერაციით:

მადლობა ცოტნე,გავატარე.

არაფერს :) თუ რაიმე დაგჭირდება კიდევ იკითხე ;)

მეც ეგ მაინტერესებდა გიორგი შენ რაც იკითხე; ცოტნე მგონი ერთი პატარა გამონაკლისია თუ 2-ივე A-ც და B-ც 1000000009-ის ჯერადებისა მაშინ ნებისმიერი შეიძლება იყოს A/B.გიორგი მართალია ამ ამოცანაში შეზღუდვების თანახმად არ ჩაიჭრება პროგრამა მაგრამ საზოგადოდ შეიძლება რაღაც ტესტი ვერ გაიაროს სხვა ამოცანებში.მადლობა მეც გავატარენ :)

@lashabuxo
პროგრამა რომ არასწორ პასუხზე ჩაიჭრას მაშინ და მაშინ პროგრამა დროშიც ვერ ჩაეტევა.

@gskhirtladze03
მართალი ხარ და ამიტომაც ვთქვი ამ შემთხვევაში არ ჩაიჭრებათქო,მითუმეტეს რომ ორივე არ აღემატება 100 000

ჰო რა თქმა უნდა სწორი ხარ, ეგრეა. არ აღვნიშნე უბრალოდ. მეტიც, 1000000009-ის მაგივრად სხვა მარტივი რიცხვებისთვისაა ეს მხოლოდ სწორი. არამარტივებისთვის არ მუშაობს.

Gtxovt mitxrat an mimanishnot 2011 wlis finalis c amocanis me5 da g amocanis me7 testi.winaswar madloba imedia damexmarebit.

warning: ერთიდაიგივეს რამდენჯერმე ნუ პოსტავ. წერე ქართულად.

კარგით აჰა:
გთხოვთ მითხრათ ან მიმანიშნოთ 2011 წლის ფინალის C ამოცანის მე-5 და G ამოცანის მე-7 ტესტი. წინასწარ მადლობა,იმედია დამეხმარებით!!!

@qasrava
"დახმარება" doesn't work this way. მე-K ტესტი მითხარითო კი არა, "აი ასე და ასე ვხსნი და მე-K ტესტზე მივარდება და ხომ ვერ მეტყვით იდეაში რა შეცდომა მაქვს?" სახის შეკითხვებს უნდა სვამდეთ. იმდენად პატარა ტესტებია C-ს მე-5ეც და G-ს მე-7ეც, რომ ჩემთვის გასაგებია რომ ლოკალურად კოდს წესიერად არ ტესტავ.

@მოდერატორი რომელმაც warning ჩაუწერა: ახლა რაც დავწერე შენ უნდა დაგეწერა. მაგდენის თავი თუ გქონდა, რომ warning მიგეცა, ბარემ პასუხის გაგეცა.

გავატარე G,მაგრამ C დროში მეჭრება მე-10 ზე :(

@eldar

გასაგებია, რომ ტესტს არ მიცემდი და ის უნდა ეკითხა რაც დაწერე. მაგრამ, მე სრულყოფილ პასუხს ვერ გავცემდი, ერთადერთი შენ შეგეძლო ამ ადამიანის დახმარება და ვიფიქრე დაწერდი "ტესტს ვერ გიჩვენებ, მაგრამ შენი კოდიდან გამომდინარე მემგონი იდეა გაქვს არასწორი" ან რამე ეგეთი (ყოველ შემთხვევაში მეგონა რომ რაიმე მინიშნებას მიცემდი). მე უნდა დამეწერა, რომ ტესტს ვერ გიჩვენებთ, მაგრამ მოვა ელდარი და ის დაგეხმარება :)

ჩემი საქმე რაც იყო, ზედმეტი პოსტები წავშალე :) ჯეოლიმპის ამოცანების ტესტებთან და ამოხსნებთან კი არ მაქვს მე შეხება ;) თანაც, შენვე გაქვს ნათქვამი, რომ გამონაკლის შემტხვევების გარდა ტესტებს არ იძლევიან :) ანუ რაღაც შანსი იყო რომ მიგეცა ტესტი (თუ ბევრი ნაწვალები ექნებოდა ეჯადჯში)

@tsotne
შენს ლოგიკაში ერთი პრობლემაა მხოლოდ - ეგ ფორუმი ხო არაა წევრების და ელდარის მიმოწერისთვის, ეგ ფორუმი არის რომ ყველამ გაუზიაროს ერთმანეთს აზრები. ამიტომ რამეს რომ წერენ, უნდა დაწერონ ყველასთვის გასაგებად. მითუმეტეს მე რატო უნდა მქონდეს ვინმეს კოდში ჩახედვის თავი :)

@qasrava
ეჰ ვერ გასწავლე ვერაფერი. C მეჭრებაო ამბობ და ადამიანმა უნდა იმარჩიელოს რა გიწერია და რატომ არ მუშაობს სწრაფად. აღწერე შენი ალგორითმი, შეაფასე ნაბიჯების რაოდენობა და შეიძლება სულ აღარ დასვა შეკითხვა, იმიტომ რომ მიხვდე რომ ნელია. აი ჩავიხედე შენს კოდში (შენიც არაა პრინციპში) და იდეა საერთოდ ვერ გავიგე. ერთი ციკლი i-k-დან i-მდე ტრიალებს, მეორე [j-k, j+k]-ში, k 70-ია - საიდან ეგ უცნაური რიცხვები?

ასე თუ ისე, 4 ჩადგმული ციკლი გაქვს, რომლებიც საზოგადოდ N-მდე უნდა ტრიალებდნენ და N^4 (300^4) რიგის რაოდენობა ოპერაცია 1 წამში არ მუშაობს. შეეცადე ამოცანაზე ასე იფიქრო: ჯვრის ცენტრი რომ დააფიქსირო და შემდეგ თითო-თითოთი გაზარდო მისი გვერდები, N^4-ზე სწრაფი (N^3 ანუ) ხომ არ შეიძლება მიიღო.