백준 12178 (C++) Power Levels (Small)

최초 업로드: 2025-11-20 13:01:53

최근 수정 시간: 2025-11-20 13:01:53

게시자: rlatjwls3333

카테고리: 백준

# [Bronze I] Power Levels (Small)

[문제 링크](https://www.acmicpc.net/problem/12178)

## 문제 설명

A multifactorial -- that is, a number N followed by some nonzero number E of exclamation points -- is defined as the product of all positive numbers (N - K*E) for which K is a nonnegative integer. Normal factorials meet the definition of multifactorials, for example: 
 
5! = 5 * (5-1) * (5-2) * (5-3) * (5-4) = 120 
 
Here are the other multifactorials of 5: 
 
5!! equals 5 * (5-2) * (5-4) = 15 
 
5!!! equals 5 * (5-3) = 10 
 
5!!!! equals 5 * (5-4) = 5 
 
5 followed by five or more !s = 5 
 
5 with no exclamation points is not considered a multifactorial. 
 
The villainous Anima and her underling Minera love three things: multifactorials, yelling "IT'S OVER 9000" followed by some number of exclamation points, and going around the universe looking for people to fight. 
 
When Anima and Minera encounter a potential opponent, Anima asks Minera to use her scanner device to determine the opponent's power level, which is always a positive integer that does not begin with any leading zeroes. Today, the display on Minera's scanner is blurry, and she can only tell Anima the number of digits D in the opponent's power level, and not what any of those digits are. 
 
Anima wants to yell IT'S OVER followed by a multifactorial of 9000 to accurately describe the opponent's power level. She will never yell something that might not be true, and she will never use more exclamation points than she needs to. For example, if D = 31682, Anima can't yell IT'S OVER 9000!, because she knows that 9000! also has 31682 digits and the opponent's power level might be a 31682-digit number that is less than or equal to 9000!. However, since 9000!! has fewer than 31682 digits, she can be confident that the opponent's power level is greater than 9000!!, so IT'S OVER 9000!! is guaranteed to be true. Although the opponent's power level is also definitely greater than 9000!!!, 9000!!!!, and so on, she won't use more exclamation points than she needs to. So, in this example, she will yell IT'S OVER 9000!! 
 
If there is no multifactorial of 9000 that is definitely less than the opponent's power level, Anima will remain dramatically silent. We represent dramatic silence as an ellipsis: <code>...</code> 
 
What should Anima say?

## 입력

The first line of the input gives the number of test cases, T. T lines follow. Each contains a positive integer D, the number of digits in an opponent's power level.

<h3>Limits</h3>

## 출력

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is either <code>...</code> if Anima must remain silent, or <code>IT'S OVER 9000</code> followed by some positive number of exclamation points. Make sure your output exactly matches these specifications. You may wish to copy our apostrophe character into your code to avoid possible Unicode issues.

## 풀이
적어도 9000의 몇 멀티 팩토리얼인지 구하는 문제입니다. 구현의 난이도보단 해석의 난이도가 더 어렵습니다.

``` c++
#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;

void find(int d) {
 ull input=1;
 while(d-->1) input*=10;
 for(int i=1990;i<=9000;i++) {
 ull cur=1;
 for(int j=9000;j>=1;j-=i) cur*=j;
 if(cur<=input) {
 cout << "IT'S OVER 9000";
 for(int j=0;j<i;j++) cout << '!';
 cout << '\n';
 return;
 }
 }
 cout << "...\n";
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int t; cin >> t;
 for(int tc=1;tc<=t;tc++) {
 int d; cin >> d;
 cout << "Case #" << tc << ": ";
 find(d);
 }
}
```