You are not logged in. Please login at www.codechef.com to post your questions!

×

COMAPR03 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Shikhar Kunal
Editorialist: Shikhar Kunal

DIFFICULTY:

EASY.

PREREQUISITES:

Math, Factorial

PROBLEM:

Given two strings representing repeated factorials of two input numbers. Compare them.

EXPLANATION:

It is not always possible to calculate the value by applying the factorial operation as the value will be very large. But the logic for this problem can be inferred from the constraints given in the problem. The integer part will always contain a value less than 10^9. The first number to have its factorial in the order of 10^9 is 12. So for all numbers less than or equal to 12, we expand one factorial sign and replace the no with the expanded number. We keep on doing this until the expanded number can overshoot 10^9. So, we keep on expanding only the numbers less than or equal to 12. We can choose to expand upto any number say 15, provided its factorial can be stored in a data type.
Example –
3!!!
4!!
3!!! Is expanded to 6!! because 3 is less than or equal to 12. Again 6!! Is expanded to 24!. Now 24! Is not expanded because it will exceed 10^9. So our first number is 24!
4!! Is expanded to 24!.
After the final expansion of the numbers, we will compare first the number of remaining factorial signs. If they are same, we will compare the integer part after the expansion to get the output.
This is because we are guaranteed that integer part of any input number will not exceed 10^9 and integer part of our expanded number will exceed 10^9 if we expand it one more time (is possible). Therefore, just by comparing the number of remaining factorial signs we can get the answer.

AUTHOR'S SOLUTIONS:

Author's solution can be found here.

This question is marked "community wiki".

asked 23 Feb '18, 18:55

akash1rakshit's gravatar image

5★akash1rakshit
7
accept rate: 0%

edited 24 Feb '18, 15:29

admin's gravatar image

0★admin ♦♦
19.8k350498541

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,852
×3,820
×1,220
×196
×16
×3

question asked: 23 Feb '18, 18:55

question was seen: 155 times

last updated: 24 Feb '18, 15:29