It's All In The Mind
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1138 Accepted Submission(s): 563
Problem Description
Professor Zhang has a number sequence a_1,a_2,...,a_n. However, the sequence is not complete and some elements are missing. Fortunately, Professor Zhang remembers some properties of the sequence:
1. For every i \in \{1,2,...,n\}, 0 \le a_i \le 100.
2. The sequence is non-increasing, i.e. a_1 \ge a_2 \ge ... \ge a_n.
3. The sum of all elements in the sequence is not zero.
Professor Zhang wants to know the maximum value of \frac{a_1+a_2}{\sum_{i=1}^{n}{a_i}} among all the possible sequences.
1. For every i \in \{1,2,...,n\}, 0 \le a_i \le 100.
2. The sequence is non-increasing, i.e. a_1 \ge a_2 \ge ... \ge a_n.
3. The sum of all elements in the sequence is not zero.
Professor Zhang wants to know the maximum value of \frac{a_1+a_2}{\sum_{i=1}^{n}{a_i}} among all the possible sequences.
Input
There are multiple test cases. The first line of input contains an integer T , indicating the number of test cases. For each test case:
The first contains two integers n and m (2 \le n \le 100, 0 \le m \le n) -- the length of the sequence and the number of known elements.
In the next m lines, each contains two integers x_i and y_i (1 \le x_i \le n, 0 \le y_i \le 100, x_i < x_{i+1}, y_i \ge y_{i+1}) , indicating that a_{x_i} = y_i .
The first contains two integers n and m (2 \le n \le 100, 0 \le m \le n) -- the length of the sequence and the number of known elements.
In the next m lines, each contains two integers x_i and y_i (1 \le x_i \le n, 0 \le y_i \le 100, x_i < x_{i+1}, y_i \ge y_{i+1}) , indicating that a_{x_i} = y_i .
Output
For each test case, output the answer as an irreducible fraction " p / q ", where p , q are integers, q > 0 .
Sample Input
2 2 0 3 1 3 1
Sample Output
1/1 200/201
Author
zimpha
Source
#include<stdio.h>
#include<iostream>
#include<string.h>
#include<string>
#include<ctype.h>
#include<math.h>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<bitset>
#include<algorithm>
#include<time.h>
using namespace std;
void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }
#define MS(x,y) memset(x,y,sizeof(x))
#define MC(x,y) memcpy(x,y,sizeof(x))
#define MP(x,y) make_pair(x,y)
#define ls o<<1
#define rs o<<1|1
typedef long long LL;
typedef unsigned long long UL;
typedef unsigned int UI;
template <class T1, class T2>inline void gmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void gmin(T1 &a, T2 b) { if (b<a)a = b; }
const int N = 105, M = 0, Z = 1e9 + 7, ms63 = 0x3f3f3f3f;
int casenum, casei;
int a[N];
int gcd(int x, int y)
{
return y == 0 ? x : gcd(y, x % y);
}
int main()
{
int n, m;
scanf("%d", &casenum);
for (casei = 1; casei <= casenum; ++casei)
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)a[i] = 0;
for (int i = 1; i <= m; ++i)
{
int x, y; scanf("%d%d", &x, &y);
a[x] = y;
}
if (!a[1])a[1] = 100;
if (!a[2])a[2] = a[1];
a[n + 1] = 0; int top = a[1] + a[2]; int bot = top;
for (int i = n; i >= 3; --i)
{
if (!a[i])a[i] = a[i + 1];
bot += a[i];
}
int g = gcd(top, bot);
printf("%d/%d\n", top/g, bot/g);
}
return 0;
}
/*
【trick&&吐槽】
这题我们是否要处理sum为0的情况？不需要，因为自然会规避。
【题意】
我们对不完整的数列a[]做填充。
使得——
1，a[]∈[0,100]
2，不上升
3，和非0
4，(a[1]+a[2])/sum尽可能大
【类型】
水题 讨论
【分析】
使得(a[1]+a[2])/sum尽可能大，也就是使得其倒数尽可能小。
也就是使得(a[3]+...+a[n])/(a[1]+a[2])尽可能小
所以显然——
1，我们要使得a[1]+a[2]尽可能大
2，我们要使得(a[3]+...+a[n])尽可能小（但是不能为负）
【时间复杂度&&优化】
O(n)
*/