Month: July 2015

CodingChillout.Malta

Sphere contest    Last week it was the first of which I took part and landed at 2nd place on the leader board

 

POS 1 2 3
NAME Peng Cao Fairmutex Javi
TEST1.00 1.00 (1) 1.00 (1) 1.00 (1)
FCTRL21.00 1.00 (17) 1.00 (1) 1.00 (1)
ADDTWO1.00 1.00 (24) 1.00 (1) 1.00 (1)
REVARR1.00 1.00 (1) 1.00 (1) 1.00 (1)
PREFSUFF10.00 10.00 (7) 10.00 (2) 10.00 (14)
CONVERT50.00 50.00 (9) 50.00 (11) 50.00 (5)
GLUTTONS5.00 5.00 (1) 5.00 (1) 5.00 (10)
HTMLTAGS25.00 25.00 (1) 25.00 (1) 25.00 (1)
LADYBUGS80.00 80.00 (1) 72.00 (3) 64.00 (4)
SOL 9 9 9
SCORE 174 166 158

The questions ranged from very easy to ones that required some thinking

http://codechillout.sphere-contest.com/ranking

Winners announced on twitter

I will try to post about the Challenges and how I tackled them soon.

Warm-up session

TEST ( c99 strict )
Small factorials ( Python 2.7 )
Add two number ( Python 2.7 )
Reverse Array ( Python 2.7 )

Online Round

Prefix-suffix balance ( c99 strict )
Simple Numbers Conversion (Python 2.7)
Gluttons (Java 7/Python 2.7 / c99 strict )
Ladybugs race (c99 strict)
HTML tags (Python 2.7)

http://codechillout.sphere-contest.com/

 

CodingChillout.Malta: Prefix-suffix balance

http://codechillout.sphere-contest.com/problems/onlineround/PREFSUFF

Prefix-suffix balance

One of the most popular problems presented during the initial stages of IT recruitment is that of finding a place in a sequence of integers which divides it into two groups of equal sum, i.e., at a position where the sum of the prefix is equal to the sum of the suffix. Your task is to find this position.

Input

The first line contains exactly one number t, representing the number of data sets. Each data set i is a single line, consisting of the sequence length mi and exactly mi integers which form the sequence. Numbers in data sets are separated by spaces.

Output

For each data set i print the shortest possible length of the prefix for which the sum of elements is equal to the sum of elements of the determined suffix. If desired number does not exist, then print 0. Answers for data sets should be separated by new lines.

Notes

The prefix and suffix cannot be empty.

Example

Input:
4
5 4 2 3 1 2
5 4 -2 1 1 -2
6 1 -1 1 -1 1 -1
3 0 0 0

Output:
2
0
2
1

 

Answer

#include 

int main(void) {
	int instances;
	scanf("%d", &instances);
	int n;
	int i;
	for(i = 0 ; i < instances ; i++){
		scanf("%d", &n);
		int entries[n];
		int j;
		for(j = 0 ; j < n ; j++){
			scanf("%d", &entries[j]);
		}
		int sumA[n-1];
    	int total = 0;
    	int k;
    	int flag1 =1;
    	for(k = 0 ; k <= n-2 ; k++){
    		if(entries[k] != entries[n-(k)]) // Check for palindrome
    		     flag1=0;
	    	total +=entries[k];
	    	sumA[k] = total;
    	}
    	if(flag1 == 1 && entries[n/2] == entries[(n/2)-1])
    	    return (n/2)-1;
    	
	    total +=entries[n-1];
	    int flag = 1;
        if(total%2 == 0){ // If it is odd it cannot be split
        	int j;
        	int tot2 = total/2;
	    	for(j = 0 ; j <= n-2 ; j++){
		      if(sumA[j] == tot2){
		         printf("%d\n", j+1);
		         flag = 0;
		         break;
		      }
		    }
        }
       if(flag ==1)
          printf("0\n");
	}
	return 0;
}

CodingChillout.Malta: Warm-up Session

Warm-Up round at Codingchillout.Malta http://codechillout.sphere-contest.com/round/test

http://codechillout.sphere-contest.com/problems/test/TEST

TEST

Your program is to use the brute-force approach in order to find the Answer to Life, the Universe, and Everything. More precisely… rewrite small numbers from input to output. Stop processing input after reading in the number 42. All numbers at input are integers of one or two digits.

Example

Input:
1
2
88
42
99

Output:
1
2
88

Answer

#include 

int main(void) {
	int i;
	while (scanf("%d", &i)==1){
		if(i == 42) break;
		printf("%d\n",i);
	}

	return 0;
}

http://codechillout.sphere-contest.com/problems/test/FCTRL2

Small factorials

You are asked to calculate factorials of some small positive integers.

Input

An integer t, 1<=t<=100, denoting the number of testcases, followed by t lines, each containing a single integer n, 1<=n<=100.

Output

For each integer n given at input, display a line with the value of n! (“n factorial”).

Example

Sample input:

4
1
2
5
3

Sample output:

1
2
120
6

Answer

import math

n = int(raw_input());
for v in range(0,n):
	print math.factorial(int(raw_input()))

http://codechillout.sphere-contest.com/problems/test/ADDTWO

Add two number

Calculate the sum a+b for given integers a and b.

Input

There will be provided certain number of data sets for the problem. Each data set consist of two integer numbers ai and bi separated with a space, where i is the number of the data set. Data sets are separated with a new line.

Output

For ith data set print the value of ai + bi. Answers should be separated with a new line.

Example

Input:
2 3
10 -2
-1 5
-3 -3
0 1

Output:
5
8
4
-6
1

Answer

import fileinput

for line in fileinput.input():
    n = line.split();
    print int(n[0]) + int(n[1])

http://codechillout.sphere-contest.com/problems/test/REVARR

Reverse array

For a given array reverse its order.

Input

In the first line there will be a number of the data sets t. In the next t lines data sets follows. Each data set is a line of numbers separated by spaces. First number ni is the length of the array. Next ni numbers are the values in array.

Output

For ith data set write values from array in reversed order. Numbers should be separated by spaces and answers for data sets should be separated by a new line.

Example

Input:
2
7 1 2 3 4 5 6 7
3 3 2 11

Output:
7 6 5 4 3 2 1
11 2 3

Answer

n = int(raw_input())
for v in range(0,n):
    j = raw_input().split(" ")
    del j[0]
    j = " ".join(reversed(j))
    print j

CodingChillout.Malta: Gluttons

http://codechillout.sphere-contest.com/problems/onlineround/GLUTTONS

Gluttons

Every year Megabyteland hosts The Great Gluttony Festival. According to tradition, during the first day of the festival all participants eat cookies nonstop for 24 hours (with not even a fraction of a second’s break!). As soon as a glutton has finished eating one cookie, he immediately stars to eat the next one (this does not apply only to the situation at the end of the day, when the participant is not allowed to start eating a cookie if he knows that he cannot finish eating it before the end of the day). Another important part of the tradition is that each glutton eats a single cookie at his very own constant characteristic pace.

For the coming festival, the organizers have invited only those gluttons who have already participated in the previous editions. This means that the pace of each glutton is already known (they don’t really like to change their natural pace). Based on this data, the organizers of the festival want to determine how many cookies they need to buy. However, the cookies in the shop are sold in boxes of fixed size, thus they may have to buy more cookies than the number that is going to be eaten.

Your task is to establish the number of boxes with cookies that are needed to carry out the competition. The number of participants, along with the pace of each of them (given in seconds needed to eat a single cookie) will be given.

Input

The first line of input contains the number of test cases t. Each test case has the following form: two numbers N and M, separated by a space, in the first line (1 ≤ N ≤ 10000, 1 ≤ M ≤ 1000000000). The first number N is the number of invited gluttons and the second number M is the numbers of cookies in the box. Each line of the next N lines contains a single integer number, representing the pace of the glutton. The pace of the glutton is expressed as the number of seconds (not greater than 100000) needed to eat a single cookie.

Output

For each test case you need to write exactly one integer denoting the number of boxes which have to be bought by the organizers to carry out the contest. Answers for distinct test cases should be written in separate lines.

Example

Input:
2
2 10
3600
1800
3 356
123
32999
10101

Output:
8
2

Answers

C

#include 
#include 
int main(void) {
	int n;
	int invites;
	int nBox;
	int i;
	scanf("%d", &n);
	for(i = 0 ; i < n ; i++){
		scanf("%d %d", &invites,&nBox);
	    double total = 0;
		int j;
		for(j = 0 ; j < invites;j++){
			    int time;
			    scanf("%d",&time);
		    	total += 86400/time;
        }
        printf("%d\n",(int)ceil(total/nBox));
	}
	return 0;

Python 2.7

import math
contestDuration = 86400
instances = int(raw_input())
for v in range(0,instances):
    data = raw_input().split(" ") # Invited/Cookies
    i = int(data[0])
    cookies = int(data[1])
    total = 0
    for k in range(0,i):
       total = total + contestDuration/int(raw_input())
    print int(math.ceil(total/cookies))

Java 7

import java.util.*;
import java.lang.*;

class Main
{
	public static void main (String[] args) throws java.lang.Exception
	{
		 java.io.BufferedReader r = new java.io.BufferedReader (new java.io.InputStreamReader (System.in));
		 int instances = Integer.parseInt(r.readLine());
		 
		 for(int k = 0 ; k < instances; k++){
		    String [] data = r.readLine().split("\\s+");
		    int invites = Integer.parseInt(data[0]);
		    double total = 0;
		    for(int i = 0 ; i < invites; i++){
		    	total += 86400/Integer.parseInt(r.readLine());
		 
		    }
		    System.out.println((int)Math.ceil(total/Integer.parseInt(data[1])));
		 }
	}
}

CodingChillout.Malta: HTML tags

http://codechillout.sphere-contest.com/problems/onlineround/HTMLTAGS

HTML tags

We often write HTML tags with both lower-case and capital letters. As a result, the website’s source code looks ugly. Your task is to write a program which will turn all the lowe-case letters in the HTML tags (i.e. those appearing in between of the signs “<” a “>”) into capital letters.

Input

You are given a fragment of HTML source code.

Output

Your output should print the same HTML source code, but with all the HTML tags written in capital letters.

Example

Input:
<html>
<head>
<TITLE>This is title</Title>
</head>
<body>
<b>Something</b>
</body>
</html>

Output:
<HTML>
<HEAD>
<TITLE>This is title</TITLE>
</HEAD>
<BODY>
<B>Something</B>
</BODY>
</HTML>

Answer

import fileinput
for line in fileinput.input():
   res = '';
   for c in line:
    if(c == '< '):
        flag = True
    elif(c == '>'):
        flag = False
    if(flag == False):
        res += c
    elif(flag == True):
        res += c.upper()
   print res

CodingChillout.Malta: Simple Number Conversion

http://codechillout.sphere-contest.com/problems/onlineround/CONVERT

Converting a number from any base to any base.
Assume that n ≤ 36 and the digits are 0,1,2,3,4,5,6,7,8,9, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z.

Input

The first line contains integer N, the number of test cases.
n s r
n is the number to convert
s is the source base
r is the resulting base

Output

For each n s r, output the number n in r base.

Example

Input:
4
56378 10 2
AB98BC 15 10
ABCDEF123456 36 2
1000100101010 2 10

Output:
1101110000111010
8182977
1001011010111011111010000110001101100010101101000110110111010
4394

import sys

digits ="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def base2base(number,rBase,sBase):
    '''
    # Implementation of Any base to Decimal, but int() is faster
    dec = 0
    for n in number:
        dec = digits.index(n,0,rBase) + dec * rBase
    '''
    dec = int(number,rBase)
    result = []
    while(dec != 0):
        dec,mod = divmod(dec, sBase)
        result.insert(0,digits[mod])
    for i in result:
        sys.stdout.write( "%s" % (i))
    print


instances = int(raw_input())
for v in range(0,instances):
    data = raw_input().split(" ")
    number = data[0]
    rBase = int(data[1])
    sBase = int(data[2])
    if(number != '0'):
       base2base(number,rBase,sBase)
    else:
        print 0

Code on Ideone

Finding the next Palindrome

Given a positive palindrome number P up to 10,000,000 digits. Find the next palindrome.

Input

The first line contains integer n, the number of test cases. Integers P are given in the next t lines.

Output

For each P, output the next palindrome larger than P.

Example

Input:
12
1
9
12
99
101
999
1001
808
900000000000000000000000000000000000009
123454321
1999999999991
199999999991

Output:
2
11
23
101
111
1001
1111
818
900000000000000000010000000000000000009
123464321
2000000000002
200000000002

#include 
#include 
#include 
#include 
int main(void) {
	char * number;
	int instances;
	scanf("%d", &instances);
	int i;
	for (i = 0; i < instances; i++){
		number =  malloc(sizeof(char)*(10000000));
		scanf("%s", number);
		int len = strlen(number);
		int k;
		int flag = 1;
		
		// In case the number is all 9s
		for (k = 0; k < len; k++){
			if (number[k] != '9'){
				flag = 0;
			}
		}
		
		if (flag == 1){
			printf("1");
			for (k = 0; k < len - 1; k++){
				printf("0");
			}
			printf("1\n");

		}
		else{
			int left = (int)ceil((double)len / 2)-1;
            int right;
			if(len%2 == 0)
			   right = left+1;
			 else
			   right = left;
			
			for (k = 0; k <= (int)floor(len / 2.0); k++){
				// if middle numbers are not 9
				if ((number[left] != '9') && (number[right] != '9')){
					int numL = number[left];
					int numR = number[right];
					number[left--] = (char)(numL + 1);
					number[right++] = (char)(numR + 1);
					break;
				}
				else{ // if middle numbers are 9
					number[left--] = '0';
					number[right++] = '0';
				}
			}
			printf("%s\n", number);
		}
	}
	free(number);
	return 0;
}

Code on ideone