СЪОБЩЕНИЕ: Ако извършваното обновяване на сайта на USACO приключи успешно, тогава изпратените решения ще могат да бъдат разглеждани от всички участници, след завършване на състезанието. ЗАБЕЛЕЖКА: Всяка задача се оценява с определен брой точки. Вашата цел е да спечелите колкото може повече точки. Резултатът ви ще бъде определен като сбор от точките на трите най-добри решения. Увеличете резултата си, като изпращате правилни решения; направете вашия резултат колкото може по-голям, като решавате правилно задачите, за които се дават най-много точки. ********************************************************************** ЗАДАЧИ ЗА ДИВИЗИЯ GOLD ********************************************************************** Четири задачи, номерирани от 1 до 4 ********************************************************************** Задача 1: "Омешани" крави [Don Piele, 2007] Всака от N-те крави на фермера Джон (4 <= N <= 16) има уникален сериен номер S_i (1 <= S_i <= 25000). Кравите са толкова горди от това, че всяка от тях е гравирала с големи цифри серийния си номер върху златна плочка и си го носи, по гангстерски маниер, окачен на врата. Кравите-гангстери са бунтовнически настроени и се подреждат за доене само в редици, наричани "омешани". Една редица от крави е омешана, ако съответната редица от серийни номера е такава, че всеки два съседни в редицата номера се различават с повече от K (1 <= K <= 3400). Наример, ако N = 6 и K = 1, тогава 1, 3, 5, 2, 6, 4 е омешана, а 1, 3, 6, 5, 2, 4 - не е (защото разликата между съседните номера 6 и 5 е 1). По колко различни начина могат да се омешат N-те крави? При първите 10 изпращания на решение, ще получите отговор, в който ще е указан резултатът от изпълнение на програмата ви въху част от тестовите примери. ТОЧКИ: 200 ИМЕ НА ЗАДАЧАТА: mixup2 ФОРМАТ НА ВХОДНИТЕ ДАННИ: * Ред 1: Две разделени с интервал цели: N и K * Редове 2..N+1: (i+1)-вия ред ще съдържа едно цяло число - серийният номер S_i на i-тата крава ПРИМЕРЕН ВХОД (файлът mixup2.in): 4 1 3 4 2 1 ФОРМАТ НА ВХОДНИТЕ ДАННИ: * Ред 1: Едно цяло число - броят на начините по които N крави могат да се подредят в "омешана" редица. Резултатът ще се побира в променлива от 64-битов цял тип. ПРИМЕРЕН ИЗХОД (file mixup2.out): 2 ОБЯСНЕНИЕ НА ИЗХОДА: Възможните омешани редици са 2: 3 1 4 2 2 4 1 3 ********************************************************************** Задача 2: Тъжни крави [David Benjamin and Jacob Steinhardt, 2008] Фермерът Джон толкова се е измързеливил, че изобщо спря да поддържа пътеките, по които кравите му достигат до всяко от неговите N пасища, номерирани традиционно от 1 до N (5 <= N <= 10000). Всяко от пасищата е дом на една от кравите. Фермерът планира да премахне колкото може повече от съществуващите P пътеки (N-1 <= P <= 100000) така, че отделните пасища да останат свързани едно с друго. Вие трябва да определите кои N-1 пътеки трябва да бъдат запазени. Двпосочната пътека j свързва пасищата S_j и E_j (1 <= S_j <= N; 1 <= E_j <= N; S_j != E_j) и по нея се се стига от едното до другото пасище за L_j единици време (0 <= L_j <= 1000). Кравите са много натъжени, че системата им за придвижване ще бъде нарушена. Затова, поне веднъж на ден, всяка крава трябва да бъде посетена и развеселена. Всеки път, когато фермерът е на пасището i (или преминава през него), ще се наложи да загуби C_i единици време и да поговори с кравата, която обитава пасището (1 <= C_i <= 1000). Докато кравите се отърсят от тъгата, всяка нощ фермерът ще трябва да нощува на едно и също пасище (което вие ще изберете). Затова с кравата, която обитава това пасище, ще трябва да говори поне един път сутринта, когато се събуди и вечерта преди да си легне. Предполагайки, че фермерът Джон следва вашите препоръки - кои пътеки да запази и на кое пасище е най-добре да нощува, определете минималното количество време, което ще е необходимо за да посети всяка от кравите поне един път на ден. При първите 10 изпращания на решение, ще получите отговор, в който ще е указан резултатът от изпълнение на програмата ви въху част от тестовите примери. ТОЧКИ: 300 ИМЕ НА ЗАДАЧАТА: cheer ФОРМАТ НА ВХОДНИТЕ ДАННИ: * Ред 1: Две, разделени с интервал, цели: N и P * Редове 2..N+1: (i+1)-вият ред съдържа само цялото C_i * Редове N+2..N+P+1: (N+j+1)-ият ред съдържа три, разделени с по един интервал цели: S_j, E_j и L_j ПРИМЕРЕН ВХОД (файлът cheer.in): 5 7 10 10 20 6 30 1 2 5 2 3 5 2 4 12 3 4 17 2 5 15 3 5 6 4 5 12 ОБЯСНЕНИЕ НА ВХОДА: +-(15)-+ / \ / \ / \ 1 -(5)- 2-(5)-3-(6)--5 \ / / (12)\ /(17) / 4------+(12) ФОРМАТ НА ИЗХОДНИТЕ ДАННИ: * Ред 1: Едно цяло - времето, необходимо за да може да се посети всяка крава (включително времето за двата разговора с кравата, която обитава пасището избрано за спане) ПРИМЕРЕН ИЗХОД (файла cheer.out): 176 ОБЯСНЕНИЕ НА ИЗХОДА: Запазете пътеките: 1-(5)-2-(5)-3 5 \ / (12)\ /(12) *4------+ Когато се събудите на пасище 4, посетете пасищата в реда 4, 5, 4, 2, 3, 2, 1, 2, 4 и ще е необходимо 176 единици време преди да може да си легнете спокойто да спите. ********************************************************************** Задача 3: Превключване на лампи [LongFan, 2008] Фермерът Джон се опитва да поддържа кравите във форма, като им позволява да си играят с интелектуални играчки. Една такава играчка е системата за осветление в обора. Всяка от N-те крави (2 <= N <= 100,000), номерирани от 1 до N, има цветна лампа над главата си. Преди да се свечери, всички лампи са изключени. Кравите могат да управляват осветлението с помощта на набор от N ключа, всеки от които превключва една лампа; натискането на i-тия ключ сменя състоянието на i-тата лампа от изключено във включено и обратно. Кравите имат на разположение списък от M операции (1 <= M <= 100,000) всяка от които е кодирана с едно от числата 0 или 1. Операцията от първия вид (кодирана с 0) има два аргумента - номерата на ключове S_i и E_i (1 <= S_i <= E_i <= N) и предписва на кравите да превключат всеки от ключовете с номера от S_i до E_i, влючително, точно по един път. Операцията от втория вид (кодирана с 1) също има два аргумента S_i и E_i (1 <= S_i <= E_i <= N) и предписва на кравите да преброят лампите с номера в интервала от S_i до E_i, включително, които светят в момента. Помогнете на фермера Джон да провери дали кравите са изпълнили правилно зададените в списъка команди и дали дават верни отговори на командите от втория вид. ТОЧКИ: 300 ИМЕ НА ЗАДАЧАТА: lites ФОРМАТ НА ВХОДНИТЕ ДАННИ: * Ред 1: Две, разделени с интервал, цели: N и M * Редове 2..M+1: Всеки от от тези редове съдържа по една операция - три, разделени с интервал цели: кодът на операцията, S_i и E_i ПРИМЕРЕН ВХОД (файлът lites.in): 4 5 0 1 2 0 2 4 1 2 3 0 2 4 1 1 4 ОБЯСНЕНИЕ НА ВХОДА: Четири лампи; пет команди. Тези команди пораждат следната последоватлност от състояния ня лампите: Лампи 1 2 3 4 Начало: O O O O O = изключена * = включена 0 1 2 -> * * O O превключи лампи 1 и 2 0 2 4 -> * O * * превключи лампи 2, 3 и 4 1 2 3 -> 1 преброй включените лампи в интервала 2..3 0 2 4 -> * * O O превключи лампи 2, 3 и 4 1 1 4 -> 2 преброй включените лампи в интервала 1..4 ФОРМАТ НА ИЗХОДНИТЕ ДАННИ: * Редове 1..{брой на командите от втори вид}: за всяка от командите за броене да се изведе едно цяло - броят включени лампи в зададения интервал. ПРИМЕРЕН ИЗХОД (файлът lites.out): 1 2 ********************************************************************** Задача 4: Играчки [Chen Hu, 2006] Рожденният ден на Беси приближава и тя се кани да празнува през следващите D дена (1 <= D <= 100000; за 70% от тестовете 1 <= D <= 500). Кравите, обаче лесно се разсейват и затова Беси бИ желала да привлича вниманиетo им по време на празниците с играчки. Тя пресметнала, че за i-тия ден ще са й необходими T_i играчки (1 <= T_i <= 50). Детската градина на Беси има различни форми на услуги за млади теле- програмисти, включително магазин за играчки, който продава всяка играчка на цена Tc долара (1 <= Tc <= 60). Беси би искала да спести пари, като използва купените играчки повече от един път, но фермерът Джон се страхува, че така се предават заболявания и настоял всяка играчка да се дезинфектира преди повторна употреба. (Магазинът за играчки дезинфектира всяка играчка преди да я продаде.) Две предприятия за дезинфекция, разположени близо до фермата могат да извършат услугата. Първото взема по C1 долара и извършва услугата за N1 нощи; второто взема по C2 долара и му трябват N2 нощи за да изърши дезинфекцията (1 <= N1 <= D; 1 <= N2 <= D; 1 <= C1 <= 60; 1 <= C2 <= 60). Беси трябва да занесе играчките за дезинфекция след партито и може да ги вземе обратно на следващата сутрин, ако услугата се изпълнява за една нощ, или в някоя от следващите сутрини, ако услугата изисква повече нощи. Тъй като е образована крава, Беси знае добре знае колко е важно да се пести. Намерете й най-евтиния начин за да осигури играчки за празниците. ТОЧКИ: 400 ИМЕ НА ЗАДАЧАТА: toy ФОРМАТ НА ВХОДНИТЕ ДАННИ: * Ред 1: Шест, разделени с интервал цели: D, N1, N2, C1, C2, Tc * Редове 2..D+1: (i+1)-вият ред съдържа цялото T_i ПРИМЕРЕН ВХОД (файлът toy.in): 4 1 2 2 1 3 8 2 1 6 ОБЯСНИНИЕ НА ВХОДА: Беси иска да празнува 4 дни, като и трябват 8 играчки за първия ден, 2 игрчки за втория, 1 - за третия and 6 - за четвъртия. Дезинфекцията в първата фирма отнема 1 нощ и струва 2 долара, а във втората - отнема 2 нощи и струва 1 долар. Всяка нова играчка струва 3 долара. ФОРМАТ НА ИЗХОДНИТЕ ДАННИ: * Ред 1: Минималната цена на която може да се осигурят безопасни и хигиенични играчки за празненствата по случай рожденният ден на Беси. ПРИМЕРЕН ИЗХОД (файлът toy.out): 35 ОБЯСНЕНИЕ НА ИЗХОДА: Ден 1 Купува 8 играчки сутринта за 24 долара; партито през този ден е след обед. След него занася 2 играчки на бързата фирма (1 нощ) а останалите 6 - в бавната (за 2 нощи). Ден 2 Взема двете дезинфекцирани играчки от бързата фирама и плаща 4 долара. С тях прави партито след обед. Вечерта занася 1 от играчките в бавната фирма. Ден 3 Взема 6 дезинфекцирани играчки от бавната фирама и плаща 6 долара. С една от тях прави партито след обед. Ден 4 Взема дезинфекцираната в бавната фирма играчка и плаща 1 долар. Добавя я към останалите от предния ден 5 дезинфикцирани играчки и с тях прави последното парти, като по този начин празниците са организирани с минимална цена. ********************************************************************** Translation by Krassimir Manev