Тренировка для школьников 28
Yüklə 76,57 Kb.
|
- Bu səhifədəki naviqasiya:
- A. Mərmər daşların götürülməsi
- B. Stepan və cütlüklər
- C. Yandırma
- D. Digi Comp II
- E. Düzxəttin tapılması
- F. Hakim problemləri
- G. Boruların təmizlənməsi
- H. Sazlama
- I. Bir zərbəyə
- J. Şam qutusu
| 17 May - Dünya Telekommunikasiya və İnformasiya Cəmiyyəti Gününə həsr olunan “Ali məktəb tələbələri arasında informatika üzrə Ümumrespublika Olimpiadası” (final) AMEA İnformasiya Texnologiyaları İnstitutu, 6 may 2017
A. Mərmər daşların götürülməsiBöyük qutuda bir və ya bir neçə rəngdə mərmər daşlar var. Hər rəngdə olan daşların sayı məlumdur. Siz ixtiyarı qaydada qutudan n sayda daş götürürsünüz və onları geri qaytarmırsınız. Bütün götürülən daşların eyni rəngdə olması ehtimalını tapın. Giriş. Bir neçə test ehtiva edir. Hər bir testin ilk sətri rənglərin col (1 ≤ col ≤ 50) sayını və n qiymətini ehtiva edir. İkinci sətirdə col sayda c1, c2, .., ccol tam ədədləri verilir. Burada ci (1 ≤ ci ≤ 50) – i rəngində olan mərmər daşların sayıdır. Məlumdur ki, 1 ≤ n ≤ c1 + c2 + .. + ccol. Çıxış. Hər bir test üçün ayrı sətirdə çıxarılan bütün daşların eyni rengdə olma ehtimalını verməli. Ehtimalları onluq nöqtədən sonra 4 işarə dəqiqliyi ilə verməli. Giriş verilənlərinə nümunə 1 8
13 3 2
5 6 7 5 4
12 2 34 13 17 Çıxış verilənlərinə nümunə 1.0000
0.3007 0.0350
B. Stepan və cütlüklərSon zamanlar Stepan ədədlər cütlükləri ilə maraqlanır, bundan başqa onu cütlüklərin ən böyük ortaq böləni də maraqlandırır. Bunu EBOB(x, y) kimi adlandıraq. İndi Stepanda n tam ədədi var və onu belə informasiya maraqlandırır: əgər 1 ≤ i, j ≤ n olarsa və i = EBOB(i, j) bərabərliyi doğrudursa, nə qədər (i, j) ədədlər cütlüyü mövcuddur. Ona bu çətin məsələni həll etməkdə kömək edin.
4
8
Sizin qarşınızda çox adi tor var. Lakin təcrübəli olimpiadaçı kimi Siz müşahidə etdiniz ki, o n təpə nöqtəsi və m tili olan əlaqəli qrafdır. Əgər hər hansı bir təpə nöqtəsi yandırılarsa, onda o yanacaq və bir saniyədən sonra onunla əlaqələnmiş bütün təpələr yanacaq, sonra isə bu təpələrlə əlaqəli olanlar yanacaq və s. Torun hansı təpə nöqtələrinin (hamısı eyni zamanda) yandırılacağı Sizə məlumdur. Sonuncu təpə nöqtəsi yanana qədər necə saniyə keçəcəyini və bunun hansı təpə nöqtəsi olacağını tapmaq lazımdır.
Növbəti sətirdə yandırılacaq təpələrin sayını ifadə edən k (1 ≤ k ≤ n) ədədi verilir. Növbəti sətir yandırılacaq k təpənin nömrələrini ehtiva edir. Çıxış. İlk sətirdə sonuncu təpənin yanacağı zamanı verməli. İkinci sətirdə bu təpənin nömrəsini verməli. Əgər belə təpələr bir necə dənə olarsa, onda nömrəsi kiçik olanı vermli. Giriş verilənlərinə nümunə 6 6
1 2 2 6
1 5 5 6
3 5 4 5
2 1 2
2 3
D. Digi Comp IIDigi Comp II – bu, şarların yuxarıdan daxil olaraq çeviricilər (açarlar) vasitəsilə təyin edilən müəyyən dövrə vasitəsilə aşağıya doğru yol tapdığı maşındır. Hər dəfə şar çevirici üzərinə düşdükdə çeviricinin vəziyyətindən asılı olaraq o ya sol, ya da sağ tərəfə gedir və bu zaman ceviricinin vəziyyəti də dəyişmiş olur. Abstrakt olaraq maşını istiqamətlənmiş qraf kimi hesab etmək olar. Burada hər bir çevirici çixiş dərəcəsi 2 olan təpə nöqtəsi kimi verilir. Sonuncu təpənin çıxış dərəcəsi 0-dır. Kommutatorun təpələrindən biri başlanğıc sayılır və giriş dərəcəsi 0-dır. Hər bir təpə (çevirici) (L/R) daxili vəziyyətdə olur. Şar başlanğıc təpədən start götürür və sonuncu təpəyə qədər yolla hərəkət edir və təpə - çeviricilərin daxili vəziyyətindən asılı olaraq hər bir təpə - çeviricidən çıxan sol və ya sağ tili seçir. Təpələrin daxili vəziyyəti şar keçdikdən sonra əksinə dəyişir. Şar həmişə aşağı düşür və dövrə düşə bilməz. Qrafın strukturunu, kommutatorun hər bir təpəsinin ilkin vəziyyətini və düşən şarların sayını göstərməklə bu maşını proqramlaşdırmaq olarmi? Hesablamanın nəticəsi sonda çeviricilərin vəziyyətidir. Maraqlıdır ki, cəmləmə, vurma, bölmə və hətda stabil evlilik problemləri kimi mürəkkəb alqoritmləri proqramlaşdırmaq olar. Lakin bu məsələ Tyurinqlə hesablanan məsələ deyil.
0 nömrəli təpə sonuncudur, 1 nömrəli təpə isə başlanğıcdır. Qrafda dövr yoxdur, yəni şar təpədən keçdikdən sonra bir daha ora qayıtmayacaq. Çıxış. Çeviricilərin son vəziyyətlərini təsvir edən M sayda 'L' və 'R' simvollarını (1-dən m-ə qədər ardıcıllıqla) verməli. Giriş verilənlərinə nümunə 5 3
L 2 3 R 0 3
L 0 0 Çıxış verilənlərinə nümunə RLL
E. Düzxəttin tapılmasıAnnabel və Riçard yeni oyunlar fikirləşməyi və bir-birinə qarşı oynamağı düşünürlər. Bir dəfə Annabel Riçard üçün yeni oyun fikirləşdi. Bu oyunda usta və oyunçu var. Usta vərəqdə n sayda nöqtə çəkir. Oyuncu elə düzxətt tapmalıdır ki, heç olmazsa p faiz nöqtə bu xətt üzərində yerləşmiş olsun. Richard və Annabelin ölçmək və çəkmək üçün yaxşı alətləri var. Buna görə də onlar nöqtənin düzxətt üzərində olub olmamasını yoxlaya bilirlər. Əgər oyunçu belə bir xətti tapa bilirsə, onda o qalib gəlir. Əks halda usta qalib gəlir. Yalnız bir problem var. Usta nöqtələri elə çəkə bilər ki, ümumiyyətlə uyğun xətti tapmaq mümkün olmasın. Onlara p faizdən, yəni ceil (n * p / 100) az olmayan nöqtənin yerləşdiyi düzxəttin mövcud olmasını yoxlamaq üçün asılı olmayan mexanizm lazımdır. İndi Siz onlara kömək edə və bu məsələni həll etmək üçün proqram yaza bilərsizniz.
Heç bir iki nöqtə ust-üstə düşmür. Çıxış. Əgər cari düzxətt mövcuddursa "possible", əks halda "impossible" verməli. 
F. Hakim problemləriNWERC təşkilatçıları qərara aldılar ki, müsabiqədə göndərilənlərin avtomatik qiymətləndirilməsini yaxşılaşdırsınlar, buna görə də onlar iki sistemdən istifadə edirlər: DOMjudge və Kattis. Hər bir göndərmə hər iki sistemlə qiymətləndirilir və sistemlərin razılaşdırılmasını dəqiqləşdirmək üçün qiymətləndirmənin nəticələri müqayisə edilir. Lakin sistemlər arasında əlaqənin qurulması zamanı nə isə düzgün getmir və indi juri yalnız hər iki sistemin bütün nəticələrini bilir, lakin hər bir göndərmənin nəticəsini yox! Buna görə Sizdən düzgün nəticələrin mümkün sayının müəyyənləşdirilməsinə kömək etməyiniz istənilir. Giriş. Ehtiva edir:
Hər bir sətir uzunluğu 5 və 15 diapazonunda kiçik hərflərdən ibarət simvollar sətri ehtiva edir. Çıxış. Hər iki sistem üçün eyni olan nəticələrin maksimal sayını verməli. Giriş verilənlərinə nümunə 5 correct wronganswer correct
correct timelimit wronganswer correct
timelimit correct
timelimit Çıxış verilənlərinə nümunə 4
G. Boruların təmizlənməsiLinçepinq çox mürəkkəb su nəqliyyatı sisteminə malikdir. Linçepinq ətrafında su çıxarılan bir neçə quyu var. Su sonra borular vasitəsilə başqa yerlərə daşınır. Hər bir boru quyudan şəhərin hər hansı bir yerinə qədər düz kanaldır. Bütün borular yerin eyni dərinliyindədirlər. Buna görə də iki boru kəsişirsə, onlar qovşaq əmələ gətirirlər. Xoşbəxtlikdən boru ilə daşıma sistemi elə qurulmuşdur ki, hər bir belə qovşaqda yalnız iki boru var. Quyular kəsişmiş sayılmırlar. İstənilən sayda boru (sıfır və ya ikidən çox daxil olmaqla) hər bir quyu ilə birləşmiş ola bilər. Qovşaqlar problem yaradır, belə ki, çirkab (qarışıqlar və digər elementlər) orda yığılıb qala bilər. Bu çirkab boruların çürüməsinə və dağılmasına, bu da öz növbəsində böyük boşluğun yaranmasına səbəb ola bilər. Bu cür boşluqlar Linçepinqdə tələbələrdə gipnoz effekti yaradadir ki, bu da onların tədqiqatlarına məhəl qoymamalarına və savadsız olaraq qalmalarına səbəb olur və nəticədə bu nəinki boru ilə ötürmə sisteminin, həmçinin cəmiyyətin öz strukturunun çökməsinə gətirib çıxarır. Buna görə də boruları mütəmadi olaraq təmizləmək lazımdır. Linçepinqin sudaşınma borularına cavabdeh olan Nordic Water Extraction and Redistribution Company (NWERC) şirkəti bu tapşırığı yerinə yetirmək üçün kifayət sayda robotlar parkına sahibdir. Robot borunun başladığı quyuya yerləşdirilə bilər. Sonra robot borunun daxilində sonuna qədər gedərək yolundakı bütün qovşaqları təmizləyir. Sona çatdıqdan sonra robot dönərək çıxdığı quyuya geri qayıdır. Robotların toqquşmasının qarşısını almaq üçün hökumət qərarlarında nəzərə alınır ki, iki borunun kəsişməsi zamanı onlardan yalnız maksimum birindən robot geçə bilər. Belə ki, təmizləmə zamanı bütün su təchizatı sistemini bağlamaq lazım gəldiyi üçün (başqa hökumət nizamlanması) NWERC eyni zamanda işləməyə başlayan təmizlikçi robotların bir dəstini istifadə edərək hər şeyi tez təmizləmək istəyir. Siz yoxlamalısınız ki, bunu etmək mümkündürmü, yəni, robotları elə bir neçə boru dəstinə yerləşdirmək olar ki, robotlar bütün qovşaqları təmizləyə bilsinlər və bu zaman iki robotun toqquşma riski olmasın.
Hər bir boru yalnız bir quyu ehtiva edir – onun başladığı quyu. İkidən çox borunun birləşdiyi istənilən nöqtə quyu adlanır. İstənilən iki borunu birdən çox olmayan ortaq nöqtə ayırır. İki borunun ortaq nöqtəsi onlardan birinin və ya hər ikisinin sonu ola bilər. Bütün borular müsbət uzunluqdadırlar. Çıxış. Bütün qovşaqları təmizləmək mümkündürsə, "possible" verməli. Əks halda "impossible" verməli.
H. SazlamaSizin müasir sazlayıcı bu məsələdə Sizə kömək edə bilməz. Çox sayda üsul mövcuddur ki, bunların vasitəsilə kod sazlama və icra arasında müxtəlif cür rəftar edə bilər və bu nə zaman baş verirsə, daha sadə sazlama formasına keçmək mümkündür. Beləliklə, Siz və Sizin printf reallaşdırma zamanı səhv verməsinə gətirib çıxaran kod sətrinin axtarılması ilə məşğulsuz. Bununla belə Sizin bəxtiniz gətirib: printf əmrinin bu proqrama əlavə edilməsi nə səhvə (o onsuz da kodun cari sətrində verilir), nə də icra zamanına (uzağı vacib deyil) təsir göstərmir. Beləliklə, həttə bu cür yanaşma, printf əmrinin hər bir sətrin əvvəlində verilməsi, proqramın səhv verməsinə qədər icrası və sonuncu çap edilən sətrin yoxlanılması zamanı işləyəcək. Lakin koda hər bir printf əmrinin əlavə edilməsi müəyyən vaxt tələb edir və proqramın çox sətri olur. Buna görə də ən yaxşı plan ondan ibarət ola bilər ki, printf əmrini proqramın ortasında yerləşdirək. Sonra isə proqramı icra edib yoxlamaq lazımdır ki, o printf əmrinin daxil edildiyi yerə qədər icra olunurmu, bundan sonra axtarışı kodun birinci və ya ikinci yarısında davam etdirmək olar. Lakin yenə də, proqramın icrası çox vaxt ala bilər, buna görə də daha səmərəli zaman strategiyası orta ola bilər. Elə proqram tərtib edin ki, səhv sətrinin (harda olmasından asılı olmayaraq) ən pis halda minimal zamanda tapılmasını təmin etsin, nəzərə alaq ki, Siz öz printf əmrlərinizi yerləşdirmək üçün optimal strategiya seçirsiniz. Biz yeni versiyanı 5 saatdan sonra icra edirik, buna görə də məsələ çətinləşir və mümkün qədər tez həll edilməlidir.
Siz artıq proqramı bir dəfə icra etmişsiniz və onun harda səhv verdiyini bilirsiniz. Çıxış. Optimal strategiyanın istifadə edilməsi zamanı səhv verən sətrin daha tez tapılma zamanını verməli.
I. Bir zərbəyəBu yaxınlarda Janin özünün yerli oyun dükanına getdi və öz kompüteri üçün yeni “Bir zəbəyə” mini-qolf oyununu aldı. Adından göründüyü kimi oyunun məqsədi ondan ibarətdir ki, şarın çuxura düşməsi üçün yalnız bir zərbə vurula bilər. Oyunda həmçinin, “kəs-doğra” stilində oyundan elementlər də istifadə edilir: oyun sahəsində bir neçə divar yerləşdirilib və bu divarlar topun zərbəsindən sonra məhv ediləcəklər. Müvəffəqiyyətli zərbələrin sayı dağıdılmış divarların sayından asılıdır. Buna görə də Janin sual verir: “Bir zərbəyə” icra edildikdə maksimum neçə divar məhv ediləcək. Bu məsələdə Siz sahəni şarın cari vəziyyətinin koordinat sisteminin əvvəlində olduğu dekart sistem kimi təsəvvür edə bilərsiniz. Divarlar bu müstəvidi koordinat oxlarına (x və ya y) paralel olan kəsişməyən parçalardır. Şarın diametri çox kiçikdir və bir nöqtə kimi qəbul edilir.
Hər dəfə şar divara toxunan zaman iki hal baş verir:
Şarın özünü aparması zərbənin gücündən asılıdır. Xüsusi olaraq, optimal zərbə üçün şarı müəyyən qədər diyirlətmək və sonra bir neçə divara zərbə vurmaq lazım gələ bilər, bundan sonra şar çuğura düşəcək. Giriş. Ehtiva edir:
Çuxur koordinat müstəvisinin başlanğıcında və divar üzərində deyil. Divarlar bir birinə toxunmur və kəsişmirlər. Heçbir divar tamamilə x və ya y oxu üzərində yerləşmir. Bütün koordinatlar tam ədədlərdir və mütləq qiymətcə 1000-i aşmır. Çıxış. Əgər zərbədən sonra şarın çuxura düşməsi mümkün deyilsə, “impossible” verməli. Əks halda “Bir zərbəyə” oyununda bir zərbə ilə məhv ediləcək divarların maksimal sayını verməli.
J. Şam qutusuRita öz doğum gününü xoşlayır. O həqiqətən də "Happy Birthday" melodiyası altında şamlara üfürərkən xoşbəxtdir. 4 yaşından başlayaraq o hər il doğum günündə şamlarını (hər il bir ədəd artıq) şam qutusunda yerləşdirir. Onun kiçik qardaşı Teo da bu işi özünün 3 yaşından etməyə başladı. Rita və Teonun qutuları şamlar kimi eyni cür görünür. Bir dəfə Rita qutusunda neçə şam olduğunu saymaq qərarına gəldi:
O indi başa düşdü ki, Teo öz qutusundan bir neçə şamı onun qutusuna qoymuşdur. Siz Ritaya öz qutusundakı şamların sayını düzəltməyə kömək edə bilərsinizmi? Rita və Teonun yaş fərqlərini, Ritanın qutusundakı şamların sayını və Teonun qutusundakı şamların sayını nəzərə alaraq Ritanın qutusunda lazım olduğu qədər şamın qalması üçün o öz qutusundan neçə şamı kənarlaşdırmalıdır. Giriş. İlk sətirdə Rita və Teonun yaşlarının d (1 ≤ d ≤ 20) fərqi. İkinci sətirdə Ritanın qutusundakı şamların r (4 ≤ r < 1000) sayı. Üçüncü sətirdə Teonun qutusundakı şamların t (0 ≤ t < 1000) sayı.
2 26 8 Çıxış verilənlərinə nümunə 4
/ Yüklə 76,57 Kb. Dostları ilə paylaş:
|
