codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

717C.md (2194B)


      1 Source: https://codeforces.com/problemset/problem/717/C
      2 
      3 C. Potions Homework
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Harry Water, Ronaldo, Her-my-oh-knee and their friends have started a new school year at their MDCS School of Speechcraft and Misery. At the time, they are very happy to have seen each other after a long time. The sun is shining, birds are singing, flowers are blooming, and their Potions class teacher, professor Snipe is sulky as usual. Due to his angst fueled by disappointment in his own life, he has given them a lot of homework in Potions class.
     22 
     23 Each of the *n* students has been assigned a single task. Some students do certain tasks faster than others. Thus, they want to redistribute the tasks so that each student still does exactly one task, and that all tasks are finished. Each student has their own laziness level, and each task has its own difficulty level. Professor Snipe is trying hard to improve their work ethics, so each student’s laziness level is equal to their task’s difficulty level. Both sets of values are given by the sequence *a*, where *a**i* represents both the laziness level of the *i*-th student and the difficulty of his task.
     24 
     25 The time a student needs to finish a task is equal to the product of their laziness level and the task’s difficulty. They are wondering, what is the minimum possible total time they must spend to finish all tasks if they distribute them in the optimal way. Each person should receive one task and each task should be given to one person. Print the answer modulo 10 007.
     26 
     27 Input
     28 
     29 The first line of input contains integer *n* (1 ≤ *n* ≤ 100 000) — the number of tasks. The next *n* lines contain exactly one integer number *a**i* (1 ≤ *a**i* ≤ 100 000) — both the difficulty of the initial task and the laziness of the *i*-th students.
     30 
     31 Output
     32 
     33 Print the minimum total time to finish all tasks modulo 10 007.
     34 
     35 Example
     36 
     37 Input
     38 
     39 ```
     40 2  
     41 1  
     42 3
     43 ```
     44 
     45 Output
     46 
     47 ```
     48 6
     49 ```
     50 
     51 Note
     52 
     53 In the first sample, if the students switch their tasks, they will be able to finish them in 3 + 3 = 6 time units.