# Whats Wrong!?!

[color=Blue]Given T (1 <= T <= 100) integers in the range (-1000,1000), representing percentages, calculate which letter grade each of them correspond to.
The mark table is as follows:
A = 80..100
B = 70.. 79
C = 60.. 69
D = 50.. 59
F = 0.. 49
X everything else

Input Format
Line 1: one integer T
Lines 2..T+1: one integer N

Output Format:
Lines 1..T: one character denoting the letter grade received

Input:
3
10
99
101

Output:
F
A
X
[/color]

[code]var
a,b:integer;
d: array [1..1000] of integer;

begin
for b:= 1 to a do

for a:= 1 to a do
begin
if (d[b]>=80) and (d[b]<=100) then
writeln('A')

else if (d[b]>=70) and (d[b]<=79) then
writeln('B')
else if (d[b]>=60) and (d[b]<=69) then
writeln('C')
else if (d[b]>=50) and (d[b]<=59) then
writeln('D')
else if (d[b] >= 49) then
writeln('F')
else
writeln('X');

end;
end.

«1

• [code]
var
i,j:integer;
d: array [1..1000] of integer;

begin
for i := 1 to j do

for [red]i[/red] := 1 to a j begin
if (d[i]>=80) and (d[i]<=100) then
writeln('A')
else if (d[i]>=70) and (d[i]<=79) then
writeln('B')
else if (d[i]>=60) and (d[i]<=69) then
writeln('C')
else if (d[i]>=50) and (d[i]<=59) then
writeln('D')
else if (d[i] [red]<=[/red] 49) [red]or (d[i] > 100)[/red] then
writeln('F')
else
writeln('X');
end;
end.
[/code]

Even better

[code]
var
i,j : integer;
d : array [1..1000] of integer;

begin
for i := 1 to i do

for i := 1 to j do
if d[i] > 100 then
writeln('X')
else if d[i] >= 80 then [red]{ no need to test d[i] <= 100 since d[i] > 100 }[/red]
writeln('A') [red]{ has been eliminated by previous test }[/red]
else if d[i] >= 70 then
writeln('B')
else if d[i] >= 60 then
writeln('C')
else if d[i] >= 50 then
writeln('D')
else if d[i] >= 0 then
writeln('F')
else
writeln('X');
end.
[/code]
?
• [color=Red]Given an integer N (0 <= N <= 200000) representing the mass of a letter in grams, print out the cost in cents to mail the letter.

The first line of input will be the number of test cases T (1 <= T <= 100). The following T lines will contain N. Output the cost in cents to mail the letter.

The pricing is as follows:
0 <= N <= 30 costs 38 cents
30 < N <= 50 costs 55 cents
50 < N <= 100 costs 73 cents
If N > 100 then the base cost is 73 cents, plus 24 cents for every additional 50 grams or part thereof.

Input:
2
5
101

Output:
38
97[/color]

[code]uses crt;
var
total,cost1,tt:integer;
a:array [1..100000] of integer;

begin
clrscr;
for total:= 1 to tt do

for total:= 1 to tt do
begin
if total<=30 then
writeln('38')

else if total<=50 then
writeln('55')

else if total<=100 then
writeln('73')

else if total>100 then
begin
cost1:= total-50;
writeln(73+24*(cost1 div 50));
end;
end;

end.[/code]

• : [code]: uses crt;
: var
: total,cost1,tt:integer;
: a:array [1..100000] of integer;
:
:
: begin
: clrscr;
: for total:= 1 to tt do
:
:
: for total:= 1 to tt do
: begin
: if total<=30 then [red]{ think about it -- if tt <= 30 then }[/red]
: writeln('38') [red]{ '38' gets printed every time } [/red]
:
: else if total<=50 then
: writeln('55')
:
: else if total<=100 then
: writeln('73')
:
: else if total>100 then
: begin
: cost1:= total-50;
: writeln(73+24*(cost1 div 50));
: end;
: end;
:
: end.[/code]:
:
:
:
:
[code]
uses crt;
var
i, t : 1 .. 100 ; [red]{ subrange of integer or byte }[/red]
n : 0 .. 200000 ; [red]{ subrange of longint - integer can only
go as high as 32767 }[/red]
cost : array [1 .. 100] of 0 .. 200000 ;

begin
clrscr;

for i := 1 to t do begin
if n <= 30 then
cost[i] := 38
else if n <= 50 then
cost[i] := 55
else if n <= 100 then
cost[i] := 73
else [red]{ n > 100 is only remaining possibility }[/red]
cost[i] := 73 + 24*(((n - 100) div 50) + 1)
end ;

for i := 1 to t do
writeln (cost[i]) ;

end.
[/code]
• [color=Blue]Given two integers N and M (N <= M), output all the prime numbers between N and M inclusive, one per line.

N and M will be positive integers less than or equal to 1,000,000,000.
The difference between N and M will be less than or equal to 5,000,000.

Sample Input

5 20

Sample Output

5
7
11
13
17
19[/color]
[color=Red]
and BTW thankx a lot for all your help!!! [/color]

[code]uses crt;
CONST
N = 100;

Var
P : Array [1 .. N] of boolean ;
i,q,j,m : longint;

begin
clrscr;

for i := 1 TO N do
P[i] := TRUE;

m := trunc(sqrt(N)) ;
for i := 2 to m do

if P[i] then
for j := 2 to N DIV i do
P[i * j] := FALSE ;

for i := 1 to q do
if P[i] then
if i>=r then
begin
writeln(i) ;
end;
end.

[/code]
• [code]
uses crt;
CONST
N = 100;

Var
P : Array [1 .. N] of boolean ;
i,j,m,q,[red]r[/red] : longint; [red]{ declare r - didn't compiler catch this? }[/red]

begin
clrscr;

for i := 1 TO N do
P[i] := TRUE;
[red]{
Sieve of Aristosthenes - good approach, but putting the
sieve in an array won't work for large N because memory
won't hold it. For large N you'll have to use a file.
}[/red]
m := trunc(sqrt(N)) ;
for i := 2 to m do
if P[i] then
for j := 2 to N DIV i do
P[i * j] := FALSE ;

for i := 1 to q do
if P[i] then
if i >= r then
begin
writeln(i) ;
end;
end.
[/code]

• Because the possible large interval we looking at any algorithm involving a look-up array won't work ( by using the sieve of Erathostenes, the biggest interval would be 'maxavail div 4', assuming that we are using longint's and real mode). The following method would work with some speed trade off ( before doing some optimizations, it covered the 5 million interval in about 3-4 minutes on my computer ):
[code][color=Blue]
program primes;

const max_val{ue}=1000000000;
max_dif{ference}=5000000;
mv:array[1..4] of byte=(2,3,5,7);

function is_prime(l:longint):boolean;
var l2:comp; {very large integer, to support square of max_value}
i:longint;
m:byte;
begin
for m:=1 to 4 do
if (l mod mv[m]=0) then begin
is_prime:=(l=mv[m]);
exit;
end;
l2:=mv[4];
while sqr(l2)min_v) and (max_v-min_v<=max_dif));
writeln;
n:=0;
for t:=min_v to max_v do
if is_prime(t) then begin
writeln(t);
inc(n);
end;
writeln(n,' number of primes found');
end.
[/color][/code]
• TIME LIMIT OF 2 SECONDS!! ANY IDEA..?
• : TIME LIMIT OF 2 SECONDS!! ANY IDEA..?
:
Wait a few years, then run the code on an entry level PC...:-)
• For one, this checks all the numbers right up to it, however we know that anything over half the number is not going to divide into it, so
[code]
while i<l2 do begin
inc(i,2);
[/code]

can be changed to:
[code]
while i < (l2 DIV 2) do begin
inc(i,2);
[/code]

however this is slow, so we use a shift instead:
[code]
while i < (l2 SHR 1) do begin
inc(i,2);
[/code]

Also, I would suggest that your main procedcure increments the prime checks by two and therefore only needs to do half the amount of function calls (slow).
• Alas, TP is not renowned for the the fast EXE's, to really speed things up ASM is the way to go. Parallel programming to take advantage of the todays multicore cpu's, 087 code + heavy optimization...but we don't want to switch from the good old TP.....
• True, but this seems like a homework question, so switching compilers is right out and using ASM is a little beyond what they want I think.
Then again, I could be wrong, in which case let's do some major ASM conversions & optimizations!
• : True, but this seems like a homework question, so switching
: compilers is right out and using ASM is a little beyond what they
: want I think.
: Then again, I could be wrong, in which case let's do some major ASM
: conversions & optimizations!

I think TP is out of question, I couldn't implement the Asm 64 bit division to handle the longint type. I guess the built in assembler is the culprit, I got the weirdest errors in some cases even killed the 16 bit virtual machine TP was running on. So turned to the latest version of Free Pascal ( using Intel's dialect for ASM ), have a [brute force / 2] algorithm running:
[code][color=Blue]
{brute force method, odd numbers only}
function is_prime_(l:longword):boolean;assembler;
asm
push ebp {Not sure is BP needs to be saved with FreePascal, but doesn't hurt}
mov ecx, 3
mov eax, l
mov esi,eax
@loop_:
mov eax,esi
cmp ecx, eax
jge @prime
mov ebx,ecx
xor edx,edx
div ebx
cmp edx,0
je @no_prime
jmp @loop_
@prime:
mov @result,true
jmp @end_
@no_prime:
mov @result,false
@end_:
pop ebp
end['eax','ebx','ecx','edx','esi'];
[/color][/code]
Now I did the optimizations to the original code what you suggested, everything looks fine with the smaller numbers, but the higher ranges return divergent results ( asm vs. pascal code ), I'm not sure so far what's going on, but soon I have some more time I'll get to the bottom of it... Oh, so far Pascal beats Asm in speed, due to the optimizations to the Pascal function and Free Pascal produces fast code comparable to GNU C.
• Not possible.
Even if you could calculate the insane amount of primes (50,847,534 between 0-1,000,000,000) the display could not output them in 2 sec. You might possibly be able to save them to a file (>200MB/sec write speed) but you also have to add in calculation time on top of that.
Again, Not possible.

• .............................
• The approach I would use is to generate a file containing all primes less than 1,000,000,000 and keep it on my computer permanently. Once you have that then writing [b]Function IsPrime(i : LongInt) : Boolean ;[/b] should be simple, and using binary search, it should be fast.

The problem with primes is that no one has ever found an elegant way to determine if a number is prime. Brute force is the only thing that works. Generating the file is going to take years, no matter what language, algorithm or tricks you use. My S.W.A.G. is 3 years on a 1 GigaHertz machine using ASM. Even a big Cray with thousands of coprocessors is not going to speed things up because the problem cannot be broken into smaller problems.

It is just possible that someone has done this and the file can be found on the open market, possibly even downloaded.