Title Description

On the national day of HH, the king invited NN ministers to play a prize game. First, he asked each minister to write an integer on his left and right hand, and the king himself wrote an integer on his left and right hand. Then let the}nn ministers line up and the king stand at the front of the line. After lining up, all ministers will receive several gold coins rewarded by the king. The number of gold coins received by each minister is: the product of the number on the left hand of everyone in front of the minister divided by the number on his own right hand, and then rounded down.

The king doesn't want a minister to get a lot of rewards, so he wants you to help him rearrange the order of the team, so that the minister who gets the most rewards will get as few rewards as possible. Note that the king is always at the front of the line.

Input format

The first line contains an integer nn indicating the number of ministers.

The second line contains two integers, {aa and} bb, separated by a space, representing the integers on the king's left hand and right hand, respectively.

Next, the ＾ nn line contains two integers aa ＾ and ＾ bb, separated by a space, representing the integers on each minister's left hand and right hand respectively.

Output format

An integer representing the number of gold coins won by the minister who received the most reward in the rearranged team.

Sample input and output

Enter #1 copy

3 
1 1 
2 3 
7 4 
4 6 

Output #1 copy

2

Description / tips

[description of input and output examples]

According to the arrangement of 11, 22 and 33 ， the number of gold coins won by the minister who won the most reward was ， 22;

According to the rank of ， 11,33,22 ， the minister who won the most reward received 22 gold coins;

Rank according to ， 22,11,33 ， and the minister who gets the most reward will get ， 22 gold coins;

According to the ranks of 22, 33 and 11, the minister who won the most rewards received 99 gold coins;

Rank according to ， 33, 11 and 22. The minister who gets the most reward will get ， 22 gold coins;

According to the arrangement of 33, 22 and 11 ， the minister who won the most reward received 99 ， gold coins.

Therefore, the minister who received the most reward received at least 22 gold coins, and the answer was 22.

[data range]

For 20% of the data, there are 1 ≤ n ≤ 10,0 < A, B < 81 ≤ n ≤ 10,0 < A, B < 8;

For 40% of the data, there are 1 ≤ n ≤ 20,0 < A, B < 81 ≤ n ≤ 20,0 < A, B < 8;

For 60% of the data, there are 1 ≤ n ≤ 1001 ≤ n ≤ 100;

For 60% of the data, ensure that the answer does not exceed 10 ^ 9109;

For 100% data, there are 1 ≤ n ≤ 1000,0 < A, B < 100001 ≤ n ≤ 1000,0 < A, B < 10000.

Second question of the first day of NOIP 2012 improvement group

#include <stdio.h>
#include <string.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#include<queue>
#pragma warning(disable:4996)
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
/*The difficulty lies in the team required by greedy ranking. Through greedy, we can know that the front and rear members A1 and A2 of the team meet the relationship of A1 * B1 < B2 * B2
    The high-precision multiplication num detail is the number of bits, which can be directly pulled to the maximum value and the prefix 0 can be deleted
    Use two loops, multiply num directly once, and then carry again
    High precision division num digit full analog operation Division
    Idea of this topic
    Greedy structure Sorting
    Use mul [] to record the product S of everyone in front
    Use temp [] to store the result of S divided by num
    Use ans [] to record the maximum value*/
const int N = 10010;
int mul[N];//Store the product S of everyone in front
int ans[N];//Record maximum
int temp[N];//Record everyone's gold coins
struct node
{
    int l;
    int r;
}a[N];
void cheng(int num)
{
    int i = 0;
    for (i = N; i >= 1; i--)
    {
        mul[i] *= num;
    }
    for (i = 1; i <= N; i++)
    {
        mul[i + 1] += mul[i] / 10;
        mul[i] %= 10;
    }
}
void chu(int num)
{
    int i = 0;
    int x = 0;
    for (i = N; i >= 1; i--)
    {
        x = x * 10 + mul[i];
        temp[i] = x / num;
        x %= num;
    }
}
int more()
{
    int i = 0;
    for (i = N; i >= 1; i--)
    {
        if (ans[i] < temp[i])
        {
            return 1;
        }
    }
    return 0;
}
void copy()
{
    int i = 0;
    for (i = N; i >= 1; i--)
    {
        ans[i] = temp[i];
    }
}
int comp(node x, node y)
{
    return x.l * x.r < y.l* y.r;
}
int main()
{
    int n = 0;
    cin >> n;
    int i = 0;
    for (i = 0; i <= n; i++)
    {
        cin >> a[i].l >> a[i].r;
    }
    sort(a+1,a+1+n,comp);
    mul[1] = 1;
    for (i = 0; i <= n; i++)
    {
        chu(a[i].r);
        if (more())
        {
            copy();
        }
        cheng(a[i].l);
    }
    int len = 0;
    for (i = N; i >= 1; i--)
    {
        if (ans[i] != 0)
        {
            len = i;
            break;
        }
    }
    for (i = len; i >= 1; i--)
    {
        cout << ans[i];
    }
   
}