Тема №7703 Решение олимпиадных задач по информатике 4
Поиск задачи:

Рассмотрим тему Решение олимпиадных задач по информатике 4 из предмета Информатика и все вопросы которые связанны с ней. Из представленного текста вы познакомитесь с Решение олимпиадных задач по информатике 4, узнаете ключевые особенности и основные понятия.

Уважаемые посетители сайта, если вы не согласны с той информацией которая представлена на данной странице или считаете ее не правильной, не стоит попросту тратить свое время на написание негативных высказываний, вы можете помочь друг другу, для этого присылайте в комментарии свое "правильное" решение и мы его скорее всего опубликуем.

Задача A. Турист
Гена собирается на туристический слет учеников своей школы. В своем классе он был назначен ответственным за палатки. У себя дома он нашел 3 палатки: первая из них весит a1 килограмм и вмещает b1 человек, вторая весит a2 килограмм и вмещает b2 человек, третья весит a3 килограмм и вмещает b3 человек.
В классе Гены K человек. Выясните, может ли он выбрать палатки так, чтобы в них все могли поместиться. При этом учитывайте, что выбранные палатки должны суммарно весить не более W килограмм.
Входные данные
Первая строка входного файла INPUT.TXT содержит два целых числа: K и W (1 ≤ K ≤ 15,
1 ≤ W ≤ 30). Вторая строка содержит шесть целых чисел: a1, b1, a2, b2, a3, b3 (1 ≤ a1, a2, a3 ≤ 10, 1 ≤ b1, b2, b3 ≤ 15).
Выходные данные
В выходной файл OUTPUT.TXT выведите YES, если палатки указанным образом выбрать
можно, и NO в противном случае.
Примеры

№  INPUT.TXT  OUTPUT.TXT
1

10 10

5 5 6 6 4 5

YES
2

10 10

5 5 6 6 7 7

 

NO
 


Разбор
Задача решается методом перебора. Существует всего 7 вариантов выбрать палатки и для
каждого из них проверить суммарные массы и вместимости. Если хоть один вариант
возможен, то вывести «YES», иначе «NO».
Программа
var
 k, w, a1, a2, a3, b1, b2, b3 : integer;
 t : boolean;
begin
 assign(input, 'input.txt'); reset(input);
 assign(output, 'output.txt'); rewrite(output);
 read(k,w);
 read(a1,b1,a2,b2,a3,b3);
 t:=false;
 if (b1+b2+b3>=k)and(a1+a2+a3<=w) then t:=true;
 if (b2+b3>=k)and(a2+a3<=w) then t:=true;
 if (b1+b3>=k)and(a1+a3<=w) then t:=true;
 if (b1+b2>=k)and(a1+a2<=w) then t:=true;
 if (b1>=k)and(a1<=w) then t:=true;
 if (b2>=k)and(a2<=w) then t:=true;
 if (b3>=k)and(a3<=w) then t:=true;
 if t then write('YES') else write('NO');
 close(output)
end. 

Задача B. К-удивительные числа
Переворотом числа X назовем число, в котором все цифры числа X стоят в обратном порядке. Например, переворотом числа 6372 является число 2736, а числа 7800 - 87. Назовем K-удивительным такое число, которое в сумме со своим переворотом дает число K. Например, у числа 222 имеется всего два K-удивительных числа: 111 и 210, а у числа 1050 имеется девять K-удивительных числа: 129, 228, 527, 426, 525, 624, 723, 822, 921. Требуется написать программу, которая по заданному K определит количество K-удивительных чисел.
Входные данные
Входной файл INPUT.TXT содержит одно натуральное число K (1 ≤ K ≤ 106).
Выходные данные
Выходной файл OUTPUT.TXT должен содержать одно число – количество
K-удивительных чисел.
Примеры

№  INPUT.TXT  OUTPUT.TXT
1

2 2 2

2
2

1 0 5 0

9
 

Разбор
Организуем перебор всех чисел от 1 до заданного. Для каждого числа проверяем его K-
удивительность.
Программа
var
 k, i, j, m, s : longint;
begin
 assign(input,'input.txt'); reset(input);
 assign(output,'output.txt'); rewrite(output);
 read(k);
 s:=0;
 for i:=1 to k do
 begin
 j:=i; m:=0;
 while j>0 do
 begin
 m:=m*10+j mod 10;
 j:=j div 10
 end;
 if i+m=k then s:=s+1
 end;
 write(s)
end.


Задача C. Роман в томах
В романе N глав. В i-той главе ai страниц. Требуется издать роман в K томах так, чтобы
объем самого «толстого» тома был минимален. В каждом томе главы располагаются по
порядку своих номеров.
Требуется написать программу, которая найдет количество страниц в самом «толстом»
томе.
Входные данные
Входной текстовый файл INPUT.TXT содержит в первой строке число N (1 ≤ N ≤ 100). Во
второй строке через пробел записаны N чисел – количество страниц в каждой главе.  Количество страниц в романе не превышает 32767. В третьей строке записано число K (1 ≤ K
≤ N).
Выходные данные
Выходной файл OUTPUT.TXT должен содержать количество страниц в самом «толстом»
томе.
Примеры

№  INPUT.TXT  OUTPUT.TXT
1

3

1 2 1

2

3
2

4

1 2 1 1

3

2



Разбор
Задача решается методом динамического программирования. Обозначим через B(i, j) –
количество страниц в самом «толстом» томе из i глав, если их издавать в j томах по
требуемому в условии задачи условию. Получим рекуррентные соотношения на эту
величину. Если j=1, то = ∑ . Для издания романа в j+1 томе в последний том могут
попасть главы: либо i (ai страниц), либо i-1 и i (ai-1 и ai страниц), …, либо j+1, j+2, …, i
∑ страниц). Для каждого из этих способов размещения глав в j+1 томе величина B для j
томов уже вычислена. Берем максимум из этих величин и находим минимум из всех
способов.
Программа
var
 a, b, c : array [1..100] of integer;
 n, k, i, j, s, min, l, t : integer;
function max(a,b:integer):integer;
begin
 if a>b then max:=a else max:=b
end;
begin
 assign(input,'input.txt'); reset(input);
 assign(output,'output.txt'); rewrite(output);
 read(n);
 for i:=1 to n do read(a[i]);
 read(k);
 s:=a[1]; b[1]:=a[1];
 for i:=2 to n do
 begin s:=s+a[i]; b[i]:=s end;
 for j:=2 to k do
 begin
 for i:=j to n do
 begin
 min:=maxint; s:=0;
 for l:=1 to i-j+1 do
 begin
 s:=s+a[i-l+1];
 t:=max(s,b[i-l]);
 if t<min then min:=t
 end;
 c[i]:=min
 end; 

b:=c
 end;
 write(b[n])
end.
Задача D. Газон
Фермер Иван с юности следит за своим газоном. Газон можно считать плоскостью, на которой в каждой точке с целыми координатами растет один пучок травы. В одно из воскресений Иван воспользовался газонокосилкой и постриг некоторый прямоугольный участок газона. Стороны этого участка параллельны осям координат, а две противоположные вершины расположены в точках (x1, y1) и (x2, y2). Следует отметить, что пучки травы, находящиеся на границе этого прямоугольника, также были пострижены. Довольный результатом Иван купил и установил на газоне дождевальную установку. Она была размещена в точке с координатами (x3, y3) и имела радиус действия струи r. Таким образом, установка начала поливать все пучки, расстояние от которых до точки (x3, y3) не превышало r. Все было хорошо, но Ивана заинтересовал следующий вопрос: сколько пучков травы оказалось и пострижено, и полито в это воскресенье?
Требуется написать программу, которая позволит дать ответ на вопрос Ивана. Входные данные
Первая строка входного файла INPUT.TXT содержит четыре целых числа x1, y1, x2, y2
(−100 000 ≤ x1 < x2 ≤ 100 000; −100 000 ≤ y1 < y2 ≤ 100 000). Во второй строке записаны три
целых числа x3, y3, r (−100 000 ≤ x3, y3 ≤ 100 000; 1 ≤ r ≤ 100 000)
Выходные данные
В выходной файл OUTPUT.TXT необходимо вывести одно целое число – число пучков
травы, которые были и пострижены, и политы.
Пример

 

№  INPUT.TXT  OUTPUT.TXT
1

0 0 5 4

4 0 3

14

Разбор
Одно из возможных решений данной задачи заключается в следующем. Для каждой прямой, содержащей все пучки травы с равной координатой по оси абсцисс (аналогично можно рассматривать и ось ординат), найдем ее точки пересечения с окружностью, отображающей область действия поливальной установки, если, конечно, такие точки существуют. Получив данные точки, не сложно за время O(1) посчитать количество пучков травы на данной прямой одновременно и политых, и постриженных. Это делается с помощью операции вычисления целой части числа. Далее, просуммировав найденные числа для всех прямых, можно найти ответ на поставленную задачу. Не сложно показать, что время работы рассматриваемого решения будет O(r). 


Категория: Информатика | Добавил: Админ (18.08.2016) Просмотров: | Рейтинг: 0.0/0

Другие задачи:
Всего комментариев: 0
avatar