fork download
copy 
  1. import java.util.*;
  2. import java.lang.*;
  3. import java.io.*;
  4.  
  5. class Main {
  6. 	private static long solve(int players, int a, int b, int c, int start) {
  7.         int strengths[] = new int[players];
  8.         strengths[0] = start;
  9.  
  10.         // calculate the strength of each player
  11.         for (int i = 1; i < players; i++) {
  12.         	int prev = strengths[i - 1];
  13.             strengths[i] = (a*prev*prev + b*prev + c) % 1000000;
  14.         }
  15.  
  16.         // We assemble two teams from the players. The teams choose the next
  17.         // member in alternation, and always choose the strongest player. So
  18.         // we sort the array, and always pick the top two.
  19.         //     But actually, we want the difference in strength. Therefore, each
  20.         // turn we pick the two strongest players, and sum up their differences.
  21.         // Note that due to the sorting, the difference will always be non-
  22.         // negative.
  23.         //     We have to special-case the possibility that there is an odd number
  24.         // of players.
  25.  
  26.         Arrays.sort(strengths);
  27.  
  28.         long difference = 0; // difference = team1 - team2
  29.         for (int i = players - 1; i >= 1; i -= 2) {
  30.             difference += strengths[i] - strengths[i - 1];
  31.         }
  32.         if (players % 2 != 0) {
  33.         	difference += strengths[0];
  34.         }
  35.  
  36.         return difference;
  37. 	}
  38.     public static void main (String args[]) {
  39.         try {
  40.             BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));
  41.             int numberOfTerms = Integer.parseInt(sc.readLine());
  42.             for (int i = 0; i < numberOfTerms; i++) {
  43.                 String fields[] = sc.readLine().trim().split(" ");
  44.                 int players = Integer.parseInt(fields[0]);
  45.                 int a = Integer.parseInt(fields[1]);
  46.                 int b = Integer.parseInt(fields[2]);
  47.                 int c = Integer.parseInt(fields[3]);
  48.                 int start = Integer.parseInt(fields[4]);
  49.  
  50.                 long difference = solve(players, a, b, c, start);
  51.                 System.out.println(difference);
  52.             }
  53.         } catch(Exception e) {
  54.             e.printStackTrace(System.out);
  55.         }
  56.     }
  57. }
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
4
1 1 1 1 1
2 1 1 1 1
3 1 2 3 4
4 2 3 4 1
stdout
copy 
1
2
763
74896
https://ideone.com/5vaIBI
language:
Java (HotSpot 12)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!