Шумен, 24. 11. 2007 г. Група а (11-12 клас) Задача хамали




ИмеШумен, 24. 11. 2007 г. Група а (11-12 клас) Задача хамали
Дата на преобразуване16.12.2012
Размер57.38 Kb.
ТипЗадача
източникhttp://infoman.musala.com/contests/fall/2007/tasks_A.doc

VІІ Национален есенен турнир по информатика и информационни технологии

“Джон Атанасов”


Шумен, 24.11.2007 г.

Група А (11-12 клас)

Задача А1. ХАМАЛИ

Боклукът, събран след пролетното почистване на града, е пакетиран в бали и трябва да бъде извозен до сметището. Тази нелека задача е възложена на хамалите от „Кърти,Чисти, Извозва” ООД. Те не са много загрижени за околната среда и решили да използват канализацията на града за да транспортират балите. Канализацията има N шахти, номерирани от 1 до N(1≤N ≤150 000), като шахтата с номер 1 се намира на сметището. Всяка шахта U (1<UN) е свързана с тръба към точно една шахта V<U и течението ще отнесе до V всеки предмет, пуснат в U. Така всяка бала с боклук, пусната в U може да стигне до всяка шахта, която се намира на пътя от U до 1, стига в шахтата да има достатъчно вода, за да не заседне балата в нея.

В 10.00:00 сутринта, когато започва пренасянето на боклука, всички шахти са празни. За радост на хамалите, в този момент започва да вали дъжд и шахтите започват да се пълнят с 10 куб.см вода в секунда. Затова хамалите използват следната тактика. Един хвърля бала боклук в шахта X(1<X), а друг я чака в шахта Y(Y<X), разположена по пътя от X до 1. Максималният обем на бала, която може да бъде пренесена така, е равен на минималнoто количество вода в куб.см., което се съдържа в шахта по пътя от X до Y в момента на пускането на балата и това е което вълнува хамалите при всяка такава операция. Отговорът на въпроса щеше да бъде тривиален, ако конкурентите от „Цепи-Лепи” АД, не изпомпваха вода от някои от шахтите. Напишете програма porters за да им помогнете.

Вход.

На първия ред на стандартния входа са зададени числата N и K(1≤N≤150 000). На втория ред са записани N–1 числа, като числото в позиция P е най-много P и означава номера на шахта, с която е свързана шахтата P+1. Всеки от следващите K реда е от един от следните два типа:

k4i <T> <X> <Y>, където 0T≤1 000 000, 1<XN, 1≤Y<X и Y е на пътя от X до 1. Това означава, че хамалите се интересуват от максималния обем на бала, която може да бъде пусната в X, T секудни след началото на извозването, и да стигне до Y;

cepy_lepy <T> <X> <V>, където 0T≤1 000 000, 1XN, 0≤V количеството вода в шахта X в момент T. Това означава, че конкурентите от „Цепи-Лепи” изпомпват V куб.см. вода от шахта X в момент, в който са изминали T секунди от началото на извозването. Изпомпването става моментално. Тези K реда са подредени в нарастващ ред на T и няма редове с еднаква стойност на T.

Изход.

За всеки ред от първи тип, срещнат във входа, програмата трябва да изведе на стандартния изход един ред с търсения максимален обем на бала. За ред от втори тип не се извежда нищо.

Примерен вход

Изход за примерния вход

8 7

1 1 3 3 2 4 3

k4i 0 5 3

k4i 2 8 3

cepy_lepy 5 6 50

cepy_lepy 6 2 40

cepy_lepy 7 1 50

k4i 8 2 1

k4i 10 6 1

0

20

30

50



VІІ Национален есенен турнир по информатика и информационни технологии

“Джон Атанасов”


Шумен, 24.11.2007 г.


Група А (11-12 клас)


Задача A2. РАЗСТОЯНИЕ

К

ласът на Елеонора е адски ШУМЕН (в сравнение с него, дори Големият Взрив е като слабо пукване). Главната причина за това е, че всеки в класа се опитва да говори със свой съученик, който, в повечето случаи, е в другата част на стаята. А както е широко известно – когато двама събеседници си говорят, шумът е пропорционален на квадрата от разстоянието между тях.

Един ден Ели се запитала, каква е максималната олелия, която може да се постигне в нейния клас. За да се определи това, е достатъчно да се знаят разстоянията между всеки два събеседника. Мярка за олелията ще бъде сборът от квадратите на всички такива разстояния. Тъй като става дума за нормално българско училище – всички ученици си говорят по време на час. Класът на Ели се състои от 22 ученика. Понякога някои ученици отсъстват, но N-те ученика в клас винаги са четен брой и всеки ученик води точно един разговор с някой от останалите N1, като двамата си говорят помежду си и с никой друг.

Ели е самата прецизност, затова мери разстоянията в милиметри. Класната стая е квадрат със страна 10 000 милиметра. Позицията на един ученик се задава с координатите му, като за начало на координатната система (0,0) е избран един от ъглите на стаята (мястото на учителя). Задачата е да се напише програма distance, която по разположението на N-те ученика в класната стая, да определи максималния възможен шум, който може да се постигне.

Вход.

На първия ред на стандартния вход ще бъде зададен броят N на учениците (2≤N≤22,N четно). На всеки от следващите N реда са зададени, разделени с един интервал, по две цели числа x и y(0≤x,y≤10 000) – координатите на поредния ученик. Възможно е да има ученици с еднакви координати – например Пет’р (така изписано, според него, името му изглежда по-хакерско) много обича да седи на главата на Брус Веселия, защото Брус има лаптоп и го носи в клас.

Изход.

На единствения ред на стандартния изход програмата трябва да изведе максималната възможна олелия, с точност 3 знака след десетичната точка.

Пример:

Вход

Изход

Обяснение:

4

1 1

9 2

10 7

2 6

182.000

При данните от примерния вход най-голям сбор се получава, когато ученикът в точка (1,1) си говори с този в точка (10,7) – квадратът на разстоянието е 117.00, а този в точка (2,6) си говори с този в точка (9,2) – квадратът на разстоянието е 65.00. Тогава сборът е 117.00 + 65.00 = 182.00.



VІІ Национален есенен турнир по информатика и информационни технологии

“Джон Атанасов”


Шумен, 24.11.2007 г.


Група A (11–12 клас)


Задача А3. ГОЛЯМО ЧИСЛО


Напишете програма bignum, която намира най-голямото число в q-ична бройна система, такова, че всичките k-цифрени числа, образувани от k последователни цифри на числото да бъдат различни.

Вход.

От стандартния вход се въвеждат q и k.

Изход.

Търсеното число да се изведе на стандартния изход.

Ограничения:

2≤q≤10, 1≤k≤14, броят на цифрите в търсеното число е по-малък от 20000.


ПРИМЕР 1

ПРИМЕР 2

Вход

Вход

2 3

3 1

Изход

Изход

1110100011

210

Свързани:

Шумен, 24. 11. 2007 г. Група а (11-12 клас) Задача хамали iconШумен, 24. 11. 2007 г. Група b (9–10 клас) Задача пермутации
Пермутация наричаме функция f:{1,2, …,n}{1,2, …,n}, за която f(I)≠f(j) при i≠j
Шумен, 24. 11. 2007 г. Група а (11-12 клас) Задача хамали iconШумен, 24. 11. 2007 г. Група c (7-8 клас) Задача числова таблица
Три клетки на таблицата ще наричаме съседни, ако всяка от тях има обща страна с поне една от останалите две. Да се напише програма...
Шумен, 24. 11. 2007 г. Група а (11-12 клас) Задача хамали iconАнали з на работата в полуинтернатна група 2 клас
През учебната 2007/08 година бе разкрита полуинтернатна група за 2 клас в съответствие с изискванията за осигуряване на качествено...
Шумен, 24. 11. 2007 г. Група а (11-12 клас) Задача хамали iconТема за 7-8 клас (група c)
Есенен турнир по информатика и информационни технологии “джон атанасов” -шумен’03
Шумен, 24. 11. 2007 г. Група а (11-12 клас) Задача хамали iconТема за 4-6 клас група
Есенен турнир по информатика и информационни технологии “джон атанасов” -шумен’03
Шумен, 24. 11. 2007 г. Група а (11-12 клас) Задача хамали iconРепублика българия сметна палата доклад
Сметната палата – Варна, е извършен одит на финансовото управление на дейността по определяне, събиране и отчитане на местните данъци...
Шумен, 24. 11. 2007 г. Група а (11-12 клас) Задача хамали iconСписък №18 на книги, депозирани от 12 до 18 април 2007 г
Арнаудова, Александра Василева. Самостоятелни работи и задачи за поправка по български език II клас. Група I ii. Димант, [2007]....
Шумен, 24. 11. 2007 г. Група а (11-12 клас) Задача хамали iconНа вниманието на Кмета на Община
Твителна група/клас (6-годишни) (одобрена със заповед № рд 09-584/29. 04. 2005 г на Министъра на образованието и науката) и аз съм...
Шумен, 24. 11. 2007 г. Група а (11-12 клас) Задача хамали iconТема за  група b (10-11 клас)
Въпросът е колко от всичките възможни начални разположения ще доведат до оформяне на p групи? Напишете програма march. Exe, която...
Шумен, 24. 11. 2007 г. Група а (11-12 клас) Задача хамали iconЗадача №1 Задача №2 Задача №3 Задача №4 Задача №5 Апелляция Кочегаров Сергей Сергеевич моу «Гимназия»
Члены жюри: Волокитина Т. И., Виниченко В. Д., Сурков С. В., Белова Н. Н., Воронова Н. И., Черняева И. В
Поставете бутон на вашия сайт:
Документация


Базата данни е защитена от авторски права ©bgconv.com 2012
прилага по отношение на администрацията
Документация
Дом