Show all threads Hide all threads Show all messages Hide all messages |
What's wrong with my code? WA#9 | Artem Bakhretdinov | 1118. Nontrivial Numbers | 15 Oct 2023 23:28 | 1 |
#include <iostream> #include <limits> #include <cmath> bool isPrime(int n) { if (n <= 1) { return false; }
for (int i = 2; i * i <= n; i++) { if (n % i == 0) { return false; } }
return true; } int lowest_trivia_number (int I, int J) { double min_trivia = std::numeric_limits<double>::max(); int res = 0; for (int i = I; i <= J; i++) { int sum_of_own_denominators = 1; for(int j = 2; j <= std::sqrt(i); j++){ if(i % j == 0) { sum_of_own_denominators += j; if(j != i / j) { sum_of_own_denominators += i / j; } } } double cur_trivia = sum_of_own_denominators/i; if (cur_trivia < min_trivia) { min_trivia = cur_trivia; res = i; } } return res; } int main() { int I, J;
std::cin >> I >> J; if(I == 1) { std::cout << 1; return 0; } int largestPrime = -1; for (int num = J; num >= I; num--) { if (isPrime(num)) { largestPrime = num; break; } } if (largestPrime != -1) { std::cout << largestPrime << std::endl; } else { std::cout << lowest_trivia_number(I, J); } return 0; } |
To admins : triviality of 1 | _icy_ | 1118. Nontrivial Numbers | 26 Nov 2022 22:51 | 2 |
If you look at the statement, it says "Triviality of a natural number N is the ratio of the sum of all its proper divisors to the number itself. Recall that a proper divisor of a natural number is the divisor that is strictly less than the number.". Therefore, triviality of 1 should be 0 / 1 == 0, since 1 doesn't have any divisor strictly less than itself. However, I couldn't get an AC (WA4) until I changed the line if (I == 1) ans = 0 to if (I == 1) ans = 1. So, either the statement or the tests are broken. Edited by author 05.08.2022 19:55 Edited by author 05.08.2022 19:55 I'm not an admin. You must write the number with minimal triviality. Triviality(1) == 0, that means you have to print 1 because 1 is number with minimal triviality. But you try to print the triviality of 1(i.e. 0). The statement is correct. |
WA 7??? | mdebvisitor@mail.ru | 1118. Nontrivial Numbers | 4 Aug 2021 15:17 | 1 |
WA 7??? mdebvisitor@mail.ru 4 Aug 2021 15:17 I have WA on test 7. What i need to do? |
if you have WA7 | alp | 1118. Nontrivial Numbers | 4 Aug 2021 15:17 | 2 |
Output is EndPoint. EndPoint is simple. |
if u have WA5 | Rabbit Girl ♥ | 1118. Nontrivial Numbers | 4 Aug 2021 13:54 | 2 |
Not work. Can i give my code? |
Test 5??? | mdebvisitor@mail.ru | 1118. Nontrivial Numbers | 4 Aug 2021 13:52 | 1 |
Test 5??? mdebvisitor@mail.ru 4 Aug 2021 13:52 What is test 5? I can give my code(It's not working), runtime error(access violation) |
The time limit | Savchuk Nickolay | 1118. Nontrivial Numbers | 23 Mar 2021 17:29 | 1 |
Good afternoon! I am a programmer-beginner. I have written the code for this task on c++, but the time limit is exceeded on the second test! The code is this: ( https://ideone.com/Rh98zQ) #include <iostream> using namespace std; float ghj(int a) {int m; m=0; for(int l=1; l<a; l++) {if(a%l==0) {m=m+l;}} float c=(float(int(m))); float b=c/a; return b;} int main() { int i,j; cin >> i >> j; float p=ghj(i); int n=i; for(int o=i; o<=j; o++) {if(ghj(o)<p) {p=ghj(o); n=o;}} cout << n; return 0; } Tell me, please, how can I optimize the code? |
What can be the reason of WA 11? I'll be glad if you give some tests. | D4nick | 1118. Nontrivial Numbers | 19 Nov 2020 04:35 | 3 |
#include <iostream> using namespace std; int main() { long long i, j, iDel; long long biggestV = 9999999, biggestDel = 9999999; cin >> i >> j; if (i == 1) { cout << 1; return 0; } else if (i == j) { cout << i; return 0; } else if (i + 1 == j) { cout << (j % 2 != 0 ? j : i); return 0; } for (long long iV = j % 2 != 0 ? j : j-1; iV >= i; iV -= 2) { for (iDel = j / 3 + 1; iDel >= 1; iDel--) { if (iV%iDel == 0) { if (iDel < biggestDel) { biggestDel = iDel; biggestV = iV; } break; } } if (iDel == 1) { cout << iV; return 0; } } cout << biggestV; } In the main cycle you doesn't compare trivialities, you search the smallest biggest divisor in the weird range instead. Could you please show the mathematical proof of your main cycle? Edited by author 31.03.2020 14:11 Edited by author 31.03.2020 14:12 Hi.Did you solve this problem? |
Why wa 11?? | wiwi | 1118. Nontrivial Numbers | 19 Nov 2020 04:28 | 1 |
---- ll l,r; cin >> l >> r; if(l==1){ cout << 1; return 0; } if(l == r){ cout << l; return 0; } ll n = 1e6+2; vector<bool> prime(n+1,1); prime[0]=prime[1] = 0; for( ll i =2; i*i <= n; i++) { if(prime[i]) { for(ll j = i*i; j <= n; j+=i) prime[j]=0; } } for(ll i = r; i >= l; i--){ if(prime[i]) { cout << i; return 0; } } double mx =1e11; ll ans = 0; for(ll i = r; i >= l; i--){ if(i % 2 == 0) continue; double suma = 1; for(ll k = 2; k*k <= i; k++){ if( i % k == 0 ){ suma += k; if(i/k != k){ suma += (i/k); } } } double q=(suma)/(i); if( q < mx){ mx = q; ans = i; } } cout << ans; return 0; ---- I used the sieve of Eratosthenes to find prime numbers. If I have not found prime numbers on the interval [l; r], then I iterate over all numbers with [l; r]. I go through the divisors (sqrt (i)). I calculate the minimum. What's wrong? WA 11. Google translator, sorry. |
HELP PLEASE WA TEST#8 | Лерник Казарян [RAU] | 1118. Nontrivial Numbers | 11 Sep 2020 21:29 | 2 |
the right border is a Prime number |
2 Judges: TEST ARE WRONG!!! Here is a prove... (+) | Akshin Salimov | 1118. Nontrivial Numbers | 31 Dec 2018 14:35 | 9 |
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 What can you say about program which got wa? How can you make it to get AC? Your mistake is that you forget to add line prime:=true; in the end of prime(x) function AC!!! Akshin Salimov 21 Jan 2006 02:40 I got AC!!! Vladimir, Thank you very much! You are genius! Большое человеческое спасибо! My code: [code deleted] I have Time limit exceeded. I need optimal solution of this task. Help me please! Edited by moderator 19.11.2019 23:40 go to the sqrt(b), not to b/2 > 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? 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 |
Triviality(1)=? | Danila | 1118. Nontrivial Numbers | 31 Dec 2018 12:15 | 2 |
|
ASD | buyolitsez | 1118. Nontrivial Numbers | 13 Nov 2018 22:11 | 1 |
ASD buyolitsez 13 Nov 2018 22:11 assc Edited by author 20.03.2019 19:54 |
who can tell me test 3 plesaseeeeee write answer | BOTLMahir | 1118. Nontrivial Numbers | 13 Nov 2018 22:11 | 4 |
My code gives true answers for all tests but when I send problem it gives WA in test 3. please write answer. test 3 is nothing, but 2 1000000. So how should the answer look like? Is it the biggest possible prime number? you are right, just prime number |
AC in 0.015 | Aditya Singh | 1118. Nontrivial Numbers | 10 Feb 2018 15:29 | 2 |
[code deleted] Edited by moderator 19.11.2019 23:40 Hi, Very good solution! Just one note, it doesn't affect AC, but: In D+=(i+N/i); if (i == N/i) you don't need to add both i and N/i, but just i. In this case result of check(N) will be 100% equal to triviality(N) in all cases. |
Test 4 | LiZheng | 1118. Nontrivial Numbers | 25 Dec 2017 17:51 | 18 |
Test 4 LiZheng 15 Jul 2005 13:53 I always get WA on test 4,who can give me the testdata of test4.Help me!Thank you. Thank's for help! You're completely right! AC now! Of course I have same bugs. AC now I also have the same mistake.thanx a lot. Thank you very much!!!!!!! It is a very good advice! Thank you for your advice. I've gotten AC now.I wrote "1" if i=1. а как выглядит второе число? ведь тест - 2 числа, через пробел. Can you tell how look test4? the first is one, and the second is ..? Triviality(1) = 1 Triviality(1)=0 Edited by author 17.09.2015 23:28 Edited by author 17.09.2015 23:28 |
WA9 please help | genchildren | 1118. Nontrivial Numbers | 4 Jan 2017 13:48 | 2 |
#include <iostream> using namespace std; bool prime(long long n); int main() { long long a,odd, i, j, nice,b; cin >> a >> b; nice=0; if (a%2==1) {odd=a;} else {odd=a+1;} for (i=b; i>a; i--) { if (prime(i)) { nice=i; break; } } if ((a==1 or nice==0) and b!=a) { cout << odd;} else if (b==a) {cout << a;} else if (nice) {cout << nice << endl;} return 0; } bool prime(long long n) { bool w; w=n==2; if (!w and n%2) { w=1; for (int i=3; i*i<=n; i+=2) { if (n%i==0) { w=0 ; break; } } } if (w) { return 1; } else return 0; } Case "no prime is found" is suspicious. You think answer is the minimal odd number in the interval. Could you prove it? Why not maximal odd number in the interval? Why you don't want to do try brute force? |
Hint | Takanashi Rikka | 1118. Nontrivial Numbers | 20 Nov 2016 01:52 | 4 |
Hint Takanashi Rikka 26 Feb 2016 09:12 Calculates sum of divisors. O(lim * log(lim)). for(int i = 2; i <= lim; ++i){ ++s[i]; for(int j = i + i; j <= lim; j += i) s[j] += i; } Maybe I don't understand it clear, but I think it will get TL. Difficult of this algorithm = O(n^2) No, it's O(n log n). Learn some math. |
i got Ac use 0.02s | ruwelcome | 1118. Nontrivial Numbers | 25 May 2016 14:39 | 5 |
[code deleted] Edited by moderator 19.11.2019 23:41 nuuu.. che skazat nu krasavchik. thanks you , my pro is TLE :) |
Some tips (got AC using 0.031s) | Adrian | 1118. Nontrivial Numbers | 25 May 2016 14:37 | 4 |
First, triviality of 1 is 0. Second, we can judge number i from 2 to 1000000, if i is a prime number, then prime[i] is true. Third, we traversal i from b to a, because if j>i and prime[j]==true, prime[i]==true, we can get 1/j<1/i. if we get prime[i]==true,just output it and break. if we can not get such a number, calculate triviality of i and output the minimum. Thus, we can get AC with a little time spended,but larger memory. My English is poor, if you cannot understand me, I would say sorry for it.^__^ your english are good) i got it. may be i got it because my solution is similar yours=) Your english good enouth to speak with Russians) |