Формат входа

Задание "распилить палку [0, 10] в точках 2,3,4,7" будет на входе описано как

10 4

2 3 4 7

то есть формат входа есть

N k

L1 L2 ... Lk

Формат выхода

Выведите как-нибудь схему распила в первой строчке.

Во второй строчке выведите минимальную цену за распил.

динампрогрзадачи

Задача 35 Не параллельный слалом

В то время, как полным ходом продолжается Зимняя олимпиада в Salt Lake City олимпийский комитет обсуждает программу проведения следующих игр. На повестке дня вопрос включения в программу олимпиады нового вида спорта: “Не параллельный слалом”.

Суть соревнования в этом виде спорта заключается в следующем:

• соревнуются два лыжника;

• лыжники спускаются с горы с одинаковой скоростью;

• второй лыжник со старта уходит на L секунд позже первого;

• по пути следования лыжники собирают призы, каждый из которых оценивается в определенное количество баллов;

• призы находятся на одинаковом расстоянии друг от друга;

• по правилам соревнования, если лыжник берет приз, то он должен задержаться на 2*L секунд (если первый лыжник, опережающий второго на L секунд, берет очередной приз, то второй лыжник обгоняет первого и будет опережать его на L секунд; если же первый лыжник пропустит приз и этот приз возьмет второй лыжник, то в результате разрыв между лыжниками увеличится до 3*L секунд;

• лыжник, который лидирует, может брать или пропускать призы по своему усмотрению, тогда как отстающий лыжник обязан собирать все призы, мимо которых он проезжает;

• победитель определяется по разнице сумм баллов призов, собранных лыжниками.

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

Входной файл INPUT.TXT содержит натуральное число N (не превышает 100) – число призов на трассе, далее следуют N натуральных чисел (каждое не превышает 100) стоимости призов в порядке их следования по трассе.

Выходной файл OUTPUT.TXT должен содержать одно число - разницу баллов первого и второго лыжника.

Примеры:

Input.txt	Output.txt
4 5 3 3 5	0
3 3 1 2	2

var t: array[1..101, 1..101] of longint;

p: array[1..100] of longint;

n,ans: longint;

procedure Init;

var i: longint;

begin read(n); for i := 1 to n do read(p[i]); end;

function max(a, b: longint): longint;

begin if a > b then max := a else max := b; end;

procedure Solve;

var sall: longint;

i, j: longint;

begin

fillchar(t,sizeof(t),0);

sall := 0;

for i := n downto 1 do движемся с конца

begin

sall := sall + p[i]; находим сумму призов

for j := 1 to n do перебираем призы

if j = 1 then если это первый приз

t[i, j] := max(sall - t[i + 1, 1], t[i + 1, 2])

else

t[i, j] := max(t[i + 1, j - 1] + p[i], t[i + 1, j + 1]);

end;

ans := 2 * t[1, 1] - sall;

end;

begin

assign(input, 'input.txt'); reset(input); assign(output, 'output.txt'); rewrite(output);

Init; Solve; writeln(ans);

end.

динампрогрзадачи

Задача 36 Цифровой экран

Для проведения чемпионата Европы по футболу в Португалии было решено соорудить К-цветный цифровой экран NxM (N по вертикали, M по горизонтали) пикселей. Но в связи с тем, что экран большой, то работать можно только с прямоугольной областью экрана N1xM1 (N1 по вертикали, M1 по горизонтали) пикселей. Экран был сконструирован таким образом, что при его включении цвета пикселей присваиваются случайным образом, а необходимо, чтобы все пиксели были черного (0-го) цвета. Вам необходимо определить минимальное количество операций, необходимое для того, чтобы сделать из исходного экрана экран черного (0-го) цвета, или указать, что решения не существует. За одну операцию считается: взять прямоугольную область экрана N1xM1 (N1 по вертикали, M1 по горизонтали) пикселей, полностью принадлежащую экрану, и все номера цветов этой области увеличить на единицу по модулю K (т.е. если номер цвета равен K-1, то после увеличения станет 0).

Ограничения и уточнения 1 ≤ N1 ≤ N ≤ 1000 1 ≤ M1 ≤ M ≤ 1000 2 ≤ K ≤ 1000 Прямоугольная область берется строго N1 пикселей по вертикали и M1 по горизонтали (т.е. нельзя взять M1 пикселей по вертикали и N1 по горизонтали (повернуть))

Формат входных данных: В первой строке 2 числа N и М, разделенные одним пробелом Во второй строке 2 числа N1 и M1, также разделенные одним пробелом В третьей строке одно число K Далее идут N строк по M чисел в каждой (разделенные одним пробелом), все числа от 0 до K-1, - номера цветов пикселей.

Формат выходных данных: Если нет решения, то вывести -1 , иначе одно число - минимальное количество операций

Input.txt	Output.txt
4 5 3 2 5 3 0 3 0 4 0 4 4 1 1 0 4 4 1 1 2 4 1 1 2	20
3 4 2 2 0 0 2 2 2 1 2 0 2 1 0 1	5
3 3 2 2 2 1 1 0 1 1 1 0 1 1	-1

program Project2;

{$APPTYPE CONSOLE}

{$o-}

uses SysUtils,Math;

var a,f:array[0..1000,0..1000]of integer;

n,m,n1,m1,k,i,j,cur:integer;

begin

reset(input,'input.txt');

rewrite(output,'output.txt');

read(n,m,n1,m1,k);

for i:=1 to n do

for j:=1 to m do

read(a[i,j]);

fillchar(f,sizeof(f),0);

for i:=1 to n-n1+1 do

for j:=1 to m-m1+1 do

begin

f[i,j]:=f[i-1,j]+f[i,j-1]-f[i-1,j-1];

cur:=f[i,j]-f[max(0,i-n1),j]-f[i,max(0,j-m1)]+f[max(0,i-n1),max(0,j-m1)];

inc(f[i,j],(k-(a[i,j]+cur)mod k)mod k);

end;

for i:=1 to n do

for j:=1 to m do

begin

if (i>n-n1+1)or(j>m-m1+1) then f[i,j]:=f[i-1,j]+f[i,j-1]-f[i-1,j-1];

cur:=f[i,j]-f[max(0,i-n1),j]-f[i,max(0,j-m1)]+f[max(0,i-n1),max(0,j-m1)];

if (a[i,j]+cur)mod k<>0 then begin writeln(-1); halt(0); end;;

end;

writeln(f[n,m]);

close(input);

close(output);

end.

динампрогрзадачи

Задача 37 Искривленное пространство

Мощные поля тяготения искривляют пространство, сворачивают его как листок тонкой бумаги и если бесконечно долго лететь, то можно вернуться в исходную точку. Какую форму приобретает пространство после искривления - не знает никто, но можно предположить, что это форма одного из тел вращения изучаемых в стереометрии. Возможно это тор, известный народу как бублик. Предположим, до искривления пространства поверхность имела форму прямоугольника. Если сначала склеить противоположные горизонтальные стороны, а затем – противоположные вертикальные стороны этого прямоугольника то получается тело, которое называется тором.

Вам дан прямоугольник размера N x M, содержащий целые числа, например такой

1	4	3	1
-3	-2	0	-4
1	1	2	-5
-8	3	0	-3

Ваша задача заключается в том, чтобы на торе, который получается из данного прямоугольника, найти прямоугольник со сторонами, не превосходящими N и M, имеющий максимальную сумму элементов.

Например, в данном случае искомым будет выделенный прямоугольник с суммой элементов, равной 13:

1	4	3	1
-3	-2	0	-4
1	1	2	-5
-8	3	0	-3

Формат входных данных:

Первая строка содержит натуральные числа N и M (1 ≤ N,M ≤ 100). В последующих N строках по M целых чисел, разделенных пробелами. Все числа не превосходят 30000 по абсолютной величине.

Формат выходных данных:

Выведите максимальную сумму чисел в прямоугольнике.

Пример

Input.txt	Output.txt
4 4 1 8 -3 -2 -2 -2 4 -4 2 1 -6 -3 -4 1 0 –5	10
3 2 1 2 4 5 7 8	27

program tor;

{$APPTYPE CONSOLE}

uses SysUtils;

const //inf=1/0;

nmax=100;

var a,f:array[1..2*nmax+1,1..2*nmax+1] of int64;

n,m,nn,mm,i,j,i2,j2:longint;

ans,ff:int64;

procedure init;

begin

assign(input,'input.txt'); assign(output,'output.txt');

reset(input); rewrite(output);

end;

procedure closing;

begin

close(input);

close(output);

halt(0);

end;

begin

init;

read(n,m);

for i:=1 to n do

for j:=1 to m do

begin

read(a[i,j]);

a[i,j+m]:=a[i,j];

a[i+n,j]:=a[i,j];

a[i+n,j+m]:=a[i,j];

end;

mm:=m shl 1;

nn:=n shl 1;

for i:=nn downto 1 do бежим начиная с нижней строки справа налево

for j:=mm downto 1 do заполняя массив f

begin fij равен сумме всех чисел из прямоугольника

с левым верхним углом (ij)

f[i,j]:=f[i+1,j]+f[i,j+1]-f[i+1,j+1]+a[i,j];

end;

ans:=-maxint;

for i:=1 to n do перебираем все возможные прямоугольники

for j:=1 to m do

for i2:=1 to n do

for j2:=1 to m do

begin

ff:=f[i,j]+f[i+i2,j+j2]-f[i+i2,j]-f[i,j+j2];

if ff>ans

then

ans:=ff;

end;

write(ans);

closing;

end.

динампрогрзадачи

Задача 38 Прямоугольное королевство

В одном Прямоугольном королевстве правил старый и мудрый король. Было у него четыре сына. Все разные, но любил он их одинаково. И когда настала пора старому королю отойти от дел, то задумал он разделить свое царство на четыре части по справедливости и раздать своим сыновьям. А царство называлось Прямоугольным по той простой причине, что оно было прямоугольной формы и было поделено на равные квадраты. В каждом из этих квадратов было по одному селению, но численность селений отличалась. Богатство любой страны не территория, а люди. Мудрый король это знал. И решил он разделить свое королевство на четыре части двумя прямыми – вертикальной и горизонтальной по границам квадратов таким образом, чтобы количество людей в полученных четырех частях отличалось как можно меньше друг от друга. Проблема не простая. Попробуйте и вы решить ее.

Формат входного файла

Первая строка входного файла содержит натуральные числа N и M – размеры королевства в маленьких квадратах (2≤N,M≤250). В последующих N строках по M чисел в – количества людей в селениях Прямоугольного королевства, т. е. карта королевства по плотности населения. Все числа разделены пробелами. Численность любого селения не превышает 32000.

Формат выходного файла

В выходном файле два числа через пробел. Первое (больше 0 и меньше N) – номер строки, под которой должна проходить горизонтальная линия. Второе (больше 0 и меньше M)– номер столбца, после которого должна проходить вертикальная линия.

Примеры

Input.txt	Output.txt
2 2 1 4 3 2	1 1
4 5 3 5 2 3 100 1 2 0 4 20 3 4 5 6 90 6 0 4 7 250	3 4

program z3;

{$APPTYPE CONSOLE}

uses SysUtils,Math;

var n,m,i,j:integer;

A,S:array[0..1000,0..1000] of int64;

mn,c:int64;

x,y:integer;

function f(a,b:integer):int64;

var

lu,ld,ru,rd:int64;

begin

lu := S[a,b];

ld := S[n,b] - S[a,b];

ru := S[a,m] - S[a,b];

rd := S[n,m] - lu - ld - ru;

f := max(lu,max(ld,max(ru,rd))) - min(lu,min(ld,min(ru,rd)))

end;

begin

assign(input,'input.txt');reset(input);

assign(output,'output.txt');rewrite(output);

read(n,m);

fillchar(S,sizeof(S),0);

for i := 1 to n do

for j := 1 to m do

begin

read(A[i,j]);

S[i,j] := S[i-1,j] + S[i,j - 1] - S[i - 1,j - 1] + A[i,j];

end;

mn := maxint;

x := 0;

y := 0;

for i := 1 to n - 1 do

begin

for j := 1 to m - 1 do

begin

c := f(i,j);

if mn > c then

begin

mn := c;

x := i;

y := j;

end;

end;

end;

writeln(x,' ',y);

close(input);

close(output);

end.