Задачи со студолимпиады, или ВМКшники шютять...
Задача A: Таракан
Описание
Комитет Островной Безопасности Одного Островного Государства ведет следствие по группе опасных международных преступников
и компьютерных пиратов, использующих фирму Маленькие Мягкие Машины (МММ) для прикрытия своей грязной деятельности.
В ближайшее время преступники планируют провести очередное совещание, содержание которого совершенно необходимо знать следствию.
Однако президент компании, некто Б.~Воротов, очень осторожен и тщательно проверяет места преступных совещаний на предмет подслушивающих устройств и прочей техники. Все попытки комитета внедрить агента в преступную среду также не увенчались успехом.
Последняя надежда комитета --- новейшее передвижное подслушивающее устройство типа таракан.
Устройство типа таракан выполнено в корпусе из прочной пластмассы в форме таракана и способно к перемещению по плоской поверхности согласно заданной программе.
Комитету удалось раздобыть планы всех комнат, в которых возможно будет проходить совещание (окончательно место совещания выбирается в самый последний момент).
Эксперты комитета определили оптимальное место, в котором должно размещаться устройство, а также исходное положение для таракана в области, которая наверняка не будет проверяться перед совещанием.
План комнаты представляет собой прямоугольную сетку, на которой отмечены препятствия, непроходимые для устройства. Препятствия имеют форму прямоугольников. Несколько прямоугольников могут объединяться, формируя препятствие более сложной формы. Однако, если два препятствия лишь касаются друг друга (то есть прямоугольники на плане имеют только общее ребро или вершину), устройство способно проникать в щель между ними.
Прямоугольник, обозначающий препятствие, может иметь нулевую ширину или высоту, соответствуя на местности, например, уступу. Устройство может двигаться вдоль такого препятствия, но не может его пересекать.
Вам необходимо написать программу, которая для заданной конфигурации комнаты и препятствий найдет кратчайший путь от начальной до конечной точки.
Входные данные
Файл со входными данными для вашей программы будет иметь название
a.dat.
Формат входного файла:
K
room_1
...
room_K
Где K --- число комнат для расчета, а каждый room_k есть \
x_c y_c \
x_t y_t \
N \
x^1_1 y^1_1 x^1_2 y^1_2 \
... \
x^N_1 y^N_1 x^N_2 y^N_2 \
где (x_c,y_c) --- исходное положение таракана,
(x_t,y_t) --- положение цели,
N (0 le N le 50) --- число препятствий,
(x^i_1,y^i_1) и (x^i_2,y^i_2) --- координаты двух
противоложных вершин i -того препятствия (прямоугольника).
Все координаты --- целые числа в интервале [0, 10000] .
Все числа могут отделятся друг от друга любым числом пробельных символов.
Пробельными символами являются пробел, табуляция, перевод строки.
Выходные данные
Ваша программа должна напечатать результаты своей работы на {\it стандартный вывод}. Результаты должны быть представлены в
следующей форме.
Ответ для каждого теста должен предваряться строкой:\\
{\tt #\#\#\#\# } i \
где i --- номер теста.
В зависимости от входных данных ваша программа должна печатать одну или несколько строк, как описано ниже:
Cockroach' position is invalid.\\ если исходная позиция таракана находится в непроходимой области;
Target position is invalid. если конечная позиция таракана находится в непроходимой области;
Cockroach is at the target. если исходная позиция таракана совпадает с конечной;
Target is unreachable. если и исходная и конечная позиции таракана допустимы, но конечная позиция не может быть достигнута (загорожена непроходимыми препятствиями);
Minimal distance is D если исходная и конечная позиции таракана допустимы и существует маршрут от начальной до конечной точки длины D .
D должно быть округлено до двух знаков после десятичной точки.
Пример
2
0 30
20 30
4
10 0 0 60
0 0 60 10
50 0 60 60
0 60 60 50
0 0 100 100
1 30 30 70 70
Пример выходных данных:
##### 1
Target is unreachable.
##### 2
Minimal distance is 152.32.
Задача C: Парламент
Описание
Совсем недавно в Одном Островном Государстве разразился правительственный кризис, в результате которого все правительство во главе с премьер-министром было отправлено в отставку.
По Конституции государства, новый премьер-министр назначается президентом, но должен пройти процедуру утверждения своей кандидатуры в парламенте.
Зная оппозиционные настроения парламента по отношению к новой кандидатуре премьер-министра, президент решил обратиться за помощью к некоему финансовому магнату, имеющему близкие связи с кандидатом в премьеры и заинтересованному в утверждении.
Финансовый магнат выделяет некоторую сумму X тугриков (6 тугриков примерно равны 1 доллару США), которая должна быть истрачена на убеждение депутатов в необходимости утверждения кандидата. Парламент государства состоит из N (0 < N < 1000) депутатов, которые всегда ходят на все заседания и голосуют всегда либо <за >, либо <против > (воздержавшихся и не голосовавших не бывает).
О каждом депутате i парламента известно априорное отношение этого депутата к кандидатуре премьер-министра, выражаемое в вероятности p_i^0 (0 <= p_i^0 <= 1) , с которой данный депутат проголосует <за > кандидатуру.
Однако если на убеждение депутата потратить K_i тугриков, депутат обычно обещает поддержать кандидата, но, поскольку голосование тайное, в действительности депутат голосует <за > с вероятностью p_i^1 (0 <= p_i^1 <= 1) . По предыдущему опыту общения президента с парламентом известно, что если президенту удается заручиться предварительной поддержкой 70 % голосов депутатов, нужное решение всегда проходит.
С другой стороны, президент желал бы сэкономить как можно больше денег, ибо его финансовое положение несколько пошатнулось в результате кризиса на азиатских рынках. Поэтому он готов заплатить 10 % от сэкономленной суммы за наилучший вариант убеждения депутатов и за сохранение конфеденциальности. Экспертная группа при президенте готова произвести необходимые расчеты, но при условии, что она в любом случае получит как минимум M тугриков (и как максимум --- 10 % от сэкономленной суммы). Если выделенная магнатом сумма будет меньше M , то группа отказывается даже производить расчет. Если сумма будет больше M , но окажется недостаточной для обеспечения прохождения кандидатуры (с учетом оплаты работы группы), группа расчитает, на какой максимальный процент голосов в поддержку может расчитывать президент. Весь остаток суммы X , не потраченный на депутатов и группу экспертов, остается в распряжении президента.
Замечания:
Все денежные суммы ограниничены сверху валовым национальным продуктом страны, составляющим 10000 тугриков;
Ожидаемое число голосов вычисляется по формуле sum limits_{i=1}^{N}p_i , где p_i либо p_i^0 , либо p_i^1 , в зависимости от того, проводилась ли работа по данному депутату.
Входные данные
Файл со входными данными для вашей программы будет иметь название
c.dat.
Формат входного файла:
T
test_1
...
test_T
Где T --- число тестов, а каждый test_i есть
X
M
N
p^0_1 p^1_1 K_1
...
p^0_N p^1_N K_N ,
Все числа могут отделятся друг от друга любым числом пробельных символов.
Пробельными символами являются пробел, табуляция, перевод строки.
Выходные данные
Результаты расчета по каждому тесту должны быть выведены на стандартный вывод.
Результат каждого расчета должен быть предварен строкой
***** i где i --- номер теста.
Далее должен следовать результат расчета в одной из двух форм:
Expert group refuses to work.
Expected percentage of agreed: Q %
Spent on parlament: T_d
Spent on expert group: T_e
President's income: T_p
Пример входных данных:
2
10
20
1
0.3 0.3 10
100
20
5
0.7 0.8 10
0.3 0.8 20
0.9 0.7 10
0.1 0.2 5
0.4 1.0 7
Пример выходных данных
***** 1
Expert group refuses to work.
***** 2
Expected percentage of agreed: 70%
Spent on parlament: 27
Spent on expert group: 20
President's income: 53
Вот так вота. Вота чё я у себя на харддиске сёднечко с утреца вдруг нашел. Дадада, ЭТИ задачи предлагались к решению на факультетсткой студолимпиаде ВМиК МГУ от 1999 года...
Выложил их сюда, чтобы и вы все здесь тоже улыбнулись, партайкамрады...
Описание
Комитет Островной Безопасности Одного Островного Государства ведет следствие по группе опасных международных преступников
и компьютерных пиратов, использующих фирму Маленькие Мягкие Машины (МММ) для прикрытия своей грязной деятельности.
В ближайшее время преступники планируют провести очередное совещание, содержание которого совершенно необходимо знать следствию.
Однако президент компании, некто Б.~Воротов, очень осторожен и тщательно проверяет места преступных совещаний на предмет подслушивающих устройств и прочей техники. Все попытки комитета внедрить агента в преступную среду также не увенчались успехом.
Последняя надежда комитета --- новейшее передвижное подслушивающее устройство типа таракан.
Устройство типа таракан выполнено в корпусе из прочной пластмассы в форме таракана и способно к перемещению по плоской поверхности согласно заданной программе.
Комитету удалось раздобыть планы всех комнат, в которых возможно будет проходить совещание (окончательно место совещания выбирается в самый последний момент).
Эксперты комитета определили оптимальное место, в котором должно размещаться устройство, а также исходное положение для таракана в области, которая наверняка не будет проверяться перед совещанием.
План комнаты представляет собой прямоугольную сетку, на которой отмечены препятствия, непроходимые для устройства. Препятствия имеют форму прямоугольников. Несколько прямоугольников могут объединяться, формируя препятствие более сложной формы. Однако, если два препятствия лишь касаются друг друга (то есть прямоугольники на плане имеют только общее ребро или вершину), устройство способно проникать в щель между ними.
Прямоугольник, обозначающий препятствие, может иметь нулевую ширину или высоту, соответствуя на местности, например, уступу. Устройство может двигаться вдоль такого препятствия, но не может его пересекать.
Вам необходимо написать программу, которая для заданной конфигурации комнаты и препятствий найдет кратчайший путь от начальной до конечной точки.
Входные данные
Файл со входными данными для вашей программы будет иметь название
a.dat.
Формат входного файла:
K
room_1
...
room_K
Где K --- число комнат для расчета, а каждый room_k есть \
x_c y_c \
x_t y_t \
N \
x^1_1 y^1_1 x^1_2 y^1_2 \
... \
x^N_1 y^N_1 x^N_2 y^N_2 \
где (x_c,y_c) --- исходное положение таракана,
(x_t,y_t) --- положение цели,
N (0 le N le 50) --- число препятствий,
(x^i_1,y^i_1) и (x^i_2,y^i_2) --- координаты двух
противоложных вершин i -того препятствия (прямоугольника).
Все координаты --- целые числа в интервале [0, 10000] .
Все числа могут отделятся друг от друга любым числом пробельных символов.
Пробельными символами являются пробел, табуляция, перевод строки.
Выходные данные
Ваша программа должна напечатать результаты своей работы на {\it стандартный вывод}. Результаты должны быть представлены в
следующей форме.
Ответ для каждого теста должен предваряться строкой:\\
{\tt #\#\#\#\# } i \
где i --- номер теста.
В зависимости от входных данных ваша программа должна печатать одну или несколько строк, как описано ниже:
Cockroach' position is invalid.\\ если исходная позиция таракана находится в непроходимой области;
Target position is invalid. если конечная позиция таракана находится в непроходимой области;
Cockroach is at the target. если исходная позиция таракана совпадает с конечной;
Target is unreachable. если и исходная и конечная позиции таракана допустимы, но конечная позиция не может быть достигнута (загорожена непроходимыми препятствиями);
Minimal distance is D если исходная и конечная позиции таракана допустимы и существует маршрут от начальной до конечной точки длины D .
D должно быть округлено до двух знаков после десятичной точки.
Пример
2
0 30
20 30
4
10 0 0 60
0 0 60 10
50 0 60 60
0 60 60 50
0 0 100 100
1 30 30 70 70
Пример выходных данных:
##### 1
Target is unreachable.
##### 2
Minimal distance is 152.32.
Задача C: Парламент
Описание
Совсем недавно в Одном Островном Государстве разразился правительственный кризис, в результате которого все правительство во главе с премьер-министром было отправлено в отставку.
По Конституции государства, новый премьер-министр назначается президентом, но должен пройти процедуру утверждения своей кандидатуры в парламенте.
Зная оппозиционные настроения парламента по отношению к новой кандидатуре премьер-министра, президент решил обратиться за помощью к некоему финансовому магнату, имеющему близкие связи с кандидатом в премьеры и заинтересованному в утверждении.
Финансовый магнат выделяет некоторую сумму X тугриков (6 тугриков примерно равны 1 доллару США), которая должна быть истрачена на убеждение депутатов в необходимости утверждения кандидата. Парламент государства состоит из N (0 < N < 1000) депутатов, которые всегда ходят на все заседания и голосуют всегда либо <за >, либо <против > (воздержавшихся и не голосовавших не бывает).
О каждом депутате i парламента известно априорное отношение этого депутата к кандидатуре премьер-министра, выражаемое в вероятности p_i^0 (0 <= p_i^0 <= 1) , с которой данный депутат проголосует <за > кандидатуру.
Однако если на убеждение депутата потратить K_i тугриков, депутат обычно обещает поддержать кандидата, но, поскольку голосование тайное, в действительности депутат голосует <за > с вероятностью p_i^1 (0 <= p_i^1 <= 1) . По предыдущему опыту общения президента с парламентом известно, что если президенту удается заручиться предварительной поддержкой 70 % голосов депутатов, нужное решение всегда проходит.
С другой стороны, президент желал бы сэкономить как можно больше денег, ибо его финансовое положение несколько пошатнулось в результате кризиса на азиатских рынках. Поэтому он готов заплатить 10 % от сэкономленной суммы за наилучший вариант убеждения депутатов и за сохранение конфеденциальности. Экспертная группа при президенте готова произвести необходимые расчеты, но при условии, что она в любом случае получит как минимум M тугриков (и как максимум --- 10 % от сэкономленной суммы). Если выделенная магнатом сумма будет меньше M , то группа отказывается даже производить расчет. Если сумма будет больше M , но окажется недостаточной для обеспечения прохождения кандидатуры (с учетом оплаты работы группы), группа расчитает, на какой максимальный процент голосов в поддержку может расчитывать президент. Весь остаток суммы X , не потраченный на депутатов и группу экспертов, остается в распряжении президента.
Замечания:
Все денежные суммы ограниничены сверху валовым национальным продуктом страны, составляющим 10000 тугриков;
Ожидаемое число голосов вычисляется по формуле sum limits_{i=1}^{N}p_i , где p_i либо p_i^0 , либо p_i^1 , в зависимости от того, проводилась ли работа по данному депутату.
Входные данные
Файл со входными данными для вашей программы будет иметь название
c.dat.
Формат входного файла:
T
test_1
...
test_T
Где T --- число тестов, а каждый test_i есть
X
M
N
p^0_1 p^1_1 K_1
...
p^0_N p^1_N K_N ,
Все числа могут отделятся друг от друга любым числом пробельных символов.
Пробельными символами являются пробел, табуляция, перевод строки.
Выходные данные
Результаты расчета по каждому тесту должны быть выведены на стандартный вывод.
Результат каждого расчета должен быть предварен строкой
***** i где i --- номер теста.
Далее должен следовать результат расчета в одной из двух форм:
Expert group refuses to work.
Expected percentage of agreed: Q %
Spent on parlament: T_d
Spent on expert group: T_e
President's income: T_p
Пример входных данных:
2
10
20
1
0.3 0.3 10
100
20
5
0.7 0.8 10
0.3 0.8 20
0.9 0.7 10
0.1 0.2 5
0.4 1.0 7
Пример выходных данных
***** 1
Expert group refuses to work.
***** 2
Expected percentage of agreed: 70%
Spent on parlament: 27
Spent on expert group: 20
President's income: 53
Вот так вота. Вота чё я у себя на харддиске сёднечко с утреца вдруг нашел. Дадада, ЭТИ задачи предлагались к решению на факультетсткой студолимпиаде ВМиК МГУ от 1999 года...
Выложил их сюда, чтобы и вы все здесь тоже улыбнулись, партайкамрады...