DUNDRG - Editorial

#PROBLEM LINK:

Practice : Click

Contest : Click

Author:Soham Chakrabarti
Tester:Arkapravo Ghosh

Editorialist:Soham Chakrabarti

#DIFFICULTY:

Cakewalk

#PREREQUISITES:

Primes, Time to think

#PROBLEM:

Again a problem!

Agniva is trapped inside the Dungeon and is about to be executed by the king of NumberLand.

Dotionmo, zoindrek and Pavo has travelled across 2 cities to help Agniva get out of this trouble. They have almost reached Agniva, when suddenly, the king of NumberLand surprises them with another trap.

“Hahahah! You Fools.”, he says.

"You have only 5 minutes to solve my puzzle, and it will be very very HARD.

Once you solve the hardest problem of NumberLand, we will release Agniva."

The problem statement:

  1. Agniva will be provided N cards in a bag.

  2. Every Card will have a number from 1 to N (inclusive).

  3. Agniva will pick a card at random from the bag, without looking at it (lets call it ‘x’). Note :: He has to read all the cards from the bag.

  4. You will decide if the number ‘x’ has exactly 3 divisors. If true, shout ‘YES’.

and “Remember!”, says Mr. Soham.

“The number x is divisible by ‘1’ and the number ‘x’ .”

“I will keep a count of the number of times, you say the words ‘YES’”, says Mr. Soham.

The friends don’t want dragons after them. Help them :stuck_out_tongue:

#EXPLANATION:

We can solve this problem by finding the primes using a seive. Square all primes till the squared value is less than N.

Keep the count. Print it.

#AUTHOR'S AND EDITORIALIST'S SOLUTIONS:

Author's and editorialist’s solution can be found (here).
1 Like

@nuttela

I don’t understand why my code is giving runtime error .

https://www.codechef.com/viewsolution/22855416

//