III_ე ამოცანაში ცოტა ფიზიკის ცოდნა იყო საჭიროო? :? აშკარად ვერ გავიგე რა შეიძლებოდა ყოფილიყო სიმძიმის ცენტრი : /

კი და უნდა დაეწერათ ჩემი აზრით ცენტრის გამოთვლის ფორმულა.

Rx=(r1x*m1x+r2x*m2x)/(m1+m2).

ესაა

სპასიბა.. :|

მაინტერესებს D და E ამოცანების ამოხსნები :)
ვისაც შეგიძლიათ დაპოსტეთ აქ :)

E ამოცანა დინამიურია. (თითოეულ წვეროში უნდა დაიმახსოვრო უშორესი სიგრძე და მაგ უშორესი სიგრძის მიღება რამდენნაირად შეიძლება.)

D ზე არ მიფიქრია ჯერ.

ნოდარ, ისე ხსნი ხოლმე რო ასი წელი ვერ გავიგებდი ამოხსნას :D

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

gpataraia

თუ 2 წერტილი გაქ მასებით M1 და M2 მაშინ მაგათი მასათა ცენტრი იქნება
მათ შემაერთებელ მონაკვეთზე ისე რომ



M1 * L1 = M2 * L2

მსგავსი იდეა მქონდა :)
ანუ ჩამოვკიდოთ ხე ... თითო წვეროსჰი მექნება დამახსოვრებული მის შთამომავლებამდე მანძილი ... ნუ ამის რეალიზაცია დეკარტის ხით შეიძლება .... ეხლა , პასუხს დავითვლი შვილის და მშობლის ხის შერწყმის დროს ... და ჯამში გამოდის O(N LOG N) ... მოკლედ რომ ვთქვა IOI 2011 RACE მსგავსად ... მაინტერესებს რამდენად სწორედ ვფიქრობ ...

დეკარტის ხე სულ არაა აქ საჭირო, უბრალოდ DFS-ით შემოვიაროთ ხე და ყოველმა წვერომ დააბრუნოს, მისგან ქვემოთ (ანუ მის ქვეხეში) წასული ყველაზე გრძელი გზა რამხელა იყო და რამდენი იყო ასეთი სიგრძის გზა. ახლა ვთქვათ X წვეროს ჰყავდა N შვილი და მათ დააბრუნეს წყვილები (Ai, Bi) - A არის რა სიგრძის გზა იყო i-ური წვეროდან ქვემოთ და B რამდენი იყო ასეთი. ცხადია, რომ X წვეროდან ქვემოთ წასული უგრძესი გზა იქნება ის, რომლისთვისაც Ai+[წიბოს სიგრძე X-დან i-მდე] არის მაქსიმალური, ხოლო მათი რაოდენობაა ყველა იმ Bi-ს ჯამი, რომლებისთვისაც Ai+[X->i წიბოს სიგრძე] ტოლია მაქსიმალურის. ამავე დროს უნდა გამოვთვალოთ, X-ის ქვეხეში უგრძესი გზა რა იყო - ანუ იგი შეიძლება დაიწყოს X-ის ერთ-ერთი შვილის ქვეხეში, გაიაროს X-ზე და წავიდეს მეორე შვილის ქვეხეში. ესე იგი უნდა ვიპოვოთ L = მაქსიმუმი(Ai+Aj+[წიბო X->i]+[წიბო X->j]) და დავითვალოთ ეს მაქსიმუმი რამდენჯერ შეგვხვდა. თუ L აღემატება მიმდინარე უგრძეს გზას, ესე იგი უკეთესი პასუხი გვიპოვნია.

@gojira

და ეს L საბოლოოდ სად უნდა შევინახო ? X წვეროში ?

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

@gojira

გასაგებია ...

მე-3 ამოცანაში ყუთის სიმაღლეს რა მნიშვნელობა ქონდა?

ხო ეგ მეც მაინტერსებს მასათა ცენტრის გეგმილი ფუძეძე ძევს თუ არა იმას ხო ისედაც გავარკვევთ?

აპსოლვინგი ჩაირთო.

სიმაღლეს ის მნიშვნელობა ჰქონდა რო ფართობზე და შესაბამისად წონაზე მოქმედებს, მაგის გარეშე სიმძიმის ცენტრს ვერ იპოვით.

გასაგებია მადლობა

@aazizyan
D-ში კიდევ ცხადია, რომ ყველა გადანაცვლების განხილვა და შემოწმება, რამდენ K-ზე გაიყო, ზედმეტად ნელია. თუმცა შეგვიძლია ჯერ შევამოწმოთ, შეიძლება თუ არა მოცემული ციფრებით მივიღოთ 2, 3, 4 და 5-ზე გაყოფადი რიცხვი. დადებით შემთხვევაში ჩვენი რიცხვის ბოლო ციფრი ცალსახად 0 უნდა იყოს, ხოლო ბოლოსწინა 0, 2, 4, 6 ან 8. მეორე დებულებით ერთი შეხედვით ბევრი ვერაფერი მოვიგეთ - ხომ შეიძლება ყველა ციფრი {0,2,4,6,8} სიმრავლიდან იყოს - მაგრამ რეალურად ამ დროს ვარიანტების რაოდენობა 11!-თან ახლოსაც კი არ დგას, იმიტომ რომ ციფრები მრავლად მეორდება.

ყოველი გადანაცვლებისთვის უბრალოდ 7-დან (2,3,4,5-ზე ხო გავყავით და 6-ზეც იყოფა ავტომატურად) დაწყებულ ციკლში შეგვიძლია შევამოწმოთ, რომელ რიცხვზე არ გაიყოფა პირველად ჩვენი შედეგი.

ეს იყო საავტორო ამოხსნა და ისე meet-in-the-middle-ის მეშვეობითაც იხსნება. აიღე 12-დან ციფრების ყველა 6-ეული, მათი ყოველი გადანაცვლებისთვის ნახე რა ნაშთები მიიღება lcm(1, ..., i) რიცხვზე გაყოფისას ყოველი i = 1..40-სთვის (40-ზე ნაკლებია იქ ზღვარი, 36 ალბათ) და შემდეგ მარცხენა მხარეს რომ დააფიქსირებ რა 6 ციფრი უნდა გქონდეს, მარჯვნივ შეძლებ სწრაფად შეამოწმო რა საუკეთესო ექვსეული ეტევა. თუმცა ზედმეტად რთულია ეგ ამოხსნა D-სთვის.

@gojira

მადლობა :)

@gojira,

მაგრამ რეალურად ამ დროს ვარიანტების რაოდენობა 11!-თან ახლოსაც კი არ დგას, იმიტომ რომ ციფრები მრავლად მეორდება.

ეგრე როგორ გადავარჩიო რო გამეორებები პირდაპირ გამოირიცხოს?


ისე მე შვიდზეც გაყოფადობის ნიშანი გამოვიყენე და წა 29 მაქ :ს (UPD: vso agar maq)

hehe სისტემას ბაგი ვუპოვე Problem status summary აქ წერია რო 28 ტესტზეა წა არადა ამოცანაზე 29 წერია ხდ

ეგრე როგორ გადავარჩიო რო გამეორებები პირდაპირ გამოირიცხოს?

next_permutation ავტომატურად უნიკალურების გადარჩევას ახდენს.