POJ 2318 TOYS

Description:

Calculate the number of toys that land in each bin of a partitioned toy box.
Mom and dad have a problem - their child John never puts his toys away when he is finished playing with them. They gave John a rectangular box to put his toys in, but John is rebellious and obeys his parents by simply throwing his toys into the box. All the toys get mixed up, and it is impossible for John to find his favorite toys.

John’s parents came up with the following idea. They put cardboard partitions into the box. Even if John keeps throwing his toys into the box, at least toys that get thrown into different bins stay separated. The following diagram shows a top view of an example toy box.
img
For this problem, you are asked to determine how many toys fall into each partition as John throws them into the toy box.

洛谷 P2313 [HNOI2005]汤姆的游戏

Description:

汤姆是个好动的孩子,今天他突然对圆规和直尺来了兴趣。于是他开始在一张很大很大的白纸上画很多很多的矩形和圆。画着画着,一不小心将他的爆米花弄撒了,于是白纸上就多了好多好多的爆米花。汤姆发现爆米花在白纸上看起来就像一个个点,有些点落在矩形或圆内部,而有些则在外面。于是汤姆开始数每个点在多少个矩形或圆内部。毕竟汤姆还只是个孩子,而且点、矩形和圆又非常多。所以汤姆数了好一会都数不清,于是就向聪明的你求助了。你的任务是:在给定平面上N个图形(矩形或圆)以及M个点后,请你求出每个点在多少个矩形或圆内部(这里假设矩形的边都平行于坐标轴)。

hihoCoder #1167 : 高等理论计算机科学

Description:

少女幽香这几天正在学习高等理论计算机科学,然而她什么也没有学会,非常痛苦。所以她出去晃了一晃,做起了一些没什么意义的事情来放松自己。
门前有一颗n个节点树,幽香发现这个树上有n个小精灵。然而这些小精灵都比较害羞,只会在一条特定的路径上活动。第i个小精灵会在ai到bi的路径上活动。
两个小精灵是朋友,当且仅当它们的路径是有公共点的。
于是幽香想要知道,有多少对小精灵a和b,a和b是朋友呢?其中a不等于b,a,b和b,a看做一对。

UVA 11291 Smeech

Description:

Professor Octastichs has invented a new pro-gramming language, Smeech. An expression in Smeech may be a positive or negative integer, or may be of the form (p e 1 e 2 ) where p is a real number between 0 and 1 (inclusive) and e 1 and e 2 are Smeech expressions.

The value represented by a Smeech expression is as follows:

  • An integer represents itself
  • With probability p, (p e 1 e 2 ) represents x+ y where x is the value of e 1 and y is the value of e 2 ; otherwise it represents x − y.

Given a Smeech expression, what is its expected value?

Codeforces Round #516 (Div. 2, by Moscow Team Olympiad)

A. Make a triangle!

Description:

Masha has three sticks of length $a$, $b$ and $c$ centimeters respectively. In one minute Masha can pick one arbitrary stick and increase its length by one centimeter. She is not allowed to break sticks.
What is the minimum number of minutes she needs to spend increasing the stick’s length in order to be able to assemble a triangle of positive area. Sticks should be used as triangle’s sides (one stick for one side) and their endpoints should be located at triangle’s vertices.

HDU 3951 Coin Game

Description:

After hh has learned how to play Nim game, he begins to try another coin game which seems much easier.
img
The game goes like this:
Two players start the game with a circle of n coins.
They take coins from the circle in turn and every time they could take 1~K continuous coins.
(imagining that ten coins numbered from 1 to 10 and K equal to 3, since 1 and 10 are continuous, you could take away the continuous 10 , 1 , 2 , but if 2 was taken away, you couldn’t take 1, 3, 4, because 1 and 3 aren’t continuous)
The player who takes the last coin wins the game.
Suppose that those two players always take the best moves and never make mistakes.
Your job is to find out who will definitely win the game.

Codeforces Round #515 (Div. 3)

A. Vova and Train

Description:

Vova plans to go to the conference by train. Initially, the train is at the point $1$ and the destination point of the path is the point $L$. The speed of the train is $1$ length unit per minute (i.e. at the first minute the train is at the point $1$, at the second minute — at the point $2$ and so on).
There are lanterns on the path. They are placed at the points with coordinates divisible by $v$ (i.e. the first lantern is at the point $v$, the second is at the point $2v$ and so on).
There is also exactly one standing train which occupies all the points from $l$ to $r$ inclusive.
Vova can see the lantern at the point $p$ if $p$ is divisible by $v$ and there is no standing train at this position ($p \not\in [l; r]$). Thus, if the point with the lantern is one of the points covered by the standing train, Vova can’t see this lantern.
Your problem is to say the number of lanterns Vova will see during the path. Vova plans to go to $t$ different conferences, so you should answer $t$ independent queries.

HDU 2222 Keywords Search

Description:

In the modern time, Search engine came into the life of everybody like Google, Baidu, etc.
Wiskey also wants to bring this feature to his image retrieval system.
Every image have a long description, when users type some keywords to find the image, the system will match the keywords with description of image and show the image which the most keywords be matched.
To simplify the problem, giving you a description of image, and some keywords, you should tell me how many keywords will be match.

HDU 1890 Robotic Sort

Description:

Somewhere deep in the Czech Technical University buildings, there are laboratories for examining mechanical and electrical properties of various materials. In one of yesterday’s presentations, you have seen how was one of the laboratories changed into a new multimedia lab. But there are still others, serving to their original purposes.

In this task, you are to write software for a robot that handles samples in such a laboratory. Imagine there are material samples lined up on a running belt. The samples have different heights, which may cause troubles to the next processing unit. To eliminate such troubles, we need to sort the samples by their height into the ascending order.

Reordering is done by a mechanical robot arm, which is able to pick up any number of consecutive samples and turn them round, such that their mutual order is reversed. In other words, one robot operation can reverse the order of samples on positions between A and B.

A possible way to sort the samples is to find the position of the smallest one (P1) and reverse the order between positions 1 and P1, which causes the smallest sample to become first. Then we find the second one on position P and reverse the order between 2 and P2. Then the third sample is located etc.

img

The picture shows a simple example of 6 samples. The smallest one is on the 4th position, therefore, the robot arm reverses the first 4 samples. The second smallest sample is the last one, so the next robot operation will reverse the order of five samples on positions 2–6. The third step will be to reverse the samples 3–4, etc.

Your task is to find the correct sequence of reversal operations that will sort the samples using the above algorithm. If there are more samples with the same height, their mutual order must be preserved: the one that was given first in the initial order must be placed before the others in the final order too.

|