## Pascal

Moderators: None (Apply to moderate this forum)
Number of threads: 4106
Number of posts: 14016

This Forum Only

Please help!!! Posted by Nemanja1234 on 22 Feb 2011 at 3:52 AM
Guys can you solve these 3 problems for me? thanks :D
Please solve at least one of these,Thanks very much!

1.Given is array (s1, ..., sn) of length n. Sign si is + or -. Given is array of n + 1 numbers (a1, ..., an+ 1).

You need to put numbers between signs so that solution of this expression is maximal. You need to find value val defined as:

val = max{ap(1) s1 ... ap(n) sn ap(n + 1) | p is a permutation of numbers from 1 to n + 1.

INPUT:
In first row of standard input is natural number n (1 <= n <= 100000). In second row are n signs s1 to sn. Every sign is '+' or '-'. Signs are not separated with empty space. In third row are n + 1 numbers: a1 to an + 1, separated with empty space. All this numbers are from interval [0, 1000000].

OUTPUT:
In first and only row of standard output, You need to write this maximal value val.

Input:
3
+-+
1 2 3 4

Output:
8

Explanation:
This is the only one solution
2+3-1+4

Input:
2
++
1 3 2

Output:
6

Explanation:
Every permutation of numbers gives optimal answer.

Input:
4
----
3 12 1 2 0

Output:
6

Explanation:
Every permutation with 12 on first place is optimal.
2.n Integers are given. You need to decompose these numbers in their factors, i.e. write them as product of their prime factors. Every number write in format p1^a1*p2^a2*...*pk^ak , where p1 <= p2 <= ... <= pk are prime factors of given number (in ascending order) and a1, a2, ..., ak - are their powers. Between factors and powers are symbols '*' and '^'. No empty spaces in printed solution.

INPUT:
In first line are integer n <= 200.000. In next n lines are numbers bi for decomposition (2 <= bi <= 200.000). Every number in separated line.

OUTPUT:
On standard output write decomposition in above given format.

Notice:
In 40% tests n <= 1.000

Input:
3
10
23
180

Output:
2^1*5^1
23^1
2^2*3^2*5^1
3.Next month will be auction for buying land on recently discovered new oil fields. Fields are spread under rectangular valley X by Y (Y represented number of rows and X represented number of columns). Lower left hectare have coordinate (1, 1). Hectare is square unit of land surface.

Your company have limited budget but also have right to choose and buy land before auction start. What sellers don’t know is that you have some satellite image of oil field positions

• No disjoint area of same oil field below surface. Two hectare units are joint if both have same side.
• Land on surface will be sell only in rectangular parts with integer sides.
• Minimal area to buy is two hectares.
• You can pump out oil from every oil field reachable from your land by digging straight downward.
• Price of one hectare is \$1,000,000.
• No two oil fields share same part of land (looking from above).

Since your company had long tradition in oil producing, equipment supply is unlimited. Your only goal is to take as much oil reserve as possible with your budget. If exist more then one part of land with maximal amount of reachable oil, you will take one that spare more money to your company. It will be only one part of valley match this conditions.

INPUT:
In first row of standard input are two integers Y and X, (0 < Y,X <= 50) dimension of valley.
Next Y rows of standard input contain X integers separated by blank space (IDi <= X x Y), identify oil field covered with this particular hectare of land. IDi = 0 means that no oil below this hectare.
In next row (Y+2) of standard input is integer M, (2,000,000 <= M <= \$1,000,000,000), budget for this purchase.

OUTPUT:
In first row of standard output write 4 integers separated with blank space (Xll Yll Xur Yur), coordinate of lower left and upper right rectangular part of valley, you can buy with proposed budget. If there is more than one solution, choose one that maximize remained money.
In second row of standard output write what is remained amount of money.
In third row of standard output write area of oil fields in hectares, available to you from your new land.

Input:
4 4
1 1 2 2
1 1 2 2
3 3 4 4
3 3 4 4
4012345

Output:
2 2 3 3
12345
16

Input:
4 4
0 7 7 7
3 3 5 5
3 5 5 5
3 3 3 9
4012345

Output:
2 2 2 4
1012345
14

Explanation for example 1: with \$4,000,000 for purchase, you can buy at most 4 hectare of land. Best solution is to buy 4 hectares in middle of valley because you can reach all 16 hectares of oil reserve in valley (oil fields with ID = 1, 2, 3, 4). In that case you spare \$12,345.
Explanation for example 2: with rectangular area (2,3) (3,4) you can reach 14 hectares of oil reserve as well as you buy (2,2) (2,4) but since you spare more money in second case, (2,2) (2,4) is desired solution (oil fields with ID = 3, 5, 7) .
Re: Please help!!! Posted by _Atex_ on 2 Mar 2011 at 9:39 AM
: Guys can you solve these 3 problems for me? thanks :D
: Please solve at least one of these,Thanks very much!

: 1.Given is array (s1, ..., sn) of length n. Sign si is + or -. Given
: is array of n + 1 numbers (a1, ..., an+ 1).
:
: You need to put numbers between signs so that solution of this
: expression is maximal. You need to find value val defined as:
:
: val = max{ap(1) s1 ... ap(n) sn ap(n + 1) | p is a permutation of
: numbers from 1 to n + 1.
:...............

Here's the solution for your first problem:
{ *** Compiler: FPC 2.x.x., should work with TP6+ as well *** }
{\$mode tp}

const max_element=12; // 12 numbers max, so the number of permutations be samller than

12! ( !=factorial )

type short_array=array[1..max_element] of integer;

// swaps two integers
procedure swap(var a,b:integer);
begin
if a=b then exit;
a:=a xor b;b:=a xor b;a:=a xor b; // fast arithmetic swap
end;

// sorts the first "l" elements of an array in ascending order
function sort(input:short_array;l{enght}:byte):short_array;
var i,j:byte;
begin
if not(l in [2..max_element]) then exit; // check for programmer error
for i:=l downto 2 do
for j:=1 to i do
if input[i]<input[j] then swap(input[i],input[j]); // simple bubble sort
sort:=input;
end;

// permutates an array, returns false if is the last combination possible according to

our algorithm
function permutate(var input:short_array;l{ength}:byte):boolean;
var i,j,k:byte;
trig{ger}:boolean;
begin
trig:=false;                         // (1) find the largest index "i", so:

input[i]<[i+1]
for i:=1 to l-1 do
if input[i]<input[i+1] then begin
trig:=true;
j:=i;
end;
if trig then begin
for i:=1 to l do                   // (2) find the largest index "i", so

input[j]<input[i]
if input[j]<input[i] then k:=i;
swap(input[j],input[k]);           // (3) swap elements "j","k"
inc(j);
for i:=0 to (l-j) div 2 do swap(input[j+i],input[l-i]); //  (4) reverse sequence from

"j+1" to "l"
end;
permutate:=trig;           // no index found in step 1, meaning: last possible

permutation
end;

// check if operator list is valid
function check(s:string;l:byte):boolean;
var i,sl:byte;
begin
sl:=byte(s[0]);
if sl=(l-1) then begin
for i:=1 to sl do if not(s[i] in ['+','-']) then begin check:=false;exit;end;
check:=true;
end else check:=false;
end;

// performs a calculation with the input's elements according to the "op" operator list
function calculate(input:short_array;l{ength}:byte;op{erator}:string):longint;
var i:byte;
r{esult}:longint;
begin
r:=input[1];
for i:=2 to l do if (op[i-1]='+') then r:=r+input[i] else r:=r-input[i];
calculate:=r;
end;

// calculate factorial
function factorial(b:longint):longint;
begin if b=0 then factorial:=1 else factorial:=b*factorial(b-1);end;

// calculate progress percentage
function calc_perc(a,b:longint):string;
var r:real;
s:string;
begin
r:=b*100/a;
str(r:3:3,s);
while byte(s[0])<7 do s:=#32+s;
calc_perc:=s+'%';
end;

/////////////////////////////////////////////////////////////////////////////////////////

/////////////////////////////
var a,b:short_array;
i,j:byte;
t,max{imum},count,max_fact:longint;
s:string[max_element-1];

begin
repeat
write('Enter array length [2..',max_element,'] : ');readln(j);
until (j in [2..max_element]);
for i:=1 to j do begin
write('Element [',i,'] = ');readln(a[i]);
end;
repeat
write('Enter operator list, must be ',j-1,' character long, ''+'' and ''-'' allowed

only : ');readln(s);
until check(s,j);

a:=sort(a,j);                           // array MUST be sorted in ascending order

before performing any permutations
max:=-2147483648;                       // the smallest value a longint can hold
count:=1;
max_fact:=factorial(j);                 // calculate no. of calculations neccessary

write('Progress: 000.000%');
t:=calculate(a,j,s);
if t>max then begin max:=t;b:=a;end;    //  new maximum found
while permutate(a,j) do begin           //  get next combination
t:=calculate(a,j,s);
if t>max then begin max:=t;b:=a;end;   //  new maximum found

inc(count);
write(#8#8#8#8#8#8#8#8,calc_perc(max_fact,count));  // display progress <-- slow,

remove for speed
end;

writeln(#13#10#13#10'Maximum possible value: ',max);
write('With the given combination: ',b[1]);
for i:=2 to j do write(s[i-1],b[i]);writeln;
readln;
end.

## Recent Jobs

Official Programmer's Heaven Blogs
Web Hosting | Browser and Social Games | Gadgets

Popular resources on Programmersheaven.com
Assembly | Basic | C | C# | C++ | Delphi | Flash | Java | JavaScript | Pascal | Perl | PHP | Python | Ruby | Visual Basic
© Copyright 2011 Programmersheaven.com - All rights reserved.
Reproduction in whole or in part, in any form or medium without express written permission is prohibited.
Violators of this policy may be subject to legal action. Please read our Terms Of Use and Privacy Statement for more information.
Operated by CommunityHeaven, a BootstrapLabs company.