studious-little-jhool

Yes, you read it right - Little Jhool is back, but no, he's not over his break up, still. And he's sad, broken and depressed; thus, he decided to visit a psychologist. She tells him to think about his pleasant memories of childhood, and stay busy so as to not miss his ex-girlfriend.

She asks him about his favorite memories from childhood, and being the genius Mathematician Little Jhool is, he remembered that solving Mathematics problem given to him by his teacher was his favorite memory.

He had two types of notebooks, when he was a kid.
10 problems could be solved in one page, in the first notebook.
12 problems could be solved in one page, in the second notebook.

Little Jhool remembered how in order to maintain symmetry, if he was given with n problems in total to solve, he tore out pages from both notebooks, so no space was wasted. EVER!

But, now he's unable to solve his own problem because of his depression, and for the exercise of the week, he has to answer the queries asked by his psychologist.

Given n number of questions, print the minimum number of pages he needs to tear out from the combination of both the notebooks, so that no space is wasted.

Input Format:
The first line will contain t - number of test cases.

The second will contain an integer n - number of questions.

Output Format:
Corresponding to the input, print the minimum number of pages Little Jhool needs to tear out from the combination of both the notebooks. If it is NOT possible, print  "-1".

Constraints:  
1 ≤ t  ≤ 100  
1 ≤ n ≤ 113 

SAMPLE INPUT
2
23
32

SAMPLE OUTPUT
-1
3

Explanation

For 32: 2 pages from the notebook, where 10 can be solved; 1 page from the notebook, where 12 can be solved.

Source: hackerearth | Difficulty: EASY
Tags: Dynamic programming

Data structures

Complete search


Solutions:
'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import sys
import os
import time

tc=input("")
tc=(int)(tc)

def check(qs):
	if (qs < 12 and qs!=10 and qs!=0):
		return 2000
	elif qs == 0:
		return 0
	return 1 + min(check(qs-10),check(qs-12))
	

for i in range(tc):
	qs=input("")
	qs=(int)(qs)
	ans = check(qs)
	if ans > qs:
		print(-1)
	else:
		print(ans)
	
	




for _ in range(int(input())):
	n=eval(input())
	flag=0
	if n%2!=0:
		print('-1')
	else:
		for i in range(12):
			for j in range(10):
				if i*10+j*12==n:
					ans=i+j
					flag=1
					break
			if flag==1:
				break

		if flag==1:
			print(i+j)
		else:
			print('-1')


for _ in range(int(input())):
	n=eval(input())
	flag=0
	if n%2!=0:
		print('-1')
	else:
		for i in range(12):
			for j in range(10):
				if i*10+j*12==n:
					ans=i+j
					flag=1
					break
			if flag==1:
				break

		if flag==1:
			print(i+j)

		else:
			print('-1')


def pages(num):
	ans=100000
	for i in range(113):
		for j in range(113):
			if(i*10+j*12==num):
				ans=min(ans,i+j)
	if(ans==100000):
		print("-1")
	else:
		print(ans)
		
test=int(input())
while(test):
	test-=1
	num=int(input())
	pages(num)


import sys

def pages(N):
	if (N % 2 == 0):
		p = 0
		decimal = N // 10
		resto = N % 10
		
		if ((decimal * 10 + resto ) <=(12 * decimal)): 
			N -= (resto / 2 * 12)
			decimal = N // 10
			s = decimal / 6
			p += resto / 2
			p += (s * 5)
			N -= (s * 5 * 12)
			while ( N != 0):
				N -= 10
				p += 1
			return p
		else:
			return - 1
	else:
		return -1
			
kases=int(input())
for kase in range(kases):
	N = int(input())
	print(pages(N))
	


t = eval(input())
for i in range(t):
	inp = eval(input())
	
	j = 0
	toggle = 1
	while(inp-10*j>=0):
			d = (inp-10*j)/12.0
			if d==int(d):
					print(int(j+d))
					toggle = 0
					break
			j+=1
	if toggle:
			print(-1)


arr=[-1]
arr=arr*114
arr[10]=1
arr[12]=1
for i in range(10,101):
	if arr[i]!=-1:
		if arr[i+10]==-1:
			arr[i+10]=arr[i]+1
		if arr[i+12]==-1:
			arr[i+12]=arr[i]+1
 
t=eval(input())
while(t>0):
	print(arr[int(eval(input()))])
	t=t-1
		


for i in range(eval(input())):
	n = eval(input())
	ans = 1000000
	for i in range(113):
		for j in range(113):
			if (i*10 + j*12 == n):
				ans = min (ans, i+j)
	if (ans==1000000):
		print(-1)
	else:
		print(ans)


cases = int(eval(input()))

l = [int(eval(input())) for x in range(cases)]

def as_sum_of(k, m, n, memo={}):
	if k == m or k == n:
		return 1
	
	elif k < m and k < n:
		return float('inf')

	elif k in memo:
		return memo[k]
	
	else:
		least = float('inf')
		for x in range(2, k//2+1):
			req = as_sum_of(x, m, n, memo) + as_sum_of(k - x, m, n, memo)
			if req < least:
				least = req
		memo[k] = least
		return memo[k]

for num in l:
	if num % 2 == 1:
		print((-1))
	else:
		ans = as_sum_of(num, 10, 12)
		if ans != float('inf'):
			print(ans)
		else:
			print((-1))
		


#!/usr/bin/env python
# -*- coding: utf-8 -*-

a = [1000] * 150
a[0] = 0
a[10] = 1
a[12] = 1
for i in range(13, len(a)):
	a[i] = min(a[i - 10] + 1, a[i - 12] + 1)

for i in range(0, len(a)):
	if a[i] >= 1000:
		a[i] = -1

t = int(input())
for _ in range(0, t):
	n = int(input())
	print(a[n])


#http://www.hackerearth.com/problem/algorithm/studious-little-jhool/
import fileinput


def findMinPages (n):
	if n%2 == 1:
		minp = -1
		return minp

	if n==10:
		minp = 1
		return minp

	if n<12:
		minp = -1
		return minp
	
	hq = n / 12
	hr = n % 12
	
	i = hq
	j = 1
	
	if hr == 0:
		minp = hq
	else:
		while ( ((i*12) + (j*10) != n) ):
			i -= 1 
			j += 1 
#        print i , j
		if i<0:
			minp = -1
		else:
			minp = i + j
	return minp

#for i in xrange (200):
#    print i, findMinPages(i)


finput=fileinput.input()

for line in fileinput.input():
	if not fileinput.isfirstline():
		ip = line.split(' ')
		print(findMinPages(int(ip[0])))


arr=[-1]
arr=arr*114
arr[10]=1
arr[12]=1
for i in range(10,101):
	if arr[i]!=-1:
		if arr[i+10]==-1:
			arr[i+10]=arr[i]+1
		if arr[i+12]==-1:
			arr[i+12]=arr[i]+1

t=eval(input())
while(t>0):
	print(arr[int(eval(input()))])
	t=t-1
		


for i in range(eval(input())):
	n = eval(input())
	ans = 1000000
	for i in range(12):
		for j in range(12):
			if (i*10 + j*12 == n):
				ans = min (ans, i+j)
	if (ans==1000000):
		print(-1)
	else:
		print(ans)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
t = int(input())
for _ in range(t):
	n=int(input())
	ans= 1000000
	for i in range(0,15):
		for j in range(0,15):
			if i*10 + j*12 == n:
				ans = min(ans,i+j)
	if(ans == 1000000):
		print("-1")
	else:
		print(ans)