Relax! It's just a game(배열 조합, 단순)
Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %llu
Submit
Status
Practice
UVALive 4365
Description
You: What's the score? Did I miss much?
Me: It's 2-1 for elAhli and the second half just started. The first half was quite boring.
You: Who scored first? elAhli or ezZamalek?
Me: What difference does it make?
You: Big difference! I can predict the outcome of the match if I knew the order of which goals were scored in the first half.
Me: What do you mean?
You: It's 2-1 for elAhli, right? One of three things could have happened: elAhli scored two goals then ezZamalek scored; Or, elAhli scored its first goal, then ezZamalek, then elAhli again; Or, ezZamalek scored first, then elAhli scored its two goals.
Me:
So?!! I still don't understand what difference does that make? It's still 2-1 for elAhli! Why don't you just relax and let us continue watching the game in peace.
You:
You don't understand!! I believe theprobability of who'll win depends on the order of how goals were scored. Now I have to predict the outcome for 3 possibilities.
Me: And what if the score was 3-2? What would you have done then?
You: I would have to work for 5 different possibilities. No?
Me:
Of course not! The number of possibilities isn't always equal to the sum.
You: Can you tell me when will it be equal to the sum?
Me: You're a programmer, why don't you write a program that counts the number of possibilities and compare it to the sum?
You: I don't have the time, I want to watch the match. Besides, I have nine other problems to worry about.
Me: I'll give you a hint. The possibilities will be equal to the sum only if one of the teams scored a certain number of goals.
Input
Your program will be tested on one or more test cases. Each test case specifies two natural numbers (A and B) (separated by one or more spaces) representing the score of the first half. No team will be able to score more than 10 goals. The last line of the input file contains two -1's (which is not part of the test cases.)
Output
Format For each test case where the number of possibilities is equal to the sum, print:
A+B=C
Where A and B are as above and C is their sum. If the number of possibilities is not equal to the sum, replace the `=' sign with `!=' (without the quotes.)
Sample Input
2 1
1 0
-1 -1
Sample Output
2+1=3
1+0=1
사고방식: 골 총수는 a+b로 모든 배열 상황을 생각하기 쉽다(a+b)!,그러나 같은 팀이 넣은 공은 배열에서 서로 다른 것으로 간주해서는 안 된다. 예를 들어 갑팀이 2골을 넣은 경우: a1, a2, a1a2와 a2a1은 같은 배열이기 때문에 모든 배열 상황수는 (a+b)!/(a ! * b!),그래서 가능한 상황은 두 팀의 골이 합쳐졌을 때와 같다.
(a + b)!/(a ! * b!)= a+b, 즉 (a+b-1)!/(a ! * b!) = 1……(1)..이 관계를 이용하면 특정한 a와 b, 상황수와 a+b의 관계를 판단할 수 있다.제목에 제시된 힌트인'The possibilities will be equal to the sum only if one of the teams scored a certain number of goals'를 요약하면 알 수 있다. a, b의 최소값은 1이다. 즉, a와 b는 적어도 하나는 1이다.
또 주의해야 할 것은 a=b=0시 상황수는 골 총수와 같지 않고 이때 상황수는 1이다.
AC CODE:
//Memory: 0 KB Time: 12 MS
//Language: C++ 4.1.2 Result: Accepted
#include <iostream>
#include <cmath>
#include <string>
using namespace std;
long long fact(long long n)
{
if(n == 1 || n == 0) return 1;
else return n * fact(n - 1);
}
int main()
{
long long a, b;
int idx;
double p;
string str[2] = {"=", "!="};
while(cin >> a >> b && a != -1 && b != -1)
{
idx = 1;
if(a+b)
{
p = 1.0 * fact(a + b - 1) / fact(a) / fact(b);
if(fabs(p - 1) <= 1e-8)
idx = 0;
}
cout << a << "+" << b << str[idx] << a + b << endl;
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Access Request, Session and Application in Struts2If we want to use request, Session and application in JSP, what should we do? We can obtain Map type objects such as Req...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.