Please, help test № 9

Подскажите, как сократить время работы программы?
[code deleted]

Edited by moderator 19.11.2019 23:42

I have 9 times WA#9 and all becouse I don't use double...
If you have WA#9, use double in computing triliality, and get AC =)
Good Luck!

test2 pls

Какой там 2 тест?
у меня не проходит(time limted);

Паскаль почти все задачи по лимиту не проходят на одно и то же время, почему???

Ok, just search biggest prime number :)

Edited by author 04.02.2014 22:13

import java.util.Scanner;
public class problem1197 {

    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);
        int I = in.nextInt();
        int J = in.nextInt();

        if (I == 1) {
            System.out.println(1);
            return;
        }
        if (I == J) {
            System.out.println(I);
            return;
        }
        int deyer[] = new int[100001];
        int idx = 0;
        int min = 10000;
        int mineded = 0;

        for (int i = J; i >= I; i--) {

            for (int j = i / 2; j >= 1; j--) {

                if (i % j == 0) {
                    if (j < min) {
                        min = j;
                        mineded = i;
                        if (j == 1) {
                            System.out.println(i);
                            return;
                        }
                    }

                    break;
                }
            }
        }
        System.out.println(mineded);

    }
}

var i,j,i1,j1,s:longint;
    b:record s,num:longint; end;
begin
 readln(i1,j1);
 if i1>j1 then
 begin
  s:=j1; j1:=i1; i1:=s;
 end;
 b.s:=1000000;
 b.num:=1;
 for i:=j1 downto i1 do
 begin
  s:=0;
  for j:=1 to i div 2 do
    if i mod j =0 then s:=s+j;
  if ((b.s/b.num)-(s/i))<0.0001 then
  begin
   b.s:=s;
   b.num:=i;
  end;
  if s=1 then
  begin
   writeln(i);
   halt(0);
  end;
 end;
 writeln(b.num);
end.

Please, what is test 9? Can't find my mistake.

Edited by author 23.08.2011 23:02

I'm getting a 'runtime error: access violation' on my code. Please help me out. Here is the program in C++:


#include<iostream>
using namespace std;

int main()
{
int i,j,a,sum,p,q;
float small,ratio[30],x;
cin>>p>>q; //Inputs

//To find the ratio for each number in the interval i to j.

for(i=p;i<=q;i++)
{sum=0;
 for(j=1;j<i;j+=1)
 {
  if(i%j==0)
  {
   sum+=j;
  }
 }
ratio[i]=sum/i;
}

//To find the number with the smallest ratio and display it.

small=ratio[p];
for(i=p+1;i<=q;i+=1)
{
  if(ratio[i]<small)
  {
                    small=ratio[i];
                    x=i;
  }
}

cout<<x;

return 0;
}

My god! When I use gcc I get the right anwer, but vc++2010 doesn't.
What should I do?

HI
  I seem to be getting WA 5 everytime. Any ideas or hints on the test?
Here is what i do:
if start is 1 cout 1
for i=stop to start and for odd numbers
    for j= 2 to floor(sqrt(i))
        add the divisors
    if it is a primeNumber cout<<i

cout the number with least triviality.

I used someone about Sieve of Eratosthenes to seach a number))))

1) as you know triviality of 1 is 0
2) N + N/2 + N/3 + ... + N/N = NlnN
3) use long long instead of int

you should find nearest prime number to J if the number doesnt exist you should find odd number because even number's divisor sum is bigger:)

Edited by author 30.05.2010 18:53

Edited by author 30.05.2010 18:53

Edited by author 30.05.2010 18:54

Firts of all search the first biggest prime, if there doesn't exists any prime number,then do searching till sqrt..

#define MAXN 1000000
#include<iostream>
using namespace std;
bool isprime[MAXN+1];
void create(){
    memset(isprime,true,sizeof(isprime));
    isprime[0]=isprime[1]=false;
    for (int i=2;i*i<=MAXN;++i)
        for (int j=i*2;j<=MAXN;j+=i)
            isprime[j]=false;
}
double Triviality(int n){
    double sum;
    for (int i=1;i*2<=n;++i)
        if (n%i==0) sum+=(double)i;
    sum/=(double)n;
    return sum;
}
int main(void){
    create();
    int l,r;cin>>l>>r;
    if (l==1){
        cout<<"1"<<endl;
        return 0;
    }
    for (int i=l;i<=r;++i)
        if (isprime[i]){
           cout<<i<<endl;
           return 0;
        }
    double minimum=Triviality(l);
    int j=l;
    for (int i=l+1;i<=r;++i)
        if (minimum>Triviality(i)){
           j=i;
           minimum=Triviality(i);
        }
    cout<<j<<endl;
    return 0;
}

#include <iostream.h>
double a[1000000];
int sum(int);
bool prost(int);
int main()
{ int y=0,i,t,I,J; double N;
cin>>I>>J; t=I;
for(i=J;i>=I;i--)if(prost(i)) {cout<<i;y++; break;}
if(y==0) {for(i=0;i<=J-I;i++) {a[i]=(sum(t))/t;t++;}
N=a[0];
for(i=1;i<=J-I;i++) if(a[i]<N) N=a[i];
cout<<N;} return 0;}
int sum(int x)
{int s=0,i;
for(i=1;i<=x/2;i++) if(x%i==0) s+=i;
return s;}
bool prost(int x)
{int i; if(x==2) return true;
else for(i=2;i<=x/2;i++) if(x%i==0) return false;
return true;}

#include <iostream.h>
int sum(int);
int main()
{unsigned int i,m;  long a[1000000],I,J;
cin>>I>>J;
for(i=0;i<=J-I;i++) {a[i]=(sum(I))/I;I++;}
m=a[0];
for(i=1;i<=J-I;i++) if(a[i]<m) m=a[i];
cout<<m; return 0;}
int sum(int x)
{int s=0;
while(x!=0) {s+=x%10; x/=10;}
return s;}