[AtCoder] AtCoder Beginner Contest 367

Posted on Edited on In ,

A - Shout Everyday

In the Kingdom of AtCoder, residents are required to shout their love for takoyaki at A o’clock every day.

Takahashi, who lives in the Kingdom of AtCoder, goes to bed at B o’clock and wakes up at C o’clock every day (in the 24-hour clock). He can shout his love for takoyaki when he is awake, but cannot when he is asleep. Determine whether he can shout his love for takoyaki every day. Here, a day has 24 hours, and his sleeping time is less than 24 hours.

Constraints

  • 0 ≤ A, B, C < 24
  • A, B, and C are pairwise different.
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

1
A B C

Output

Print Yes if Takahashi can shout his love for takoyaki every day, and No otherwise.

Analysis

Takahashi is required to shout his love for takoyaki at A o’clock every day.

Takahashi goes to bed at B o’clock and wakes up at C o’clock.

We need to determine if A falls within Takahashi’s waking hours.

case:

  • B<C: Takahashi sleeps within the same day, A is not in [B, C)
  • B>C: Takahashi sleeps at midnight, wakes up at C the next day, A is not in [B, 24], [0, C)

Pseudocode:

1
2
3
4
5
6
7
8
if b < c:
    if a >= b and a < c:
        no 
else if b > c:
    if a <=c && a > b:
        no

yes

Solution

1
2
3
4
5
6
7
8
9
10
11
def shout_love(a, b, c):
  if b < c:
    if a >= b and a < c:
      return 'No'
  else: # b > c
    if a >= b or a < c:
      return 'No'
  return 'Yes'

a, b, c = map(int, input().split())
print(shout_love(a, b, c))

B - Cut .0

A real number X is given to the third decimal place.

Print the real number X under the following conditions.

  • The decimal part must not have trailing 0s.
  • There must not be an unnecessary trailing decimal point.

Constraints

  • 0 ≤ X < 100
  • X is given to the third decimal place.

Input

The input is given from Standard Input in the following format:

1
X

Output

Output the answer.

Analysis

Pseudocode

1
2
3
4
5
6
7
8
9
10
11
12
get input as X
Convert X to a list of characters

def cut_zero(X):
	count = 0

    while len(X) > 0 and X[-1] == '0':
        X.pop()
        count++
    if count == 3:
        X.pop()
    return X as a string

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
def cut_zero(X):
    count = 0
    
    while len(X) > 0 and X[-1] == '0':
        X.pop()
        count += 1
    if count == 3:
        X.pop()
    
    return ''.join(X)

X = list(input())
print(cut_zero(X))

A simple version:

1
2
3
4
5
def cut_zero(X):
    return str(float(x))

X = list(input())
print(cut_zero(X))

C - Enumerate Sequences

Print all integer sequences of length $N$ that satisfy the following conditions, in ascending lexicographical order.

  • The $i$-th element is between 1 and $R_i$, inclusive.
  • The sum of all elements is a multiple of $K$.

Constraints

All input values are integers.

  • $1 \leq N \leq 8$
  • $2 \leq K \leq 10$
  • $1 \leq R_i \leq 5$

Input

The input is given from Standard Input in the following format:

1
2
N K
R1 R2 …… RN

Output

Print the answer in the following format, where X is the number of sequences to print, the i-th of which is $A_i$=($A_{i, 1}$, $A_{i, 2}$,…,$A_{i, N}$):

1
2
3
4
A1,1 A1,2 ... A1,N
A2,1 A2,2 ... A2,N
...
AX,1 AX,2 ... AX,N

Analysis

Generate All Sequences: You need to generate all possible sequences of length N. For each sequence, the i-th element can range from 1 to $R_i$. The total number of possible sequences is $R_1 \times R_2 \times \dots \times R_N$.

Lexicographical Order: The sequences must be printed in lexicographical order, meaning sequences that are “smaller” in dictionary order should come first.

Sum as a Multiple of K: For each generated sequence, you must check whether the sum of its elements is a multiple of K. If not, discard that sequence.

Pseudocode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
get N, K, R

def generate_sequence(N, K, R):
    result = []
    current = []

    def backtrack(index):
        if index == N:
            if sum(current) % K == 0
            	result.append(current)
            return
        
        for i in range(1, R[index+1]):
            currunt.append(i)
            backtrack(index+1)
            currunt.pop()
            
    backtrack(0)
    return result

generate_sequence(N, K, R)

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def generate_sequence(N, K, R):
    result = []
    currunt = []

    def backtrack(index):
        if index == N:
            if sum(currunt)%K == 0:
                result.append(currunt.copy())
            return
    
        for i in range(1, R[index]+1):
            currunt.append(i)
            backtrack(index+1)
            currunt.pop()

    backtrack(0)
    return "\n".join(" ".join(map(str, row)) for row in result)

N, K = map(int, input().split())
R = list(map(int, input().split()))

print(generate_sequence(N, K, R))

D - Pedometer

There are N rest areas around a lake.
The rest areas are numbered 1, 2, …, N in clockwise order.
It takes $A_i$ steps to walk clockwise from rest area ii to rest area i+1 (where rest area N+1 refers to rest area 1).
The minimum number of steps required to walk clockwise from rest area ss to rest area tt (s≠t) is a multiple of M.
Find the number of possible pairs (s,t).