[Codeforces 718C] Sasha and Array

Problem Description

Sasha has an array of integers a1, a2, ..., an. You have to perform m queries. There might be queries of two types:

1. 1 l r x — increase all integers on the segment from l to r by values x;
2. 2 l r — find , where f(x) is the x-th Fibonacci number. As this number may be large, you only have to find it modulo 109 + 7.

In this problem we define Fibonacci numbers as follows: f(1) = 1, f(2) = 1, f(x) = f(x - 1) + f(x - 2) for all x > 2.

Sasha is a very talented boy and he managed to perform all queries in five seconds. Will you be able to write the program that performs as well as Sasha?

AIO2012 Solution(Chinese)

NORT

It is the year 1982. Malcolm Fraser is the Prime Minister of Australia, you frequently listen to Down Under by Men at Work on your boombox and roller blading is the default mode of transport. As a budding computer scientist, you spend most weekends at the local arcade trying to top your score in the popular video game NORT.

NORT is played on a rectangular grid of square cells with H columns and W rows. You ride a light-bike through the grid, starting in the top-left corner cell. Each second, you can move your light-bike up, down, left or right to any of the four adjacent grid cells (as long as you don't go off the grid!). As you move, your bike's exhaust pipe creates an impenetrable wall of light in the cell you were previously in. If you ever move into a cell containing a wall of light (i.e. a cell you have travelled through before), your bike will disintegrate into pixels in a dramatic 8-bit explosion. The only exception is if you return to the top-left corner cell where you started, in which case the wall of light will be connected and your score for the game will be the total length of wall you have created.

Your goal is therefore to plan the longest possible route through the grid starting and ending in the top-left cell without ever passing through a cell more than once.

AIO2015 Solution(English)

Wet Chairs

As luck would have it, it has rained on the morning of the concert. To make matters worse, the staff did a very rushed job drying the seats! Now it is up to you to decide how to seat everyone.

The seats are arranged in a single long line in front of the stage. In particular there are chairs in the line, and each seat is either wet or dry.

However, all is not lost. Out of the N friends you are bringing to the concert K of them are happy to sit on a wet chair. The other N-K of your friends insist on sitting on a dry chair.

Since this concert is best enjoyed with friends, you would also like your group to be seated as close together as possible so that the distance between the leftmost person and rightmost person is as small as possible. Output the smallest distance possible between the leftmost and rightmost friend at the concert.

Your task is to write a program that outputs this smallest possible distance.