| # | ამოცანა | ავტორი |
| A | match | გიორგი საღინაძე |
| B | network | ანდრეი ლუცენკო |
| C | clock | ანდრეი ლუცენკო |
| D | paint | ელდარ ბოგდანოვი |
| E | grain | ელდარ ბოგდანოვი |
ამოცანების პირობების სანახავად ამ ბმულს მიჰყევით.
იდეურად ამოცანა ტრივიალურია - დავთვალოთ, {A≥AM}, {B≥BM}, {C≥CM} უტოლობებიდან რამდენი შესრულდა და შევადაროთ 2-ს. ამისთვის შეგვიძლია შემოვიღოთ მთვლელი cnt, რომლის მნიშვნელობასაც გავზრდით ყოველი შესრულებული უტოლობისთვის:
cnt = 0
if A >= AM then cnt = cnt + 1
if B >= BM then cnt = cnt + 1
if C >= CM then cnt = cnt + 1
if cnt >= 2 then “YES” else “NO”
C++-ის მოქნილობის წყალობით, მასზე შეიძლება ეს კოდი ერთხაზიანი გავხადოთ:
puts( ( ( (A >= AM) + (B >= BM) + (C >= CM) ) >= 2 ) ? ”YES” : ”NO” );ეს კოდი შემდგენაირად იმუშავებს: ჯერ შეფასდება ყოველი უტოლობა და მიენიჭებათ true ან false მნიშვნელობა. შემდეგ, ვინაიდან ეს მნიშვნელობები არითმეტიკულ გამოსახულებაში (აჯამვაში) მონაწილეობს, მოხდება მათი int-ზე დაყვანა, რის შედეგადაც ისინი მიიღებენ მნიშვნელობას 0 ან 1 (სტანდარტით არაა გარანტირებული, რომ true 1-ზე დაიყვანება, მაგრამ ჩვენს კომპილატორშიც და სავარაუდოდ იმ კომპილატორებში, რასაც თქვენ იყენებთ, ზუსტად ასე მოხდება). მიღებული ჯამი შეედარება 2-ს და თუ მასზე მეტი ან ტოლი იქნება, მთელი გამოსახულების მნიშვნელობა „YES” იქნება, წინააღმდეგ შემთხვევაში კი “NO”. puts ფუნქციას ის-ღა დარჩენია, ეს მნიშვნელობა დაბეჭდოს. ლამაზია, არა? =)
შეიძლება ამ ამოცანის ამოხსნა ერთი ლოგიკური ფორმულის მეშვეობითაც. ვინაიდან გვჭირდება, ორი მაინც უტოლობა შესრულდეს, ამოვწეროთ ყველა უტოლობათა წყვილის კონიუნქციები (ლოგიკური “და“) და ავიღოთ მათი დიზიუნქცია (ლოგიკური „ან“):
(A>=AM AND B>=BM) OR ( A>=AM AND C>=CM) OR (B>=BM AND C>=CM)ეს გამოსახულება თუ ჭეშმარიტია, ამოცანის პასუხი „YES” იქნება.
გარჩევა მომზადებულია ელდარ ბოგდანოვის მიერ.
პირველ რიგში, დავაკვირდეთ, რა ხდება კომუტატორის როუტერთან ან კომუტატორთან მიერთებისას - 1 პორტი კავდება იმ მოწყობილობაზე, რომელსაც მივუერთეთ კომუტატორი, 1 კი თვითონ კომუტატორზე. ამგვარად, კომუტატორი თუ X-პორტიანია, მისი ქსელში დამატებით ქსელში თავისუფალი პორტების რაოდენობა იზრდება (X-2)-ით.
ვინაიდან თავიდან ქსელში უკვე იყო 4 პორტი, დასმული ამოცანის მათემატიკური მოდელი შემდეგნაირი ხდება: (A * X + B * Y) ფუნქციის მინიმიზაცია (4 + 3 * X + 6 * Y ≥ N) პირობით მთელი X, Y-ისთვის.
პირობა ნიშნავს “საწყის ქსელს, რომელშიც 4 თავისუფალი პორტია, ვუმატებთ X ცალ 5-პორტიან კომუტატორს, ყოველი რომელთაგანიც 5-2=3 თავისუფალ პორტს დაუმატებს ქსელს და Y ცალ 8-პორტიან კომუტატორს, ყოველი რომელითაგანიც 8-2=6 თავისუფალ პორტს დაუმატებს ქსელს“. მიზნის ფუნქციაა დახარჯული ფულის ოდენობა.
საზოგადოდ, ასეთ ორცვლადიან ამოცანაში მოგვიწევს ერთ-ერთი ცვლადის მნიშვნელობის გადარჩევა, რის შემდეგაც მეორეს მნიშვნელობა ცალსახად განისაზღვრება. იმის გამო, რომ N შეიძლება მილიარდიც იყოს, ოპტიმალური X ან Y საკმაოდ დიდი შეიძლება გამოდგეს, ამიტომ საჭიროა დამატებითი ანალიზი ჩავატაროთ. ზოგად შემთხვევაში ერთ-ერთი ცვლადის (მაგალითად X-ის) მნიშვნელობა იქნება (უსჯ(A,B) / X)-ზე მცირე (ამის დასაბუთებას მკითხველს დავალებად დავუტოვებ). ჩვენი კონკრეტული A=3 და B=6-სთვის კი გავაკეთოთ რამდენიმე დაკვირვება:
1) ვთქვათ, A > B/2. მაშინ 2 5-პორტიან კომუტატორის ნაცვლად 1 ცალი 8-პორტიანის შეძენით ფულს დავზოგავთ. ამგვარად, მაქსიმუმ 1 ცალი 5-პორტიანი კომუტატორი უნდა ვიყიდოთ. ეს მოხდება იმ შემთხვევაში, თუ A < B და (N-4) mod 6 ≤ 3 (ანუ (N-4)/6 ცალი 8-პორტიანი კომუტატორის შეძენის შემდეგ 3 ან ნაკლები კომპიუტერი დაგვრჩა მისაერთებელი).
2) A = B/2 შემთხვევაში ვერაფერს ვზოგავთ, მაგრამ არც მეტს ვიხდით და ვინაიდან ერთნაირი ფასის შემთხვევაში 8-პორტიანებს ვანიჭებთ უპირატესობას, აქ წინა პუნქტის ანალოგიური ლოგიკა მუშაობს.
3) A ≤ B/2 შემთხვევაში მხოლოდ 5-პორტიანი კომუტატორები უნდა შევიძინოთ. როგორც ზოგადი მიდგომიდანაც და ამ ანალიზიდანაც ჩანს, სამი ვარიანტი გვაქვს: ყველა 5-პორტიანი შევიძინოთ, ყველა 8-პორტიანი შევიძინოთ, შევიძინოთ 1 ცალი 5-პორტიანი და დანარჩენები 8-პორტიანები. ამგავარად, ყველაზე მარტივი ამოხსნა იქნება ამ სამი სიტუაციისთვის ფასის დადგენა და იმ X და Y-ის არჩევა, რომლებიც მინიმალურს იძლევიან.
გარჩევა მომზადებულია ელდარ ბოგდანოვის მიერ.
ამ ამოცანას შეიძლება ორი მხრიდან მივუდგეთ. პირველი მიდგომაა, ყველა შესაძლო დროის მნიშვნელობა განვიხილოთ 00:00:00-დან 23:59:59-მდე (სულ 24*60*60=86400) და ყოველი მათგანისთვის შევამოწმოთ, შეიძლება თუ არა აჩვენებდეს მას საათი. მეორე მიდგომაა, საათზე ყოველი გაფუჭებული ნათურისთვის ვთქვათ, ჩართულია იგი თუ გამორთული, ანუ განვიხილოთ ყოველი ნათურისთვის 2 შესაძლო მდგომარეობა და მდგომარეობათა ყოველი სიმრავლისთვის (სულ 2^10 = 1024) შევამოწმოთ, რომ იგი სწორ დროს შეესაბამება.
დაწვრილებით განვიხილოთ პირველი მიდგომა. აქ შეგვიძლია როგორც ერთი ციკლი დავატრიალოთ 0-დან 24*60*60-მდე, რომელიც დროს წამებში განიხილავს, ასევე სამი ჩადგმული ციკლი ვამუშავოთ, რომლეებიც საათებს, წუთებს და წამებს შეესაბამება. საბოლოოდ მაინც მოგვიწევს HH:MM:SS ფორმატში დროის ყოველი ციფრი შევადაროთ ბინარული საათის შესაბამის სვეტს და დავადგინოთ, შეიძლება თუ არა ეს ციფრი იყოს საათზე ნაჩვენები.
აქ კვლავ ორი არჩევანი გვაქვს. პირველ რიგში, შეგვიძლია ციფრი ორობითი თვლის სისტემაში გადავიყვანოთ და თითოეული ბიტის მნიშვნელობა შევადაროთ სვეტის შესაბამის სიმბოლოს. ასევე შეიძლება ყველა სვეტს თავიდანვე (ჩვენი ციკლების გაშვებამდე) შევუსაბამოთ ორი რიცხვი: პირველი განსაზღვრავს ჩართული ნათურების განლაგებას, მეორე კი გაფუჭებულების. ეს რიცხვები სვეტის ორობით რიცხვად წაკითხვით მივიღოთ, ანუ პირველი ჩართულ ნათურებს ჩათვლის 1-იან ბიტებად, დანარჩენებს კი 0-ვან, მეორე კი 1-ანებად მხოლოდ გაფუჭებულებს ჩათვლის. ამ რიცხვების მიღების შემდეგ მარტივად, ბიტური ოპერაციებით შევძლებთ ციფრისთვის იმის დადგენას, შეიძლება თუ არა იგი საათის შესაბამის სვეტში იყოს ჩაწერილი.
მეორე მიდგომა, რომელშიც გაფუჭებული ნათურების ანთებულობის/ჩამქრალობის ყველა შესაძლო ვარიანტს ვიხილავთ, მეტი დეტალის განხილვას ითხოვს. ყოველი გაფუჭებული ნათურისთვის გადაწყვეტილების მისაღებად შეგვიძლია გამოვიყენოთ რეკურსია. რეკურსიის სიღრმეში, როდესაც ყოველი ნათურისთვის გადავწყვიტეთ, იგი სინამდვილეში ანთებული უნდა ყოფილიყო თუ არა, უნდა მოვახდინოთ შემოწმება, რომ საათზე ვალიდური დრო არის ნაჩვენები.
შემოწმება წუთებისთვის და წამებისთვის ერთნაირია: მეორე ციფრი [0, 9] შუალედში უნდა იყოს, პირველი კი [0, 5] შუალედში. საათების ციფრებზე კი მეორე ციფრი უნდა იყოს [0, 9] შუალედში, თუ პირველი 0 ან 1 არის, და [0, 3] შუალედში, თუ პირველი ციფრია 2. პირველი ციფრის სხვა მნიშვნელობები დაუშვებელია. და ბოლოს, თუ გაფუჭებული ნათურების მდგომარეობების გადარჩევა სწორი მიმდევრობით არ მოვახდინეთ (პირველი სვეტიდან დაწყებული ზემოდან ქვემოთ, მერე მეორე სვეტი და ასე შემდეგ), შედეგებს არ მივიღებთ დროის მიხედვით დალაგებულებს და ამიტომ უნდა შევინახოთ, დავალაგოთ და ისე გამოვიტანოთ.
გარჩევა მომზადებულია ელდარ ბოგდანოვის მიერ.
ამოცანებში, სადაც გვთხოვენ რაიმე პირობების დამაკმაყოფილებელი უმცირესი შესაძლო მნიშვნელობის პოვნას, ერთ-ერთი პირველი მიდგომა, რაც უნდა განიხილოთ, არის პასუხის ორობითი ძებნით გადარჩევა. როდის შეგვიძლია გამოვიყენოთ ორობითი ძებნა? ალბათ ყველაზე ზოგადი პასუხი ასეთია: როდესაც გვაქვს მონოტონური ფუნქცია, რომელსაც მხოლოდ 2 შესაძლო მნიშვნელობა აქვს (true, false) და გვჭირდება უმცირესი არგუმენტის მოძებნა, რომელშიც ფუნქციის მნიშვნელობა არის true. მაგალითად, როდესაც ზრდადობით დალაგებულ მასივში ვეძებთ რაღაც X-ზე უფრო დიდ ელემენტს, ჩვენი ფუნქცია კონკრეტული i არგუმენტისთვის (ინდექსისთვის) არის „i-ური ელემენტი მეტია X-ზე?“
ამგვარად, როდესაც ეჭვი გვაქვს, რომ ორობითი ძებნა გამოგვადგება, უნდა ვიპოვოთ ასეთი ფუნქცია (რომელიც თან ამოცანას ამოგვახსნევინებს =) ) და თუ მოვძებნეთ, მოვიფიქროთ როგორ შეიძლება კონკრეტული არგუმენტისთვის მისი მნიშვნელობა შევაფასოთ.
ამ ამოცანისთვის შემოვიღოთ ფუნქცია F(x), რომლის შინაარსია „შეიძლება, ისე დავხაზოთ წრფეები პირობის თანახმად, რომ ყოველ რეგიონში არაუმეტეს x წერტილი მოხვდეს?“. ვუპასუხოთ ორ შეკითხვას:
1) რატომაა ეს ფუნქცია მონოტონური? აშკარად, თუ შეიძლება რომ ყველა რეგიონში მქონდეს ≤x წერტილი, მაშინ ნებისმიერი y > x-ისთვის შეიძლება ≤y წერტილიც მქონდეს. და პირიქით, თუ ვერ ვახერხებ ისე რეგიონებად დაყოფას, რომ ყველგან იყოს ≤x, მაშინ y < x მნიშვნელობებისთვის ≤y მითუმეტეს არ გამოვა.
2) როგორ დავადგინო (საკმარისად სწრაფად), რომ შესაძლებელია წრფეების ისე დახაზვა, რომ ყოველ რეგიონში ≤x წერტილი მოხვდეს, ანუ F(x)-ის მნიშვნელობა? დავალაგოთ დახაზვადი წრფეები მათი y-კოორდინატის მიხედვით. მივყვეთ მათ ზემოდან ქვემოთ და თან ვითვალოთ, რამდენი წერტილი არის წრფის ზემოთ. როდესაც პირველად შეგვხვდება ისეთი წრფე, რომლის ზემოთაც x-ზე მეტი წერტილია მოთავსებული, ნათელი ხდება, რომ წინა წრფე აუცილებლად უნდა გაგვევლო (თუ ის ისედაც გავლებული გვაქვს, ესე იგი ამ ორ წრფეს შორის x-ზე მეტი წერტილია და F(x) მცდარია). ამგვარად, ამ შემთხვავაში წინა წრფეს გავავლებთ და იმ წერტილებს, რომლებიც მის ზემოთ მოხვდა, განხილვიდან ამოვიღებთ. ასე ვაგრძელებთ მანამ, სანამ არ დავხაზავთ K წრფეს ან არ გავივლით ყველა დახაზვად წრფეს. ბოლოს შევამოწმებთ, რომ ბოლო დახაზული წრფის ქვემოთ x-ზე ნაკლები ან ტოლი წერტილი მოთავსდა და თუ ასეა, F(x) ჭეშმარიტია.
მაშ ასე, გვიპოვნია მონოტონური ფუნქცია და ვისწავლეთ მისი მნიშვნელობის ეფექტურად დადგენა კონკრეტული არგუმენტისთვის. რაღაც პრეკალკულაციების შემდეგ (წრფეების დალაგება, წრფეებს შორის მოთავსებული წერტილების რაოდენობათა დათვლა) ეს ეფექტური დადგენა O(M) დრომდე დავა, რაც სავსებით საკმარისია მოცემული შეზღუდვების პირობებში. ალგორითმის საერთო მუშაობის დრო კი O(logN * M) გახდება.
გარჩევა მომზადებულია ელდარ ბოგდანოვის მიერ.
დაფის [i, j] უჯრაში მდგომი რიცხვი აღვნიშნოთ a[i, j] -თი.
a[x1,y1] a[x1,y1+1] … a[x1, y2]
a[x1+1,y1] a[x1+1,y1+1] … a[x1+1,y2]
…
a[x2,y1] a[x2,y2+1] … a[x2,y2]გამოსათვლელი მატრიცის i-ურ სტრიქონში ჯამი აღვნიშნოთ S[i]-თი.
S[x1] = a[x1,y1] + a[x1, y1+1] + … + a[x1, y2] =
= a[x1, y1] + k*a[x1, y1] + k^2*a[x1, y1] + … + k^(y2-y1)*a[x1, y1] =
= a[x1, y1] * (1 + k + k^2 + … + k^(y2-y1))რადგანაც a[i+1,j] = k^n * a[i,j], ამიტომ S[i+1] = S[i] *k^n.
დასათვლელი გვექნება ასეთი ჯამი: პასუხი =
S[x1] + S[x1+1] + … + S[x2] = S[x1] + k^n * S[x1] +
+ (k^n)^2 * S[x1] + … + (k^n)^(i1-i) * S[x1] = (1 + (k^n) +
+ (k^n)^2 + … + (k^n)^(x2-x1)) * a[x1,y1] * (1+k+k^2+…+k^(y2-y1))ამ ფორმულაში მიიღება სამი თანამამრავლი, სამივე გამოვთვალოთ ცალცალკე.
(1 + (k^n) + (k^n)^2 + … + (k^n)^(x2-x1)) და (1+k+k^2+…+k^(y2-y1)) ანალოგიური ფორმულებია, განვაზოგადოთ და გამოვთვალოთ (1 + x + x^2 + … + x^b) მოდულით 1 000 000 009.
a[x1, y1] = k^{(x1-1)*n + (y1-1)} ფორმულაც განვაზოგადოთ და გამოვთვალოთ k ^ b მოდულით 1 000 000 009.
ჩვენი ამოცანა დავიდა შემდეგი სამი ფორმულის გამოთვლაზე:
k ^ b მოდულით 1 000 000 009, სადაც k არის 1000–მდე, ხოლო b ეტევა long long ტიპში.
1 + a + a^2 + … + a^b მოდულით 1 000 000 009, სადაც a და b არიან 1 000 000 009–მდე.
ჯერ განვიხილოთ პირველი ამოცანა. გადაჭრა ხდება ცნობილი რეკურსიული ალგორითმით:
a–ს 2n ხარისხის (ლუწი ხარისხის) გამოსათვლელად გვჭირდება გამოვითვალოთ a^n და გადავამრავლოთ თავის თავზე, უფრო ზუსტად:
a^2n = (a^n * a^n) მოდულით 1 000 000 009
a^(2n+1) = (a * a^n * a^n) მოდულით 1 000 000 009
ახლა გადავიდეთ მეორე ამოცანაზე.
ვნახოთ ამ ამოცანის ამოხსნის ორი ცნობილი ხერხი. პირველი იყენებს ფაქტს, რომ 1 000 000 009 მარტივია:
გეომეტრიული პროგრესიის ჯამის ფორმულით 1 + a + a^2 + … + a^b = (a^(b+1) – 1 ) / ( a – 1) უნდა ვიპოვოთ ისეთი q, რომ q * (a-1) სადარი იყოს a ^ (b+1) – 1 - ისა მოდულით 1 000 000 009. ფერმას მცირე თეორემის მიხედვით, თუ a-1 არ იყოფა მოდულზე (ანუ ჩვენს შემთხვევაში a არ არის 1–ის ტოლი), q გამოითვლება ფორმულით (a-1) ^ (p-2) * (a^(b+1) – 1). ეს q იქნება ამ მეორე ამოცანის პასუხი. თუ a-1 არის 0–ის ტოლი, მაშინ 1 + a + a^2 + … + a^b = b.მეორე ხერხი რეკურსიული ალგორითმია, რომელიც კენტ და ლუწ ხარისხებს ისევ ცალცალკე იხილავს და ეყრდნობა ფაქტს:
1 + a + a^2 + … + a^(2k-1) = (1 + a + … + a ^ (k-1)) * (1 + a ^ k) მოდულით 1 000 000 009 [1 + a^k თანამამრავლს ვითვლით a^n-ის გამოთვლის ალგორითმით, ხოლო 1 + a + … + a^(k-1)-ს კი რეკურსიაში ჩასვლით]
1 + a + a^2 + … + a^(2k) = 1 + a * ( 1 + a + a^2 + … + a^(2k-1) ) მოდულით 1 000 000 009 ამ მეთოდის უპირატესობა ზემოხსენებულთან შედარებით ისაა, რომ მოდული შეიძლება ნებისმიერი ნატურალური რიცხვი იყოს, არ არის აუცილებელი მარტივობა.
ამრიგად, ამოცანის პასუხს ამ სამი მეთოდის გამოყენებით დავითვლით:
დავითვლით (1 + (k^n) + (k^n)^2 + … + (k^n)^(x2-x1))–სდავითვლით (1+k+k^2+…+k^(y2-y1)) –ს
დავითვლით k^{(x1-1)*n + (y1-1)}–ს
გადავამრავლებთ ერთმანეთზე და ავიღებთ 1 000 000 009–ზე მოდულს.
გასათვალისწინებელი ფაქტია, რომ პროგრამის ყოველ ბიჯზე long long-ს არ გადავცდეთ.
გარჩევა მომზადებულია ლევან ვარამაშვილის მიერ.
