ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1118. Nontrivial Numbers

2 Judges: TEST ARE WRONG!!! Here is a prove... (+)
Posted by Akshin Salimov 20 Jan 2006 20:36
Judjes tell me after you read my message, I will delete
an AC program.

Here is th 1st program it got WA#3:

[Program was deleted by author, beacuse it got AC =)]
[Thx Vladimir! Judges if you need it, I can post it.]


Here is 2nd program it got AC:

[Program was deleted by author]
[Judges if you need it, I can post that code for a while]

Here is one test:
318 330

Correct answer is 323 (Triviality(323)=0.114551)
AC programs answer for this tests was :
324 (Triviality(324)=1.619195)

It means that AC program gave incorrect answer, but
program which got WA#3 gave correct answer!!!
It's shameful!!!

Edited by author 20.01.2006 20:49

Edited by author 21.01.2006 02:45
Sometimes wrong programs get AC...
Posted by Vladimir Yakovlev (USU) 20 Jan 2006 22:18
Re: Sometimes wrong programs get AC...
Posted by Akshin Salimov 20 Jan 2006 22:50
What can you say about program which got wa?
How can you make it to get AC?
Re: Sometimes wrong programs get AC...
Posted by Vladimir Yakovlev (USU) 21 Jan 2006 02:21
Your mistake is that you forget to add line
prime:=true;
in the end of prime(x) function
AC!!!
Posted by Akshin Salimov 21 Jan 2006 02:40
I got AC!!!
Vladimir, Thank you very much! You are genius!
Большое человеческое спасибо!
help me please
Posted by Nash 8 Jul 2007 00:31
 My code:
#include <stdio.h>

#pragma comment(linker, "/STACK:16777216")
int a,b,c,i,k,n,j;
float min = 6555,d;

void main()
{
scanf("%d",&a);
scanf("%d",&b);

for(i=a;i<=b;i++)
    {

    {n=0;
        for(k=1;k<=b/2;k++)
        {

            {if(i%k==0)
                {

                    n=n+k;


                }

            }
            }


            d=(float)n/i;

            if (d<min)
            {
                min=d;
                j=i;
            }



    }
printf("%d",j);
    }



}

I have Time limit exceeded. I need optimal solution of this task. Help me please!
Re: help me please
Posted by Uros Poznan 8 Dec 2016 23:45
go to the sqrt(b), not to b/2
Re: help me please
Posted by PO 31 Dec 2018 12:32
> go to the sqrt(b), not to b/2

could you help understanding why? for 20 the triviality is `(1+2+4+5+10)/20`, kind of meaning you would need to go to b/2. no?
Re: help me please
Posted by PO 31 Dec 2018 14:35
gotcha. you can do (i + N/i), so the N/i bit will make sure you would need to go only up to sqrt(N). thanks