XIX ÍÀÖÈÎÍÀËÍÀ ÎËÈÌÏÈÀÄÀ ÏÎ ÈÍÔÎÐÌÀÒÈÊÀ

Íàöèîíàëåí êðúã, Ãàáðîâî, 3?4 ìàé 2003 ã.

 

 

 

Çàäà÷à  1.1   ÏÐÈßÒÅËÈ

 

 åäèí ãðàä  èìà  N  æèòåëè, çà íÿêîè äâîéêè îò êîèòî ñå çíàå, ÷å ñà ïðèÿòåëè. Îò èçâåñòíàòà ìàêñèìàòà ?Ïðèÿòåëèòå íà ìîèòå ïðèÿòåëè ñà è ìîè ïðèÿòåëè? ñëåäâà, ÷å àêî A è B ñà ïðèÿòåëè è B è C ñà ïðèÿòåëè, òî  A è C ñúùî ñà ïðèÿòåëè.

Äà ñå íàïðàâè ïðîãðàìà FRIEND.EXE, êîÿòî íàìèðà áðîÿ íà õîðàòà â íàé-ãîëÿìàòà ãðóïà îò ïðèÿòåëè.

Ïúðâèÿò ðåä íà ñòàíäàðòíèÿ âõîä ñúäúðæà ÷èñëàòà N è M, êúäåòî  N  å áðîÿò íà æèòåëèòå (10≤ N≤ 30000), à M (0≤ M≤ 500000) å áðîÿò íà äàäåíèòå äâîéêè ïðèÿòåëè. Íà âñåêè îò ñëåäâàùèòå M ðåäà èìà ïî äâå ÷èñëà ? íîìåðàòà íà äâîéêà ïðèÿòåëè A, B (1≤ A≤ N, 1≤ B≤ N, A≠ B), êàòî ìåæäó äàäåíèòå äâîéêè ìîæå äà èìà è ïîâòàðÿùè ñå.

Íà ñòàíäàðòíèÿ èçõîä äà ñå èçâåäå åäíî ÷èñëî ? ìàêñèìàëíèÿò áðîé íà õîðàòà â îáðàçóâàíèòå ãðóïè îò ïðèÿòåëè.

 

ÏÐÈÌÅÐ

Âõîä

10 12

1 2

3 1

3 4

5 4

3 5

4 6

5 2

2 1

7 10

1 2

9 10

8 9

Èçõîä

6

 

XIX ÍÀÖÈÎÍÀËÍÀ ÎËÈÌÏÈÀÄÀ ÏÎ ÈÍÔÎÐÌÀÒÈÊÀ

Íàöèîíàëåí êðúã, Ãàáðîâî, 3?4 ìàé 2003 ã.

 

 

Çàäà÷à 1.2  ÈÃÐÀ

 

Äâàìà èãðà÷è A è B èãðàÿò ñ ðåäóâàùè ñå õîäîâå èãðà, ïðè êîÿòî öåëèòå ÷èñëà îò 1 äî N âêëþ÷èòåëíî ñà íàïèñàíè â åäíà ðåäèöà è èãðà÷èòå ãè çàäðàñêâàò ñúãëàñíî ñëåäíèòå ïðàâèëà: Êîãàòî A å íà õîä (íåçàâèñèìî äàëè å ïúðâè èëè âòîðè), òîé òðÿáâà äà èçáåðå åäíî ÷åòíî ÷èñëî, êîåòî äîòîãàâà íå å áèëî çàäðàñêàíî, äà ãî çàäðàñêà è äà çàäðàñêà îùå âñè÷êè äåëèòåëè íà èçáðàíîòî ÷èñëî (âêë. è ÷èñëîòî 1), êîèòî íå ñà çàäðàñêàíè. Êîãàòî B å íà õîä, òîé òðÿáâà äà çàäðàñêà èçáðàíî îò íåãî íå÷åòíî ÷èñëî, êîåòî äîòîãàâà íå å áèëî çàäðàñêàíî è àíàëîãè÷íî äà çàäðàñêà îùå âñè÷êè äåëèòåëè íà òîâà èçáðàíî ÷èñëî, êîèòî íå ñà çàäðàñêàíè. Èãðàòà ãóáè òîçè èãðà÷, êîéòî íå ìîæå äà íàïðàâè õîä, êîãàòî å íåãîâ ðåä, à äðóãèÿò èãðà÷ ïå÷åëè.

 

Íàïèøåòå ïðîãðàìà GAME.EXE, êîÿòî èãðàå çà èãðà÷à A ñðåùó ïðîãðàìà íà æóðèòî, èãðàåùà çà èãðà÷à B.  Ïðîãðàìàòà òðÿáâà äà ìîæå äà èãðàå, êàêòî êîãàòî èãðà÷úò A çàïî÷âà ïðúâ, òàêà è êîãàòî çàïî÷âà âòîðè. Äàííèòå çà åäíî òåêóùî ñúñòîÿíèå íà èãðàòà ïðîãðàìàòà ùå ïîëó÷è íà ôàéë ÷ðåç ñòàíäàðòíèÿ ñè âõîä. Âõîäíèÿò ôàéë ñúäúðæà öÿëîòî ïîëîæèòåëíî ÷èñëî N  < 100 è ñëåä åäèí èíòåðâàë âúâ ôàéëà ñà çàïèñàíè ñëÿòî åäèí äî äðóã çíàöè A, B èëè O (ãëàâíè ëàòèíñêè áóêâè, îáùî N áðîÿ), âñåêè â ñúîòâåòñòâèå ñ ïîðåäíîòî öÿëî ÷èñëî â ðåäèöàòà 1, 2, 3, ..., N. Áóêâàòà A îçíà÷àâà, ÷å ÷èñëîòî íà ìÿñòîòî, íà êîåòî å òÿ ? å çàäðàñêàíî îò èãðà÷à A ïðè íÿêîé íåãîâ ïðåäèøåí õîä, áóêâàòà B îçíà÷àâà, ÷å ñúîòâåòíîòî ÷èñëî å áèëî çàäðàñêàíî îò èãðà÷à B, à áóêâàòà O îçíà÷àâà, ÷å ÷èñëîòî âñå îùå íå å çàäðàñêàíî. ×èñëîòî N íå ñå ïðîìåíÿ ïî âðåìå íà åäíà èãðà. Âàøàòà ïðîãðàìà òðÿáâà äà èçâåäå íà ñòàíäàðíèÿ ñè èçõîä åäíî öÿëî ÷èñëî, ïîêàçâàùî èçáðàíîòî îò èãðà÷à A çà òåêóùèÿ ìó õîä.

 

Ïðèìåð 1. Ïðè N = 9, àêî èãðà÷úò A çàïî÷âà ïðúâ, Âàøàòà ïðîãðàìà ùå ïîëó÷è ïðè ïúðâîòî èçâèêâàíå âõîäíè äàííè:  9 OOOOOOOOO.

Ïðèìåð 2. Àêî èãðà÷úò A å çàïî÷íàë âòîðè, òîãàâà âúçìîæíè âõîäíè äàííè, êîèòî ìîæå äà ïîëó÷è Âàøàòà ïðîãðàìà ñëåä òðåòèÿ õîä íà B ñà 9 BABAOOBAB, êàòî òîâà ìîæå äà ñòàíå, àêî Âàøàòà ïðîãðàìà å èãðàëà òàêà, ÷å íà ïúðâèÿ ñè õîä å èçáðàëà  ÷èñëîòî 2, à íà âòîðèÿ ñè õîä ? ÷èñëîòî 8.

 

Ïî âðåìå íà åäíà èãðà ïðîãðàìàòà Âè ùå áúäå èçâèêâàíà ìíîãîêðàòíî, êàòî âñåêè ïúò ùå ïîëó÷àâà äàííè, îòðàçÿâàùè òåêóùîòî ñúñòîÿíèå ñëåä ïîðåäíèÿ õîä íà èãðà÷à B. Ïðîãðàìàòà íà æóðèòî èãðàå âèíàãè êîðåêòíî è äåòåðìèíèðàíî. Âàøàòà ïðîãðàìà âèíàãè ùå  ïîëó÷àâà êîðåêòíè âõîäíè äàííè, îòðàçÿâàùè òî÷íî ïðîòè÷àíåòî íà èãðàòà. Íå å ðàçðåøåíî ïðîãðàìàòà Âè äà ÷åòå èëè çàïèñâà äðóãè ôàéëîâå, îñâåí ñòàíäàðòíèÿ âõîä è èçõîä.

 

Ïðè ïîáåäà ïîëó÷àâàòå 10 ò., à ïðè çàãóáà èëè ïðè íåêîðåêòåí õîä ? 0 ò. Âñÿêà èãðà ùå áúäå ðàçèãðàâàíà ñ ïðîãðàìàòà ïîâå÷å îò âåäíúæ. Ïðè ðàçëè÷íè ðåçóëòàòè â îòäåëíèòå ðàçèãðàâàíèÿ ïîëó÷àâàòå 0 ò.

 

 

XIX ÍÀÖÈÎÍÀËÍÀ ÎËÈÌÏÈÀÄÀ ÏÎ ÈÍÔÎÐÌÀÒÈÊÀ

Íàöèîíàëåí êðúã, Ãàáðîâî, 3-4 ìàé 2003 ã.

 

 

Çàäà÷à 1.3  ÑÎÐÒÈÐÀÍÅ

 

Ñîðòèðàíåòî íå âèíàãè å ëåñíà çàäà÷à. Ïðåäñòàâåòå ñè, ÷å ñúùåñòâóâàò K (4<K<200) íåïðàçíè ñîðòèðàíè ðåäèöè îò íåîòðèöàòåëíè öåëè ÷èñëà íå íàäâèøàâàùè 2000000000, êàòî ðåäèöèòå ñà íîìåðèðàíè îò 1 äî K, à äúëæèíèòå èì íå ñà èçâåñòíè. Çàäà÷àòà å äà íàïèøåòå ïðîãðàìà SORK.EXE, êîÿòî äà ñîðòèðà âñè÷êè ÷èñëà îò K-òå ðåäèöè. Çà öåëòà ùå ìîæå äà èçïîëçâàòå ïîäïðîãðàìà srv ñ òðè ôîðìàëíè ïàðàìåòúðà ? ïúðâèòå äâà codå è value ñà öåëè ñòîéíîñòè, êîèòî ïðåäàâàòå â ïîäïðîãðàìàòà, à òðåòèÿò å öÿëà ïðîìåíëèâà answ, â êîÿòî äà ïîëó÷àâàòå îòãîâîðà íà ïîäïðîãðàìàòà, êîãàòî òàêúâ îòãîâîð å ñìèñëåí. Âúçìîæíè ñà 4 ñòîéíîñòè çà ïàðàìåòúðà codå ñúñ ñëåäíèÿ ñìèñúë:

• Èíèöèàëèçàöèÿ (codå=0): èçâèêâàíåòî ñ òîçè êîä òðÿáâà äà ñå èçâúðøè åäíîêðàòíî è ïðåäè âñè÷êè äðóãè èçâèêâàíèÿ íà ïîäïðîãðàìàòà srv.  òîçè ñëó÷àé ñòîéíîñòòà íà ïàðàìåòúðà value å áåç çíà÷åíèå. Êàòî ðåçóëòàò ïîäïðîãðàìàòà srv âðúùà â ïàðàìåòúðà answ ñòîéíîñòòà íà K.
• Çàÿâêà çà ïîðåäíî ÷èñëî (codå=1): èçâèêâàíåòî ñ òîçè êîä ìîæå äà ñå èçâúðøè ìíîãîêðàòíî, íî ñàìî ñëåä èíèöèàëèçàöèÿ.  òîçè ñëó÷àé ñòîéíîñòòà íà ïàðàìåòúðà value å íîìåðúò íà ðåäèöàòà, îò êîÿòî èñêàòå ïîðåäíîòî ÷èñëî. Êàòî ðåçóëòàò ïîäïðîãðàìàòà srv âðúùà â ïàðàìåòúðà answ èñêàíîòî ÷èñëî, àêî ÷èñëàòà â ðåäèöàòà íå ñà ñâúðøèëè. Àêî ÷èñëàòà â óêàçàíàòà ðåäèöà ñà ñâúðøèëè, ïîäïðîãðàìàòà srv âðúùà ?1 â ïàðàìåòúðà answ. Íå å ïîçâîëåíî äà ïðàâèòå òàçè çàÿâêà çà ðåäèöà, çà êîÿòî âå÷å çíàåòå, ÷å ÷èñëàòà ñà ñâúðøèëè.
• Èçïðàùàíå íà ñîðòèðàíî ÷èñëî (codå=2): èçâèêâàíåòî ñ òîçè êîä ìîæå äà ñå èçâúðøè ìíîãîêðàòíî, íî ñàìî ñëåä èíèöèàëèçàöèÿ.  òîçè ñëó÷àé ñòîéíîñòòà íà ïàðàìåòúðà value òðÿáâà äà å ïîðåäíîòî ÷èñëî â ñîðòèðàíàòà ðåäèöà íà âñè÷êè ÷èñëà.  òîçè ñëó÷àé ïîäïðîãðàìàòà srv íå âðúùà ñòîéíîñò â ïàðàìåòúðà answ. Âúâ âñåêè ìîìåíò îò ðàáîòàòà íà ïðîãðàìàòà, ðàçëèêàòà ìåæäó áðîÿ íà èçïúëíåíèòå çàÿâêè çà ïîðåäíî ÷èñëî (codå=1) è èçïðàòåíèòå ñîðòèðàíè ÷èñëà (codå=2) íå áèâà äà íàäâèøàâà 250000.
• Êðàé (codå=3): èçâèêâàíåòî ñ òîçè êîä òðÿáâà äà ñå èçâúðøè åäíîêðàòíî è ñëåä âñè÷êè äðóãè èçâèêâàíèÿ íà ïîäïðîãðàìàòà srv.  òîçè ñëó÷àé ñòîéíîñòòà íà ïàðàìåòúðà value å áåç çíà÷åíèå, ïîäïðîãðàìàòà íå âðúùà ñòîéíîñò â ïàðàìåòúðà answ è ïðåêðàòÿâà èçïúëíåíèåòî íà ïðîãðàìàòà.

Çà äà ìîæå äà òåñòâàòå ïðîãðàìàòà ñè, ñëåä íîðìàëíî çàâúðøâàíå â òåêñòîâèÿ ôàéë sork.out ùå íàìåðèòå ñúîáùåíèåòî OK! ïðè óñïåøåí êðàé íà ðàáîòàòà èëè ñúîòâåòåí òåêñò îïèñâàù äåôåêòà, êîéòî å îòêðèò ïî âðåìå íà ðàáîòà. Ïîäïðîãðàìàòà srv ùå ïðåêðàòè èçïúëíåíèåòî íà ïðîãðàìàòà Âè ïðè ïúðâîòî íåïðàâèëíî èçâèêâàíå. 

Çà ïðîãðàìèñòèòå íà Ñ/Ñ++: Ïîäïðîãðàìàòà srv ùå áúäå îôîðìåíà êàòî îáåêòåí ìîäóë srv.obj, êîéòî ùå ïîëó÷èòå íà äèñêåòà, çàåäíî ñ óñëîâèåòî íà çàäà÷àòà.  íåãî å äåôèíèöèÿòà íà ôóíêöèÿòà srv. Çà äà ìîæå äà ÿ èçïîëçâàòå, ïîñòàâåòå â ïðîãðàìàòà ïðîòîòèïà:

            extern void srv(int, int, *int);

 

Çà ïðîãðàìèñòèòå íà Pascal: Ïîäïðîãðàìàòà srv ùå áúäå îôîðìåíà â áèáëèîòåêà (unit) ñ èìå usrv.*, êîÿòî ùå ïîëó÷èòå çàåäíî ñ óñëîâèåòî íà çàäà÷àòà. Ïîäïðîãðàìàòà å äåôèíèðàíà êàòî

procedure srv(code:byte; value:longint; var answ:longint);.

Çà äà ìîæåòå äà ÿ èçïîëçâàòå, âêëþ÷åòå â ïðîãðàìàòà   uses usrv;

 

XIX ÍÀÖÈÎÍÀËÍÀ ÎËÈÌÏÈÀÄÀ ÏÎ ÈÍÔÎÐÌÀÒÈÊÀ

Íàöèîíàëåí êðúã, Ãàáðîâî, 3?4 ìàé 2003 ã.

 

 

Çàäà÷à  2.1   ÊÓÁ×ÅÒÀ

 

Îò 12 ïðú÷êè ñ ðàâíà äúëæèíà, âñÿêà îò êîèòî å îöâåòåíà ñ íÿêàêúâ öâÿò òðÿáâà äà ñå ïîñòðîè êóá. Äà ñå íàïðàâè ïðîãðàìà CUBE.EXE, êîÿòî îïðåäåëÿ ïî êîëêî ðàçëè÷íè íà÷èíà ìîæå äà áúäå ïîñòðîåí êóáà. Äâà êóáà ñå ñ÷èòàò çà åäíàêâè, àêî åäèíèÿò ìîæå äà áúäå çàâúðòÿí è ïîñòàâåí äî äðóãèÿ ïî òàêúâ íà÷èí, ÷å ñúîòâåòíèòå  ðúáîâå äà ñà åäíàêâî îöâåòåíè.

Âõîäíèòå äàííè ñà 12 öåëè ïîëîæèòåëíè ÷èñëà c₁, c₂, ?, c₁₂ ? öâåòîâåòå íà äàäåíèòå ïðú÷êè (1 ≤ c₁ ≤ c₂ ≤ ? ≤ c₁₂ ≤ 6), êîèòî ñå âúâåæäàò îò åäèí ðåä íà ñòàíäàðòíèÿ âõîä. Íà ñòàíäàðòíèÿ èçõîä äà ñå èçâåäå åäíî ÷èñëî ? áðîÿ íà ðàçëè÷íèòå êóáîâå, êîèòî ìîãàò äà ñå ïîñòðîÿò îò äàäåíèòå ïðú÷êè.

                                                                                           

ÏÐÈÌÅÐÈ

 

Âõîä

1 2 2 2 2 2 2 2 2 2 2 2

Èçõîä

1

 

Âõîä

1 1 2 2 2 2 2 2 2 2 2 2

Èçõîä

5

 

 

XIX ÍÀÖÈÎÍÀËÍÀ ÎËÈÌÏÈÀÄÀ ÏÎ ÈÍÔÎÐÌÀÒÈÊÀ

Íàöèîíàëåí êðúã, Ãàáðîâî, 3?4 ìàé 2003 ã.

 

 

Çàäà÷à 2.2   ÏÐÅËÈÂÀÍÅ

 

Ðàçïîëàãàìå ñ òðè ñúäà, ñúîòâåòíî ñ âìåñòèìîñò a, b è c ëèòðà (a, b è c ñà öåëè ïîëîæèòåëíè ÷èñëà, íåíàäìèíàâàùè 200). Ïúðâèÿò è âòîðèÿò ñúä ñà ïðàçíè, à òðåòèÿò å íàïúëíåí äîãîðå ñ âîäà. Ðàçðåøåíî å äà ïðåëèâàìå íåêîëêîêðàòíî (íóëà, åäèí èëè ïîâå÷e ïúòè) îò åäèí ñúä â äðóã, íî ïîíåæå íå ðàçïîëàãàìå ñ íèêàêâè ìåðêè, ìîæå ñàìî äà íàïúëâàìå äîãîðå ñúäà â êîéòî íàëèâàìå èëè äà èçïðàçâàìå äîêðàé ñúäà îò êîéòî ïðåëèâàìå, êîãàòî òîâà å âúçìîæíî. Íå å ðàçðåøåíî äà èçëèâàìå âîäà èçâúí ñúäîâåòå.

 

Íàïèøåòå ïðîãðàìà FILL.EXE, êîÿòî ïðåñìÿòà êàêâî íàé-ìàëêî ñóìàðíî êîëè÷åñòâî òå÷íîñò òðÿáâà äà áúäå ïðåëÿòî òàêà, ÷å â ïîíå åäèí îò ñúäîâåòå äà ñå ïîëó÷è çàäàäåíî êîëè÷åñòâî òå÷íîñò d ëèòðà (d å öÿëî ïîëîæèòåëíî ÷èñëî, íåíàäìèíàâàùî 200). Àêî íå å âúçìîæíî äà ñå ïîëó÷è ïî óêàçàíèÿ íà÷èí êîëè÷åñòâîòî d, Âàøàòà ïðîãðàìà òðÿáâà äà íàìåðè íàé-áëèçêîòî äî d ïî-ìàëêî íåîòðèöàòåëíî öÿëî ÷èñëî ëèòðè d', êîåòî å âúçìîæíî äà ñå ïîëó÷è âìåñòî d è äà ïðåñìåòíå çà íåãî ìèíèìàëíîòî êîëè÷åñòâî ïðåëÿòà òå÷íîñò.

 

Âõîäíèòå äàííè ñå ÷åòàò îò ñòàíäàðòíèÿ âõîä êàòî ÷åòèðè öåëè ïîëîæèòåëíè ÷èñëà  a, b, c è d, ðàçäåëåíè ñ ïî åäèí èíòåðâàë. Ðåçóëòàòúò òðÿáâà äà áúäå èçâåäåí íà ñòàíäàðòíèÿ èçõîä êàòî äâîéêà öåëè íåîòðèöàòåëíè ÷èñëà, ðàçäåëåíè ñ åäèí èíòåðâàë ? ïúðâîòî îò òåçè ÷èñëà òðÿáâà äà å ðàâíî íà íàìåðåíîòî ìèíèìàëíî êîëè÷åñòâî ïðåëÿòà òå÷íîñò, à âòîðîòî òðÿáâà äà å ðàâíî íà d, àêî çà íåãî å âúçìîæíî äà ñå îñúùåñòâè îïèñàíîòî ïðåëèâàíå, èëè äà å ðàâíî íà íàìåðåíàòà îò Âàøàòà ïðîãðàìà ïî-ìàëêà âúçìîæíà ñòîéíîñò d'.

 

ÏÐÈÌÅÐ

 

Âõîä

2 3 4 2

 

Èçõîä

2 2

 

 

XIX ÍÀÖÈÎÍÀËÍÀ ÎËÈÌÏÈÀÄÀ ÏÎ ÈÍÔÎÐÌÀÒÈÊÀ

Íàöèîíàëåí êðúã, Ãàáðîâî, 3?4 ìàé 2003ã.

 

 

Çàäà÷à 2.3   ÀÐÈÒÌÅÒÈÊÀ

 

Äàäåíè ñà öåëèòå ïîëîæèòåëíè ÷èñëà N è a₁, a₂, ?, a_m. Ñ ïîìîùòà íà îïåðàöèèòå + (ñúáèðàíå), - (èçâàæäàíå), * (óìíîæåíèå) è / (äåëåíèå) è ÷èñëàòà a₁, a₂, ?, a_m îáðàçóâàìå àðèòìåòè÷íè èçðàçè ñúñ ñòîéíîñò N è òàêèâà, ÷å âñåêè òåõåí ïîäèçðàç å öÿëî ïîëîæèòåëíî ÷èñëî. Âñÿêî îò ÷èñëàòà a₁, a₂, ?, a_m å ðàçëè÷íî îò äðóãèòå è ìîæå äà ó÷àñòâà â òàêúâ èçðàç íå ïîâå÷å îò âåäíúæ.

Êîëêî êúñ èçðàç îò òîçè âèä ìîæåì äà îáðàçóâàìå?

Íàïèøåòå ïðîãðàìà EXPR.EXE, êîÿòî ïî äàäåíè N, a₁, a₂, ?, a_m (âñè÷êèòå ïî-ìàëêè îò 3000, m £ 20) íàìèðà åäèí íàé-êúñ èçðàç ñ îïèñàíèòå ñâîéñòâà. ×èñëàòà N è a₁, a₂, ?, a_m ñå âúâåæäàò îò äâà ïîñëåäîâàòåëíè ðåäà íà ñòàíäàðòíèÿ âõîä, à ðåçóëòàòúò ñå îòïå÷àòâà íà åäèí ðåä íà ñòàíäàðòíèÿ èçõîä, êàòî çà âñÿêà àðèòìåòè÷íà îïåðàöèÿ â èçðàçà ñà ïîñòàâåíè ñêîáè.

 

ÏÐÈÌÅÐ

 

Âõîä

20

1 2 3 7

 

Èçõîä (ïîêàçàíè ñà äâå îò âúçìîæíîñòèòå)

(2*(3+7))

 èëè

((3*7)-1)