Hercy wants to save money for his first car. He puts money in the Leetcode bank every day.
He starts by putting in $1 on Monday, the first day. Every day from Tuesday to Sunday, he will put in $1 more than the day before. On every subsequent Monday, he will put in $1 more than the previous Monday.
Given n, return the total amount of money he will have in the Leetcode bank at the end of the nth day.
Example 1:
Input: n = 4 Output: 10 Explanation: After the 4th day, the total is 1 + 2 + 3 + 4 = 10.
Example 2:
Input: n = 10 Output: 37 Explanation: After the 10th day, the total is (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4) = 37. Notice that on the 2nd Monday, Hercy only puts in $2.
Example 3:
Input: n = 20 Output: 96 Explanation: After the 20th day, the total is (1 + 2 + 3 + 4 + 5 + 6 + 7) + (2 + 3 + 4 + 5 + 6 + 7 + 8) + (3 + 4 + 5 + 6 + 7 + 8) = 96.
Constraints:
1 <= n <= 1000program main
implicit none
integer :: n, i, j
integer :: days(7), prev_days(7)
integer :: total
do while (.true.)
read(*,*) n
if (n == -1) exit
! Initialize the array with the starting values
days = (/1, 1, 1, 1, 1, 1, 1/)
! Loop through the days
do i=2,n
! If it's a Monday, add one to the previous Monday's value
if (mod(i,7) == 1) then
days(1) = days(1) + 1
else
! Otherwise, add one to the previous day's value
days(mod(i-1,7)+1) = days(mod(i-1,7)+1) + 1
end if
end do
! Print the total
write(*,'(I0)') sum(days)
end do
end program mainAt line 9 of file temp.f95 (unit = 5, file = 'stdin') Fortran runtime error: End of file Error termination. Backtrace: #0 0x7d81f1b42960 in ??? #1 0x7d81f1b434d9 in ??? #2 0x7d81f1d9717b in ??? #3 0x7d81f1d90684 in ??? #4 0x7d81f1d912aa in ??? #5 0x5a643a56c209 in MAIN__ #6 0x5a643a56c401 in main
PROGRAM LeetcodeBank
IMPLICIT NONE
INTEGER :: n, i, j, total
READ(*,*) n
total = 0
DO i = 1, n
IF (MODULO(i, 7) == 1) THEN
total = total + i
ELSE
total = total + (i - 1)
END IF
END DO
WRITE(*,*) total
END PROGRAM LeetcodeBank
At line 6 of file temp.f95 (unit = 5, file = 'stdin') Fortran runtime error: End of file Error termination. Backtrace: #0 0x799d1b924960 in ??? #1 0x799d1b9254d9 in ??? #2 0x799d1bb7917b in ??? #3 0x799d1bb72684 in ??? #4 0x799d1bb732aa in ??? #5 0x558fcb872209 in MAIN__ #6 0x558fcb872329 in main
def maxProductPath(grid):
m, n, mod = len(grid), len(grid[0]), int(1e9 + 7)
dp = [[[0, 0] for _ in range(n)] for _ in range(m)]
dp[0][0] = [grid[0][0], grid[0][0]]
for i in range(1, m):
dp[i][0] = [dp[i - 1][0][0] * grid[i][0], dp[i - 1][0][0] * grid[i][0]]
for j in range(1, n):
dp[0][j] = [dp[0][j - 1][0] * grid[0][j], dp[0][j - 1][0] * grid[0][j]]
for i in range(1, m):
for j in range(1, n):
if grid[i][j] < 0:
dp[i][j][0] = min(dp[i - 1][j][1], dp[i][j - 1][1]) * grid[i][j]
dp[i][j][1] = max(dp[i - 1][j][0], dp[i][j - 1][0]) * grid[i][j]
else:
dp[i][j][0] = max(dp[i - 1][j][0], dp[i][j - 1][0]) * grid[i][j]
dp[i][j][1] = min(dp[i - 1][j][1], dp[i][j - 1][1]) * grid[i][j]
return dp[m - 1][n - 1][0] % mod if dp[m - 1][n - 1][0] >= 0 else -1
The algorithm used is a dynamic programming approach, where we maintain a 3D DP array `dp` with dimensions m x n x 2. For each cell `dp[i][j]`, we store the maximum non-negative product and the minimum non-positive product of the path up until cell (i, j) in the grid. We initialize the first row and first column of the grid, and then iterate through the remaining cells.
At each cell, if the corresponding grid value is negative, the product of this value with the minimum non-positive value of the previous cells will give the maximum non-negative value for the current cell, and vice versa for minimum non-positive value. If the value is non-negative, multiplying by maximum non-negative values from previous cells will give the maximum non-negative value for the current cell, and similarly for minimum non-positive value.
After filling out the DP array, the result is the modulo of the maximum non-negative product of the last cell in the DP array, unless it's negative, in which case we return -1.
#include <vector>
using namespace std;
int maxProductPath(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), mod = 1e9 + 7;
vector<vector<vector<long long>>> dp(m, vector<vector<long long>>(n, vector<long long>(2)));
dp[0][0] = {grid[0][0], grid[0][0]};
for(int i = 1; i < m; i++) {
dp[i][0][0] = dp[i][0][1] = dp[i-1][0][0] * grid[i][0];
}
for(int j = 1; j < n; j++) {
dp[0][j][0] = dp[0][j][1] = dp[0][j-1][0] * grid[0][j];
}
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
if(grid[i][j] < 0) {
dp[i][j][0] = min(dp[i - 1][j][1], dp[i][j - 1][1]) * grid[i][j];
dp[i][j][1] = max(dp[i - 1][j][0], dp[i][j - 1][0]) * grid[i][j];
} else {
dp[i][j][0] = max(dp[i - 1][j][0], dp[i][j - 1][0]) * grid[i][j];
dp[i][j][1] = min(dp[i - 1][j][1], dp[i][j - 1][1]) * grid[i][j];
}
}
}
return dp[m - 1][n - 1][0] >= 0 ? dp[m - 1][n - 1][0] % mod : -1;
}
The algorithm used is a dynamic programming approach, where we maintain a 3D DP array `dp` with dimensions m x n x 2. For each cell `dp[i][j]`, we store the maximum non-negative product and the minimum non-positive product of the path up until cell (i, j) in the grid. We initialize the first row and first column of the grid, and then iterate through the remaining cells.
At each cell, if the corresponding grid value is negative, the product of this value with the minimum non-positive value of the previous cells will give the maximum non-negative value for the current cell, and vice versa for minimum non-positive value. If the value is non-negative, multiplying by maximum non-negative values from previous cells will give the maximum non-negative value for the current cell, and similarly for minimum non-positive value.
After filling out the DP array, the result is the modulo of the maximum non-negative product of the last cell in the DP array, unless it's negative, in which case we return -1.