AT_newjudge_2308_heuristic_a AtCoder Contest Scheduling (Online Version)

AtCoder currently hosts four types of contests, ABC, ARC, AGC, and AHC. As the number of users has grown, in order to meet the needs of more users, AtCoder has decided to increase the number of contests to 26 types, from AAC to AZC. For convenience, we number these 26 types as type 1 through type 26. For every day, AtCoder will hold exactly one contest, and each contest will end on that day. Please schedule contests so that user satisfaction is as high as possible. **The amount of satisfaction increased by holding a contest will depend on various factors, such as the schedule of contests other than AtCoder, etc. Therefore, instead of deciding on the entire schedule in advance, it is necessary to determine it one day at a time.** The satisfaction is calculated as follows. - The satisfaction at the beginning of day 1 is 0. Satisfaction can take negative values. - Holding contests increases satisfaction. The amount of increase will vary depending on a variety of factors, such as the schedule of contests other than AtCoder, the day of the week, and so on. Holding a contest of type $ i $ on day $ d $ will increase the satisfaction by $ s_{d,i} $ . **The value $ s_{d,i} $ is only revealed at the time of determining the contest to be held on day $ d $ , so when determining the contest on day $ d $ , the value of $ s_{d',i} $ is unknown for day $ d'\geq d+1 $ .** - If a particular type of contest is not held for a while, the satisfaction decreases. Each contest type $ i $ has an integer $ c_i $ , and at the end of each day $ d=1,2,...,D $ , the satisfaction decreases as follows. Let $ \mathrm{last}(d,i) $ be the last day before day $ d $ (including $ d $ ) on which a contest of type $ i $ was held. If contests of type $ i $ have never been held yet, we define $ \mathrm{last}(d,i)=0 $ . At the end of day $ d $ , the satisfaction decreases by $ \sum _{i=1}^{26}c_i \times (d-\mathrm{last}(d,i)) $ . ### Input & Output Format First, the number of days $ D $ and the rate of decrease in satisfaction $ c_i $ for each contest type $ i $ are given from Standard Input in the following format. > $ D $ $ c_1 $ $ c_2 $ $ \cdots $ $ c_{26} $ For all test cases, $ D = 365 $ is fixed and each $ c_i $ is an integer satisfying $ 0\leq c_i \leq 100 $ . After reading the above information, repeat the following process $ D $ times. In the $ d $ -th process ( $ 1\leq d\leq D $ ), the satisfaction $ s_{d,i} $ obtained by holding a contest of type $ i $ on day $ d $ is given from Standard Input in the following format. > $ s_{d,1} $ $ s_{d,2} $ $ \cdots $ $ s_{d,26} $ Each $ s_{d,i} $ is an integer satisfying $ 0\leq s_{d,i} \leq 100000 $ . After reading the above information, output the contest type $ t_d $ ( $ 1\leq t_d\leq 26 $ ) to be held on day $ d $ to Standard Output in a single line. **The output must be followed by a new line, and you have to flush Standard Output.** Otherwise, the submission might be judged as TLE. **Note that the input for day $ d+1 $ will not be given until you output $ t_d $ .** Your program may output comment lines starting with #. The web version of the visualizer displays the comment lines at the corresponding timing, which may be useful for debugging and analysis. Since the judge program ignores all comment lines, you can submit a program that outputs comment lines as is. #### Example $ d $ Input Output Prior information > 365 2 99 18 $ \cdots $ 24 1 > 20704 21183 16332 $ \cdots $ 9433 ``` 1 ``` 2 > 9611 17267 13088 $ \cdots $ 11234 ``` 2 ``` $ \vdots $ 365 > 14903 15204 7889 $ \cdots $ 10388 ``` 1 ``` [Show example](https://img.atcoder.jp/newjudge-2308-heuristic/af186b91.html?lang=en&seed=0)

N/A

N/A

### Scoring Let $ S $ be the satisfaction at the end of day $ D $ in the contest schedule determined by the submitted program. Let $ B $ be the satisfaction at the end of day $ D $ in the baseline schedule that holds a contest of type $ ((d-1)\% 26) + 1 $ on day $ d (1\leq d\leq D) $ . Here, $ (d-1)\% 26 $ denotes the remainder of dividing $ (d-1) $ by 26. Then, you will obtain a score of $ \max(S-B+1, 0) $ . For each test case, we compute the **relative score** $ \mathrm{round}(10^9\times \frac{\mathrm{YOUR}}{\mathrm{MAX}}) $ , where YOUR is your score and MAX is the maximum score among all competitors obtained on that test case. The score of the submission is the sum of the relative scores. The final ranking will be determined by the system test with more inputs which will be run after the contest is over. In both the provisional/system test, if your submission produces illegal output or exceeds the time limit for some test cases, only the score for those test cases will be zero, and your submission will be excluded from the MAX calculation for those test cases. The system test will be performed only for **the last submission which received a result other than CE** . Be careful not to make a mistake in the final submission. #### Number of test cases - Provisional test: 50 - System test: 1000. We will publish [seeds.txt](https://img.atcoder.jp/newjudge-2308-heuristic/seeds.txt) (sha256=83dc490c0904b4cbb1d541143bd1a6f478180b94df4f834d5d873330ffa62ad6) after the contest is over. #### About relative evaluation system In both the provisional/system test, the standings will be calculated using only the last submission which received a result other than CE. Only the last submissions are used to calculate the MAX for each test case when calculating the relative scores. The scores shown in the standings are relative, and whenever a new submission arrives, all relative scores are recalculated. On the other hand, the score for each submission shown on the submissions page is the sum of the evaluation value for each test case, and the relative scores are not shown. In order to know the relative score of submission other than the latest one in the current standings, you need to resubmit it. If your submission produces illegal output or exceeds the time limit for some test cases, the score shown on the submissions page will be 0, but the standings show the sum of the relative scores for the test cases that were answered correctly. #### About execution time Execution time may vary slightly from run to run. In addition, since system tests simultaneously perform a large number of executions, it has been observed that execution time increases by several percent compared to provisional tests. For these reasons, submissions that are very close to the time limit may result in TLE in the system test. Please measure the execution time in your program to terminate the process, or have enough margin in the execution time. ### Input Generation Let $ \mathrm{rand}(L,U) $ be a function that generates a uniform random integer between $ L $ and $ U $ , inclusive. Let $ \mathrm{normal}(\mu,\sigma) $ be a function that randomly generates a real value from the normal distribution with mean $ \mu $ standard deviation $ \sigma $ . Each $ c_i $ is generated by $ \mathrm{rand}(0,100) $ . For each $ i $ , the mean $ \mu_i $ and the standard deviation $ \sigma_i $ are generated by $ \mu_i=\mathrm{rand}(10000,20000) $ and $ \sigma_i=\mathrm{rand}(2000,8000) $ . Using these values, each $ s_{d,i} $ is generated by $ \min(\max(\mathrm{round}(\mathrm{normal}(\mu_i,\sigma_i)), 0), 100000) $ . ### Tools (Input generator and visualizer) - [Web version](https://img.atcoder.jp/newjudge-2308-heuristic/af186b91.html?lang=en) - [Local version](https://img.atcoder.jp/newjudge-2308-heuristic/af186b91.zip): You need a compilation environment of [Rust language](https://www.rust-lang.org/). - [Pre-compiled binary for Windows](https://img.atcoder.jp/newjudge-2308-heuristic/af186b91_windows.zip): If you are not familiar with the Rust language environment, please use this instead. Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited.