Solution of 834 - Continued Fractions

Problem Description
source:https://uva.onlinejudge.org/external/8/834.html

Let b0, b1, b2, . . . , bn be integers with bk > 0 for k > 0. The continued fraction of order n with coeficients b1, b2, . . . , bn and the initial term b0 is defined by the following expression

which can be abbreviated as [b0; b1, . . . , bn]. An example of a continued fraction of order n = 3 is [2; 3, 1, 4]. This is equivalent to 

Algorithm of 579 - ClockHands

Problem Description Link

This is a calculation of the angle between the minute hand and the hour hand on a regular analog clock.
To solve this problem you can follow this stapes:
image

Solution of 579 - ClockHands

Problem Description
source:https://uva.onlinejudge.org/external/5/579.html

The medieval interest in mechanical contrivances is well illustrated by the development of the mechanical clock, the oldest of which is driven by weights and controlled by a verge, an oscillating arm engaging with a gear wheel. It dates back to 1386.
    Clocks driven by springs had appeared by the mid-15th century, making it possible to con- struct more compact mechanisms and preparing the way for the portable clock.
    English spring-driven pendulum clocks were first commonly kept on a small wall bracket and later on a shelf. Many bracket clocks contained a drawer to hold the winding key. The earliest bracket clocks, made for a period after 1660, were of architectural design, with pillars at the sides and a pediment on top.
     In 17th- and 18th-century France, the table clock became an object of monumental design, the best examples of which are minor works of sculpture
image

Algorithm of 575 - Skew Binary

Problem Description Link

This is a simple problem . only convert skew value to decimal value.
You can follow this stapes:
1. Get input string for skew value.
    (N.B: Input is string because input value range may greater than any type of value ie, int,... But
          result range in 2^31-1)
2. determine the length of input value.
3. under for loop i=0 to length-1
       decimalvalue+=(input[i]-48)*(pow(2,length-i)-1);
4. finally print the value of decimalvalue.
ie.
    input=10120
       length=5 so process is
    =1*(2^5-1)+0*(2^4-1)+1*(2^3-1)+2*(2^2-1)+0*(2^1-1)
    =31+0+7+6+0
    = 44
 so 44 is equivalent decimal value.

   
image

Solution of 575 - Skew Binary

Problem Description
source:httpa://uva.onlinejudge.org/external/5/575.html

When a number is expressed in decimal, the k-th digit represents a multiple of 10k . (Digits are numbered from right to left, where the least significant digit is number 0.) For example,

Algorithm of 694 - The Collatz Sequence

Problem Description Link

This is a simple problem . Just follow  this stapes:

Step 1:
    Choose an arbitrary positive integer A as the first item in the sequence.
Step 2:
    If A = 1 then stop.
Step 3:
    If A is even, then replace A by A / 2 and go to step 2.
Step 4:
    If A is odd, then replace A by 3 * A + 1 and go to step 2.

[You can use long long int data type ]

Solution Link
image

Solution of 694 - The Collatz Sequence

Problem Description
source:https://uva.onlinejudge.org/external/6/694.html

An algorithm given by Lothar Collatz produces sequences of integers, and is described as follows: 

Step 1: Choose an arbitrary positive integer A as the first item in the sequence. 
Step 2: If A = 1 then stop. 
Step 3: If A is even, then replace A by A/2 and go to step 2. 
Step 4: If A is odd, then replace A by 3 ∗ A + 1 and go to step 2. 

It has been shown that this algorithm will always stop (in step 2) for initial values of A as large as 109 , but some values of A encountered in the sequence may exceed the size of an integer on many computers. In this problem we want to determine the length of the sequence that includes all values produced until either the algorithm stops (in step 2), or a value larger than some specified limit would be produced (in step 4). 

image

Algorithm of 673 - Parentheses Balance

Problem Description Link
This problem is a easy problem. You can solve this problem using stack just follow this stapes
1. get input string for parenthesis.
2. Check, input is opening bracket then push in stack.
3. if  input is closing bracket then compare with top of the stack element
       if valid expression then input and stack top element same type opening and closing bracket
         ie. input= ")" then top= "(" or input= "]" then top= "["

image

Solution of 673 - Parentheses Balance

Problem Description
source:https://uva.onlinejudge.org/external/6/673.html

You are given a string consisting of parentheses () and []. A string of this type is said to be correct: 

(a) if it is the empty string 
(b) if A and B are correct, AB is correct, 
(c) if A is correct, (A) and [A] is correct. 

Write a program that takes a sequence of strings of this type and check their correctness. Your program can assume that the maximum string length is 128.

image

Algorithm of 591 - Box of Bricks

Problem Description Link

It is a simple problem read carefully and solve easilly .
one condition for print output
ie.
printf("Set #%ld\n",k);
printf("The minimum number of moves is %ld.\n\n",result);
image

Solution of 591 - Box of Bricks

Problem Description
source:https://uva.onlinejudge.org/external/5/591.html

Little Bob likes playing with his box of bricks. He puts the bricks one upon another and builds stacks of different height. “Look, I’ve built a wall!”, he tells his older sister Alice. “Nah, you should make all stacks the same height. Then you would have a real wall.”, she retorts. After a little con- sideration, Bob sees that she is right. So he sets out to rearrange the bricks, one by one, such that all stacks are the same height afterwards. But since Bob is lazy he wants to do this with the minimum number of bricks moved. Can you help?

Algorithm of 621 - Secret Research

Problem Description Link
Actually this problem can be very easy once you know what it means (or when you read this hint).
How to know which output we have to give for each input? The answer is simple:

Positive when S is exactly "1","4",or "78"
Negative when the last two digits of S are exactly "35"
Experiment failed if the first digit of S is exactly "9" and the last one digit of S is exactly "4"
Experiment not completed if the first three digits are exactly "190"
image

Solution of 621 - Secret Research

Problem Description
source:https://uva.onlinejudge.org/external/6/621.html

At a certain laboratory results of secret research are thoroughly encrypted. A result of a single experiment is stored as an information of its completion:
      ‘positive result’, ‘negative result’, ‘experiment failed’ or ‘experiment not completed’
      The encrypted result constitutes a string of digits S, which may take one of the following forms:
        • positive result S = 1 or S = 4 or S = 78
        • negative result S = S35
        • experiment failed S = 9S4
        • experiment not completed S = 190S

(A sample result S35 means that if we add digits 35 from the right hand side to a digit sequence then we shall get the digit sequence corresponding to a failed experiment)
      You are to write a program which decrypts given sequences of digits.

image

Algorithm of 616 - Coconuts, Revisited

Problem Description Link

You can solve this problem using many method.
One condition is the
      If n is the number of people, then
           (n^n-n+1) is the number of coconuts.
you can get idea from this condition.
You can see solution
image

Solution of 616 - Coconuts, Revisited

Problem Description
source:https://uva.onlinejudge.org/external/6/616.html

The short story titled Coconuts, by Ben Ames Williams, appeared in the Saturday Evening Post on October 9, 1926. The story tells about five men and a monkey who were shipwrecked on an island. They spent the first night gathering coconuts. During the night, one man woke up and decided to take his share of the coconuts. He divided them into five piles. One coconut was left over so he gave it to the monkey, then hid his share and went back to sleep.
    Soon a second man woke up and did the same thing. After dividing the coconuts into five piles, one coconut was left over which he gave to the monkey. He then hid his share and went back to bed. The third, fourth, and fifth man followed exactly the same procedure. The next morning, after they all woke up, they divided the remaining coconuts into five equal shares. This time no coconuts were left over.
image

Solution of 555 - Bridge Hands

Problem Description
source:https://uva.onlinejudge.org/external/5/555.html

Many games, such as Bridge, involve dealing a standard deck of 52 cards to 4 players, so each receives 13 cards. Good players can then play with the hand as it is dealt, but most ordinary players will need to sort it, firstly by suit, and then by rank within suit. 
     There is no fixed ranking of the suits for this purpose, but it is useful to alternate the colours, so we will presume the following ordering: ♣ < ♢ < ♠ < ♡. (Note that from now on we will use the more conventional ‘C’, ‘D’, ‘S’, ‘H’ for CLUBS, DIAMONDS, SPADES and HEARTS). Within a suit Ace is high, so the ordering is 2 < 3 < 4 < 5 < 6 < 7 < 8 < 9 < T < J < Q < K < A.

Algorithm of 555 - Bridge Hands

Problem Description Link

You can follow this stapes :
1. first assign the all card according to order that order (given in
     problem description ) in a two dimensional array
         ie. rank[55][4].
2. then distributed the card among 4 players and when distributed
     card compare the card value from rank index and store the index
for each player(each players have individual array int type)
3. finally sort each array and print from rank table this sorted
     value is used for rank index.
image

Solution of 551 - Nesting a Bunch of Brackets

Problem Description
source:https://uva.onlinejudge.org/external/5/551.html

In this problem we consider expressions containing brackets that are properly nested. These expressions are obtained by juxtaposition of properly netsted expressions in a pair of matching brackets, the left one an opening and the right one a closing bracket.
        ( a + $ ( b = ) ( a ) ) is properly nested 
        ( a + $ ) b = ) ( a ( ) is not 

In this problem we have several pairs of brackets, so we have to impose a second condition on the expression: the matching brackets should be of the same kind. Consequently ‘(())’ is OK, but ‘([))’ is not. The pairs of brackets are:

(   ) 
[   ] 
{   } 
<   > 
(*   *)  

image

Algorithm of 551 - Nesting a Bunch of Brackets

Problem Description Link

To solve this problem easilly you can use stak.
The pairs of brackets are:
(   )
[   ]
{   }
<   >
(*   *)
image

Solution of 541 - Error Correction

Problem Description
source: https://uva.onlinejudge.org/external/5/541.html

A boolean matrix has the parity property when each row and each column has an even sum, i.e. contains an even number of bits which are set. Here’s a 4 × 4 matrix which has the parity property: 

1 0 1 0 
0 0 0 0 
1 1 1 1 
0 1 0 1 

    The sums of the rows are 2, 0, 4 and 2. The sums of the columns are 2, 2, 2 and 2. 
    Your job is to write a program that reads in a matrix and checks if it has the parity property. If not, your program should check if the parity property can be established by changing only one bit. If this is not possible either, the matrix should be classified as corrupt. 

image

Solution of 424 - Integer Inquiry

Problem Description
source: https://uva.onlinejudge.org/external/4/424.html

One of the first users of BIT’s new supercomputer was Chip Diller. He extended his exploration of powers of 3 to go from 0 to 333 and he explored taking various sums of those numbers. 
     “This supercomputer is great,” remarked Chip. “I only wish Timothy were here to see these results.” (Chip moved to a new apartment, once one became available on the third floor of the Lemon Sky apartments on Third Street.)

Input 

The input will consist of at most 100 lines of text, each of which contains a single VeryLongInteger. Each VeryLongInteger will be 100 or fewer characters in length, and will only contain digits (no VeryLongInteger will be negative). 
     The final input line will contain a single zero on a line by itself

image

Algorithm of 424 - Integer Inquiry

 Problem Description Link

This is easy big integer problem. To solve this problem you can use character array or string
because input size is large this input can not handle by any integer type. You can follow this stapes.

1. get a string input.
2. Reverse that input using user defined function
    N.B: if you use built in function strrev() ,you may get compile error for this problem.
3. after after completing  reverse  add each value with other array that initially assign NULL.
image

Concrete Mathematics

This book introduces the mathematics that supports advanced computer programming and the analysis of algorithms . The primary aim of its well-known authors is to provide a solid and relevant base of mathematical skills - the skills needed to solve complex problems
Click Here To Download

Art of Programming Vol I II III IV

This book is very essential for a programmer. You can download this book without any payment.
Click Here To Download

Solution of 494 - Kindergarten Counting Game

Problem Description
source: https://uva.onlinejudge.org/external/4/494.html

Everybody sit down in a circle. Ok. Listen to me carefully. 
     “Woooooo, you scwewy wabbit!”

 Now, could someone tell me how many words I just said?

Input 

Input to your program will consist of a series of lines, each line containing multiple words (at least one). A “word” is defined as a consecutive sequence of letters (upper and/or lower case). 

image

Solution of 458 - The Decoder

Problem Description
source: https://uva.onlinejudge.org/external/4/458.html

Write a complete program that will correctly decode a set of characters into a valid message. Your program should read a given file of a simple coded set of characters and print the exact message that the characters contain. The code key for this simple coding is a one for one character substitution based upon a single arithmetic manipulation of the printable portion of the ASCII character set.

Input and Output 

For example: with the input file that contains: 

1JKJ'pz'{ol'{yhklthyr'vm'{ol'Jvu{yvs'Kh{h'Jvywvyh{pvu5 
1PIT'pz'h'{yhklthyr'vm'{ol'Pu{lyuh{pvuhs'I|zpulzz'Thjopul'Jvywvyh{pvu5 
1KLJ'pz'{ol'{yhklthyr'vm'{ol'Kpnp{hs'Lx|pwtlu{'Jvywvyh{pvu5 

image

Solution of 445 - Marvelous Mazes

Problem Description
source: https://uva.onlinejudge.org/external/4/445.html

Your mission, if you decide to accept it, is to create a maze drawing program. A maze will consist of the alphabetic characters A-Z, * (asterisk), and spaces.

Input 

Your program will get the information for the mazes from the input file. This file will contain lines of characters which your program must interpret to draw a maze. Each row of the maze will be described by a series of numbers and characters, where the numbers before a character tell how many times that character will be used. If there are multiple digits in a number before a character, then the number of times to repeat the character is the sum of the digits before that character. 
    The lowercase letter ‘b’ will be used in the input file to represent spaces in the maze. The descriptions for different rows in the maze will be separated by an exclamation point (!), or by an end of line. 
    Descriptions for different mazes will be separated by a blank line. The input file will be terminated by an end of file.  

image

Solution of 382 - Perfection

Problem Description
source: https://uva.onlinejudge.org/external/3/382.html

From the article Number Theory in the 1994 Microsoft Encarta: “If a, b, c are integers such that a = bc, a is called a multiple of b or of c, and b or c is called a divisor or factor of a. If c is not ±1, b is called a proper divisor of a. Even integers, which include 0, are multiples of 2, for example, -4, 0, 2, 10; an odd integer is an integer that is not even, for example, -5, 1, 3, 9. A perfect number is a positive integer that is equal to the sum of all its positive, proper divisors; for example, 6, which equals 1 + 2 + 3, and 28, which equals 1 + 2 + 4 + 7 + 14, are perfect numbers. A positive number that is not perfect is imperfect and is deficient or abundant according to whether the sum of its positive, proper divisors is smaller or larger than the number itself. Thus, 9, with proper divisors 1, 3, is deficient; 12, with proper divisors 1, 2, 3, 4, 6, is abundant.” 

     Your task is: Given a number, determine if it is perfect, abundant, or deficient. 

image

Solution of 374 - Big Mod

Problem Definition
source: https://uva.onlinejudge.org/external/3/374.html

Calculate 
                                                                  R := B P 
mod M for large values of B, P, and M using an efficient algorithm. (That’s right, this problem has a time dependency !!!.)

Input 

The input will contain several test cases, each of them as described below. Consecutive test cases are separated by a single blank line. 
     
    Three integer values (in the order B, P, M) will be read one number per line. B and P are integers in the range 0 to 2147483647 inclusive. M is an integer in the range 1 to 46340 inclusive.

image

371 - Ackermann Functions

Problem description:
source: https://uva.onlinejudge.org/external/3/p371.html

An Ackermann function has the characteristic that the length of the sequence of numbers generated by the function cannot be computed directly from the input value. One particular integer Ackermann function is the following:

This Ackermann has the characteristic that it eventually converges on 1. A few examples follow in which the starting value is shown in square brackets followed by the sequence of values that are generated, followed by the length of the sequence in curly braces:

    [10] 5 16 8 4 2 1 {6}
    [13] 40 20 10 5 16 8 4 2 1 {9}
    [14] 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 {17}
    [19] 58 29 88 44 22 ... 2 1 {20}
    [32] 16 8 4 2 1 {5}
    [1] 4 2 1 {3}

Standard header file for c++

You can use this header file in maximum problem solving. If you use this header file you may not get compile error. No need extra run time for using this header file.
 
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include<stdio.h>
#include<stdlib.h>

using namespace std;
int main()
{
}
image

113 - Power of Cryptography

Problem Description
source: https://uva.onlinejudge.org/external/1/113.html

Current work in cryptography involves (among other things) large prime numbers and computing powers of numbers modulo functions of these primes. Work in this area has resulted in the practical use of results from number theory and other branches of mathematics once considered to be of only theoretical interest. 
    This problem involves the efficient computation of integer roots of numbers. 

    Given an integer n ≥ 1 and an integer p ≥ 1 you are to write a program that determines n√p, the positive n-th root of p. In this problem, given such integers n and p, p will always be of the form kn for an integer k (this integer is what your program must find).

image

Algorithm of 272 - TEX Quotes

Solution steps:

This problem is a simple problem just follow the stapes
1. get a character and check the character is " or not
2. if the character is " then check is it first or second time
3. if first time then replace " by `` and
4. if second time then replace it by '' and print this character
   (N.B: if get second time then next " is first time)
5. otherwise print the character without any change
image

272 - TEX Quotes

Problem Description
source: https://uva.onlinejudge.org/external/2/p272.html

TEX is a typesetting language developed by Donald Knuth. It takes source text together with a few typesetting instructions and produces, one hopes, a beautiful document. Beautiful documents use “ and ” to delimit quotations, rather than the mundane " which is what is provided by most keyboards. Keyboards typically do not have an oriented double-quote, but they do have a left-single-quote ` and a right-single-quote '. Check your keyboard now to locate the left-single-quote key ` (sometimes called the “backquote key”) and the right-single-quote key ' (sometimes called the “apostrophe” or just “quote”). Be careful not to confuse the left-single-quote ` with the “backslash” key \. TEX lets the user type two left-single-quotes `` to create a left-double-quote “ and two right-single-quotes '' to create a right-double-quote ”. Most typists, however, are accustomed to delimiting their quotations with the un-oriented double-quote ".

image

Algorithm of 102- Ecological Bin Packing

In this problem have three color bottol B, G, C and three recycle or bucket. given some bottol each bucket each color you need to minimum change as a result same color bottol in only one bucket . if more than one combination precedence of alphabatic order.

image

102- Ecological Bin Packing

Problem Description
source: https://uva.onlinejudge.org/external/1/p102.html

Bin packing, or the placement of objects of certain weights into different bins subject to certain constraints, is an historically interesting problem. Some bin packing problems are NP-complete but are amenable to dynamic programming solutions or to approximately optimal heuristic solutions.
    In this problem you will be solving a bin packing problem that deals with recycling glass.

    Recycling glass requires that the glass be separated by color into one of three categories: brown glass, green glass, and clear glass. In this problem you will be given three recycling bins, each containing a specified number of brown, green and clear bottles. In order to be recycled, the bottles will need to be moved so that each bin contains bottles of only one color.
image

Algorithm of 3n + 1 problem

Consider the following algorithm:
 
  1.    input n

  2.    print n

  3.    if n = 1 then STOP

100 - The 3n + 1 problem

 Problem description
source:https://uva.onlinejudge.org/external/1/p100.html

Problems in Computer Science are often classified as belonging to a certain class of problems (e.g., NP, Unsolvable, Recursive). In this problem you will be analyzing a property of an algorithm whose classification is not known for all possible inputs.

Consider the following algorithm:
1. input n
2. print n
3. if n = 1 then STOP
4. if n is odd then n ←− 3n + 1
5. else n ←− n/2
6. GOTO 2

Given the input 22, the following sequence of numbers will be printed

image