ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА ШУМЕН’02
16 ноември 2002
ТЕМА ЗА 11-12 КЛАС (ГРУПА A)
Задача 1. ОБИКОЛКА
Хора от различни професии (пощальони, разносвачи на стоки по домовете, търговци и т.н.) често са изправени пред следната задача: те трябва да тръгнат от точка, съответна на работното им място (пощенска станция, магазин, склад или офис на фирмата), да посетят няколко други точки, където са разположени клиентите им и да се върнат в началната точка на обиколката. Нека точките, през които трябва да мине обиколката са означени с числата от 1 до N, като началната точка е означена с 1. За всеки две точки, които трябва да бъдат посетени (включително и началната точка на обиколката) е известно цяло число – разстояние между двете точки (време за изминаване на това разстояние или или някаква друга цена за изминаването му). Няма съмнение, че колкото по-кратка (по-бърза, по-евтина) е обиколката, толкова по-добре. За съжаление, добре известно е, че да се намери най-добрата възможна обиколка не е никак лесно, ако броят на местата, които трябва да бъдат посетени е достатъчно голям. Вашата задача е да напишете програма TRAVEL.EXE, която да опита да намери за отпуснатото й време колкото може по-добро решение.
Данните ще бъдат зададени в текстов файл, който вашата програма ще прочете от стандартния си вход. В първия ред на входния файл ще бъде зададено цялото число N (3 < N < 200) – броят на точките, които трябва да бъдат посетени, включително началната. Всеки от следващите N реда ще съдържа целочислените координати (разделени с интервал) на една от точките – в реда на номерата им. Разстоянието между две точки е т.н. манхатънско разстояние. За точките с координати (x1,y1) и (x2,y2) то се пресмята по формулата |x1–x2| + |y1–y2|. Всички координати са неотрицателни цели числа, не надхвърлящи 10000.
Изходният файл трябва да бъде изведен на стандартния изход. Той трябва да съдържа един ред с пермутацията на числата от 1 до N, разделени с по един интервал – намерена от програмата обиколка.
Оценката на резултата от работата на Вашата програмата върху всеки тест ще бъде извършена след сравняване с резултатите на другите състезатели. Програмите построили най-добра обиколка ще получат пълния брой точки за теста, а всяка останала програма – част от пълния брой, пропорционална на дължината на намереното решение.
6 1 4 6 5 3 2
0 0
40 0
25 5
20 10
40 20
10 20
ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА ШУМЕН'02
16 ноември 2002
ТЕМА ЗА 11 – 12 КЛАС (ГРУПА A)
Задача 2. ИНВЕСТИЦИЯ
Един инвеститор внася начален капитал x0 лева в строителна компания. От получения дивидент в края на всяка година той консумира ut лева, а остатъка добавя към своя капитал. Капиталът е инвестиран при лихвен процент p така, че капиталът през (t + 1)-вата година ще бъде равен на xt +1 = xt + (p/100)xt – ut.
Напишете програма INVEST.EXE, която да определи как инвеститорът може да максимизира общото потребление u0 + u1 + u2 + ... + uT–1 за T години чрез подходящо заделяне на пари за консумация ut през всяка от годините t = 0, 1, 2, ..., T – 1, като се спазва условието, че потреблението ut не може да е по-голямо от получения дивидент (p/100)xt, т.е. 0 <= ut <= (p/100)xt.
Входните данни за задачата са записани на текстов файл и програмата ви трябва да ги прочете от стандартния си вход. Текстовият файл съдържа на един ред три стойности, отделени с по един интервал: стойността на T (цяло число в интервала от 1 до 5000), p (дробно число в интервала от 0.001 до 20.000, зададено с най-много 3 знака след десетичната точка) и началния капитал x0, зададен като цяло число между 1000 и 1000000.
Изходните данни (възможното най-голямо общо потребление) програмата трябва да изведе на стандартния изход като число с десетична точка с точност до 6 цифри в дробната си част, закръглено чрез отсичане на евентуалните следващи десетични цифри.
Пример.
Вход:
2
10.0
1000
Изход:
200.000000
ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА ШУМЕН'02
16 ноември 2002
ТЕМА 11-12 КЛАС (ГРУПА А)
Задача 3. ТРОИЧНИ КАРТИ
В играта “Множества” участват 81 карти. Всяка карта има 4 атрибута (A, B, C и D), като всеки атрибут има една от три възможни стойности (0,1 или 2).
Три карти образуват множество, когато за всеки атрибут стойностите на трите карти са или еднакви или различни.
Например следните три карти образуват множество:
|
|
A |
B |
C |
D |
|
Карта 1 |
2 |
2 |
1 |
0 |
|
Карта 2 |
0 |
2 |
1 |
2 |
|
Карта 3 |
1 |
2 |
1 |
1 |
В следващия пример никои три от посочените карти не образуват множество:
|
|
A |
B |
C |
D |
|
Карта 1 |
0 |
1 |
0 |
0 |
|
Карта 2 |
1 |
0 |
0 |
0 |
|
Карта 3 |
1 |
1 |
0 |
1 |
|
Карта 4 |
1 |
1 |
1 |
1 |
|
Карта 5 |
1 |
2 |
1 |
2 |
|
Карта 6 |
2 |
2 |
0 |
2 |
|
Карта 7 |
2 |
1 |
1 |
0 |
Какъв е максималният брой карти, които не съдържат множество ?
Да се създаде текстов файл с име SETFREE.TXT със следната структура:
– на първия ред трябва да е записано едно число N – намереният максимален брой;
– на следващите N реда – по четири числа, разделени с интервал – стойностите на атрибутите за всяка от N-те карти, които не съдържат множество.
Правила за оценяване: Точките, който ще получите са 100*N/Nmax, където Nmax е максималният възможен брой.