Attic Crossing Codechef Solution

Hello Programmers In this post, you will know how to solve the Attic Crossing Codechef Solution. The Problem Code: ATTIC

Attic Crossing Codechef Solution
Attic Crossing Codechef Solution

One more thing to add, don’t directly look for the solutions, first try to solve the problems of Codechef by yourself. If you find any difficulty after trying several times, then you can look for solutions.

Problem

Digory Kirke and Polly Plummer are two kids living next door to each other. The attics of the two houses are connected to each other through a passage. Digory’s Uncle Andrew has been secretly doing strange things in the attic of his house, and he always ensures that the room is locked. Being curious, Digory suspects that there is another route into the attic through Polly’s house, and being curious as kids always are, they wish to find out what it is that Uncle Andrew is secretly up to.

So they start from Polly’s house, and walk along the passageway to Digory’s. Unfortunately, along the way, they suddenly find that some of the floorboards are missing, and that taking a step forward would have them plummet to their deaths below.

Dejected, but determined, they return to Polly’s house, and decide to practice long-jumping in the yard before they re-attempt the crossing of the passage. It takes them exactly one day to master long-jumping a certain length. Also, once they have mastered jumping a particular length L, they are able to jump any amount less than equal to L as well.

The next day they return to their mission, but somehow find that there is another place further up the passage, that requires them to jump even more than they had practiced for. So they go back and repeat the process.

Note the following:

  • At each point, they are able to sense only how much they need to jump at that point, and have no idea of the further reaches of the passage till they reach there. That is, they are able to only see how far ahead is the next floorboard.
  • The amount they choose to practice for their jump is exactly the amount they need to get across that particular part of the passage. That is, if they can currently jump upto a length L0, and they require to jump a length L1(> L0) at that point, they will practice jumping length L1 that day.
  • They start by being able to “jump” a length of 1.

Find how many days it will take them to cross the passageway. In the input, the passageway is described as a string P of ‘#’s and ‘.’s. A ‘#’ represents a floorboard, while a ‘.’ represents the absence of a floorboard. The string, when read from left to right, describes the passage from Polly’s house to Digory’s, and not vice-versa.

Input

The first line consists of a single integer T, the number of testcases. Each of the next T lines consist of the string P for that case.

Output

For each case, output the number of days it takes them to cross the passage.

Constraints

  • 1 ≤ T ≤ 1,000,000 (106)
  • 1 ≤ |P| ≤ 1,000,000 (106)
  • The total length of P will be ≤ 5,000,000 (5 * 106)across all test-cases of a test-file
  • P will consist of only the characters # and .
  • The first and the last characters of P will be #.

Example

Sample Input 1 

4
####
##.#..#
##..#.#
##.#....#

Sample Output 1 

0
2
1
2

Ezoicreport this adAttic Crossing CodeChef Solution in JAVA

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for (int tc = 0; tc < T; tc++) {
			String P = sc.next();
			System.out.println(solve(P));
		}
		sc.close();
	}
	static int solve(String P) {
		int result = 0;
		int jump = 1;
		int prevIndex = 0;
		for (int i = 0; i < P.length(); i++) {
			if (P.charAt(i) == '#') {
				int distance = i - prevIndex;
				if (distance > jump) {
					jump = distance;
					result++;
				}
				prevIndex = i;
			}
		}
		return result;
	}
}

Attic Crossing CodeChef Solution in Cpp

#include <bits/stdc++.h>
using namespace std;
int main() {
	long long t;
	cin >> t;
	while(t--){
	    string p;
	    cin >> p;
	    long long i = 0,count = 0,ans = 0,capability = 0;
	    while(i < p.size()){
	        while(p[i] == '.'){
	            count++;
	            i++;
	        }
	        if(count > capability){
	            ans++;
	            capability = count;
	        }
	        i++;
	        count = 0;
	    }
	    cout << ans << endl;
	}
	return 0;
}

Attic Crossing CodeChef Solution in Python

for t in range(0,int(input())):
    arr=input()
    days=0
    capacity=0
    i=0
    while i<len(arr):
        if(arr[i]=='.'):
            start=i
            while(arr[i]!='#'):
                i+=1
            if(capacity<i-start):
                days+=1
            if(i-start>capacity):
                capacity=i-start
        else:
            i+=1
    print(days)
Ezoicreport this ad

Disclaimer: The above Problem (Attic Crossing) is generated by CodeChef but the solution is provided by BrokenProgrammers. This tutorial is only for Educational and Learning purposes.

Note:- I compile all programs, if there is any case program is not working and showing an error please let me know in the comment section. If you are using adblocker, please disable adblocker because some functions of the site may not work correctly.

Next: Minimum Attendance Requirement Codechef Solution

Sharing Is Caring

Leave a Comment

Ezoicreport this ad