Posts

uva online judge self describing sequence problem solution python | uva 10049

-
The self describing sequence problem  (uva 10049) is also very straight forward and easy programming challenge in competitive programming once understood well. Which can be stated as (from online judge) Solomon Golomb’s self–describing sequence ⟨f(1),f(2),f(3),...⟩ is the only nondecreasing sequence of positive integers with the property that it contains exactly f(k) occurrences of k for each k. A few moments thought reveals that the sequence must begin as follows: n 1 2 3 4 5 6 7 8 9 10 11   12 f(n) 1 2 2 3 3 4 4 4 5 5 5 6 In this problem you are expected to write a program that calculates the value of f(n) given the value of n. Sample Input 100  9999  123456  1000000000  0 Sample Output 21  356  1684  438744 Programming Explanation This is very simple problem states that for given range of n as input (as shown in above image), we have
1 comment
Read more

uva online judge how many fibs problem solution python | uva 10183

-
How many fibs? problem (uva 10183) is one of the easiest programming challenge in competitive programming. Which can be stated as (from online judge) Recall the definition of the Fibonacci numbers: f1 := 1  f2 := 2  fn := fn−1 + fn−2    (n ≥ 3)  Given two numbers a and b, calculate how many Fibonacci numbers are in the range [a,b]. That's it, our jobs is to calculate total number of fibonacci numbers in given range. This problem is pretty straight forward and doesn't need any explanation. Sample Input 10 100  1234567890 9876543210  0 0 Sample Output 5  4 Code fibbo = [] a = 1 b = 1 fibbo.append(a) fibbo.append(b) for i in range(0, 100):     temp = a + b     fibbo.append(temp)     a = b     b = temp z = input().split(" ") a = int(z[0]) b = int(z[1]) count = 0 if (a <= 1):     count = 2 for temp in fibbo:     if(temp >= a and temp <= b):        
1 comment
Read more

uva online judge football (aka soccer) problem solution python | uva 10194

-
The football problem (uva 10194) is very straight forward programming challenge from competitive programming in which we just have to observe string and pull values out. Which can be stated as (from online judge) write a program that receives the tournament name, team names and games played and outputs the tournament standings so far. A team wins a game if it scores more goals than its opponent. Obviously, a team loses a game if it scores less goals. When both teams score the same number of goals, we call it a tie. A team earns 3 points for each win, 1 point for each tie and 0 point for each loss. Teams are ranked according to these rules (in this order): 1. Most points earned. 2. Most wins. 3. Most goal difference (i.e. goals scored - goals against) 4. Most goals scored. 5. Less games played. 6. Lexicographic order. Please note that this tutorial does not cover ordering of teams, it just simply shows extracting required values from string. Ordering of teams if lef
Post a Comment
Read more

uva online judge bridge problem solution python | uva 10037

-
The Bridge problem (uva 10037) is one of the tricky and interesting problem in programming challenge from competitive programming. Which can be stated as (from online judge) There are n number of persons (entered by user) standing on one side of the bridge. Only two persons can cross the bridge at a time and they have only one torch common in all. Thus, we have to find sequence of peoples such that overall time taken is minimum. The person is denoted by time required by that person to cross bridge (e.g if person named 1, then it takes 1 unit of time to cross bridge). If 1 and 5 cross bridge then time taken to cross bridge will be 5 since max time is considered. Our goal is to cross all persons at another side of bridge. Since only two persons at a time can cross bridge and they have only one torch, thus one should have to return to give torch to other peoples. If you observe all the possible method, there are two methods found to be at minimum time, Consider A, B, C,
Post a Comment
Read more

uva online judge vito's family problem solution python | uva 10041

-
The vito's family problem (uva 10041) is a sorting problem in programming challenges from competitive programming. Which can be stated as (from online judge) The world-known gangster Vito Deadstone is moving to New York. He has a very big family there, all of them living in Lamafia Avenue. Since he will visit all his relatives very often, he is trying to find a house close to them. Vito wants to minimize the total distance to all of them and has blackmailed you to write a program that solves his problem. The distance between two street numbers si and sj is dij = |si −sj|. Sample Input 2 2 2 4 3 2 4 6 Sample Output 2 4 Explanation Given random sequence of vito's relatives as input [number of relatives] [relatives distances] (relative name = distance of relative from vito's room) we have to sort out and find the best way to visit all relatives in minimum time. We can do it in two ways: 1) find absolute difference between each relati
Post a Comment
Read more

uva online judge automated judge script problem solution python | uva 10188

-
The automated judge script problem (uva 10188) is sequence checker programming challenge in competitive programming. Which can be stated as (from online judge) write an automated judge script to judge solution runs from teams all over the world. All you have to do is write a program which receives the standard solution and a team output and gives as answer one of the following messages: “Accepted”, “Presentation Error” or “Wrong Answer”. We define each one as: Accepted: Give ‘Accepted’ as answer if the team output matches the standard solution integrally. That is, ALL characters must match and must be in the same order. Presentation Error: We want you to give ‘Presentation Error’ if all NUMERIC characters match (and in the same order) but there is at least one non-numeric character wrong (or in wrong order). For instance, ‘15 0’ and ‘150’ would receive a ‘Presentation Error’, whereas ‘15 0’ and ‘1 0’ would not (it would receive ‘Wrong Answer’, see bellow). Wrong Answer
Post a Comment
Read more

uva online judge common permutation problem solution python | uva 10252

-
The common permutation problem (uva 10252) is a simple and words puzzle programming challenge from competitive programming. Which can be stated as (from online judge) Given two strings of lowercase letters, a and b, print the longest string x of lowercase letters such that there is a permutation of x that is a subsequence of a and there is a permutation of x that is a subsequence of b. In this problem, we just have to find matching words in given two strings. After finding, just print them in alphabetical order, thats it. Sample Input pretty  women  walking  down  the  street Sample Output e  nw  et Explanation We just have to compare two strings and find out common characters, using old school method. Print them in alphabetical order. Code Final_answer = [] while(True):     count = 0     temp = []     str1 = str()     a = list(input())     try:         a[0]     except:         break     b = lis
Post a Comment
Read more

Popular posts from this blog

uva online judge vito's family problem solution python | uva 10041

-
The vito's family problem (uva 10041) is a sorting problem in programming challenges from competitive programming. Which can be stated as (from online judge) The world-known gangster Vito Deadstone is moving to New York. He has a very big family there, all of them living in Lamafia Avenue. Since he will visit all his relatives very often, he is trying to find a house close to them. Vito wants to minimize the total distance to all of them and has blackmailed you to write a program that solves his problem. The distance between two street numbers si and sj is dij = |si −sj|. Sample Input 2 2 2 4 3 2 4 6 Sample Output 2 4 Explanation Given random sequence of vito's relatives as input [number of relatives] [relatives distances] (relative name = distance of relative from vito's room) we have to sort out and find the best way to visit all relatives in minimum time. We can do it in two ways: 1) find absolute difference between each relati
Read more

uva online judge australian voting problem solution python | uva 10142

-
The australian voting problem is little tricky but very easy problem, which can be stated as, Australian ballots require that the voter rank the candidates in order of choice. Initially only the first choices are counted and if one candidate receives more than 50% of the vote, that candidate is elected. If no candidate receives more than 50%, all candidates tied for the lowest number of votes are eliminated. Ballots ranking these candidates first are recounted in favour of their highest ranked candidate who has not been eliminated.  This process continues [that is, the lowest candidate is eliminated and each ballot is counted in favour of its ranked non-eliminated candidate] until one candidate receives more than 50% of the vote or until all candidates are tied. Sample Input 1 3  John Doe  Jane Smith  Sirhan Sirhan  1 2 3  2 1 3  2 3 1  1 2 3  3 1 2 Sample Output John Doe Explanation In australian voting, each voter has to vote all candidates, but
Read more

uva online judge common permutation problem solution python | uva 10252

-
The common permutation problem (uva 10252) is a simple and words puzzle programming challenge from competitive programming. Which can be stated as (from online judge) Given two strings of lowercase letters, a and b, print the longest string x of lowercase letters such that there is a permutation of x that is a subsequence of a and there is a permutation of x that is a subsequence of b. In this problem, we just have to find matching words in given two strings. After finding, just print them in alphabetical order, thats it. Sample Input pretty  women  walking  down  the  street Sample Output e  nw  et Explanation We just have to compare two strings and find out common characters, using old school method. Print them in alphabetical order. Code Final_answer = [] while(True):     count = 0     temp = []     str1 = str()     a = list(input())     try:         a[0]     except:         break     b = lis
Read more