You are given a string s of lowercase English letters and an array widths denoting how many pixels wide each lowercase English letter is. Specifically, widths[0] is the width of 'a', widths[1] is the width of 'b', and so on.
You are trying to write s across several lines, where each line is no longer than 100 pixels. Starting at the beginning of s, write as many letters on the first line such that the total width does not exceed 100 pixels. Then, from where you stopped in s, continue writing as many letters as you can on the second line. Continue this process until you have written all of s.
Return an array result of length 2 where:
result[0] is the total number of lines.result[1] is the width of the last line in pixels.Example 1:
Input: widths = [10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10], s = "abcdefghijklmnopqrstuvwxyz " Output: [3,60] Explanation: You can write s as follows: abcdefghij // 100 pixels wide klmnopqrst // 100 pixels wide uvwxyz // 60 pixels wide There are a total of 3 lines, and the last line is 60 pixels wide.
Example 2:
Input: widths = [4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10], s = "bbbcccdddaaa " Output: [2,4] Explanation: You can write s as follows: bbbcccdddaa // 98 pixels wide a // 4 pixels wide There are a total of 2 lines, and the last line is 4 pixels wide.
Constraints:
widths.length == 262 <= widths[i] <= 101 <= s.length <= 1000s contains only lowercase English letters.program main
implicit none
integer :: i, j, k, n, m, result(2)
character(len=100) :: s
integer, dimension(26) :: widths
! Example 1
widths = (/10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10/)
s = 'abcdefghijklmnopqrstuvwxyz '
call solve(widths, s, result)
print *, result
! Example 2
widths = (/4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10/)
s = 'bbbcccdddaaa '
call solve(widths, s, result)
print *, result
contains
subroutine solve(widths, s, result)
implicit none
integer, intent(in) :: widths(:), s(:)
integer, intent(out) :: result(2)
integer :: i, j, k, n, m
n = size(s)
m = size(widths)
do i = 1, n
if (sum(widths(1:i)) > 100) then
exit
end if
end do
result(1) = i - 1
do j = i, n
if (sum(widths(j-i+1:m)) > 100) then
exit
end if
end do
result(2) = sum(widths(j-i+1:m))
end subroutine solve
end program maintemp.f95:9:4:
9 | widths = (/10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10/)
| 1
Error: Different shape for array assignment at (1) on dimension 1 (26 and 24)
temp.f95:11:33:
11 | call solve(widths, s, result)
| 1
Error: Type mismatch in argument āsā at (1); passed CHARACTER(100) to INTEGER(4)
temp.f95:15:4:
15 | widths = (/4,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10/)
| 1
Error: Different shape for array assignment at (1) on dimension 1 (26 and 25)
temp.f95:17:33:
17 | call solve(widths, s, result)
| 1
Error: Type mismatch in argument āsā at (1); passed CHARACTER(100) to INTEGER(4)
program main
implicit none
integer, parameter :: MAX_WIDTH = 100
integer, parameter :: MAX_LETTERS = 26
integer, parameter :: MAX_STRING_LENGTH = 1000
integer :: widths(MAX_LETTERS)
character(len=MAX_STRING_LENGTH) :: s
integer :: result(2)
integer :: i, j, k, l
integer :: line_count, line_width
read(*,*) widths
read(*,*) s
line_count = 1
line_width = 0
do i = 1, len_trim(s)
if (line_width + widths(ichar(s(i:i))) > MAX_WIDTH) then
line_count = line_count + 1
line_width = 0
end if
line_width = line_width + widths(ichar(s(i:i)))
end do
result(1) = line_count
result(2) = line_width
write(*,*) result
end program main
At line 15 of file temp.f95 (unit = 5, file = 'stdin') Fortran runtime error: End of file Error termination. Backtrace: #0 0x7ed192150960 in ??? #1 0x7ed1921514d9 in ??? #2 0x7ed1923a517b in ??? #3 0x7ed19239e684 in ??? #4 0x7ed19239f2aa in ??? #5 0x7ed1923a4b7a in ??? #6 0x55eaf57492a2 in MAIN__ #7 0x55eaf57494c9 in main
def numberOfWays(n):
MOD = 1000000007
dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
dp[i] = (dp[i - 1] + dp[i - 2]) % MOD
return dp[n]
The optimal way to solve this problem is to use dynamic programming. The idea is to maintain a dp array where dp[i] holds the number of ways to tile a 2 x i board. Initialize dp[0] and dp[1] to 1 (base cases). Then, for each i from 2 to n, we calculate dp[i] as the sum of dp[i - 1] and dp[i - 2]. For each i, two cases are possible:
After iterating through the entire dp array, the result will be in dp[n]. Return this value modulo 109 + 7.
int numberOfWays(int n) {
int MOD = 1000000007;
vector<int> dp(n + 1, 0);
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; ++i)
dp[i] = (dp[i - 1] + dp[i - 2]) % MOD;
return dp[n];
}
The optimal way to solve this problem is to use dynamic programming. The idea is to maintain a dp array where dp[i] holds the number of ways to tile a 2 x i board. Initialize dp[0] and dp[1] to 1 (base cases). Then, for each i from 2 to n, we calculate dp[i] as the sum of dp[i - 1] and dp[i - 2]. For each i, two cases are possible:
After iterating through the entire dp array, the result will be in dp[n]. Return this value modulo 109 + 7.