oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

bribe Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

bribe.html

Problem Description

Rar the Cat is distributing flyers in order to supplement his income. Instead of distributing flyers at common areas like MRT stations and pet shops, he wants to bribe (or rather give a small reward) to his friends to help him distribute the flyers to their friends.

However, as smart as Rar the Cat is to devise this plan, he does not know how to choose friends to bribe! However, what he does know is how much money is required to bribe each friend, and the friendships between the friends. Therefore, help Rar the Cat calculate which friend is the most worthwhile to bribe. The measurement of worthwhile is calculated by the 'number of cats the flyer is distributed to' (including the one being bribed) divided by the 'cost of bribing the person selected'.

Friends are labelled from 1 to N, up to a total of N friends (if you can't count) and there will be a total of E friendships. In the event where more than 1 friends is the most worthwhile to bribe, output the one with the lower label instead.

Input

The first line of input consist of a single integer, N

The second line of input consists of N integers, with the ith integer being the cost to bribe the ith cat. All the numbers in this line will be positive and fit into a 32-bit signed integer.

The third line of input consist of a single integer, E

The following E lines will contain 2 integers each, A and B. This denotes a friendship between cat A and B. Friendships are known to be mutual and unique (no repeated A and B).

Output

Output a single integer, the label of the friend that is most worthwhile to bribe.

Limits

Subtask 1 (18%): 0 < N ≤ 200, 0 ≤ E ≤ 19900.

Subtask 2 (25%): 0 < N ≤ 3000, 0 ≤ E ≤ 300000.

Subtask 3 (57%): 0 < N ≤ 100000, 0 ≤ E ≤ 1000000.

Subtask 4 (0%): Sample Testcases

Implementation Details

Due the large amounts of input for this question, we recommend you use scanf/printf instead of cin/cout. A template for inputing and outputting is provided under attachment as well.

Sample Testcase 1

Input:

5
1 2 3 4 5
4
1 2
2 3
3 4
4 5

Output:

1

Tags

Graph Theory, Greedy

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
118201s64MBMinimum
225211s64MBMinimum
357211s64MBMinimum
4011s64MBMinimum

Attachments

Attachment Filesize Last Updated
bribe.cpp636B25 Jan 2013, 13:54:26

Judge Compile Command

g++-8 ans.cpp -o bribe -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.