НАЦИОНАЛЕН ПРОЛЕТЕН ТУРНИР ПО ИНФОРМАТИКА

Ямбол, 3-5 Юни 2005

Задача A1.1. КНИГИ

Наредени са N книги, съответно със s₁, s₂,…, s_N страници (1< N < 200). Те трябва да се дигитализират от K сътрудника (1< K < 100), като първият сътрудник трябва да обработи първите няколко (нула, една или повече) книги, вторият сътрудник – следващите няколко и т.н. На всеки сътрудник се заплаща по d₁ долара за всяка страница от първата книга, която той обработва, по d₂ долара за всяка страница от втората за него книга, и изобщо – по d_i долара на страница за i-ата поредна за него книга. Напишете програма BOOKS, която разпределя книгите между сътрудниците така, че работодателят да им плати минимална обща парична сума, за да се свърши цялата работа.

Входните данни се четат от стандартния вход. На първия ред са записани числата N и K. На втория ред са дадени стойностите s₁, s₂, …, s_N, разделени с по един интервал. На третия ред следват стойностите d₁, d₂, …, d_N, също разделени с по един интервал. Всички входни данни са цели положителни числа, по-малки от 10⁷.

Търсената минимална парична сума трябва да се изведе на стандартния изход като едно цяло число.

ПРИМЕР

Вход 6 3 50 100 60 5 6 30 1 2 3 4 5 6

Изход 339

НАЦИОНАЛЕН ПРОЛЕТЕН ТУРНИР ПО ИНФОРМАТИКА

Ямбол, 3-5 Юни 2005

Задача А1.2. ИГРА

Игра с действащи лица герой и две чудовища се играе в квадратен лабиринт с размери N x N, разбит на N ² еднакви квадратчета. По някои от страните на квадратчетата се издигат непробиваеми стени (както за героя, така и за чудовищата), а в някои от квадратчетата има смъртоносни (за героя, но не и за чудовищата) капани. Целта на героя е да се спаси от чудовищата, като внимава да не попадне в капан и да напусне лабиринта през единствения изход, намиращ се на външна стена на някое от периферните квадратчета.

В началото всяко от трите действащи лица се намира на различно квадратче. Героят и чудовищата се редуват да правят ходове, състоящи се от стъпки. Стъпката е преместване в някое от четирите съседни квадратчета през страна, на която няма стена. Героят започва играта пръв и на всеки ход може да направи 1 стъпка. Чудовищата имат право на 2 стъпки на всеки ход, като едновременно правят първата си, а след това и втората си стъпка. Ако след поредна стъпка чудовищата се озоват в едно и също квадратче, те се “сливат” в суперчудовище. Ако стъпката е първа за хода – те загубват правото си на втора стъпка на този ход, но на всеки следващ ход суперчудовището има право на 3 стъпки.

Чудовищата и суперчудовището се движат по твърди правила. Те първо се опитват с хоризонтални стъпки да достигнат стълба в който се намира героя, а след това, ако са им останали стъпки, тръгват по вертикала към него. Ако чудовище/суперчудовище не може да направи стъпка по хоризонтала заради срещната стена, то прави стъпката си по вертикала до който е достигнало в посоката, в която се намира героят (стига героят да не е на същата хоризонтала). Ако в даден момент чудовище/суперчудовище не може да направи стъпка нито по хоризонтал нито по вертикал, то пропуска останалите стъпки от хода. Ако след стъпка на чудовище/суперчудовище то попадне на квадратчето с героя, героят губи играта.

Ако героят попадне на квадратче с капан – той губи играта. Ако чудовище попадне на такова квадратче, то пропуска 3 последователни хода, като това не се отразява на ходовете на другото чудовище. Ако след трите пропуснати хода се окаже, че чудовището не може да направи стъпка, тогава то не получава ново наказание от три хода затова, че е в квадратче с капан. Ако чудовището, което не е в капан влезе в капана, където вече има чудовище, то губи правото си на втора стъпка, а за следващия ход двете вече са обединени в суперчудовище. Капаните не се отразявят по никакъв начин на движението на суперчудовището.

Напишете програма WAPPO, която играе играта вместо героя и печели с колкото може по-малко ходове.

На първия ред на стандартния вход са зададени 8 цели числа: размерът на лабиринта N (3_£_N_£_6), координатите R и C – съответно реда и колоната на героя, координатите R₁,C₁ и R₂,C₂ - реда и колоната на двете чудовища и T – броят на капаните. Чудовищата започват играта от различни квадратчета. Нито героят, нито чудовищата започват в капан. Следват T реда с по 2 цели числа всеки – координатите на поредния капан. Входните данни завършват с N реда с по N цели числа всеки, като j-тото число на i-тия ред описва стените на квадратчето на i-ти ред, j-ти стълб. Съответното число се получава като сума от стойностите на стените, които има. За лява стена се прибавя 1, за дясна – 2, за горна – 4 и за долна – 8. Така например квадратче без стени има стойност 0, квадратче само с горна стена има стойност 4, квадратче с лява и долна стена – 9, квадратче с дясна, долна и горна – 14, а квадратче, обградено от всички страни със стени – стойност 15. Kвадратчето с координати (1,1) се намира в горния ляв ъгъл на лабиринта.

На първия ред на стандартния изход програмата трябва да изведе броя F на ходовете, които трябва да направи героят, за да се спаси. Всеки от следващите F реда трябва да съдържа по една цифра, в зависимост от хода на героя:

0 – героят прави ход нагоре 1 – героят прави ход надолу

2 – героят прави ход наляво 3 – героят прави ход надясно

Програмата ще получи пълния брой точки за един тест само ако е посочила минимален брой позволени ходове, в резултат на които героят се измъква от лабиринта. Във всеки останал случай програмата ще получи 0 точки за съответния тест.

ПРИМЕР

Вход 4 3 3 4 1 4 3 2 4 2 4 4 5 4 0 6 1 0 0 2 1 0 0 2 9 8 8 10

Изход 5 3 0 0 2 0

НАЦИОНАЛЕН ПРОЛЕТЕН ТУРНИР ПО ИНФОРМАТИКА

Ямбол, 3-5 Юни 2005

Задача А1.3. РАДИО

Дадени са множество от N предавателя и множество от M приемника. Името на всеки предавател е битов низ с дължина 8, а името на всеки приемник е низ, съставен от 3 нули, 3 единици и 2 звезди. Предавателят T “покрива” приемника R тогава и само тогава, когато T има 0 във всяка позиция в която R има 0 и T има 1 във всяка позиция в която R има 1. Например, предавателят 01001110 покрива приемника 010*1*10. Задачата е да се определи минималният брой предаватели, които трябва да бъдат включени, за да може да бъдат покрити всички приемници.

Разполагате с 10 файла (RADIO01.IN, RADIO02.IN, …, RADIO10.IN). Първият ред на всеки файл съдържа целите числа N и M (1 ≤ N ≤ 256, 1 ≤ M ≤ 560). Следващите N реда съдържат по едно име на предавател. Последните M реда съдържат по едно име на приемник. Трябва да се намери колкото може по-малко K такова, че съществува подмножество от K от дадените предаватели и всеки от приемниците е покрит от предавател в подмножеството. Трябва да се намери и едно подмножество от такива K предавателя.

Трябва да изпратите файл, съдържащ намереното решение. Не трябва да изпращате програми. Първият ред на изпратения файл трябва да бъде

#FILE RADIO T

където T е номерът на съответния тест (T = 1,2,…10). Вторият ред трябва да съдържа намереното число K. Следващите K реда трябва да съдържат имена на K от зададените предаватели, които представляват решение на поставената задача.

За всеки тестов пример, ако K_min е размерът на най-доброто решение, намерено от някой състезател, а вашето решение използва K приемника, то ще получите 10*(N – K)/(N – K_min) точки за теста.

ПРИМЕР

RADIO00.IN 3 4 00001111 10001011 10011011 000*111* *0001*11 **001011 100*10*1

RADIO00.OUT #FILE RADIO 0 2 00001111 10001011