Paragraph Formatting CodeChef Solution

Problem -Paragraph Formatting CodeChef Solution

This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.

Paragraph Formatting CodeChef Solution in C++17

#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <iomanip>
#include <algorithm>
using namespace std;

const int Maxn = 50005;
const int Maxp = 225; 

int t;
int m, n;
int my[Maxn], sum[Maxn];

int main()
{
	scanf("%d", &t);
	for (int tc = 1; tc <= t; tc++) {
		scanf("%d %d", &m, &n); m++;
		for (int i = 0; i < n; i++) {
			scanf("%d", &my[i]); my[i]++;
			sum[i] = my[i];
			if (i % Maxp) sum[i] += sum[i - 1];
		}
		printf("Case #%d:\n", tc);
		while (true) {
			char typ; scanf(" %c", &typ);
			if (typ == 'I') {
				int ind; scanf("%d", &ind); ind--;
				int p = ind / Maxp * Maxp;
				int lft = m;
				int res = 0;
                for (int i = 0; i < p; i += Maxp) {
					int j = i;
					int cur = 0;
					while (true)
						if (lft >= sum[i + Maxp - 1] - cur) { lft -= sum[i + Maxp - 1] - cur; break; }
						else {
							int f = upper_bound(sum + j, sum + i + Maxp, lft + cur) - sum - 1;
							res++; lft = m;
							if (f >= j) cur = sum[f];
							j = f + 1;
						}
				}
				for (int i = p; i <= ind; i++)
					if (lft >= my[i]) lft -= my[i];
					else { lft = m - my[i]; res++; }
				printf("%d\n", res + 1);
			} else if (typ == 'C') {
				int ind, len; scanf("%d %d", &ind, &len); ind--;
				my[ind] = len + 1;
				int j = ind / Maxp * Maxp;
				for (int i = j; i < j + Maxp && i < n; i++) {
					sum[i] = my[i];
					if (i % Maxp) sum[i] += sum[i - 1];
				}
			} else if (typ == 'E') break;
		}
		printf("\n");
	}
	return 0;
}

Paragraph Formatting CodeChef Solution in C++14

#include <cstdio>
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <cstring>
#include <sstream>
#include <queue>
#include <iomanip>
#include <algorithm>
using namespace std;

const int Maxn = 50005;
const int Maxp = 225; 

int t;
int m, n;
int my[Maxn], sum[Maxn];

int main()
{
	scanf("%d", &t);
	for (int tc = 1; tc <= t; tc++) {
		scanf("%d %d", &m, &n); m++;
		for (int i = 0; i < n; i++) {
			scanf("%d", &my[i]); my[i]++;
			sum[i] = my[i];
			if (i % Maxp) sum[i] += sum[i - 1];
		}
		printf("Case #%d:\n", tc);
		while (true) {
			char typ; scanf(" %c", &typ);
			if (typ == 'I') {
				int ind; scanf("%d", &ind); ind--;
				int p = ind / Maxp * Maxp;
				int lft = m;
				int res = 0;
				for (int i = 0; i < p; i += Maxp) {
					int j = i;
					int cur = 0;
					while (true)
						if (lft >= sum[i + Maxp - 1] - cur) { lft -= sum[i + Maxp - 1] - cur; break; }
						else {
							int f = upper_bound(sum + j, sum + i + Maxp, lft + cur) - sum - 1;
							res++; lft = m;
							if (f >= j) cur = sum[f];
							j = f + 1;
						}
				}
				for (int i = p; i <= ind; i++)
					if (lft >= my[i]) lft -= my[i];
					else { lft = m - my[i]; res++; }
				printf("%d\n", res + 1);
			} else if (typ == 'C') {
				int ind, len; scanf("%d %d", &ind, &len); ind--;
				my[ind] = len + 1;
				int j = ind / Maxp * Maxp;
				for (int i = j; i < j + Maxp && i < n; i++) {
					sum[i] = my[i];
					if (i % Maxp) sum[i] += sum[i - 1];
				}
			} else if (typ == 'E') break;
		}
		printf("\n");
	}
	return 0;
}

Paragraph Formatting CodeChef Solution in C

#include<stdio.h>
int  main()
{
int T=0,M=0,N=0,n,t=0;
scanf("%d",&T);
 
for(;t<T;t++)
{
	printf("Case #%d:\n",t+1);
	scanf("%d",&M);
 
	int temp;
	scanf("%d",&N);
	int a[N+1];
	int l[N+1];
	int p[N+1];
	l[0]=0;
	p[0]=0;
	for(n=1;n<=N;n++){
		scanf("%d",&temp);
		a[n]=temp;
		if(n==1){
			l[n]=1;
			p[n]=0;
		}
		else
		{
			int s;
 
			s=p[n-1]+a[n-1]+1;
			p[n]=(s+a[n]>M)?0:s;
			l[n]=l[n-1];
			if(s+a[n]>M)l[n]++;
 
 
		}
 
	//	printf("p:%d l:%d \n",p[n],l[n]);
 
	}
 
	int word_no,size;
	char c=' ';
	do{
		scanf("%c",&c);
		switch(c)
		{
			case 'I':
 
				scanf("%d",&word_no);
				printf("%d\n",l[word_no]);
				break;
			case 'C':
 
				scanf("%d %d",&word_no,&size);
				a[word_no]=size;
 
 
				int _cn;
				for(_cn=word_no;_cn<=N;_cn++){
					if(_cn==1)
					continue;
				int oldp=p[_cn];
				int oldl=l[_cn];
				l[_cn]=l[_cn-1];
				p[_cn]=p[_cn-1]+a[_cn-1]+1;
				if(p[_cn]+a[_cn]>M)
				{	p[_cn]=0;l[_cn]++;
				}
				if(_cn>word_no && oldp==p[_cn] && oldl==l[_cn])
				break;
 
				}
 
				break;
			default:
				break;
 
		}
		//printf("%c",c);
	}
	while(!(c=='E'));
	printf("\n");
/*	int i=1,line=0;
		for(i=1;i<=N;i++)
		{int j=0;
				if(line!=l[i])
						{printf("\n");
						line++;
						}
				else
					 printf(" ");
			for(j=0;j<a[i];j++)
			{
				printf("%d",i);
			}
		}
		*/
}
 
 
return 0;
 
}
 

Paragraph Formatting CodeChef Solution in JAVA

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Locale;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        Locale.setDefault(Locale.US);
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out, true);
        int X = Integer.parseInt(in.readLine());
        for (int x=0; x<X; x++) {
            out.println("Case #"+(x+1)+":");
            in.readLine();
            int[][] line = new int[201][3];
            int M = Integer.parseInt(in.readLine());
            int N = Integer.parseInt(in.readLine());
            int[] w = new int[N];
            int lineLength = 0;
            int cLine = 0;
            StringTokenizer st = new StringTokenizer(in.readLine());
            for (int i=0; i<N; i++) {
                w[i] = Integer.parseInt(st.nextToken());
                if (i==0) {
                    lineLength = w[i];
                } else if (w[i]+lineLength<M) {
                    lineLength += w[i]+1;
                } else {
                    line[cLine][1]=i-1;
                    line[cLine][2]=lineLength;
                    lineLength = w[i];
                    cLine++;
                    line[cLine][0]=i;
                }
            }
            line[cLine][1]=N-1;
            line[cLine][2]=lineLength;
            String s;
            while (!(s=in.readLine()).startsWith("E")) {
                if (s.startsWith("I")) {
                    int index = Integer.parseInt(s.substring(2));
                    int pos = 0;
                    while (line[pos][1]<index-1) pos++;
                    out.println(pos+1);
                } else if (s.startsWith("C")) {
                    int idx = s.lastIndexOf(' ');
                    int wi =  Integer.parseInt(s.substring(2,idx))-1;
                    int nl =  Integer.parseInt(s.substring(idx+1));
                    int pos = 0;
                    while (line[pos][1]<wi) pos++;
                    int delta = nl-w[wi];
                    w[wi]=nl;
                    if (delta == 0) {
                        // no-op
                    } else if (delta>0) {
                        line[pos][2]+=delta;
                        while (line[pos][2]>M) {
                            line[pos][1]--;
                            if (line[pos+1][2]==0) {
                                line[pos+1][0]=line[pos][1]+1;
                                line[pos+1][1]=line[pos+1][0];
                                line[pos+1][2]=-1;
                            } else {
                                line[pos+1][0]--;
                            }
                            line[pos+1][2]+=w[line[pos+1][0]]+1;
                            line[pos][2]-=w[line[pos+1][0]]+1;
                            if (line[pos][2]<=M) {
                                pos++;
                            }
                        }
                    } else if (delta<0) {
                        line[pos][2]+=delta;
                        if (pos>0) pos--;
                        while (line[pos+1][2]!=0) {
                            if (w[line[pos+1][0]]+line[pos][2]<M) {
                                line[pos][1]++;
                                line[pos+1][0]++;
                                line[pos][2]+=w[line[pos][1]]+1;
                                if (line[pos+1][0]>line[pos+1][1]) {
                                    for (int i=pos+1; i<line.length-1; i++) {
                                        line[i][0]=line[i+1][0];
                                        line[i][1]=line[i+1][1];
                                        line[i][2]=line[i+1][2];
                                    }
                                } else {
                                    line[pos+1][2]-=w[line[pos][1]]+1;
                                }
                            } else {
                                pos++;
                            }
                        }
                    }
                }
            }
            out.println();
        }
        out.close();
    }

}

Paragraph Formatting CodeChef Solution in C#

using System;
using System.Collections.Generic;

namespace CodeChef_200910_H5
{

    public struct Line
    {
        public int start_index;
        public int length;
        
        public Line(int start_index, int length)
        {
            this.start_index = start_index;
            this.length = length;
        }
    }

    public class Query
    {
        public string type;
        public int p1, p2;
    }

    class CaseItem
    {
        public const int MAX_LINES = 202;
        public const int MAX_QUERYS = 10002;

        int caseIndex;
        int line_width;
        int word_num= 0;
        int[] words;
        Line[] lines = new Line[MAX_LINES]; // start, width,
        int line_count = 0;
        int[,] queries = new int[MAX_QUERYS, 3]; // type, p1, p2
        int query_count = 0;

        List<Query> querylist = new List<Query>(10001);


        public CaseItem(int index)
        {
            
                caseIndex = index;
                Console.ReadLine();
                line_width = int.Parse(Console.ReadLine());
                word_num = int.Parse(Console.ReadLine());
                words = new int[word_num];

                string str_words = Console.ReadLine();

                string[] a = str_words.Split(' ');
                for (int wi = 0; wi < word_num; wi++)
                {
                    words[wi] = int.Parse(a[wi]);
                }
                
                    //query_count = 0;
                    //string qline = Console.ReadLine();
                    //while (qline[0] != 'E')
                    //{
                    //    try
                    //    {
                    //        string[] b = qline.Split(' ');
                    //        queries[query_count, 0] = qline[0]; // query_type;
                    //        queries[query_count, 1] = int.Parse(b[1]);
                    //        if (qline[0] == 'C')
                    //        {
                    //            queries[query_count, 2] = int.Parse(b[2]);
                    //        }
                    //        query_count++;
                    //        qline = Console.ReadLine();
                    //    }
                    //    catch (Exception ex)
                    //    {
                    //        throw new ApplicationException("1");
                    //    } 
                    //}

                while (true)
                {
                    string qline = Console.ReadLine();
                    string[] b = qline.Split(' ');
                    Query q = new Query();
                    if (b[0] == "E")
                    {
                        break;
                    }
                    q.type = b[0];
                    q.p1 = int.Parse(b[1]);
                    if (b.Length > 2)
                    {
                        q.p2 = int.Parse(b[2]);
                    }
                    querylist.Add(q);
                }
                
            
                this.Init();
            
        }


        private void Init()
        {
            this.Format();
        }

        private void Format()
        {
            line_count = 0;
            lines[0].start_index = 0;  
            lines[0].length = words[0]; 

            int word_length;

            for (int wi = 1; wi < word_num; wi++)
            {
                word_length = words[wi];
                if (lines[line_count].length + 1 + word_length <= line_width)
                {
                    lines[line_count].length += (1 + word_length);
                }
                else
                {
                    line_count += 1;
                    lines[line_count].start_index = wi;
                    lines[line_count].length = word_length;
                }
            }
            line_count += 1;
        }


        private void Rep_Debug(int word_index, int len)
        {
            words[word_index] = len;
            this.Format();
        }


        private void RepAdd(int word_index, int len, int line_index)
        {
            try
            {
                while (lines[line_index].length > line_width)
                {
                    do
                    {
                        if (line_index < line_count - 1)
                        {
                            int end_index = lines[line_index + 1].start_index - 1;
                            lines[line_index].length -= (words[end_index] + 1);
                            lines[line_index + 1].start_index = end_index;
                            lines[line_index + 1].length += (words[end_index] + 1);
                        }
                        else
                        {
                            int end_index = word_num - 1;
                            lines[line_index].length -= (words[end_index] + 1);
                            lines[line_index + 1].start_index = end_index;
                            lines[line_index + 1].length += words[end_index];
                            line_count += 1;
                        }

                    } while (lines[line_index].length > line_width);
                    line_index++;
                }
            }
            catch (Exception ex)
            {
                throw new ApplicationException("2");
            }
        }

        private void RepSub(int word_index, int len, int line_index)
        {
            try
            {
                if (line_index > 0)
                {
                    if (lines[line_index].start_index == word_index)
                    {
                        if (lines[line_index - 1].length + len + 1 <= line_width)
                        {
                            line_index -= 1;
                        }
                    }
                }


                while (line_index < line_count - 1)
                {
                    if (lines[line_index].length == 0)
                    {
                        while (line_index < line_count - 1)
                        {
                            lines[line_index] = lines[line_index + 1];
                            line_index += 1;
                        }
                        line_count -= 1;
                        lines[line_count].start_index = word_num;
                        lines[line_count].length = 0;
                        break;
                    }

                    int next_line_index = line_index + 1;
                    int next_start_index = lines[next_line_index].start_index;

                    while ((lines[next_line_index].length > 0) &&
                            (lines[line_index].length + words[next_start_index] + 1 <= line_width))
                    {
                        int temp_length = words[next_start_index];
                        lines[line_index].length += (temp_length + 1);
                        lines[next_line_index].start_index += 1;

                        if (lines[next_line_index].length > temp_length)
                        {
                            lines[next_line_index].length -= (temp_length + 1); // 此处可能小于0
                        }
                        else
                        {
                            lines[next_line_index].length = 0;
                        }
                        next_start_index += 1;
                    }

                    line_index++;
                }

                if (lines[line_count - 1].length == 0)
                {
                    line_count -= 1;
                }

            }
            catch (Exception ex)
            {
                throw new ApplicationException("1");
            }
        }

        private void Rep(int word_index, int len)
        {
            try
            {
                int dw = len - words[word_index];
                if (dw == 0) return;

                int line_index = this.GetWordLineNumber(word_index);
                words[word_index] = len;
                lines[line_index].length += dw;

                if (dw > 0)
                {
                    this.RepAdd(word_index, len, line_index);
                }

                if (dw < 0)
                {
                    this.RepSub(word_index, len, line_index);
                }
            }
            catch (Exception ex)
            {
                throw new ApplicationException("2");
            }
        }


        public int GetWordLineNumber(int word_index)
        {
            int start = 0;
            int end = line_count - 1;

            if (word_index >= lines[end].start_index)
            {
                return end;
            }

            while (end - start > 1)
            {                
                int line_index = (start + end) >> 1;

                if (lines[line_index].start_index > word_index)
                {
                    end = line_index;
                }
                else if (lines[line_index].start_index < word_index)
                {
                    start = line_index;                    
                }
                else
                {
                    return line_index;
                }
            }

            return start;
        }


        //public void Execute()
        //{
            
        //    Console.WriteLine("Case #" + caseIndex.ToString() + ":");
        //    for (int qi = 0; qi < query_count; qi++)
        //    {
        //        int wi = queries[qi, 1] - 1;
        //        if (queries[qi, 0] == 'I')
        //        {
        //            int line_index = this.GetWordLineNumber(wi);
        //            Console.WriteLine((line_index + 1).ToString());
        //        }
        //        else
        //        {
        //            //Rep_Debug(wi, queries[qi, 2]);
        //            Rep(wi, queries[qi, 2]);
        //        }
        //    }
            
        //}

        public void Execute()
        {

            Console.WriteLine("Case #" + caseIndex.ToString() + ":");
            foreach(Query q in querylist)
            {
                int wi = q.p1 - 1;
                if (q.type == "I")
                {
                    int line_index = this.GetWordLineNumber(wi);
                    Console.WriteLine((line_index + 1).ToString());
                }
                else
                {
                    //Rep_Debug(wi, queries[qi, 2]);
                    Rep(wi, q.p2);
                }
            }

        }
    }

        

    class Round
    {
        int case_num;
        CaseItem[] items;
        public Round()
        {
            
            case_num = int.Parse(Console.ReadLine());
            items = new CaseItem[case_num];
            for (int i = 0; i < case_num; i++)
            {
                items[i] = new CaseItem(i + 1);
            }
            
        }

        public void Execute()
        {            
            foreach (CaseItem item in items)
            {
                item.Execute();
            }           
        }
    }


    class Program
    {
        static void Main(string[] args)
        {
            try
            {
                (new Round()).Execute();
                //Debug();
            }
            catch (Exception ex)
            {
                if (ex.Message == "1")
                {
                    System.Console.WriteLine("error");
                }
                else if (ex.Message == "2")
                {
                    System.Console.WriteLine("error");
                }
                else
                {
                    throw ex;
                }
            }
        }

        static void Debug()
        {

            System.IO.TextReader stdin = System.Console.In;
            System.IO.TextWriter stdout = System.Console.Out;

            try
            {
                using (System.IO.StreamReader reader = new System.IO.StreamReader("a.in"))
                {
                    using (System.IO.StreamWriter writer = new System.IO.StreamWriter("out.txt"))
                    {

                        long datetime1 = DateTime.Now.Ticks;

                        System.Console.SetIn(reader);
                        System.Console.SetOut(writer);
                        (new Round()).Execute();

                        long datetime2 = DateTime.Now.Ticks;

                        DateTime datetime3 = DateTime.Now;

                        long seconds = (datetime2 - datetime1) / (datetime3.AddSeconds(1).Ticks - datetime3.Ticks);

                        System.Console.WriteLine(" second is : " + seconds.ToString());
                    }
                }
            }
            finally
            {
                System.Console.SetIn(stdin);
                System.Console.SetOut(stdout);
            }
        }
    }
}

Paragraph Formatting CodeChef Solution in GO

package main

import (
	"bufio"
	"bytes"
	"fmt"
	"os"
)

func main() {
	reader := bufio.NewReader(os.Stdin)

	tc := readNum(reader)
	var buf bytes.Buffer
	for i := 0; i < tc; i++ {
		buf.WriteString(fmt.Sprintf("Case #%d:\n", i+1))
		readString(reader)
		line_width := readNum(reader)
		n := readNum(reader)
		words := readNNums(reader, n)
		solver := NewSolver(words, line_width)

		for {
			s, _ := reader.ReadBytes('\n')
			if s[0] == 'E' {
				break
			}
			if s[0] == 'I' {
				var id int
				readInt(s, 2, &id)
				ans := solver.QueryLineNo(id)
				buf.WriteString(fmt.Sprintf("%d\n", ans))
			} else {
				var id, v int
				pos := readInt(s, 2, &id) + 1
				readInt(s, pos, &v)
				solver.ChangeWordLength(id, v)
			}
		}
		buf.WriteByte('\n')
	}
	fmt.Print(buf.String())
}

func readUint64(bytes []byte, from int, val *uint64) int {
	i := from

	var tmp uint64
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + uint64(bytes[i]-'0')
		i++
	}
	*val = tmp

	return i
}

func readInt(bytes []byte, from int, val *int) int {
	i := from
	sign := 1
	if bytes[i] == '-' {
		sign = -1
		i++
	}
	tmp := 0
	for i < len(bytes) && bytes[i] >= '0' && bytes[i] <= '9' {
		tmp = tmp*10 + int(bytes[i]-'0')
		i++
	}
	*val = tmp * sign
	return i
}

func readString(reader *bufio.Reader) string {
	s, _ := reader.ReadString('\n')
	for i := 0; i < len(s); i++ {
		if s[i] == '\n' || s[i] == '\r' {
			return s[:i]
		}
	}
	return s
}

func readNum(reader *bufio.Reader) (a int) {
	bs, _ := reader.ReadBytes('\n')
	readInt(bs, 0, &a)
	return
}

func readTwoNums(reader *bufio.Reader) (a int, b int) {
	res := readNNums(reader, 2)
	a, b = res[0], res[1]
	return
}

func readThreeNums(reader *bufio.Reader) (a int, b int, c int) {
	res := readNNums(reader, 3)
	a, b, c = res[0], res[1], res[2]
	return
}

func readNNums(reader *bufio.Reader, n int) []int {
	res := make([]int, n)
	x := 0
	bs, _ := reader.ReadBytes('\n')
	for i := 0; i < n; i++ {
		for x < len(bs) && (bs[x] < '0' || bs[x] > '9') && bs[x] != '-' {
			x++
		}
		x = readInt(bs, x, &res[i])
	}
	return res
}

type Solver struct {
	words      []int
	arr        []int
	n          int
	line_width int
}

func NewSolver(words []int, line_width int) *Solver {
	n := len(words)

	arr := make([]int, n+1)

	for i := 0; i < n; i++ {
		words[i]++
		set(arr, i+1, words[i])
	}

	line_width++

	return &Solver{words, arr, n, line_width}
}

func (solver *Solver) QueryLineNo(id int) int {
	cur := 1
	no := 1
	for {
		kk := get(solver.arr, cur-1)
		kk += solver.line_width
		cur = find(solver.arr, kk)
		if cur >= id {
			return no
		}
		cur++
		no++
	}
}

func (solver *Solver) ChangeWordLength(id int, width int) {
	width++
	set(solver.arr, id, width-solver.words[id-1])
	solver.words[id-1] = width
}

func set(arr []int, p int, v int) {
	for p < len(arr) {
		arr[p] += v
		p += p & -p
	}
}

func get(arr []int, p int) int {
	var res int
	for p > 0 {
		res += arr[p]
		p -= p & -p
	}
	return res
}

func find(arr []int, sum int) int {
	var x int
	var ans int
	for i := 16; i >= 0; i-- {
		if (x + (1 << uint(i))) < len(arr) {
			x |= 1 << uint(i)
			if ans+arr[x] > sum {
				x ^= 1 << uint(i)
			} else {
				ans += arr[x]
			}
		}
	}
	return x
}
Paragraph Formatting CodeChef Solution Review:

In our experience, we suggest you solve this Paragraph Formatting CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.

If you are stuck anywhere between any coding problem, just visit Queslers to get the Paragraph Formatting CodeChef Solution.

Find on CodeChef

Conclusion:

I hope this Paragraph Formatting CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.

This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.

Keep Learning!

More Coding Solutions >>

Cognitive Class Answer

CodeChef Solution

Microsoft Learn

Leave a Reply

Your email address will not be published. Required fields are marked *