Тренировка для школьников 28



Yüklə 68,73 Kb.
tarix25.05.2018
ölçüsü68,73 Kb.
#45806

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ə XII Ümumrespublika Olimpiadası” (I tur)

Bakı Mühəndislik Universiteti, 29 aprel 2017





Məsələ

A - Kibrit çöpləri

B - Salam, Piroq!

C - 2^n-çi olmaq istəyirsinizmi?

D - Axmaq oyunu

E - Eustace-Alex

F - Marşrut taksi

G - Yolların ləğvi

H - Ümumi qiymətlər

I - Bu qətldir!

J - İkinin dərəcəsi



A - Kibrit çöpləri


Tərəfi bir kibrit çöpündən ibarət olan N kvadratı müstəvi üzərinə düzmək üçün minimum hansı sayda kibrit çöpü lazımdır? Kibrit çöplərini sındırmaq və bir-birinin üzərinə qoymaq olmaz. Kvadratların təpə nöqtələri kibrit çöplərinin uclarının birləşdiyi nöqtələr, tərəfi isə kibrit çöplərinin özüdür.

Kvadratların N sayına görə elə proqram tərtib edin ki, onu düzəltmək üçün lazım olan kibrit çöplərinin minimum sayını tapsın.


Giriş verilənləri

Giriş faylında yeganə bir tam N (1 ≤ N ≤ 109) ədədi verilir.


Çıxış verilənləri

Çıxış faylının yeganə sətrində bir tam ədəd - verilmiş sayda kvadratların qurulması üçün tələb olunan kibrit çöplərinin minumum sayını verməli.


Giriş verilənlərinə nümunə

4
Çıxış verilənlərinə nümunə

12


B - Salam, Piroq!


Picceriya Pizazz öz alıcılarına imkan daxilində daha tez pizza çatdıra bilməsi ilə fəxr edir. Bədbəxtçilikdən çatdırma üçün yalnız bir sürücü tutmaq olar. Çatdırmadan əvvəl o müəyyən sayda (1-dən 20-yə qədər) sifariş gəlməsini gözləyir. Sürücü bütün sifarişlərin çatdırılması üçün, hətta eyni bir yerə bir neçə dəfə getmək tələb olunsa da, ən qısa yolu seçməyə üstünlük verir. Çatdırılma sonunda sürücü cari yerinə, yəni picceriyaya qayıtmalıdır. Sizə belə marşrutu seçməyə imkan verən proqram yazmaq lazımdır.

Giriş verilənləri


İlk sətirdə sifarişlərin n (1n20) sayı verilir. Sonra hər biri n + 1 tam ədəd ehtiva edən n + 1 sətir verilir. Bu ədədlər picceriya (onun nömrəsi 0-dır) və sifarişlərin verildiyi n yer (onlar 1-dən n-ə qədər nömrələnir). i sətrinin j-ci qiyməti i yerindən j yerinə yol boyunca başqa yerlərə baş çəkmədən birbaşa getmə vaxtına işarə edir. Qeyd edək ki, yollarda tıxacların və işıqforların olması səbəbindən ij yerləri arasında birbaşa gediş daha tez olmaya bilər. Gediş vaxtı simmetrik deyil. Yəni, i-dən j-yə birbaşa gediş vaxtı j-dən i-yə birnaşa gedış vaxtı ilə eyni olmaya bilər.

Çıxış verilənləri


Pizzanı bütün sifarişçilərə çatdırmaq və geriyə qayıtmaq üçün lazım gələn minimal vaxtı verməli.
Giriş verilənlərinə nümunə

3

0 1 10 10



1 0 1 2

10 1 0 10

10 2 10 0
Çıxış verilənlərinə nümunə

8

C - 2^n-çi olmaq istəyirsinizmi?

Oyunçuda 1$ var və ondan ardıcıl olaraq n suala cavab vermək tələb olunur. Hər bir sualdan əvvəl o:


  • oyunu dayandıra və onda olan pulları götürə bilər.

  • suala cavab verə bilər. Əgər cavab doğru deyilsə, oyunu heçnəsiz tərk edir. Cavab doğru olarsa, pulun məbləği iki dəfə artır və növbəti suala keçilir.

Sonuncu suala cavab verərək oyunçu pulları götürür. Oyunçu uduşun gözlənilən məbləğinin maksimum olmasını istəyir.

Hər bir verilən suala oyunçu p ehtimalla doğru cavab verə bilər. Hesab edin ki, p ehtimalı t..1 parçasında bərabər paylanmışdır.


Giriş verilənləri

Hər bir sətir ayrıca testdir və iki ədəddən ibarətdir: n (1n30) tam qiyməti və həqiqi t (0t1) qiyməti. Sonuncu sətir 0 0-dan ibarətdir və emal edilmir.


Çıxış verilənləri

Hər bir nt ədədlər cütlüyü üçün ayrıca sətirdə oyunçunun yüksək səviyyədə oynadığını nəzərə alaraq uduşun gözlənilən maksimal məbləğini verin. Nəticə onluq nöqtədən sonra 3 rəqəm saxlamaqla verilməlidir.



Giriş verilənlərinə nümunə


1 0.5

1 0.3


2 0.6

24 0.25

0 0

Çıxış verilənlərinə nümunə


1.500

1.357


2.560

230.138




D - Axmaq oyunu


Nadinc meymun, eşşək, keçi və əyripəncə ayı balası axmaq oyunu oynamağı qərara aldılar. Bilindiyi kimi, ilk oyunda kimdə kozır ən kiçik qiymətlidirsə, o gediş edir. Buna görə də kartları payladıqdan sonra dördü də eyni vaxtda özlərində olan ən kiçik qiymətli kozırı söyləyirlər. Xüsusilə də hər biri 6-dan 14-ə qədər və ya 0 ədədini söyləyirlər (10-dan böyük ədədlər şəkillərə uyğundur: valent, dama, karol və ya tuz, sıfır kozırın olmamasını bildirir).

Sizə hansı ədədlərin söyləndiyi məlumdur. Bu kompaniyada yalandan söyləyənlərin sayını təyin edin.

Oyunda hər biri 4 mastın 9 kartı olan 36 kartdan ibarət oyun kartından istifadə edilir. Hər bir oyunçuya 6 kart paylanır, dəstin növbəti kartı açılır və onun mastı bu oyun üçün kozırı təyin edir.
Giriş verilənləri

Oyunçuların söylədikləri dörd tam ədəd verilir. Ədədlər boşluqla ayrılir. Hər bir ədəd ya 0, ya da 6-dan 14-ə qədər ədəddir.


Çıxış verilənləri

Yeganə ədədi - yalandan söyləyənlərin sayını verin.


Giriş verilənlərinə nümunə1

10 7 11 0


Çıxış verilənlərinə nümunə1

0
Giriş verilənlərinə nümunə2

6 10 10 11
Çıxış verilənlərinə nümunə2

1

E - Eustace-Alex


Müvəffəqiyyətlə keçirilən əməliyyatdan sonra Ştirlis alman ordusunun sayını təyin edə bildi. Təbii ki, belə informasiyanı sovet ordusu qərargahında dörd ildir ki, gözləyirdilər. Qərargahla əlaqə saxlamaq üçün Ştirlis n rabitəçidən istifadə edir. Hər bir rabitəçi Ştirlisdən məlumatları qərargaha çatdırmalıdır. Ştirlis, məharətli kəşfiyyatçı kimi öz məktubunu növbəti şəkildə şifrələdi: hər bir rabitəçiyə o eyni ədədi verdi – ordunun sayını, lakin öz say sistemində və rabitəçilərdə bütün say sistemlərinin əsası cüt-cüt qarşılıqlı sadədir. Radioqramın ötürülməsindən sonra Myullerin xəfiyyələri hər bir məlumatın son simvolunu təyin edə bildilər. Siz ştatlı proqramçı işləyirsiniz və müəyyən etməlisiniz ki, Ştirlis öz məlumatında hansı minimal ədədi göndərə bilər. Myuller sizdən fərqli olaraq ikilik kodu xoşlamır, buna görə də o istəyir ki, bu ədədi onluq say sistemində verəsiniz.
Giriş verilənləri

Birinci sətirdə Ştirlisin rabitəçilərinin sayı - n verilir. Növbəti sətirdə Ştirlisin rabitəçilərə məlumatı verdiyi say sisteminin əsası - n sayda ai (2ai36 ) ədədi verilir. Üçüncü sətirdə isə boşluqla ayrılmış n sayda hər bir məlumatın son simvolu ci (0ci < ai; ci - 09 arası hər hansı bir rəqəm, ya da AZ hərflərindən biridir) verilir.


Çıxış verilənləri

Ştirlisin göndərə biləcəyi minimal ədədi onluq say sistemində verməli.



Giriş verilənlərinə nümunə


2

6 13


1 B

Çıxış verilənlərinə nümunə


37

F - Marşrut taksi


Pik saatında dayanaçağa eyni marşrutla hərəkət edən üç marşurut taksi gəldi və həmin anda sərnişinlərlə doldular. Sürücülər müəyyən etdilər ki, müxtəlif marşrutlardakı sərnişinlərin sayı müxtəlifdir və hər marşrutda eyni sayda sərnişin olması üçün onların bir hissəsinin yerini dəyişdirmək qərarına gəldilər. Bu zaman ən az neçə sərnişinin yerinin dəyişəcəyini təyin etmək lazımdır.

Giriş verilənləri


Birinci, ikinci və üçüncü marşrutlardakı uyğun sərnişinlərin sayını ifadə edən 100-dən böyük olmayan üç natural ədəd verilir.

Çıxış verilənləri


Yeganə ədədi - yerlərini dəyişdirmək lazım gələn sərnişinlərin minimal sayını verin. Əgər bu mümkün deyilsə, böyük hərflərlə "IMPOSSIBLE" sözünü verin.
Giriş verilənlərinə nümunə1

1 2 3
Çıxış verilənlərinə nümunə1

1
Giriş verilənlərinə nümunə2

99 100 100


Çıxış verilənlərinə nümunə2

IMPOSSIBLE


G - Yolların ləğvi


n şəhərdən və bu şəhərləri birləşdirən m ikiistiqamətli yollardan ibarət şəbəkə var. İlk k şəhər əhəmiyyətlidir. Sizə elə minimal sayda yolları ləğv etmək lazımdır ki, qalan şəbəkədə əhəmiyyətli şəhərlərdən keçən dövrlər olmasın. Dövr elə ardıcıllıqdır ki, ən azı elə üç şəhər vardır ki, hər bir qonşu şəhərlər cütlüyü öz aralarında yolla birləşmiş olsun, birinci və sonuncu şəhərlər də həmçinin birləşmiş olsunlar.

Giriş verilənləri

Birinci sətir testlərin t (1t20) sayını ehtiva edir.

Hər bir test üç tam n, mk (1n10000, 1m50000, 1kn) ədədlərini – uyğun olaraq şəhərlərin, yolların və əhəmiyyətli şəhərlərin sayını ehtiva edən sətirlə başlayır. Şəhərlər 0-dan n–1-ə qədər ədədlərlə nömrələnir. Növbəti m sətrin hər biri yolla birləşdirilmiş müxtəlif şəhərlərin nömrələrini əks etdirən iki aibi (0i < m) tam ədədlərini ehtiva edir.

Məlumdur ki, 0ai, bi < naibi. İki şəhər arasında yolların sayı birdən çox deyil.



Çıxış verilənləri

1-dən t-yə qədər nömrələnmiş hər bir test üçün "Case #i: " sətrini, ardına da, tam ədədi – ləğv ediləcək minimal sayda yolların sayını verin (heç olmazsa bir vacib şəhərin belə daxil olduğu dövrün olmadığı yollar ləğv edilməlidir).
Misal

Birinci misalda n = 5 şəhər və m = 7 yol vardır. 01 şəhərləri əhəmiyyətlidir. (0, 1) və (1, 2) yollarını silmək olar, bundan sonra qalan şəbəkə vacib şəhərlər olan dövrlər ehtiva etməyəcək. Qeyd edək ki, qalan şəbəkədə vacib olmayan şəhərlərdən keçən dövr var. Məsələdə qoyulan tələbləri yerinə yetirmək üçün iki tili silməyin bir neçə üsulu vardır. Bir tili silməklə vacib şəhərlərdən keçən bütün dövrləri ləğv etmək olmaz.


Giriş verilənlərinə nümunə

2

5 7 2



0 1

1 2


1 4

0 2


2 4

2 3


3 4

8 12 2


0 2

0 4


0 5

2 3


2 7

3 1


3 4

4 6


5 6

5 7


6 1

7 1
Çıxış verilənlərinə nümunə

Case #1: 2

Case #2: 4


H - Ümumi qiymətlər


n sayda a1 , a2 , ... , an tam ədədləri artan ardıcıllıqda verilir. Sizə həmçinin ij (1ijn) indeksli bir neçə sorğu verilir. Hər bir sorğu üçün ai , ... , aj arasında ən çox rast gəlinən ədədi təyin edin.
Giriş verilənləri

Bir neçə test ehtiva edir. Hər bir test iki tam nq (1n, q100000) ədədlərini ehtiva edən sətirlə başlayır. Növbəti sətir boşluqla ayrılmış n sayda a1, ... , an (hər bir i ∈ {1, ..., n} üçün -100000ai100000) tam ədədlərini ehtiva edir. Hesab edin ki, hər bir i ∈ {1, ..., n - 1} üçün: aiai+1. Növbəti q sətrin hər biri sorğunun indekslərinin sərhədlərini ifadə edən iki ij (1ijn) tam qiymətlərindən ibarət bir sorğu ehtiva edir.

Sonuncu testdən sonra tək 0 ehtiva edən sətir gəlir.
Çıxış verilənləri

Hər bir test üçün yeganə ədədi – verilmiş intervaldakı ən çox rast gəlinən ədədin rastgəlmə sayını verməli.


Giriş verilənlərinə nümunə

10 3


-1 -1 1 1 1 1 3 10 10 10

2 3


1 10

5 10


0
Çıxış verilənlərinə nümunə

1

4



3

I - Bu qətldir!


Bir dəfə detektiv Saykat qətl işini tədqiq etdi. Cinayətin olduğu yerdə o hər bir pilləsində bir ədəd yazılmış pilləkən aşkar etdi. O bundan şübhələndi və bütün keçilən ədədləri yadda saxlamaq qərarına gəldi. Keçilən ədədləri xatırlayaraq o onlarda qanunauyğunluq tapdı. Detektiv pilləkəndəki hər bir ədəd üçün pilləkəndə əvvəlcədən gördüyü və cari pillədəki ədəddən kiçik olan bütün ədədlərin cəmini yazmaq qərarına gəldi. Detektivin gündəliyində yazılmış bütün ədədlərini cəmini hesablayın.
Giriş verilənləri

İlk sətir testlərin t (t10) sayını ehtiva edir. Sonra 2t sayda sətir verilir. İlk sətir pillələrin n (1n105) sayını ehtiva edir. Növbəti sətir pillələrdə yazılmış n ədəd ehtiva edir. Bütün yazılmış ədədlər 0-dan 106-a qədərdir.


Çıxış verilənləri

Hər bir test üçün ayrı sətirdə yekun cəmi verin.


Giriş verilənlərinə nümunə

1

5



1 5 3 6 4
Çıxış verilənlərinə nümunə

15

J - İkinin dərəcəsi


Məlumdur ki, istənilən tam, mənfi olmayan n üçün 2n ədədi ikilik say sistmeində çox sadə şəklə malikdir: yazılışında yüksək mərtəbədə (bitdə) 1 dayanır, sonra isə n sayda sıfır yazılır. Onluq say sistemində isə bu ədədlər belə birmənalı şəkildə yazılmır. Lakin bu ədədlər arasında elələrinə rast gəlmək olar ki, onlar 1 rəqəmi ilə başlansın.

Verilmiş diapazonda neçə belə ədəd olduğunu müəyyən edin.


Giriş verilənləri


Boşluqla ayrılmış n1 və n2 (0 ≤ n1 < n2 ≤ 109) tam ədədləri.

Çıxış verilənləri


İkinin dərəcələri olan, [2n1; 2n2] intervalında yerləşən və onluq say sistemində birinci rəqəmi 1 olan ədədlərin sayını ekrana verin.
Giriş verilənlərinə nümunə

0 10
Çıxış verilənlərinə nümunə



4


/

Yüklə 68,73 Kb.

Dostları ilə paylaş:




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2024
rəhbərliyinə müraciət

    Ana səhifə