第二十八次codeforces竞技结束 #291 Div 2

# Name A Chewbaсca and Number standard input/output 1 s, 256 MB x3704 B Han Solo and Lazer Gun standard input/output 1 s, 256 MB x2790 C Watto and Mechanism standard input/output 3 s, 256 MB x895 D R2D2 and Droid Army standard input/outpu

#	Name
A	Chewbaсca and Number standard input/output 1 s, 256 MB		x3704
B	Han Solo and Lazer Gun standard input/output 1 s, 256 MB		x2790
C	Watto and Mechanism standard input/output 3 s, 256 MB		x895
D	R2D2 and Droid Army standard input/output 2 s, 256 MB		x744

这次在C题上纠结的有点多了浪费了不少时间……

Codeforces Round #291 (Div. 2)

A. Chewbaсca and Number

time limit per test

memory limit per test

input

output

Luke Skywalker gave Chewbacca an integer number x. Chewbacca isn't good at numbers but he loves inverting digits in them. Inverting digit t means replacing it with digit 9?-?t.

Help Chewbacca to transform the initial number x to the minimum possible positive number by inverting some (possibly, zero) digits. The decimal representation of the final number shouldn't start with a zero.

Input

The first line contains a single integer x (1?≤?x?≤?1018) — the number that Luke Skywalker gave to Chewbacca.

Output

Print the minimum possible positive number that Chewbacca can obtain after inverting some digits. The number shouldn't contain leading zeroes.

Sample test(s)

input

27

output

22

input

4545

output

4444

其实读题真的是很重要的事情，The number shouldn't contain leading zeroes 意思是，数字不含前导零…… 没看见……

题意是说，给你一个数字，你可以将其中任意数位的数字变成（9-当前数字），需要获得一个最小的数（但是不含前导零！）。

所以基本上就是一个把大于等于5的都变成9和当前数字的差，然后注意首位如果是0请改成9，即可…… 叹气，不审题害死人呐

Code：

#include  
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))

bool cmp(const int a, const int b)
{
	return a > b;
}

int main()
{
	string s;	cin>>s;
	for(int i=0;i



B. Han Solo and Lazer Gun


time limit per test
1 second



memory limit per test
256 megabytes



input
standard input



output
standard output




There are n Imperial stormtroopers on the field. The battle field is a plane with Cartesian coordinate system. Each stormtrooper is associated with his
 coordinates (x,?y) on this plane.

Han Solo has the newest duplex lazer gun to fight these stormtroopers. It is situated at the point (x0,?y0).
 In one shot it can can destroy all the stormtroopers, situated on some line that crosses point (x0,?y0).

Your task is to determine what minimum number of shots Han Solo needs to defeat all the stormtroopers.

The gun is the newest invention, it shoots very quickly and even after a very large number of shots the stormtroopers don't have enough time to realize what's happening and change their location.



Input

The first line contains three integers n, x0 и y0 (1?≤?n?≤?1000, ?-?104?≤?x0,?y0?≤?104)
 — the number of stormtroopers on the battle field and the coordinates of your gun.

Next n lines contain two integers each xi, yi (?-?104?≤?xi,?yi?≤?104)
 — the coordinates of the stormtroopers on the battlefield. It is guaranteed that no stormtrooper stands at the same point with the gun. Multiple stormtroopers can stand at the same point.



Output

Print a single integer — the minimum number of shots Han Solo needs to destroy all the stormtroopers.



Sample test(s)



input
4 0 0
1 1
2 2
2 0
-1 -1




output
2




input
2 1 2
1 1
1 0




output
1






Note

Explanation to the first and second samples from the statement, respectively:






这道题比起A对于参赛者而言倒是最简单AC的一个，告诉你雷射炮的坐标和敌人的坐标，问你多少枪能把他们全干掉。
题意解析的话大概是这么个情况，从炮台坐标开始画多少条直线能穿透所有已知点。
再优化一下就相对坐标系一下，就是把炮台所在点视为原点，那么斜率相同的（没有斜率的也互相称作相同）即为在同一次攻击内被干掉。
一旦有除法要考虑精度浮点数判断相等的时候就很头疼，于是我用了分数表示斜率的方法，用map存一个来代表 n/m 这样一个分数的斜率，化为最简分数即可。
我的这种方法需要考虑到的为以下问题：
1、 其中有一个为0的时候，因为0和非0数组成的分数，要么就是无斜率的0分母斜率，要么就是求最大公约数没办法把各种分之0化为相同的。于是一旦遇到一个为0，另一个为非0，我们就把他变成 0/1 和 1/0 的形式存即可。
2、 都为0的时候，您是不是怎么打都会死……
3、 这里我用的是map，很棒的STL，如果有不懂的可以这么理解，map是一个数组，但是下标可以为任何的东西，此处我用的下表是点对，就是分数。m[make_pair(a,b)]就是下标为的意思。
Code：

#include