### Mehedi33's blog

By Mehedi33, 11 days ago, ,

Problem

Solution

I have matched all forum I/O. All O/Ps are matched correctly. But still getting Wrong Answer. Can anyone please tell where I did mistake ?

Problem Description:

Given an array of integers (0 indexed), you have to perform two types of queries in the array.

1. 1 i j v — change the value of the elements from ith index to jth index to v.

2. 2 i j — find the average value of the integers from ith index to jth index.

You can assume that initially all the values in the array are 0.

Input

Input starts with an integer T (≤ 5), denoting the number of test cases.

Each case contains two integers: n (1 ≤ n ≤ 105), q (1 ≤ q ≤ 50000), where n denotes the size of the array. Each of the next q lines will contain a query of the form:

1 i j v (0 ≤ i ≤ j < n, 0 ≤ v ≤ 10000)

2 i j (0 ≤ i ≤ j < n)

Output

For each case, print the case number first. Then for each query of the form '2 i j' print the average value of the integers from i to j. If the result is an integer, print it. Otherwise print the result in 'x/y' form, where x denotes the numerator and y denotes the denominator of the result and x and y are relatively prime.

Sample Input

1

10 6

1 0 6 6

2 0 1

1 1 1 2

2 0 5

1 0 3 7

2 0 1

Output for Sample Input

Case 1:

6

16/3

7

Note

Dataset is huge. Use faster i/o methods.

•
• -5
•

By Mehedi33, 3 years ago, ,

Problem: LightOJ 1042 — Secret Origins

My Solution: http://ideone.com/jMD5fa

Give me some hints to avoid TLE.

Thanks

Problem Description:

This is the tale of Zephyr, the greatest time traveler the world will never know. Even those who are aware of Zephyr's existence know very little about her. For example, no one has any clue as to which time period she is originally from.

But we do know the story of the first time she set out to chart her own path in the time stream. Zephyr had just finished building her time machine which she named — "Dokhina Batash". She was making the final adjustments for her first trip when she noticed that a vital program was not working correctly. The program was supposed to take a number N, and find what Zephyr called its Onoroy value.

The Onoroy value of an integer N is the number of ones in its binary representation. For example, the number 13 (11012) has an Onoroy value of 3. Needless to say, this was an easy problem for the great mind of Zephyr. She solved it quickly, and was on her way.

You are now given a similar task. Find the first number after N which has the same Onoroy value as N.

Input

Input starts with an integer T (≤ 65), denoting the number of test cases.

Each case begins with an integer N (1 ≤ N ≤ 10^9).

Output

For each case of input you have to print the case number and the desired result.

Sample Input

5

23

14232

391

7

8

Output for Sample Input

Case 1: 27

Case 2: 14241

Case 3: 395

Case 4: 11

Case 5: 16

•
• +3
•

By Mehedi33, 3 years ago, ,