IUHCoder Contest Round 3

Time limit: 2.0s / Memory limit: 256M

Points: 100

Problem Statement

In some village, there are ~999~ towers that are ~1,(1+2),(1+2+3),...,(1+2+3+...+999)~ meters high from west to east, at intervals of ~1~ meter.

It had been snowing for a while before it finally stopped. For some two adjacent towers located ~1~ meter apart, we measured the lengths of the parts of those towers that are not covered with snow, and the results are ~a~ meters for the west tower, and ~b~ meters for the east tower.

Assuming that the depth of snow cover and the altitude are the same everywhere in the village, find the amount of the snow cover.

Assume also that the depth of the snow cover is always at least ~1~ meter.

Constraints
  • ~1 \leq a < b < 499500(=1+2+3+...+999)~
  • All values in input are integers.
  • There is no input that contradicts the assumption.
Input

Input is given from Standard Input in the following format:

~a~ ~b~

Output

If the depth of the snow cover is ~x~ meters, print ~x~ as an integer.

Sample Input 1
8 13
Sample Output 1
2

The heights of the two towers are ~10~ meters and ~15~ meters, respectively. Thus, we can see that the depth of the snow cover is ~2~ meters.

Sample Input 2
54 65
Sample Output 2
1
Time limit: 2.0s / Memory limit: 256M

Points: 100

Problem Statement

Việc rút tiền là một việc khó khăn, vì vậy một ngân hàng đã quyết định chỉ cho khách hàng với các mệnh giá sau:

  • ~1~ yen (Đơn vị tiền của Nhật)

  • ~6~ yen, ~6^2(=36)~ yen, ~6^3(=216)~ yen, ...

  • ~9~ yen, ~9^2(=81)~ yen, ~9^3(=729)~ yen, ...

Một vị khách đang cần đi vội, hỏi vị khách này cần rút ít nhất bao nhiều lần để được ~N~ yen tổng cộng?

Không được phép đổi lại số tiền bạn đã rút.

Constraints
  • ~1 \leq N \leq 100000~
  • ~N~ is an integer.
Input

Đầu vào được cung cấp từ Đầu vào chuẩn ở định dạng sau:

~N~

Output

Số lần rút ít nhất để được N yen

Sample Input 1
127
Sample Output 1
4

Số tiền rút như sau ~1~ yen, ~9~ yen, ~36(=6^2)~ yen and ~81(=9^2)~ yen, chúng ta sẽ có được ~127~ yen sau 4 lần rút.

Sample Input 2
3
Sample Output 2
3
Sample Input 3
44852
Sample Output 3
16
Time limit: 2.0s / Memory limit: 976M

Points: 100

Problem Statement

Có một dãy số ~N~ , ~a = ~ { ~a_1, a_2, a_3, ..., a_N~ }.
Aquarius muốn chơi đùa cùng dãy số này

Được biết cậu ấy có thể thực hiện phép tính sau bao nhiêu lần tùy thích:

Với mỗi vị trí ~i~ thuộc ~1 \leq i \leq N~ , Bạn có thể thực hiện các phép tính sau: "chia ~a_i~ cho ~2~ " hoặc "Nhân ~a_i~ cho ~3~ "

sao cho với mỗi ~i~ trong dãy đều phải có cả 2 phép tính

Thay vì như bao bài toán khác lần này Aquarius quyết định xử lý phức tạp hơn, cậu ấy tự hỏi có thể làm dãy số trên trở nên lẻ nhiều nhất bao nhiêu phép tính?

Thay vì ít nhất :333

Constraints
  • ~N~ là một số nguyên thuộc ~1~ và ~10 \ 000~
  • ~a_i~ là một số nguyên thuộc ~1~ và ~1 \ 000 \ 000 \ 000~
Input

Đầu vào được mô tả như sau:

~N~

~a_1~ ~a_2~ ~a_3~ ~...~ ~a_N~

Output

In số lượng phép tính nhiều nhất mà cậu ta có thể thực hiện

Sample Input 1
3
5 2 4
Sample Output 1
3

Chuỗi ban đầu là ~ {5, 2, 4} ~. Ba hoạt động có thể được thực hiện như sau:

  • Đầu tiên, nhân ~ a_1 ~ với ~ 3 ~, nhân ~ a_2 ~ với ~ 3 ~ và chia ~ a_3 ~ cho ~ 2 ~. Trình tự bây giờ là ~ {15, 6, 2} ~.
  • Tiếp theo, nhân ~ a_1 ~ với ~ 3 ~, chia ~ a_2 ~ với ~ 2 ~ và nhân ~ a_3 ~ với ~ 3 ~. Trình tự bây giờ là ~ {45, 3, 6} ~.
  • Cuối cùng, nhân ~ a_1 ~ với ~ 3 ~, nhân ~ a_2 ~ với ~ 3 ~ và chia ~ a_3 ~ cho ~ 2 ~. Trình tự bây giờ là ~ {135, 9, 3} ~.
Sample Input 2
4
631 577 243 199
Sample Output 2
0
Sample Input 3
10
2184 2126 1721 1800 1024 2528 3360 1945 1280 1776
Sample Output 3
39
Time limit: 2.0s / Memory limit: 1G

Points: 100

Problem Statement

There is a sequence of length ~N~ : ~A_1, A_2, ..., A_N~ . Initially, this sequence is a permutation of ~1, 2, ..., N~ .

On this sequence, Snuke can perform the following operation:

  • Choose ~K~ consecutive elements in the sequence. Then, replace the value of each chosen element with the minimum value among the chosen elements.

Snuke would like to make all the elements in this sequence equal by repeating the operation above some number of times. Find the minimum number of operations required. It can be proved that, Under the constraints of this problem, this objective is always achievable.

Constraints
  • ~2 \leq K \leq N \leq 100000~
  • ~A_1, A_2, ..., A_N~ is a permutation of ~1, 2, ..., N~ .
Input

Input is given from Standard Input in the following format

~N~ ~K~

~A_1~ ~A_2~ ~...~ ~A_N~

Output

Print the minimum number of operations required.

Sample Input 1
4 3
2 3 1 4
Sample Output 1
2

One optimal strategy is as follows:

  • In the first operation, choose the first, second and third elements. The sequence ~A~ becomes ~1, 1, 1, 4~ .

  • In the second operation, choose the second, third and fourth elements. The sequence ~A~ becomes ~1, 1, 1, 1~ .

Sample Input 2
3 3
1 2 3
Sample Output 2
1
Sample Input 3
8 3
7 3 1 8 4 6 2 5
Sample Output 3
4
Time limit: 2.0s / Memory limit: 256M

Points: 100

Problem Statement

There is a grid with ~N~ rows and ~N~ columns of squares. Let ~(i,j)~ be the square at the ~i~ -th row from the top and the ~j~ -th column from the left.

These squares have to be painted in one of the ~C~ colors from Color ~1~ to Color ~C~ . Initially, ~(i,j)~ is painted in Color ~c_{i,j}~ .

We say the grid is a good grid when the following condition is met for all ~i,j,x,y~ satisfying ~1 \leq i,j,x,y \leq N~ :

  • If ~(i+j) \% 3=(x+y) \% 3~ , the color of ~(i,j)~ and the color of ~(x,y)~ are the same.
  • If ~(i+j) \% 3 \neq (x+y) \% 3~ , the color of ~(i,j)~ and the color of ~(x,y)~ are different.

Here, ~X \% Y~ represents ~X~ modulo ~Y~ .

We will repaint zero or more squares so that the grid will be a good grid.

For a square, the wrongness when the color of the square is ~X~ before repainting and ~Y~ after repainting, is ~D_{X,Y}~ .

Find the minimum possible sum of the wrongness of all the squares.

Constraints
  • ~1 \leq N \leq 500~
  • ~3 \leq C \leq 30~
  • ~1 \leq D_{i,j} \leq 1000 (i \neq j),D_{i,j}=0 (i=j)~
  • ~1 \leq c_{i,j} \leq C~
  • All values in input are integers.
Input

Input is given from Standard Input in the following format:

~N~ ~C~

~D_{1,1}~ ~...~ ~D_{1,C}~

~:~

~D_{C,1}~ ~...~ ~D_{C,C}~

~c_{1,1}~ ~...~ ~c_{1,N}~

~:~

~c_{N,1}~ ~...~ ~c_{N,N}~

Output

If the minimum possible sum of the wrongness of all the squares is ~x~ , print ~x~ .

Sample Input 1
2 3
0 1 1
1 0 1
1 4 0
1 2
3 3
Sample Output 1
3
  • Repaint ~(1,1)~ to Color ~2~ . The wrongness of ~(1,1)~ becomes ~D_{1,2}=1~ .
  • Repaint ~(1,2)~ to Color ~3~ . The wrongness of ~(1,2)~ becomes ~D_{2,3}=1~ .
  • Repaint ~(2,2)~ to Color ~1~ . The wrongness of ~(2,2)~ becomes ~D_{3,1}=1~ .

In this case, the sum of the wrongness of all the squares is ~3~ .

Note that ~D_{i,j} \neq D_{j,i}~ is possible.

Sample Input 2
4 3
0 12 71
81 0 53
14 92 0
1 1 2 1
2 1 1 2
2 2 1 3
1 1 2 2
Sample Output 2
428
Time limit: 2.0s / Memory limit: 976M

Points: 100

Problem Statement

Takahashi became a pastry chef and opened a shop La Confiserie d'ABC to celebrate AtCoder Beginner Contest 100.

The shop sells ~N~ kinds of cakes.
Each kind of cake has three parameters "beauty", "tastiness" and "popularity". The ~i~ -th kind of cake has the beauty of ~x_i~ , the tastiness of ~y_i~ and the popularity of ~z_i~ .
These values may be zero or negative.

Ringo has decided to have ~M~ pieces of cakes here. He will choose the set of cakes as follows:

  • Do not have two or more pieces of the same kind of cake.
  • Under the condition above, choose the set of cakes to maximize (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity).

Find the maximum possible value of (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) for the set of cakes that Ringo chooses.

Constraints
  • ~N~ is an integer between ~1~ and ~1 \ 000~ (inclusive).
  • ~M~ is an integer between ~0~ and ~N~ (inclusive).
  • ~x_i, y_i, z_i \ (1 \leq i \leq N)~ are integers between ~-10 \ 000 \ 000 \ 000~ and ~10 \ 000 \ 000 \ 000~ (inclusive).
Input

Input is given from Standard Input in the following format:

~N~ ~M~

~x_1~ ~y_1~ ~z_1~

~x_2~ ~y_2~ ~z_2~

~:~ ~:~

~x_N~ ~y_N~ ~z_N~

Output

Print the maximum possible value of (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) for the set of cakes that Ringo chooses.

Sample Input 1
5 3
3 1 4
1 5 9
2 6 5
3 5 8
9 7 9
Sample Output 1
56

Consider having the ~2~ -nd, ~4~ -th and ~5~ -th kinds of cakes. The total beauty, tastiness and popularity will be as follows:

  • Beauty: ~1 + 3 + 9 = 13~
  • Tastiness: ~5 + 5 + 7 = 17~
  • Popularity: ~9 + 8 + 9 = 26~

The value (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) here is ~13 + 17 + 26 = 56~ . This is the maximum value.

Sample Input 2
5 3
1 -2 3
-4 5 -6
7 -8 -9
-10 11 -12
13 -14 15
Sample Output 2
54

Consider having the ~1~ -st, ~3~ -rd and ~5~ -th kinds of cakes. The total beauty, tastiness and popularity will be as follows:

  • Beauty: ~1 + 7 + 13 = 21~
  • Tastiness: ~(-2) + (-8) + (-14) = -24~
  • Popularity: ~3 + (-9) + 15 = 9~

The value (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) here is ~21 + 24 + 9 = 54~ . This is the maximum value.

Sample Input 3
10 5
10 -80 21
23 8 38
-94 28 11
-26 -2 18
-69 72 79
-26 -86 -54
-72 -50 59
21 65 -32
40 -94 87
-62 18 82
Sample Output 3
638

If we have the ~3~ -rd, ~4~ -th, ~5~ -th, ~7~ -th and ~10~ -th kinds of cakes, the total beauty, tastiness and popularity will be ~-323~ , ~66~ and ~249~ , respectively.
The value (the absolute value of the total beauty) + (the absolute value of the total tastiness) + (the absolute value of the total popularity) here is ~323 + 66 + 249 = 638~ . This is the maximum value.

Sample Input 4
3 2
2000000000 -9000000000 4000000000
7000000000 -5000000000 3000000000
6000000000 -1000000000 8000000000
Sample Output 4
30000000000

The values of the beauty, tastiness and popularity of the cakes and the value to be printed may not fit into 32-bit integers.

Time limit: 2.0s / Memory limit: 1G

Points: 50

Problem Statement

Let ~S(n)~ denote the sum of the digits in the decimal notation of ~n~ . For example, ~S(123) = 1 + 2 + 3 = 6~ .

We will call an integer ~n~ a Snuke number when, for all positive integers ~m~ such that ~m > n~ , ~\frac{n}{S(n)} \leq \frac{m}{S(m)}~ holds.

Given an integer ~K~ , list the ~K~ smallest Snuke numbers.

Constraints
  • ~1 \leq K~
  • The ~K~ -th smallest Snuke number is not greater than ~10^{15}~ .
Input

Input is given from Standard Input in the following format:

~K~

Output

Print ~K~ lines. The ~i~ -th line should contain the ~i~ -th smallest Snuke number.

Sample Input 1
10
Sample Output 1
1
2
3
4
5
6
7
8
9
19