Codeforces Global Round 7
A. Bad Ugly Numbers
You are given a integer nnn (n>0)(n>0)(n>0). Find any integer sss which satisfies these conditions, or report that there are no such numbers:
In the decimal representation of sss:
s>0s>0s>0,
sss consists of nnn digits,
no digit in sss equals 000,
sss is not divisible by any of it’s digits.
Input
The input consists of multiple test cases. The first line of the input contains a single integer ttt (1⩽t⩽400)(1\leqslant t\leqslant 400)(1⩽t⩽400), the number of ...
匈牙利算法
二分图最大匹配
二分图
二分图又称作二部图,是图论中的一种特殊模型。 设G=(V,E)G=(V,E)G=(V,E) 是一个无向图,如果顶点 VVV 可分割为两个互不相交的子集 (A,B)(A,B)(A,B),并且图中的每条边 (i,j)(i,j)(i,j) 所关联的两个顶点iii和jjj分别属于这两个不同的顶点集(i∈A,j∈B)(i \in A,j \in B)(i∈A,j∈B),则称图 GGG 为一个二分图。
判定定理:无向图G为二分图的充分必要条件是,G至少有两个顶点,且其所有回路的长度均为偶数。
最大匹配
给定一个二分图 GGG,在 GGG 的一个子图 MMM 中,MMM 的边集中的任意两条边都不依附于同一个顶点,则称 MMM 是一个匹配。所有匹配组成的集合中,边数最大的子集称为图的最大匹配。
如果一个匹配中,图中的每个顶点都和图中某条边相关联,则称此匹配为完全匹配,也称作完备匹配。
增广路径
给定图 GGG 的一个匹配 MMM,如果一条路径的边 EEE 交替出现 E∈ME\in ME∈M 和 E∉ME\notin ME∈/M 的情况,我们称之为一条 M−M-M−交错路径。而 ...
UPCOJ 1116 奎奎发红包
题目描述
情人节又到了,又到了一年一度发红包的时间。经大家研究决定,今年让奎奎自愿发红包。
俱乐部有nnn个人(0<n<100000)(0<n<100000)(0<n<100000),每个人都有一个单身值v[i]v[i]v[i]与亲密度t[i]t[i]t[i](0≤v[i]≤10000,0≤t[i]≤10000)(0≤v[i]≤10000,0≤t[i]≤10000)(0≤v[i]≤10000,0≤t[i]≤10000),单身值越大的人,在情人节的时候就越羡慕奎奎,奎奎就需要给他更大的红包来安慰他。 由于一个寒假没有见到奎奎,领红包的时候大家都想跟奎奎py,花费时间t[i]t[i]t[i],先py后给红包噢。
大家都厌倦了等待,如果一个人等了时间ttt,那么奎奎发给他的红包大小就是v[i]⋅tv[i]·tv[i]⋅t。
但是奎奎还要和女朋友去快乐,想要花最少的钱来满足大家。
请你帮他计算最少需要发多少钱的红包。
输入
第一行一个整数nnn。接下来nnn行,每行两个数v[i]v[i]v[i]和t[i]t[i]t[i]。
输出
一个整数表示答案。
样例 ...
Codeforces Round #628 (Div. 2)
A. EhAb AnD gCd
You are given a positive integer xxx. Find any such 222 positive integers aaa and bbb such that GCD(a,b)+LCM(a,b)=xGCD(a,b)+LCM(a,b)=xGCD(a,b)+LCM(a,b)=x.
As a reminder, GCD(a,b)GCD(a,b)GCD(a,b) is the greatest integer that divides both aaa and bbb. Similarly, LCM(a,b)LCM(a,b)LCM(a,b) is the smallest integer such that both aaa and bbb divide it.
It’s guaranteed that the solution always exists. If there are several such pairs (a,b)(a,b)(a,b), you can output any of them.
Input
Th ...
Codeforces Round #627 (Div. 3)
A. Yet Another Tetris Problem
You are given some Tetris field consisting of n columns. The initial height of the i-th column of the field is ai blocks. On top of these columns you can place only figures of size 2×12×12×1 (i.e. the height of this figure is 222 blocks and the width of this figure is 111 block). Note that you cannot rotate these figures.
Your task is to say if you can clear the whole field by placing such figures.
More formally, the problem can be described like this:
The followi ...
POJ 3087 Shuffle'm Up
Description
A common pastime for poker players at a poker table is to shuffle stacks of chips. Shuffling chips is performed by starting with two stacks of poker chips, S1S_1S1 and S2S_2S2, each stack containing CCC chips. Each stack may contain chips of several different colors.
The actual shuffle operation is performed by interleaving a chip from S1S_1S1 with a chip from S2S_2S2 as shown below for C=5C=5C=5:
The single resultant stack, S12S_{12}S12, contains 2C2C2C chips. The bottommost ...
UVA 11624 Fire!
Joe works in a maze. Unfortunately, portions of the maze have caught on fire, and the owner of the maze neglected to create a fire escape plan. Help Joe escape the maze.
Given Joe’s location in the maze and which squares of the maze are on fire, you must determine whether Joe can exit the maze before the fire reaches him, and how fast he can do it.
Joe and the fire each move one square per minute, vertically or horizontally (not diagonally). The fire spreads all four directions from each square ...
HDU 2612 Find a way
Problem Description
Pass a year learning in Hangzhou, yifenfei arrival hometown Ningbo at finally. Leave Ningbo one year, yifenfei have many people to meet. Especially a good friend Merceki.
Yifenfei’s home is at the countryside, but Merceki’s home is in the center of city. So yifenfei made arrangements with Merceki to meet at a KFC. There are many KFC in Ningbo, they want to choose one that let the total time to it be most smallest.
Now give you a Ningbo map, Both yifenfei and Merceki can m ...
FZU 2150 Fire Game
Problem Description
Fat brother and Maze are playing a kind of special (hentai) game on an N×MN\times MN×M board (N rows, M columns). At the beginning, each grid of this board is consisting of grass or just empty and then they start to fire all the grass. Firstly they choose two grids which are consisting of grass and set fire. As we all know, the fire can spread among the grass. If the grid (x,y)(x, y)(x,y) is firing at time ttt, the grid which is adjacent to this grid will fire at time t+1t+ ...
POJ 3126 Prime Path
Description
The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.
— It is a matter of security to change such things every now and then, to keep the enemy in the dark.
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the ...