passer
Зарегистрирован: 27.09.2005
Сообщения: 5
Откуда: баку
|
 Добавлено: Сб Июл 05 2008 20:01 Заголовок сообщения: омогите разобраться с заданиями |
 |
|
есть задания по программированию на англиском. никак не пойму про что это
Задание 1
| Код: |
Problem
Imagine that you are in a building with F floors (starting at floor 1, the lowest floor), and you have a large number of identical eggs, each in its own identical protective container. For each floor in the building, you want to know whether or not an egg dropped from that floor will break. If an egg breaks when dropped from floor i, then all eggs are guaranteed to break when dropped from any floor j ≥ i. Likewise, if an egg doesn't break when dropped from floor i, then all eggs are guaranteed to never break when dropped from any floor j ≤ i.
We can define Solvable(F, D, B) to be true if and only if there exists an algorithm to determine whether or not an egg will break when dropped from any floor of a building with F floors, with the following restrictions: you may drop a maximum of D eggs (one at a time, from any floors of your choosing), and you may break a maximum of B eggs. You can assume you have at least D eggs in your possession.
Input
The first line of input gives the number of cases, N. N test cases follow. Each case is a line formatted as:
F D B
Solvable(F, D, B) is guaranteed to be true for all input cases.
Output
For each test case, output one line containing "Case #x: " followed by three space-separated integers: Fmax, Dmin, and Bmin. The definitions are as follows:
Fmax is defined as the largest value of F' such that Solvable(F', D, B) is true, or -1 if this value would be greater than or equal to 232 (4294967296).
(In other words, Fmax = -1 if and only if Solvable(232, D, B) is true.)
Dmin is defined as the smallest value of D' such that Solvable(F, D', B) is true.
Bmin is defined as the smallest value of B' such that Solvable(F, D, B') is true.
Limits
1 ≤ N ≤ 100.
Small dataset
1 ≤ F ≤ 100,
1 ≤ D ≤ 100,
1 ≤ B ≤ 100.
Large dataset
1 ≤ F ≤ 2000000000,
1 ≤ D ≤ 2000000000,
1 ≤ B ≤ 2000000000.
Sample
Input
2
3 3 3
7 5 3
Output
Case #1: 7 2 1
Case #2: 25 3 2
|
Задание 2
| Код: |
Problem
You have a list of items you need to buy today, and you know the locations (represented as points on a cartesian grid) of a few stores in the area. You also know which of these stores are selling each item on your list, and at what price each store sells it. Given the price of gas, what is the minimum amount you need to spend in order to buy all the items on your shopping list and then drive back home? You start and end the journey at your house, which is located at (0,0).
To make matters interesting, some of the items on your list may be perishable. Whenever you make a purchase that includes one or more perishable items, you cannot drive to another store without first stopping back at your house. Every item on your shopping list is guaranteed to be sold by at least one store, so the trip will always be possible.
Input
The first line of input gives the number of cases, N. N test cases follow. Each case starts with a line formatted as
num_items num_stores price_of_gas
The next line contains the num_items items on your shopping list. The items will be space separated, and each item will consist of only lowercase letters. If an item is perishable, its name will be followed by a single exclamation point. There will be no duplicate items on your list. The next num_stores lines will each be formatted as
x_pos y_pos item1:price1 item2:price2 ...
Each of these lines gives the location of one store, along with the items available at that store and their corresponding prices. Only items which are on your shopping list will appear in these lists. Perishable items will not end with exclamation points on these lists. No item will be repeated in a store's list. Each store will offer at least one item for sale. No two stores will be at the same location, and no store will be located at (0,0).
Output
For each test case, output one line containing "Case #x: " followed by the minimum possible cost of the trip, rounded to seven decimal places. Don't forget about price_of_gas, which is the amount of money you must spend per unit distance that you drive.
Limits
1 ≤ N ≤ 100,
0 ≤ price_of_gas ≤ 1000,
-1000 ≤ x_pos ≤ 1000,
-1000 ≤ y_pos ≤ 1000,
1 ≤ price of each item ≤ 1000.
Small dataset
1 ≤ num_items ≤ 5,
1 ≤ num_stores ≤ 10.
Large dataset
1 ≤ num_items ≤ 15,
1 ≤ num_stores ≤ 50.
Sample
Input
2
1 2 10
cookies
0 2 cookies:400
4 0 cookies:320
3 3 5
cookies milk! cereal
0 2 cookies:360 cereal:110
4 0 cereal:90 milk:150
-3 -3 milk:200 cookies:200
Output
Case #1: 400.0000000
Case #2: 519.2920690
|
всем зарание спосибо за ответы |
|
FAQ 
Поиск 
Пользователи 
Группы
Регистрация
Профиль 
Войти и проверить личные сообщения 
Вход 
